机制设计

机制设计研究怎样规定参与规则，使掌握不同私人信息的人在各自选择行动时，得到符合设计目标的结果。拍卖中的出价规则、公共资源的分配规则、平台的收费方式，都可以作为机制。机制既要说明物品交给谁，也要说明谁向谁支付多少。

参与者“愿不愿意按要求报告”是数学模型的一部分。把真实信息直接填入优化问题，得到一个理想分配，并不等于已经设计出能够实施它的制度。本条用单件物品拍卖建立最基本的模型，证明第二价格规则的激励性质，并比较效率、收入与参与约束。

私人价值、分配与支付

有 $n \geq 1$ 名竞买人。竞买人 $i$ 对物品的真实价值为 $v_{i} \geq 0$ ，向机制报告出价 $b_{i} \geq 0$ 。这里的私人价值假设指，获得物品的价值由自己的类型决定，不随其他人的信息改变。它不等于“所有人的价值服从相同分布”。

直接机制按报告向量 $b$ 给出分配 $x_{i} (b) \in {0, 1}$ 和支付 $p_{i} (b)$ ，要求 $\sum_{i} x_{i} (b) \leq 1$ 。取向机制支付为正，竞买人的准线性效用为 $u_{i} (b; v_{i}) = v_{i} x_{i} (b) - p_{i} (b) .$ 这一表达假定货币和物品价值可以相加，且没有另行建模的预算限制。它并不涵盖厌恶风险、财富效应或拍得物品后再转卖等全部情形。

占优策略激励相容，简称DSIC，要求不论其他人如何报告，真实报告都是自己的一个最优选择： $\begin{matrix} v_{i} x_{i} (v_{i}, b_{- i}) - p_{i} (v_{i}, b_{- i}) \\ \geq v_{i} x_{i} (b_{i}, b_{- i}) - p_{i} (b_{i}, b_{- i}) \end{matrix}$ 对每名参与者、每个真实价值和每个允许的偏离报告成立。符号 $b_{- i}$ 表示其余人的报告。这里是弱不等式：真实报告不必是唯一最优报告。

个体理性要求按约定参与时效用不低于退出的效用；把退出效用规范为零，就是 $u_{i} \geq 0$ 。配置效率则要求物品交给价值最高者。二者与最大化卖方收入是不同目标。上述基本概念及第二价格拍卖的激励证明可见Roughgarden的课程讲义。^[1]

第二价格拍卖

规则如下：最高出价者得到物品，支付其余人中的最高出价；没有其他人时这一价格取零。未得物品者支付零。并列最高时按事先固定、与出价数值之外的临时选择无关的规则打破平局，例如固定按编号较小者优先。

固定其他人的报告，记 $τ = max_{j \neq i} b_{j} .$ 对参与者 $i$ 而言， $τ$ 是自己不能通过改写出价来改变的门槛。出价超过门槛即可获胜，低于门槛便落败；相等时由固定平局规则决定。只要获胜，支付就是 $τ$ 。

竞争者最高出价六时，自己的报告低于六不获胜，高于六获胜且支付恒为六 — 图以该竞买人在平局时优先为例，将获胜和落败对应的支付分开表示。一般的门槛处是否获胜由固定的平局规则决定，不影响真实报告的弱最优性。

激励相容性证明。 分三种情况：

若 $v_{i} > τ$ ，获得物品的效用 $v_{i} - τ > 0$ ，落败的效用为零。真实出价能获胜，改报更高数额并不能降低所付价格，改报过低反而可能失去正效用。
若 $v_{i} < τ$ ，真实出价会落败，效用为零。为获胜而报高价将得到负效用 $v_{i} - τ$ 。
若 $v_{i} = τ$ ，获胜与落败的效用均为零，真实报告仍是一个最优选择。

其他人的出价自始至终任意，因此这是占优策略证明，不需要预先知道他们的价值分布。真实报告下，胜者的价值不低于所付价格，所以个体理性也成立。所有人真实报告时物品交给最高价值者，因而实现这一私人价值模型中的配置效率。

