CS4261笔记

Nash Equilibrium

Step 0：删 strictly dominated

只要一个 strategy 被 strictly dominated：

$\boxed{\text{它在 NE 中概率一定为 }0}$

删完之后再检查一次，因为可能出现新的 dominated strategy。

Case 1：Pure–Pure

这个最简单。

直接找双方的 best response，两个 best response 相交的格子就是 pure NE。

口诀：

横着看 Row player 最大值，竖着看 Column player 最大值。

双方同时最大 → Nash equilibrium。

Case 2：Pure–Mixed

这是你这两道题最重要的情况。

假设：

Player 2 纯选一个 strategy；
Player 1 在两个 strategies 之间以概率 $p,1-p$ 混合。

有两个条件：

条件 A：Player 1 为什么愿意mixed？

如果 Player 2 固定选 $L$ ，而

$u_1(C,L)=u_1(B,L),$

那么 Player 1 对 $C,B$ 都无所谓，所以可以任意 mix。

根据条件A，在选择的时候完全可以同行/同列两个相同的utility，直接锁定比较范围。

条件 B：Player 2 为什么愿意继续纯选 $L$ ？

计算面对这个 mixture 时（EU为expected utility）：

$EU_2(L), EU_2(M), EU_2(R)$

要求

$EU_2(L)\ge EU_2(M),EU_2(R).$

这通常会给你一个关于 $p$ 的区间。

所以：

Pure–Mixed 的核心不是解“indifference equality”，而是一个人已经 indifferent，另一个人满足 best-response inequality。

Case 3：Mixed–Mixed

双方都真正 mixing。

这时候用经典的：

我要让你 mix，就必须让你对自己 support 里的策略 indifferent。

例如 Row 在 $T,B$ 混，Column 在 $L,M$ 混。

设

$P(T)=p,\qquad P(L)=q.$

那么：

为了让 Row 愿意混：

$EU_1(T)=EU_1(B)$

解出 $q$ 。

为了让 Column 愿意混：

$EU_2(L)=EU_2(M)$

解出 $p$ 。

最后还要检查：

$0<p<1,\qquad0<q<1$

以及没有第三个 strategy payoff 更高。

如果算出来

$q=1$

那就不是 Mixed–Mixed，而是退化回 Case 2。

Auction

1. 拍卖类型

Single-item auction：一个物品，多人竞争。
Multi-unit auction：多个相同物品，每个 bidder 可获得一个或多个。
Combinatorial auction：多个不同物品，bidder 对“物品组合”有 valuation。

2. 单物品拍卖形式

English auction：价格不断上升，最后出价者获胜并支付自己的 bid。
Japanese auction：价格不断上升，bidder 可退出且不能回来；最后留下者获胜。
Dutch auction：从高价不断下降，第一个接受者获胜。
First-price sealed bid：最高价获胜，支付自己的 bid。
Vickrey / Second-price：最高价获胜，但支付第二高价。

3. Vickrey Auction 最重要性质

设真实价值为 $v$ ，别人最高 bid 为 $p$ 。

Truthful bidding $b=v$ 是 weakly dominant strategy。

分两种情况：

$v\ge p$ ：真实出价可以赢，utility $=v-p\ge0$ 。只要 bid 足够高，付款仍是 $p$ ；bid 太低反而可能输。
$v$ ：真实出价会输，utility $=0$ 。若谎报更高并获胜，则 utility $=v-p<0$ 。

所以无论别人怎么 bid，虚报都不会比真实报告更好。

注意：Vickrey auction 仍可能存在其他 Nash Equilibrium，因此 NE 不等于 dominant-strategy equilibrium。

4. Mechanism Design

基本元素：

players $N$
outcomes $O$
valuation $v_i(o)$
payment $\pi_i$

若有 payment：

$u_i(o)=v_i(o)-\pi_i$

中心希望选择某个 outcome，例如最大化 social welfare：

$\sum_i v_i(o).$

5. IC 与 DSIC

