算法博弈论

稳定婚姻匹配问题

有 $N$ 位男生和 $N$ 位女生，每个男生都对 $N$ 个女生的喜欢程度做了排序，每个女生都对 $N$ 个男生的喜欢程度做了排序，现在需要确定一个稳定的约会状态（匹配）。

若存在两对匹配 $A=(u,v)$ ， $B=(p,q)$ ，满足男生 $u$ 比起女生 $v$ 更喜欢女生 $q$ ，且女生 $q$ 比起男生 $p$ 更喜欢男生 $u$ ，那么我们称这组方案是不稳定的。

想法一：Local Change

Local change: 若两个人互相都觉得对方比自己当前的伴侣更好，就让这两个人成为一对，被甩的那两个人组成一对，重复逐步改进，直到消除所有的拆分对。
这个算法是不行的，可以构造例子陷入循环。Local Change每次是找到一个拆分对就换，而不是找到一个最合适的拆分对再换。

Gale–Shapley 算法

首先选择一个单身男生，他会按照他的喜欢程度对一个还没有表白过的女生表白。
如果女生此时处于单身状态，则他们两人将进入约会状态。
如果女生已经有匹配对象，会将他与当前对象做比较。如果她更喜欢表白的男生，该男生成功上位，原对象进入单身状态；否则男生表白失败。
当所有的男生都脱离单身状态时，此时的约会状态是稳定的。

该算法的时间复杂度是 $O(N^2)$ ， $N$ 是男女生的数量。

显然，女生的对象都一定是不断变优的。GS算法是稳定的，可以用反证法证明，该算法一定能找到一组稳定的解。若不稳定，则存在两对相互吸引的匹配 $A=(u,v)$ ， $B=(p,q)$ 。既然 $u$ 最终没有和 $q$ 匹配在一起，说明 $u$ 曾向 $q$ 表白过但被拒绝了（或者开始同意最后被踢了）。根据引理， $q$ 必然有一个比 $u$ 更好的对象，现在却与 $p$ 在一起，矛盾。

这种男追女女拒男的方案对男性更有利，这组解是所有稳定解里对所有男生最有利且对所有女生最不利的解。也就是说，其他稳定解里任何一个男生的伴侣排名都不会比当前解高。男生也不能通过变换自己的表白顺序来获得更喜欢的女生。

局限：算法无法处理一般图的稳定匹配问题，例如宿舍的稳定匹配问题。它有可能不存在稳定的分配。

算法博弈论介绍

$n$ 个参与者
每个参与者 $i$ 都有一个策略集 $S_i$
$𝑆=𝑆_1×𝑆_2×⋯×𝑆_𝑛$ 成为一个策略空间
第 $𝑖$ 个参与者所作决策的效用函数 $𝑈_𝑖$

社会效用函数 $𝐶(𝑂)=𝑓[𝑈_1𝑂,𝑈_2O,…,𝑈_𝑛(𝑂)]$

有关概念

纳什均衡：任何一个博弈者均无法通过单方面改变策略使自己的效用函数值增大。每个人的策略都是针对其他人策略的最佳反应。

占优策略：无论对方采取何种策略，都是最佳反应的策略

占优策略均衡：当一个博弈中的每位参与者都选择了各自的占优策略时，相应的博弈结果就是占优策略均衡。

囚徒困境：“认罪” 对A和B来说都是占优策略，（认罪，认罪）是一个占优策略均衡，（认罪，认罪）是一个纳什均衡。采用这种均衡策略的社会收益没有采用非均衡策略的收益好，故类似这种博弈属于社会两难。

均衡衡量

给定一个博弈系统的例子I，其最差的纳什均衡解NE(I) 与社会最优解OPT(I) 的比值记着PoA(I), 其最好的纳什均衡与社会最优解的比值记成PoS (I)。

Price of Anarchy (PoA): 所有PoA (I)中最差的值
- 对任何一个实例，证明任何一个纳什均衡对应的目标函数值不超过最优解的某个比值（上界）;构造一个例子证明比值的下界。
Price of Stability (PoS): 所有PoS (I)中最差的值
- 对任何一个实例，证明某一个纳什均衡对应的目标函数值不超过最优解的某个比值（上界）;构造一个例子证明比值的下界。

Pigou’s example:

两条不相交的边分别连接着起点S和终点T，函数 $c(𝑥)$ 表示一条边上产生的延迟费用，𝑥表示这条边上的交通量。 $c(𝑥) = 1$ 表示这条路相当长而没有交通堵塞； $c(𝑥) = 𝑥$ 表示这条路的费用随着堵塞时间越长而越高。特别地，下方那条边费用不超过上方那条边的费用当且仅当交通量不超过一个单位。

假设只有一个单位的交通量，参与者有很多且相互独立地选取从起点S到终点T的路。
假设每个参与者的目标都是最小化费用，每个人选择下方那条边即是占优策略；在这个纳什均衡中，所有参与者都会产生1的费用。