三名竞买人的可复算案例

三人的价值分别为九、六、四。真实出价时，第一人获胜，支付六，效用为三，其余两人的效用为零。

固定后两人的报告，第一人改报五会落败，效用零；改报七、九、十二均获胜，所付价格仍为六，效用仍为三。出价七没有额外收益，这同时说明“诚实最优”与“只有诚实才最优”的区别。

价值九且竞争门槛六时，落败效用零，获胜效用三，增加获胜后的出价不会改变效用 — 横轴是报告而非真实价值。把报告提高到九以上并不会使第二价格变高，但也不能因此推断所有拍卖规则都有这种性质。

若改用第一价格拍卖，胜者支付自己的出价。第一人如实出价九将得到零效用，而报六点一仍高于其他人的出价，效用为二点九。因此第一价格规则通常不具有这里的真实报告占优性质。这一比较只是在给定他人报告时构造一次有利偏离，没有假定第一价格拍卖的均衡出价。

保留价变式

卖方设保留价八，只有最高出价不低于八才成交；成交者支付保留价与其他最高出价中的较大者。此时个人门槛变为 $τ_{i} = max {8, max_{j \neq i} b_{j}} .$ 门槛仍不受自己报告影响，前述三种情况证明继续适用。价值九、六、四时，成交价八，胜者效用一；卖方收入高于无保留价时的六。

若价值改为七、六、四，保留价八会使交易取消，而无保留价时可以把物品交给价值七的人。这不是计算错误：加入保留价后，设计目标还涉及卖方保留物品的价值与收入。若卖方保留价值为零，无成交并不实现所有参与方总价值的最大化。单看一个样本的收入增加，也不能推出某个保留价在未知总体分布下总是最优。

Python实现与规则检查

下面实现确定性单件第二价格拍卖，平局按编号较小者优先。返回胜者编号、全部支付。无人成交时胜者为 None。输入必须为非负有限数；函数不修改输入。

Python 3

from math import isfinite

def second_price(bids, reserve=0.0):
    bids = [float(b) for b in bids]
    reserve = float(reserve)
    if not bids or not isfinite(reserve) or reserve < 0:
        raise ValueError("nonempty bids and nonnegative finite reserve required")
    if any(not isfinite(b) or b < 0 for b in bids):
        raise ValueError("bids must be nonnegative finite values")
    payments = [0.0] * len(bids)
    winner = max(range(len(bids)), key=lambda i: (bids[i], -i))
    if bids[winner] < reserve:
        return None, payments
    threshold = max((b for j, b in enumerate(bids) if j != winner),
                    default=0.0)
    payments[winner] = max(reserve, threshold)
    return winner, payments

assert second_price([9, 6, 4]) == (0, [6.0, 0.0, 0.0])
assert second_price([9, 6, 4], 8) == (0, [8.0, 0.0, 0.0])
assert second_price([7, 6, 4], 8) == (None, [0.0, 0.0, 0.0])
assert second_price([6, 6]) == (0, [6.0, 0.0])
assert second_price([5]) == (0, [0.0])

寻找最高出价与竞争门槛各扫描一次，时间为 $O (n)$ ，保存规范化出价和支付需要 $O (n)$ 空间。真实货币结算宜以整数最小货币单位表示，避免把浮点数舍入混入平局规则。

代码只实现既定机制，不能仅靠几个断言证明激励相容。保证对所有报告都成立的是前面的门槛证明。多物品互补价值、合谋、共同价值及预算约束会改变问题结构，应重新写明效用和信息条件；不能把单件私人价值的结论直接搬用。

参考文献

↑ Tim Roughgarden，Stanford CS364A，Lecture 2: Mechanism Design Basics，准线性效用、Vickrey拍卖及truthfulness证明。

[1] Tim Roughgarden，Stanford CS364A，Lecture 2: Mechanism Design Basics，准线性效用、Vickrey拍卖及truthfulness证明。

[1]