返回题库

拍卖博弈：纯纳什均衡数量

Counting Nash Equillibria

专题
Strategy / 策略
难度
L6

题目详情

一场拍卖有 10 个参与者竞拍一个宝箱。

宝箱价值由幕后抛 20 次公平硬币决定：每出现 1 个正面，宝箱价值增加 1 美元，因此宝箱价值 V∈{0,1,…,20}V\in\{0,1,\dots,20\}。

参与者看不到抛硬币结果，但知道价值生成方式。每位参与者同时提交一个非负整数出价。

  • 宝箱会分配给“出价最高者”中的随机一人。
  • 获胜者支付自己的出价并获得宝箱；其余人退还出价（净支付为 0）。

假设金钱效用在 00 到 1010 之间线性（可理解为风险中性且不会在均衡中出价超过 10）。

问：该博弈的纯策略纳什均衡共有多少个？（纯策略指每个玩家确定性出一个整数。）

You're at a big auction for a treasure chest with 1010 participants. The chest's value is determined by flipping 2020 fair coins behind a curtain. For each head, 11 is added to the chest. Participants cannot see the flips but know how the value is set. Each participant submits a non-negative integer bid. The chest is awarded to a random person among the highest bidders, who pays their bid. Everyone else gets their bid returned. The goal is to count the number of pure Nash equilibria in this game, assuming utility for money is linear between 00 and 1010.

Note: In a pure Nash equilibrium, each player must choose a single bid with probability 11 (i.e., no mixed strategies).

解析

记 μ=E[V]=20⋅12=10\mu=\mathbb{E}[V]=20\cdot\tfrac12=10。

在任意出价向量下，某玩家若以出价 bb 取胜，其期望净收益为 μ−b\mu-b；若未取胜则为 0。

因此某玩家在给定对手出价的情况下，会在“提高胜率”与“支付更高出价”之间权衡，其期望收益形如

P(赢)⋅(10−b).P(\text{赢})\cdot(10-b).

首先注意：任何 b>10b>10 的出价使得 (10−b)<0(10-b)<0，即使赢也期望为负，因此在均衡中不会出现 b>10b>10。

  • 情形 1：最高出价为 9。 若有任意玩家出价低于 9，他可以把出价提高到 9 并获得正的胜率与正的期望净收益 1m⋅(10−9)=1m\frac{1}{m}\cdot(10-9)=\frac{1}{m}（其中 mm 为出价 9 的人数），从而严格变好。因此若最高出价是 9，则必须所有人都出 9。此时任何人改出 10 会保证赢但期望净收益为 0，反而更差；改出更低则胜率为 0。故 全体出 9 是一个纯纳什均衡。

  • 情形 2：最高出价为 10。 只要至少有一人出价 10，则任何玩家的最佳可达期望收益都不可能为正：

    • 出价 <10：必然不会赢（因为总有至少一个 10），期望 0；
    • 出价 =10：可能赢但期望净收益 10−10=010-10=0，仍为 0；
    • 出价 >10：赢但期望为负。

    因此在“至少一人出 10”时，每个人当前拿到的期望都是 0，且无法通过单边偏离获得正收益，所以 所有出价都在 0..10 且至少一个人出 10 的任意出价向量，都是纯纳什均衡。

综上，纯纳什均衡数量为：

  • “至少一个 10”的出价向量数：1110−101011^{10}-10^{10}（每人 0..10 共 11 种，减去没人出 10 的 10 种）。
  • 再加上“全体出 9”这一额外均衡：+1+1。

因此答案为

(1110−1010)+1.\boxed{(11^{10}-10^{10})+1}.