Incentive Compatible (IC)：truthful reporting 构成一个 NE。
Dominant Strategy Incentive Compatible (DSIC)：truthful reporting 是 weakly dominant strategy。
DSIC 明显比 IC 更强。

6. VCG Mechanism

VCG 是把 Vickrey 推广到一般 mechanism design 的框架：

根据 bids 选择最大化社会福利的 outcome

$o^*=\arg\max_o\sum_i b_i(o).$

玩家 $j$ 支付其对其他人的 externality：

$\pi_j= \underbrace{\max_o\sum_{i\ne j}b_i(o)}_{\text{没有 }j\text{ 时其他人的最大福利}} - \underbrace{\sum_{i\ne j}b_i(o^*)}_{\text{有 }j\text{ 时其他人的福利}}.$

因此每个人“为自己给别人造成的损失买单”。VCG 中 truthful reporting 是 dominant strategy。

直观说明：

VCG 里“每个人支付自己造成的 externality”，核心目的就是：

让你的个人利益，和社会总福利的变化对齐。

假设没有玩家 $j$ 时，其他人最多能获得福利：

$W_{-j}^{\text{without }j}$

有了 $j$ 之后，因为资源可能分给 $j$ ，其他人的福利变成：

$W_{-j}^{\text{with }j}$

那么 $j$ 的付款定义为：

$\pi_j = W_{-j}^{\text{without }j} - W_{-j}^{\text{with }j}$

也就是：

你让别人损失了多少，你就支付多少。 这就是 externality。

为什么这样设计有用？因为玩家 $j$ 的 utility 变成：

$u_j=v_j(o^*)-\pi_j$

代入付款：

$u_j = v_j(o^*) + W_{-j}^{\text{with }j} - W_{-j}^{\text{without }j}$

前两项其实就是：

$\underbrace{v_j(o^*)+W_{-j}^{\text{with }j}}_{\text{整个社会的总福利}} - \underbrace{W_{-j}^{\text{without }j}}_{\text{与 }j\text{ 的报告无关}}$

所以 $j$ 想最大化自己的 utility，就等价于想最大化整个社会总福利。因此他没有必要通过谎报 valuation 来扭曲结果，truthful reporting 就变成 dominant strategy。

最简单的例子就是 second-price auction：

你价值 $100
第二高的人价值 $70
如果你不存在，那件物品会给第二个人，社会福利 = $70
你出现后，你拿走物品，其他人的福利 = $0

所以你造成的 externality：

$70-0=70$

于是你付 $70。

这其实就是为什么 Vickrey second-price auction 是 VCG 的一个特例。

7. 组合拍卖（Combinatorial Auctions）

我们有 $m$ 个待出售的物品，这些物品可能彼此不同。
一共有 $(n+1)^m$ 种可能的结果，也就是把这些物品分配给各个竞拍者，或者不分配。
竞拍者可以对不同的物品子集有不同的估值。

VCG 机制在这里仍然是 truthful（如实报价） 的，但有几个挑战：

偏好获取（Preference elicitation）：每个竞拍者可能有 $2^m$ 个私有参数，也就是对每个物品子集都可能有一个估值。
计算问题（Computational issues）：寻找最优结果 $o^*$ 可能是 NP-hard。
收入非单调性（Revenue non-monotonicity）：增加竞拍者后，卖家的收入反而有可能下降。

Revenue non-monotonicity 的例子

有两个物品 $A,B$ 。

最开始只有两个 bidder：
- Bidder 1：只有同时拿到 $A+B$ 才值 $1$ ，单独拿都值 $0$ 。
- Bidder 2：只想要 $A$ ，价值 $1$ 。
此时卖家收入：

$\text{Revenue}=1$

现在加入 Bidder 3：
- Bidder 3：只想要 $B$ ，价值 $1$ 。
最优分配变成：

$A\to \text{Bidder 2},\qquad B\to \text{Bidder 3}$

总福利变成 $2$ 。

但此时 Bidder 2 和 3 各自都没有给其他人造成损失，所以两人的 VCG payment 都是 $0$ 。

