算法博弈论笔记 - 3 梅尔森的引理

因为感觉看英文教材比较不好理解，所以打算把重点记下来。

维氏拍卖作为一个好的拍卖(Awesome Auctions)，具有3个保证

1. [强动机保证] DSIC (Dominant Strategy Incentive Compatible). 即真实的竞价是优势策略，并且永远不会导致负的效益。

   追求DSIC的理由有两个：

   1. 投标人只需要很轻易地投出对于他们来说最具有优势的价格；
   2. 如果所有投标人都按照优势策略的价格进行投标，那么我们能够很自信地预测拍卖的结果。

2. [强性能保证] 社会福利最大化。

3. [计算性能] 拍卖能够在多项式(线性)时间内被计算。

机制设计步骤

1. 首先设想投标人真实地(truthfully)投标，即假设DISC成立的情况下，设置一个能够保证社会福利最大化和计算性能的分配原则。
2. 由第1步设计出的分配原则，设计一个满足DSIC的支付原则。

单一参数环境

在单一参数的环境下陈述梅尔森的引理，假设在这种环境中有n个投标人。每一个投标人 i i i都有一个自己的估价 v i v_i vi​， x i x_i xi​ 表示投标人 i i i 获得物品的数量。那么可以得到一个可行集合 X X X，其中的每一个元素都是1个n向量( x 1 x_1 x1​, x 2 x_2 x2​,…, x n x_n xn​)。

举例说明：

• 在单一物品拍卖中，X是一个至多只有一个1的0-1向量的集合，也就是说 ∑ i = 1 n x i < = 1 \sum_{i=1}^n x_i<=1 i=1∑n​xi​<=1.
• 同时拍 k k k个相同物品并限制每一位顾客至多获得1个商品的的情况下，可行集合是满足 ∑ i = 1 n x i < = k \sum_{i=1}^n x_i<=k i=1∑n​xi​<=k的0-1向量。

分配原则和支付原则

密封式拍卖需要正式定义分配原则和支付原则。也就是说，密封式拍卖需要3步完成：

(1) 收集bids: b = ( b 1 , … , b n ) \bold b=(b_1,\dots,b_n) b=(b1​,…,bn​)

(2)设计分配原则：选择可行的分配函数 x ( b ) ∈ X ⊂ R n \bold x(\bold b)\in X \subset R^n x(b)∈X⊂Rn

(3)设计支付原则：选择可行的支付函数 p ( b ) ∈ R n \bold p(\bold b) \in R^n p(b)∈Rn

有了分配原则和支付原则厚，我们继续使用一个拟线性效用模型，在竞价的向量 b \bold b b中得到bidder i i i的效用函数
u i ( b ) = v i ⋅ x i ( b ) − p i ( b ) u_i(b)=v_i\cdot x_i(\bold b)-p_i(\bold b) ui​(b)=vi​⋅xi​(b)−pi​(b)

我们将会将集中关注于满足 p i ∈ [ 0 , b i ⋅ x i ( b ) ] p_i \in [0,b_i\cdot x_i(\bold b)] pi​∈[0,bi​⋅xi​(b)]的支付原则。 p i ( b ) > = 0 p_i(\bold b)>=0 pi​(b)>=0代表拍卖房不会支付金额给投标人。

p i ( b ) < = b i ⋅ x i ( b ) p_i(\bold b)<=b_i\cdot x_i(\bold b) pi​(b)<=bi​⋅xi​(b)确保了支付原则是DISC的，也就是说每一位投标人都会真实地进行投标，并且不会有负效益。

梅尔森引理的陈述

• 定义1: 可实现的分配原则：在单一参数的情况下，如果在密封式拍卖中应该有一个支付原则 p \bold p p是DSIC的，那么称分配原则 x \bold x x是可以实现的。
• 定义2：单调的分配原则：在单一参数的情况下，如果分配原则 x \bold x x是单调的，那么对于所有的bidder i i i以及除了 i i i外其他人的投标价格 b − i \bold b_{-i} b−i​，在 i i i投标 z z z的情况下分配原则 x i ( z , b − i ) x_i(z,\bold b_{-i}) xi​(z,b−i​)是不会递减的 。也就是说， i i i的投标的价格越高，不会使 i i i获得的物品减少，只能是增多。

梅尔森引理的定义(单一参数)

1. 当且仅当分配原则是单调的时候，分配原则 x x x是可以实现的。

2. 如果分配原则是可以实现的，那么在密封式拍卖机制 ( x , p ) (\bold x,\bold p) (x,p)中存在一个唯一的支付原则 p p p是DISC的。

3. 满足2的支付原则负责以下的形式。

   • 假设归一化后 p ( 0 ) = 0 p(0)=0 p(0)=0，对于所有bidder i投标 b i b_i bi​，其他人投标 b − i \bold b_{-i} b−i​来说：
     p i ( b i , b − 1 ) = ∑ j = 1 l z j ⋅ jump in  x i ( ⋅ , b i ) at  z j p_i(b_i,\bold b_{-1})=\sum_{j=1}^lz_j\cdot \text {jump in } x_i(\cdot ,\bold b{_i}) \text {at }z_j pi​(bi​,b−1​)=j=1∑l​zj​⋅jump in xi​(⋅,bi​)at zj​
     其中 z 1 , … , z l z_1,\ldots,z_l z1​,…,zl​是分配函数$ x_i(\cdot ,\bold b{_i}) 在 在 在[0,b_i]$范围内的跳跃点。

大家好，今天收到了一所学校的offer，因为太开心，所以本章到此结束！