Single-Item Auction
Description
有一个物品和多个买家，每个买家有私有的 效用 \(\theta_i\)。一般作出 Bayesian 假设，即第 \(i\) 个买家的效用是从公开的分布 \(f_i(\theta_i)\) 中随机采样。
卖家希望得到一种 结果 \((\b x,\b p)\)，其中：
- \(x_i\) 为第 \(i\) 个买家最终获得物品的概率。应该保证 \(\sum x_i\leq1\)——有时卖家选择保留不卖也是一种选择。
- \(p_i\) 为第 \(i\) 个买家的期望支付价格。即，买家实际获得该物品时，要支付的价格应为 \(p_i/x_i\)。未获得物品的人不需要支付。
[!TIP]
这个定义看似奇怪，但注意到一般 \(\b x\) 都会是 one-hot 的，所以此时确定性获得物品的那个买家总是支付 \(p_i\) 的价格，此时即符合一般惯例。
在这种结果下，第 \(i\) 个买家的期望收益即为 \(u_i=x_i\theta_i-p_i\)。
[!NOTE]
这隐含了一种「拟线性」的假设，即收益随价格线性变化。
为了保证这个拍卖场景合理，以下条件需要被满足：
- \(u_i\geq0\)，称作 个体理性 (individual rationality)——你不能要求一个人明知亏损仍然参与交易。
- \(p_i\geq0\)。这很显然——没见过卖货还搭钱的卖家。
[!TIP]
\(p_i\geq0\) 且 \(\sum x_i\leq1\) 是「拍卖」场合应该遵循的原则。但是如果换成「竞标」的背景，此时 \(\theta_i\) 作为竞标者的成本是负数，那么甲方则需要提供负的 \(p_i\) 作为激励。为了找到人完成，此时要加入 \(\sum x_i=1\) 的条件。 不过我们先不讨论这种场景，局限于正价格的拍卖吧。
从私有的效用到公开的结果需要一个公开的机制。其为每个买家圈定其可以执行的公开行为集合 \(M_i\)，同时公开由行为决定最终结果的映射 \(\phi:\prod M_i\to(\b x,\b p)\)。每个买家根据其自身的效用决定其执行的行为，换句话说就是其行为可以由 \(f_i:\theta_i\mapsto m_i\) 描述，而这个行为应该与他人无关。
衡量机制的优劣主要有两种方式：
- 效率最大化，即最大化 \(\sum\theta_ix_i\)。该定义与售价 \(p_i\) 无关——因为买家支付的金额会转移到卖家的钱包中。
- 收益最大化，即最大化 \(\sum p_i\)。
Auction Modes
有两种常见的拍卖方式：
- 加价模式：从一个底价开始，不断加价，直至只剩一个人仍然未退出。
- 减价模式：从一个顶价开始，不断降价，直到有一个人终于愿意支付当前价格。
但是这两种模式均不符合上述机制的定义：它包含一个多轮的决策过程。
[!NOTE]
虽然过程比较复杂，但仍然可以对其中的每一步决策分析 DSE 性：
- 加价模式中，所有人的策略都是，只要当前价格未到达自身 \(\theta_i\) 就继续跟价。因此其是 DSE。
- 减价模式中，真实估价最高者可以在价格仍高于第二高估价前暂缓入场，也就是说可能不存在 DSE。
这两种模式都可以被转换成等价机制：
- 加价模式等价于所有人秘密报一个出价，最终中标者是出价最高者，但支付金额是第二高的出价。这种机制也被称作 second-price auction。
- 减价模式等价于所有人秘密报一个出价，最终中标者是出价最高者，支付金额即为其出价。这种机制也被称作 first-price auction。
Myerson's Lemma
在 mechanism design 中，我们有 revelation principle；而在 auction 中，同样有相似的定理，它刻画何时一个直接机制会是激励相容的。
定义：一个直接机制是 单调不减 (monotone non-decreasing) 的，如果所有人中标的概率不会随着其个人单方面提高出价反倒降低。即对于一切 \(\b\theta\)，对于某个 \(\theta'_i>\theta_i\)，有 \(x_i(\b \theta_{i'\neq i},\theta'_i)\geq x_i(\b \theta_i)\)。
Myerson 引理：直接机制是 IC 的，当且仅当它是单调不减的，且价格通过下式确定：
[!TIP]
这里为了形式一般化，在左侧保留了 \(p_i(\b\theta_{i'\neq i},0)\) 的项；但是在拍卖场景中，出价为 \(0\) 的人中标的概率可以认为是 \(0\)，因此可以直接扔掉这一项。这之后，仅凭 \(x_i\) 即可唯一确定对应的 \(p_i\)。
换句话说，Myerson 引理指出，拍卖场景中，为了保证激励相容，任何一种单调不减的中标概率都唯一确定一种定价策略。
由其可知，所有效率最大化的激励相容直接机制必然等价于 second-price auction。
Virtual Value Theorem
虽然 second-price auction 最大化效率，但它显然并没有最大化收益——在合理范围内稍微抬高对出价最高者的售价，并不会违背个体理性。
然而，这个「合理范围」显然需要对买者的效用分布有一些观察，因此本文开头提到的 Bayesian 假设确有必要。在此条件下，我们最大化期望收益
我们仍然使用 Myerson 引理的条件，即使用激励相容的直接机制。此时代入 Myerson 引理的最低临界出价条件并推推式子可知期望收益等于
其中 \(\psi_i(\theta_i)\) 是一个 只与 \(\theta_i\) 有关的函数 \(\theta_i-\dfrac{1-F_i(\theta_i)}{f_i(\theta_i)}\)，其中 \(F\) 是 CDF、\(f\) 是 PDF。从 \(\theta_i\) 也即「第 \(i\) 个买家能接受的最高售价」减掉的部分被称作「信息租金」，是由于信息不对称，买家能够获得的额外收益。假如卖家拒绝给买家留下额外收益，强行要求「报价多少实收多少」，那买家就会偷奸耍滑，压低报价，不再 IC 了。
这个 \(\psi_i\) 有一点很不好，就是其不一定递增。于是称分布 \(f\) 是 regular 的，如果其对应的 virtual value \(\psi\) 是严格增的，此时易构建拍卖策略：
- 卖家向每个买家询问其估值。Myerson 引理保证他们会如实相告。
- 计算 virtual value 并售卖给最高者。
- 如果最高者的 virtual value 也为负，则卖家无法得利，于是拒绝售卖。
Multi-Item Auction
Description
现在考虑多物品的场合。此时我们仅考虑确定性的结果，则 \(x_i\) 是一个集合，\(p_i\) 则是该集合的总价。要求所有 \(x_i\) 两两不交。而每个人的效用 \(v_i(x_i)\) 则是对「集合」而非「单品」定义的。仍然可以定义个体理性的要求，以及最大化效率/收益的目标。
Unit-Demand
这是一种特殊的多物品拍卖，此时所有人对零个或多于一个物品的集合的效用是零，也即所有人想要至多一个物品。
[!TIP]
一种很常见的理解方式是将其看做买家和物品间的匹配。
这种场合下，按照某种顺序一个个售卖物品，每次售卖使用前面提到的 Single-Item Auction 模式——并非效率最大化的方案，可以找到反例。不论是所有拍卖前统一给出叫价还是每一轮分别给出叫价均如此。
Groves Mechanism and VCG Mechanism
将「个人效率」与「社会效率」通过价格相挂钩，即可将个人的理性转化为社会的理性。
Groves 机制：要求所有人如实上报他们的 \(v_i(\cdot)\)（直接机制），然后依以下过程确定结果：
其中 \(h_i(\cdot)\) 是公开的函数，与 \(v_i\) 无关。
则个人收益为 \(v_i(x_i)-p_i=\sum v_j(x_j)-h_i(\b v_{i'\neq i})\)，前半部分因为 \(\b x\) 是 argmax 所以被最大化了，后半部分仅与他人行为相关，与个人行为无关。于是这即激励所有人如实汇报个人效用以将其最大化。
但要想具有个体理性，就必须选择合适的 \(\b h\)。一种保证合适的方法是如下 Vickrey-Clarke-Groves 机制：其中
[!NOTE]
那么此时上述匹配场景即可派上用场。
定义 \(S\) 为全体物品集合、\(B\) 为全体买家集合。定义 \(V_B^S\) 为依据所有人汇报的 \(v_i(\cdot)\)，此时的最大匹配，即 \(\arg\max_{\b y\in S^{|B|}}\sum_{i\in B}v_i(y_i)\)。则 \(\b x\) 为取到 \(V_B^S\) 的一组匹配，而 \(h_i=V_{B\setminus i}^S\)。
那么，VCG 机制即可被解释为，如果买家 \(i\) 被分配到物品 \(j\)，该场景下其支付金额为
\[p_{i,j}=V_{B\setminus i}^S-V_{B\setminus i}^{S\setminus j} \]注意此处把 \(\sum_{i'\neq i}v_{i'}(x_{i'})\) 解释为 \(V_{B\setminus i}^{S\setminus j}\)。二者确实是相等的：因为 \(\b x\) 是 argmax 所以必有 \(\sum v_k(x_k)=V_B^S=v_i(x_i)+V_{B\setminus i}^{S\setminus j}\)。
于是 VCG 的流程即可描述为：
- 所有人汇报 \(v_i\)。
- 关于 \(v\) 求最大权匹配 \(\b x\)。
- 实际支付的金额是 \(p_{i,x_i}\)。
这里实际支付的金额不超过他们的估价，缺额和 Virtual Value 的场合一样，是「信息租金」。但是不同的是，VCG 不需要先验分布。此外，此处支付可以被视作对「外部性」的补偿——你购买该商品的场合（\(V_{B\setminus i}^{S\setminus j}\)）相比你不购买的场合（\(V_{B\setminus i}^S\)）会对他人产生机会成本的损害。
进一步其还可以扩展至多物品：此时 \(\b x\) 仍然是最大匹配，\(i\) 分配到 \(T\) 时支付金额 \(p_{i,T}\) 仍然是外部性补偿，有两种等价表现形式，即
| Single-Item | Multi-Item | |
|---|---|---|
| 效用最大化（不需要先验分布） | second-price auction | VCG |
| 收益最大化（需要先验分布） | virtual value auction | Myerson 定理的复杂扩展 |
Free Market
Description
「拍卖」是一种中心化的环境：有一个举办方划定「机制」。但是如果我们想要用大手，那么我们就不能假定一个主办方。
但是如果完全没有规则，那也不成市场。我们必须作出一些最小的先验假设，例如「统一且可加的定价」：如果某人购买了集合 \(S\)，那么他要支付的金额为 \(\sum_{i\in S}p_i\)。
[!TIP]
从这个角度来说，你也可以认为这是某种特殊规则下的拍卖。
如果多个人同时青睐某个商品，这个商品应该分配给谁呢。最理想的情况是「所有人偏好的集合彼此不交」，此时所有人直接取用效用最高的集合即可。也即，有 \(x_i\) 两两不交，且
这看上去很美好吧？还不止！
还嫌不够？我们可以额外定义「市场出清条件」：所有 \(p_i\) 都降无可降了。也即，如果某个商品未分配给任何人，那么其必然有 \(p_i=0\)。偏好不交+市场出清，这就是 Walrasian 均衡。
怎么啥好事都让你占了？这样的方案真的存在吗？
不过先假设它存在，此时有如下性质：定义 \(z_i=v_i(x_i)-\sum_{j\in x_i}p_j\) 也即买家 \(i\) 的收益，定义 \(Z=\sum z_i,P=\sum p_j\)，则有以下良好的式子：
换句话说，Walrasian 均衡必然最大化效率，即 \(\b x\) 一定是所有匹配中总效用最大的一个。这是因为对于其它任何一种匹配 \(\b y\)，均有
一方面，因为不在 \(\b x\) 中的物品售价均为零，于是有 \(\sum_i\sum_{j\in x_i}p_j=\sum p_j=P\)；另一方面，又必有 \(\sum_i\sum_{j\in y_i}p_j\leq P\)，于是得到
这就是 第一福利定理。
Unit-Demand
我们首先考虑一个极端场合，即物品和人一样多，所有人想要恰好一个物品。此时有一个很好的结论：Walrasian 均衡必然存在！且不像 Nash 均衡，它是可以被显式求出的！具体流程如下：
首先初始化所有售价为 \(p_i=0\)。之后重复以下过程：
- 如果最低售价非 \(0\)，则可以将所有物品的价格同步减少最低售价，显然这不影响任何匹配结果，且最低售价变成了 \(0\)。
- 建立 \(i\to j\in\arg\max_j\left[v_i(j)-p_j\right]\) 的二分图（称作「喜好图」），检查是否存在完美匹配。
- 如果存在，那我们已经取得了 Walrasian 均衡，可以结束循环了。
- 否则由 Hall 定理，存在一个买家集合 \(S\)，其最喜爱的商品集合 \(N(S)\) 满足 \(|N(S)|<|S|\)。于是令 \(N(S)\) 中所有商品售价同时提高 \(1\)。之后回到循环开头。
[!TIP]
准确地说，此处售价提高值应当是让 \(N(S)\) 恰好得到扩张的最小 \(\delta\)。然而在整数收益的前提下，取 \(\delta=1\) 则总是可以通过重复这一过程来达成目标。
我们只需要证明循环必然停止。首先，定义买家的势能为 \(\max_j\left[v_i(j)-p_j\right]\)，定义商品的势能为 \(p_j\)，定义系统总势能为它们的和。第一步的同步降价会让所有商品的势能同步下降，但所有买家的势能同步上升相同值，所以总势能不变；最后一步的同步抬价会让总势能减少 \(|S|-|N(S)|>0\)。于是迭代过程中势能严格降。
另一方面，第一步降价后，所有人都至少有一个选择售价为零商品的选项，因此所有人的势能均非负；而所有商品的售价亦非负；所以总势能有零的下界。于是知循环必然停止。
事实上，上述分析同样适用于物品数量比人多的场合。此时第一步的同步降价仍然可以保证总势能下降，因此迭代必然收敛，但是如何保证未被选中的商品售价必为零呢？只需要引入一堆对所有商品评价均为零的「虚拟买家」，补齐买家和物品数量间的缺口即可。虚拟买家购买的商品被视作未分配，而因为虚拟买家的势能必然非负，所以其买到的商品售价必然为零。
另一方面，有定理 [Demange, Gale, Sotomayor]：VCG 机制的定价必然达到 Walrasian 均衡，且是所有 Walrasian 均衡中，总售价最低的唯一一个。
引理一：对于任何总售价最低的 Walrasian 均衡，则喜好图中的任意一个售价非零的商品，其必然可以沿着一条「首边是非匹配边」的增广路到达某个售价为零的商品。
首先一个前提是证明所有售价非零商品必然与某个非匹配边相邻。这很显然：如果这个商品只有唯一邻居，换句话说就是只被一个人喜欢，那么稍微降一点价仍然保证其是 Walrasian 均衡的，而这就违背了总售价最低的前提。
进一步，可以考虑仅使用首边为非匹配边的增广路，从商品 \(i\) 开始能到达的全体商品和买家集合，记作 \(X\)。假如我们可以让 \(X\) 中的所有物品同步降价，则：
- 如果一个买家匹配的物品属于 \(X\)，则降价不会改变其选择。
- 如果一个买家匹配的物品不属于 \(X\)，则该买家必然亦不属于 \(X\)，于是该买家偏好的所有商品都不属于 \(X\)，那么 \(X\) 稍微降一点价并不会改变其选择。
然后知，如果 \(X\) 还有降价余地，换句话说就是 \(X\) 中最低售价非零，则当前售价未达到总售价最低。
引理二：对于任何总售价最低的 Walrasian 均衡，在把任何买家「zeroed out」——也即将其对所有物品的评价设为零，换句话说干掉它并用一个虚拟买家替换——后，其仍然是 Walrasian 均衡的（当然，此时不一定是新场景的总价最低均衡了，所以你不能靠这个把所有买家一个个干掉）。其副效果为，zeroed out 后的场景中，成为虚拟买家者必然获得零价物，而其它买家的收益不变。
把买家 zeroed out 后，它只喜欢那些售价为零的物品。假如它原来就匹配着零价物那没问题，否则使用引理一给出的增广路连接到零价物后，被 zeroed out 的买家可以转而选择那个零价物，然后路径上其它人按照增广路调整即可。
有引理二即可简单证明。我们考虑任何一个总售价最低的 Walrasian 均衡：
首先根据第一福利定理，有 \(Z=V_B^S-P\)。
另一方面，假如我们将买家 \(i\) zeroed-out 了，那么由引理二，其它人的收益均不变，唯独买家 \(i\) 的收益 \(z_i\) 被移除了。在 zeroed-out 图上再使用第一福利定理，即得 \(Z-z_i=V_{B\setminus i}^S-P\)。
最后，由最大效率匹配的相关性质，有 \(v_i(j)+V_{B\setminus i}^{S\setminus j}=V_B^S\)；由效率的定义有 \(z_i=v_i(j)-p_j\)，于是把所有式子叠一块推一推即得
而这恰好是 VCG price 的定义。于是证毕。
General Case and Second Welfare Theorem
在不一定只想要一个物品的场合，Walrasian 均衡不一定存在——但是某些特定场合仍然可以改造上述策略以显式求出之。不过这并非本节重点。
首先由第一福利定理，Walrasian 均衡最大化社会效率，而最大化社会效率就是如下整数规划的一组解 \(\b x\)：
众所周知，线性规划 \(\max\b c\cdot \b x:A\b x\leq\b b,\b x\geq\b0\) 的对偶是 \(\min \b b\cdot\b y:A^\top\b y\geq\b c,\b y\geq\b0\)。同时有 KKT 条件连接两者：\((\b x,\b y)\) 二元组是原始和对偶规划的最优解，如果在满足条件的同时有 \(\b y\cdot(A\b x-\b b)=\b x\cdot(A^\top\b y-\b c)=0\)。
而上述线性规划的对偶就是
可以验证，KKT 条件恰好就是 Walrasian 均衡的定义。于是即有第二福利定理（的简化版）：如果最大化社会效率的线性规划存在整数解，则其亦存在 Walrasian 均衡。