因此：

$\boxed{\text{Revenue}: 1\rightarrow 0}$

也就是说，增加一个 bidder，卖家的收入反而下降了，这就是 revenue non-monotonicity。

Auction	两人联合谎报，能否让两人都严格变好？	增加 bidder 后，Revenue 是否保证不下降？
Single-item Vickrey	❌ 不可以	✅ 可以保证
Multi-unit Vickrey（ $k$ 个相同物品、每人最多要 1 个）	❌ 不可以	✅ 可以保证
Combinatorial VCG	✅ 可能	❌ 不保证

Facility Location

1. Facility Location

有 $n$ 个玩家，每个人的位置为 $x_i\in\mathbb R$ ，机制根据所有玩家报告的位置选择设施位置：

$f:\mathbb R^n\rightarrow \mathbb R$

玩家 $i$ 的 cost 为

$|f(\vec x)-x_i|$

常见社会目标有 Total Cost 和 Max Cost。

Total Cost

选择 median（中位数）：

$f(\vec x)=\text{median}(x_1,\dots,x_n)$

若 $n$ 为偶数，课件规定取两个中位数中靠左的一个。

Median mechanism 有两个重要性质：

Strategyproof / truthful
对 Total Cost 是最优的

直觉：玩家如果谎报但没有跨过 median，结果不变；如果跨过 median，设施只会离自己的真实位置更远。

2. Max Cost

如果只追求最小化最大距离，最优位置是最左和最右玩家的中点：

$OPT=\frac{x_1+x_n}{2}$

但这个机制 not truthful。

因此考虑 approximation。

例如直接选择最左玩家 $x_1$ ：

$MC=x_n-x_1$

而最优解：

$OPT=\frac{x_n-x_1}{2}$

所以 approximation ratio 为

$\boxed{2}$

而且更强：

$\boxed{\text{任何 deterministic truthful mechanism 的 ratio 至少为 }2}$

也就是说 2 已经是确定性 truthful mechanism 能达到的最好结果。

3. Randomized Mechanism

随机选择：

$x_1 \quad \text{概率 }\frac14$
$x_n \quad \text{概率 }\frac14$
$\frac{x_1+x_n}{2}\quad \text{概率 }\frac12$

它仍然是 strategyproof，并把 max-cost approximation 提升到：

$\boxed{\frac32}$

而且 $\frac32$ 也是所有 randomized strategyproof mechanisms 的理论下界。

所以要记：

Objective	Deterministic	Randomized
Total Cost	$1$	$1$
Max Cost	$2$	$3/2$

4. 构造truthful

选择所有点中的中位数很有可能是一个truthful策略。

Routing Games

Routing game 中，每个玩家自私地选择自己的路径，因此 Nash Equilibrium 不一定等于社会最优。

衡量这种损失：

$\boxed{PoA=\frac{\text{Worst Nash Equilibrium Cost}}{OPT}}$

叫 Price of Anarchy。

Pigou Example

两条 $s\to t$ 路：

$c_1(x)=1,\qquad c_2(x)=x$

玩家各自选对自己最好的路，可能导致 equilibrium 的社会成本高于集中优化的结果。

Braess's Paradox

增加一条零成本道路，反而可能让所有人的 equilibrium cost 更高。

原因不是新道路本身差，而是它改变了玩家的 incentive，使每个人的 selfish choice 组合成更差的全局结果。

Atomic Routing Game

Atomic：每个玩家是一整单位流量，不能拆分。

重要结论：

$\boxed{\text{Pure Nash Equilibrium 一定存在}}$

证明核心：atomic routing game 是 potential game。

定义 potential：

$\Phi(f)=\sum_{e\in E}\sum_{i=1}^{f_e}c_e(i)$

关键性质：

一个玩家改变路径时，potential 的变化量 = 该玩家 cost 的变化量。

因此若 $f$ 最小化 $\Phi$ ，任何玩家单独 deviation 都不能降低自己的 cost，所以 $f$ 就是 Nash Equilibrium。