为了引进“最优结果”的概念，我们假设目标函数是要最小化所有参与者费用总和的平均值。在以上的均衡中，平均值为1。

设上方交通量为𝑥，总费用为 $𝑥 ∙ 1 + (1 − 𝑥) ∙ (1 − 𝑥)$ ，欲使其达到最小，即 $𝑥$ 取0.5。把交通量均分到两条线路上才是这个例子的“最优结果” ， $(0.5 ∙ 1 + 0.5 ∙ 0.5 = 0.75)$ 。

故 $𝑃𝑜𝐴 = 𝑃𝑜𝑆 = 1/0.75 = 4/3$ .

算法机制设计

信息不完全以及决策交互式的条件下，设计机制（规则或制度）达到既定目标。整体框架：设计者发布机制 => 玩家各自选择策略 => 达到一个均衡或者结局。

Cake Cutting

Cake Cutting： 一共n个人，选择一个方案把蛋糕分成n份。每个人对蛋糕的大小评判标准不同，但认同基本的运算。

公平：如果每个人都认为自己拿到至少1/n，称分蛋糕结果“公平”。
无嫉妒：每个人都觉得自己的蛋糕是最大的一块之一。

公平

$n^3$ 的方案：

n=2：A把蛋糕分成2块；B先选；A后选。
n=3：A把蛋糕分成2块，B先A后；这时A、B再把自己的蛋糕分成3块，C从里面各拿一块。
n>3：假设前n-1个人满意了，它们分别把自己的切成n块，第n个人从里面各拿一块。

这个方案要切 $\Sigma n^2$ 刀，所以是 $n^3$ 的。

优化：

每个人都切一刀，认为这个是1/2的分界线，这样能把人分成两组。继续下去。

这个方案是 $nlogn$ 的。

无嫉妒

这时候只满足公平的、n=3的方案就已经不满足，C可能觉得A那一半更大或者B那一半更大。

n=3：
- 第一阶段：A切成3块，B把最大的两块修剪成一样的，修完了是T，切下来的一小块是S。然后C选一块，如果C没有选T，B必须选T。A最后选。
- 第二阶段：没有选T的人（B或者C）把S切成3块，然后选了T的人先选，之后A选，最后切S的人选。
这样两个阶段都是无嫉妒的。这个方法不能推广到n>3。

无嫉妒的lower bound: $n^2$ 。

二价拍卖

二价拍卖：令获胜者为报价最高的参与者 $i$ ，报价为 $w_i$ ，他需要支付所有参与者中报价第二高的费用。此时，任何任何理性的参与者都不会谎报自己的报价。

对每一个参与者的报价 $𝑤_1, … , 𝑤_𝑛$ ，以及可能谎报价 $𝑤_1', … , 𝑤_n'$ ，若参与者 $𝑖$ 的报价是 $𝑤_𝑖$ ，其效用为 $𝑢_𝑖$ ；若参与者 $𝑖$ 的可能慌报价是 $𝑤_𝑖'$ ，其效用为 $𝑢_𝑖'$ ；那么， $𝑢_𝑖 ≥ 𝑢_𝑖'$ 。

设施选址博弈

问题描述

公有信息：网络上有n个局中人。
私有信息：每个局中人有一个私有的位置 $x_i$ 。位置组合 $x=(x_1, ..., x_n)$ 。
输出：一个设施位置 $y$ 。 $f(x) = y$ 。
局中人目标：自己到设施距离最小。
社会目标：所有人到设施距离之和最小(sc)/局中人当中离设施最远的距离最小（mc)。

防策略操纵性：说实话是最佳选择。

问题分析

网络为一条线，以sc为目标的优化问题可以找到最优的策略位置：选中位点，也就是 $x_1....x_n$ 这串数里的中位数。

防策略操纵，且最优

网络为一条线，以mc为目标的优化问题容易找到最优的策略位置：选中心点，也就是 $(min+max)/2$ 。

是最优，但不是防策略操纵的。会撒谎，但是可以做到2近似，选断点即可。
证明2机制已经是最好的：任何一个防策略操纵机制的近似比至少是2。

厌恶型设施选址博弈： 最优解是所有居民距离垃圾站最远。

考虑网络是一条线段时，最优解一定在0或者1上，应该取0和1中距离之和更大的那个。

此时考虑策略的话，每个人都会撒谎，机制作废。（其实这个机制也不差，可以算近似比）
majority机制：左边人多建在右边，右边人多建在左边。这样就没有人撒谎。近似比是3。
- 近似比证明：假设左边 $n_1$ ，右边 $n_2$ 。不妨设 $n_1 \le n_2$ 。最坏情况， $n_1$ 个局中人在0点， $n_2$ 个局中人在离 $1/2$ 很近的位置， $n_1$ 和 $n_2$ 几乎相等。则有近似比 $\rightarrow 3$ 。
补充：环上也是3，一般图上是4。