理解potential function

可以把 potential function（势函数） 先理解成一个“全局记分器”：

它不一定等于所有人的总 cost，但它被刻意设计成：任何一个玩家单独换路时，势函数的变化量，恰好等于这个玩家自己的 cost 变化量。

这就是它最核心的意义。课件也正是用这个性质来证明 atomic routing game 一定存在 pure Nash equilibrium。

课件定义：

$\Phi(f)=\sum_{e\in E}\sum_{i=1}^{f_e} c_e(i)$

其中 $f_e$ 表示当前有多少玩家经过 edge $e$ 。

比如一条边的 cost 是

$c_e(x)=x$

如果现在有 3 个人走这条边，那么：

每个人实际付出的 cost 是 $3$
social cost 是 $3+3+3=9$
但 potential 在这条边上的值是

$1+2+3=6$

所以一定要注意：

$\boxed{\text{Potential }\neq \text{Social Cost}}$

为什么要定义成 $1+2+3$ 这种奇怪形式？

因为假设现在 3 个人，再来第 4 个人：

原来：

$\Phi_e=1+2+3=6$

后来：

$\Phi_e=1+2+3+4=10$

所以

$\Delta\Phi=4$

而新加入的这个玩家经过这条边时，他付出的 cost 也正好是：

$c_e(4)=4$

于是：

$\boxed{\Delta\Phi=\text{这个玩家的 cost 变化}}$

这不是巧合，而是 potential function 被这样定义的原因。

再看一个“换路”的例子。

玩家原来走路径 $A$ ，cost = 7；后来换到路径 $B$ ，cost = 5。

那么课件所说的 crucial property 就保证：

$\Delta\Phi=5-7=-2$

也就是说：

玩家只要通过换路让自己变得更好，整个 potential 就一定下降。

所以我们可以想象所有玩家不断 selfishly 改路线：

Φ = 20
   ↓ 玩家1发现更好的路
Φ = 17
   ↓ 玩家3发现更好的路
Φ = 15
   ↓
Φ = 13
   ↓
再也没人能让自己的 cost 降低

因为 atomic game 只有有限种 routing 状态， $\Phi$ 不可能永远下降。

最终一定到某个状态：

$\boxed{\text{没有任何玩家能够单独换路降低自己的 cost}}$

这不就是 Pure Nash Equilibrium 的定义吗？

所以整套证明其实只有一句话：

$\boxed{ \text{玩家改善自己} \Rightarrow \Phi \text{下降} \Rightarrow \text{最终不能再下降} \Rightarrow \text{Nash Equilibrium} }$

所谓potential function只是一个辅助函数来证明任何人都不能再下降这件事。

Cooperative Games

Core：在core中的分配保证没有subset会因为能获得更多的利益而自己分出去。在core里面我们会只对veto player进行分配利益。如果有一个
Shapley Value：按照所有permutation中，每个人的边际贡献的期望值进行分配利益
$\textbf{Monotone:}\quad \forall S \subseteq T \subseteq N,\quad v(S) \leq v(T)$
$\textbf{Superadditive:}\quad \forall S,T \subseteq N,\ S \cap T = \emptyset,\quad v(S) + v(T) \leq v(S \cup T)$
$\textbf{Convex:}\quad \forall S \subseteq T \subseteq N,\ i \in N \setminus T,\quad v(S \cup \{i\}) - v(S) \leq v(T \cup \{i\}) - v(T)$
monotone + convex -> superadditive

Nash Bargaining

1. efficiency
不存在另一个可行分配，可以让所有人的效用不下降，并且至少一个人的效用严格上升。

\nexists (u_1,u_2)\in S: \begin{cases} u_1\ge u_1^*\\ u_2\ge u_2^* \end{cases} \quad\text{with at least one strict inequality.}

2. Symmetry
如果交换两个玩家之后，整个 Bargaining Problem 没有变化，那么两个玩家应该获得相同的效用。
如果

(u_1,u_2)\in S\iff(u_2,u_1)\in S

且 $d_1=d_2$ ，那么

\boxed{u_1^*=u_2^*}

3. Independence of Irrelevant Alternatives
如果删除一些可行方案，但原先选中的最优方案仍然可行，那么最终选择不能改变。
对于两个可行集合 $T\subseteq S$ ，如果

f(S,d)\in T

那么

\boxed{f(T,d)=f(S,d)}

其中 disagreement point $d$ 保持不变。
4. Invariance under Equivalent Representations
如果对每个玩家的效用进行正仿射变换，同时对 disagreement point 做相同变换，那么最终选择的实际分配不应该改变。
对每个玩家进行：

u_i'=a_i u_i+b_i,\qquad a_i>0

同时：

d_i'=a_i d_i+b_i

令 $S'$ 为变换后的可行效用集合。如果原来的解是

f(S,d)=(u_1^*,u_2^*)

那么新的解必须满足：

\boxed{ f(S',d') = (a_1u_1^*+b_1,\ a_2u_2^*+b_2) }

也就是说，最终效用的数字可以改变，但对应的实际分配不能改变。

Nash Bargaining是唯一符合上述所有性质的分配方法。
Nash Bargaining Solution 定义为：

(x^*,y^*)=\arg\max_{(x,y)\in S} (u_1(x)-d_1)(u_2(y)-d_2)

Stable Matching

一个 matching $M$ 是 stable 的，当且仅当不存在任何 blocking pair。
形式化定义：

\boxed{ \forall (s,h)\notin M,\quad M(s)\succ_s h \;\lor\; M(h)\succ_h s }

其中：

$M(s)$ ：学生 $s$ 当前匹配的医院。
$M(h)$ ：医院 $h$ 当前匹配的学生。
$\succ_s$ ：学生 $s$ 的严格偏好关系。
$\succ_h$ ：医院 $h$ 的严格偏好关系。
等价地，Blocking Pair $(s,h)$ 满足：

\boxed{ h\succ_s M(s) \quad\land\quad s\succ_h M(h) }

直观理解：不存在一对尚未匹配的学生和医院，双方都更喜欢彼此，而不是自己当前的匹配对象。

Gale-Shapley Algorithm

核心思想：学生依次向自己最喜欢、且尚未拒绝过自己的医院申请。医院暂时保留最喜欢的申请者，拒绝其他人，直到所有学生匹配成功。
假设是 Students-Proposing Gale-Shapley，每个医院只能接收一名学生。
算法步骤
1. Initialization

所有学生和医院最初都 unmatched。
每个学生有自己的 preference list。
2. Proposal
选择一个尚未匹配的学生 $s$ 。
$s$ 向自己还没有申请过的医院中最喜欢的医院 $h$ 提出申请。
3. Hospital's Decision
如果 $h$ 当前没有匹配对象，就暂时接受 $s$ 。
如果 $h$ $h$ 已经暂时接受了 $s'$ $s^{'}$ ：
- 若 $s\succ_h s'$ ，则保留 $s$ ，拒绝 $s'$ 。
- 否则保留 $s'$ ，拒绝 $s$ 。
  4. Repeat
被拒绝的学生继续向 preference list 中下一个医院申请。
重复以上过程，直到所有学生都匹配成功。
5. Termination
所有暂时接受的匹配变为最终匹配。
注意：医院的接受是 tentative acceptance（暂时接受），不是永久接受。医院之后可以拒绝原来的学生，选择更喜欢的新申请者。

Stable Matching一定存在，且不一定只有一个。是否只有一个可以用先student propose然后hospital propose看是否一样。

Fair allocation of indivisible goods

1. 基本公平性：Proportionality 与 Envy-Freeness

假设有 $n$ 个玩家、物品集合 $G$ ，玩家 $i$ 获得 $A_i$ ，估值函数为 $v_i$ ， $v_i(A_i)$ 代表玩家i认为他获得的物品的价值。

我们希望实现两种公平性：

Proportionality：每个人至少获得其视角中总价值的 $1/n$ 。
$v_i(A_i)\geq\frac{v_i(G)}n$
Envy-Freeness（EF）：每个人都不嫉妒其他人的分配。
$v_i(A_i)\geq v_i(A_j),\quad\forall i,j$

二者的关系：

\boxed{EF\implies Proportionality}

当 $n=2$ 时，二者等价；当 $n\geq3$ 时，反方向不成立。

但是，由于物品不可分割，EF 和 Proportionality 都不一定存在，因此需要放宽。

2. 第一条路线：EF → EFX → EF1

EF1：Envy-Freeness up to One Good

允许玩家嫉妒别人，但移除对方的某一件物品后必须不再嫉妒：

\exists g\in A_j:\quad v_i(A_i)\geq v_i(A_j\setminus\{g\})

EF1 保证存在，有三种实现方法：

算法	思路	保证
Round-Robin	玩家轮流选择最喜欢的剩余物品	EF1
Envy-Cycle Elimination	将物品分给无人嫉妒的玩家，通过交换 Bundle 消除 Envy Cycle	EF1
Maximum Nash Welfare	最大化 $\prod_i v_i(A_i)$	EF1 + Pareto Optimality

其中 Round-Robin 和 MNW 基于 Additive Valuations，Envy-Cycle Elimination 可以处理更一般的 Monotonic Valuations。

EFX 比 EF1 更强：移除对方的任意一件物品后，都必须不再嫉妒。

\forall g\in A_j:\quad v_i(A_i)\geq v_i(A_j\setminus\{g\})

因此：

\boxed{EF\implies EFX\implies EF1}

EFX 的存在性：

$n=2$ ：保证存在，可通过 Cut-and-Choose 实现。
$n=3$ ：保证存在，但证明较复杂。
$n\geq4$ ：一般情况下是否始终存在仍是 Open Problem。

前面三种 EF1 算法均不保证 EFX。

3. 第二条路线：Proportionality → Maximin Share

Maximin Share（MMS） 是 Proportionality 的放宽。

假设玩家 $i$ 自己把全部物品分成 $n$ 份，然后只能拿价值最低的一份。他会选择让最差结果尽可能好的划分：

\boxed{ MMS_i=\max_{(S_1,\ldots,S_n)}\min_k v_i(S_k) }

MMS Allocation 要求：

v_i(A_i)\geq MMS_i

由于最差一份的价值不可能超过平均值：

MMS_i\leq\frac{v_i(G)}n

因此：

\boxed{Proportionality\implies MMS}

但 MMS 也不一定存在：

$n=2$ ：保证存在（Cut-and-Choose）。
$n\geq3$ ：不保证存在。
任意 $n$ ：可以保证每个人获得超过 $\frac34 MMS_i$ 。

4. 各种公平性之间的关系

最重要的两条蕴含链：

\boxed{EF\implies EFX\implies EF1}

\boxed{EF\implies Proportionality\implies MMS}

但跨路线的性质不一定存在蕴含关系：

性质比较	关系
EF1 与 Proportionality	互不蕴含
EF1 与 MMS	互不蕴含
EFX 与 Proportionality	一般互不蕴含
EFX 与 MMS	一般互不蕴含

例如，EF1 只要求消除一件物品后的嫉妒，不意味着获得了自己的 MMS；反过来，获得 MMS 也不代表不会严重嫉妒其他玩家。

5. 总结

这节课研究的是：当完美公平无法保证时，如何放宽公平性，同时尽可能保证可实现性和效率？

EF 路线：EF 不一定存在 → 放宽到 EF1（始终存在）→ 研究更强的 EFX（一般存在性仍未解决）。
Proportionality 路线：Proportionality 不一定存在 → 放宽到 MMS（仍不总能实现）→ 研究近似 MMS 保证。
效率问题：Maximum Nash Welfare 同时保证 EF1 和 Pareto Optimality。

核心是区分三件事：公平性的强弱、是否保证存在、以及是否具有效率保证。