AFTD Auto-Formalizing Theoretical Domains

Research Blogs

双参与者块蛇形挑选博弈中的子博弈完美均衡满足至多一个物品的无嫉妒与对更大捆绑包无嫉妒

medium tier2026-11-10OP-1323审阅: Claude CodeEnglish

摘要

在两个参与者于完全信息下分配奇数个不可分物品 $2k+1$ 的序贯挑选博弈中,补偿性挑选序列旨在平衡序贯选择所固有的次序优势。arXiv:2611.09685 第 7 节提出的一个问题是:由此类序列诱导的唯一子博弈完美均衡分配,在成对占优下关于参与者的真实偏好是否能保证补偿性公平准则——具体为至多一个物品的无嫉妒(EF1)与对更大捆绑包至多任意物品的无嫉妒(NEL)。本博文介绍了定理 block_snake_two_agent_spe_nel_ef1 的形式化验证,该定理针对双参与者块蛇形选秀序列,对其中挑选博弈部分给出了肯定的回答。对于每个物品具有不同取值的任意正可加效用,每个子博弈完美均衡延续配置所产生的根分配在成对占优下同时满足 EF1 和 NEL。块蛇形序列让获得 $k$ 个物品的参与者 0 在前 $k$ 轮的每一轮中先选,并在最后将多出的物品赋予参与者 1。该证明将均衡的经典自底向上刻画形式化,表明每个均衡根分配均与逆向划除分配重合,并证明了块蛇形序列下的逆向划除分配满足这两种公平性质。所有定义、引理和定理均已在 Lean 4 中形式化验证。

1. 引言

当两个参与者按序贯方式分配一组不可分物品时,参与者选择物品的次序会极大地影响最终分配。在完全信息和严格可加偏好下,序贯挑选博弈可以通过逆向归纳法进行分析。已知此类双参与者挑选博弈具有唯一的子博弈完美均衡分配。然而,序贯机制通常会赋予具有较早轮次的参与者固有优势。为了缓解这种不对称性,补偿性挑选序列通过调整轮次顺序,使得后续的选择能够补偿先前的次序劣势。

在 arXiv:2611.09685(第 7 节)中,所设定的情境涉及两个参与者在完全信息下分配奇数个物品 $T = 2k + 1$ 件不可分物品,其中参与者对物品具有严格偏好,并通过成对占优或可加估值来比较物品组。在此背景下,成对占优下的两个主要公平准则是核心:至多一个物品的无嫉妒(EF1)与对更大捆绑包至多任意物品的无嫉妒(NEL)。如果任何参与者对另一参与者的嫉妒可以通过从另一参与者的捆绑包中移除至多一个物品并找到逐项占优的单射来消除,则分配在成对占优下满足 EF1。如果只要某个参与者获得的物品严格少于另一参与者,从较大的捆绑包中移除任意单个物品后较小的捆绑包均能成对占优剩余部分,则该分配在成对占优下满足 NEL。

在真实序贯行动下——即参与者在每个轮次中挑选其最偏好的剩余物品——已知块蛇形序列同时满足 EF1 和 NEL。然而,在完全信息下的策略性环境中,理性参与者通常不会进行近视挑选;相反,他们会预判未来的选择并根据子博弈完美均衡采取行动。在轮换(round-robin)序列下的报告博弈中,已知纯纳什均衡关于真实价值是 EF1 的。尽管如此,正如 arXiv:2611.09685 中所提出的,该论文的结论部分将这些均衡分配是否满足 EF1 和 NEL 列为未决问题。

这些保证取决于序列。轮换序列不具备补偿性:在双参与者和五个物品的情况下,它将多出的物品分配给同样先选的参与者 0,且该论文的表 1 已经记载了它在真实行动下不满足 NEL。作为合理性检验,round_robin_five_item_spe_not_nel 表明,对于在五个物品上具有效用 16、8、4、2 和 1 的相同估值的两个参与者,交替轮换序列下的唯一子博弈完美均衡分配给予参与者 0 三个价值为 16、4 和 1 的物品,给予参与者 1 两个价值为 8 和 2 的物品。从参与者 1 的角度来看,该分配在成对占优下不满足 NEL:移除价值为 1 的物品后,参与者 0 剩下价值为 16 和 4 的物品,由于 16 严格大于每一个可用价值,因而无法单射匹配到参与者 1 的捆绑包 $\{8, 2\}$ 中。

三个物品的情形($k = 1$,顺序为 $0, 1, 1$)已先作为 block_snake_two_agent_spe_nel_ef1_three_items 得到检验。

本博文介绍了通过 Lean 4 定理 block_snake_two_agent_spe_nel_ef1 对该问题的形式化解决。我们证明了对于任意非负整数 $k$,具有正且相异的可加价值的任意两个参与者,根据块蛇形序列分配 $2k + 1$ 个物品时,所达到的均衡根分配在成对占优下同时满足 NEL 和 EF1。该证明将子博弈完美行动与自底向上(逆向划除)过程之间的经典对应关系形式化(该论文援引了该对应关系以证明均衡分配的唯一性),并证明了块蛇形次序下的每个逆向划除分配均满足所需的成对占优匹配。

2. 预备知识

定义 1(block_snake_seq_two)。对于 $k \in \mathbb{N}$,在 $2k+1$ 个物品上的双参与者块蛇形序列为序列 $s \in \{0, 1\}^{2k+1}$,定义为对轮次索引 $t \in \{0, \dots, 2k\}$: $$s(t) = \begin{cases} 0 & \text{if } t < 2k \text{ and } t \equiv 0 \pmod 2, \\ 1 & \text{otherwise}, \end{cases}$$

*注。*在 Lean 中,block_snake_seq_two k 是通过 List.ofFn 构造的长为 $2k+1$ 的 List (Fin 2)。轮次从参与者 0 开始,在参与者 0 和 1 之间交替。在最终轮次 $t = 2k$ 处,条件 $t < 2k$ 不满足,从而将轮次 $2k$ 赋予参与者 1。因此,参与者 0 获得 $k$ 个轮次($0, 2, \dots, 2k-2$),参与者 1 获得 $k+1$ 个轮次($1, 3, \dots, 2k-1, 2k$)。

定义 2(pick_game_is_spe)。设 $n \in \mathbb{N}$,$s \in \{0, 1\}^n$,且 $u : \{0, 1\} \to \{0, \dots, n-1\} \to \mathbb{R}$。结果-延续函数 $F : \text{List } \{0, \dots, n-1\} \to \mathcal{P}(\{0, \dots, n-1\})$ 对于 $s$ 和 $u$ 是子博弈完美的,如果 $s$ 的长度为 $n$,且对于每个无重复历史 $h$,令 $R = \{0, \dots, n-1\} \setminus h$:

1. $F(h) \subseteq R$;

2. 若 $R$ 非空,则存在 $x \in R$ 使得 $F(h) = \text{pick\_game\_move\_zero}(s, F, h, x)$,且对所有 $y \in R$, $$\text{pick\_game\_move\_payoff}(u, s, F, h, y) \le \text{pick\_game\_move\_payoff}(u, s, F, h, x);$$

3. 若 $R = \emptyset$,则 $F(h) = \emptyset$。

*注。*函数 $F(h)$ 记录从历史 $h$ 起分配给参与者 0 的物品组。该条件要求在每个历史 $h$ 处,处于轮次 $h.\text{length}$ 的挑选者选择一个可用的物品,以最大化其可加延续收益。当 $R = \emptyset$ 时,$F(h) = \emptyset$。

定义 3(pick_game_root_allocation)。给定结果-延续函数 $F$,根分配 $A : \{0, 1\} \to \mathcal{P}(\{0, \dots, n-1\})$ 定义为: $$A(0) = F([]), \quad A(1) = \{0, \dots, n-1\} \setminus F([]).$$

*注。*在 Lean 中,pick_game_root_allocation F i 在 $i = 0$ 时求值为 $F([])$,在 $i = 1$ 时求值为 $\text{Finset.univ} \setminus F([])$,对物品进行了划分。

定义 4(is_nel_pd)。对于偏好 $\le$,分配 $A : \text{Agent} \to \mathcal{P}(\text{Object})$ 在成对占优下满足对更大捆绑包至多任意物品的无嫉妒(NEL),如果只要 $|A(i)| < |A(j)|$,对于每个物品 $y \in A(j)$,均存在单射 $f : A(j) \setminus \{y\} \to A(i)$ 使得 $$z \le_i f(z) \quad \text{for all } z \in A(j) \setminus \{y\}.$$

*注。*前提要求严格不等式 $|A(i)| < |A(j)|$;若 $|A(i)| \ge |A(j)|$,则平凡成立。单射必须对*每一个* $y \in A(j)$(“至多任意物品”)均存在,而非仅仅对某个 $y$ 存在。

定义 5(is_ef1_pd)。对于偏好 $\le$,分配 $A : \text{Agent} \to \mathcal{P}(\text{Object})$ 在成对占优下满足至多一个物品的无嫉妒(EF1),如果对于所有 $i, j$:

1. 存在单射 $f : A(j) \to A(i)$ 使得对于所有 $z \in A(j)$ 均有 $z \le_i f(z)$;或

2. 存在 $y \in A(j)$ 以及单射 $f : A(j) \setminus \{y\} \to A(i)$ 使得对于所有 $z \in A(j) \setminus \{y\}$ 均有 $z \le_i f(z)$。

*注。*EF1 要求存在性地选择 $y \in A(j)$(“至多一个物品”)。当 $|A(j)| > |A(i)|$ 时,从基数上看子句 1 被排除,从而要求子句 2 成立。

定义 6(picking_reverse_crossout_valid)。设 $u : \{0, 1\} \to \{0, \dots, n-1\} \to \mathbb{R}$ 且 $s \in \{0, 1\}^n$。置换 $\pi : \{0, \dots, n-1\} \to \{0, \dots, n-1\}$ 是 $u$ 和 $s$ 的有效逆向划除序列,如果 $s$ 的长度为 $n$,$\pi$ 是双射,且对所有 $t < j$, $$u(1 - s^{\text{rev}}(t), \pi(t)) \le u(1 - s^{\text{rev}}(t), \pi(j)),$$ 其中 $s^{\text{rev}} = s.\text{reverse}$。

*注。*在逆向轮次 $t$ 处,挑选者 $s^{\text{rev}}(t)$ 在剩余物品中选择一个使得对手 $1 - s^{\text{rev}}(t)$ 的估值最小的物品 $\pi(t)$。该不等式为弱不等式,允许任意决胜规则。

定义 7(picking_reverse_crossout_allocation)。对于长为 $n$ 的序列 $s$ 和置换 $\pi$,逆向划除分配为每个参与者 $i \in \{0, 1\}$ 指定: $$A_{\pi}(i) = \{\pi(t) \mid t \in \{0, \dots, n-1\}, \, s^{\text{rev}}(t) = i\}.$$

*注。*集合 $\{t \mid s^{\text{rev}}(t) = 0\}$ 和 $\{t \mid s^{\text{rev}}(t) = 1\}$ 划分了所有轮次,因此 $A_\pi(0)$ 和 $A_\pi(1)$ 划分了全部 $n$ 个物品。

3. 主要结果

本工作的主要结果解决了块蛇形选秀序列的补偿性公平问题。

定理(block_snake_two_agent_spe_nel_ef1)。设 $k$ 为非负整数。考虑由 $\text{Fin } 2 = \{0, 1\}$ 索引的两个参与者分配由 $\text{Fin } (2k+1)$ 索引的 $2k+1$ 个不可分物品。设 $u : \text{Fin } 2 \to \text{Fin } (2k+1) \to \mathbb{R}$ 为满足下列条件的可加估值配置:

1. 每个物品对两个参与者均具有严格正的效用:$\forall i \in \{0, 1\}, \forall x, \, 0 < u(i, x)$;

2. 每个参与者在不同物品上的效用各不相同:$\forall i \in \{0, 1\}, \forall x \ne y, \, u(i, x) \ne u(i, y)$。

设 $F : \text{List } (\text{Fin } (2k+1)) \to \text{Finset } (\text{Fin } (2k+1))$ 为构成块蛇形序列 block_snake_seq_two k 的子博弈完美均衡配置的任意结果-延续函数,满足 pick_game_is_spe u (block_snake_seq_two k) F。则根分配 pick_game_root_allocation F 在成对占优下关于由 $u$ 诱导的物品偏好关系(其中参与者 $i$ 弱偏好物品 $y$ 胜过 $x$ 当且仅当 $u(i, x) \le u(i, y)$)同时满足对更大捆绑包至多任意物品的无嫉妒(is_nel_pd)和至多一个物品的无嫉妒(is_ef1_pd)。

block_snake_two_agent_spe_nel_ef1 的 Lean 陈述表达了这一表述:给定 $k : \mathbb{N}$、带有正值性假设 $hu$ 和相异性假设 $hd$ 的估值函数 $u : \text{Fin } 2 \to \text{Fin } (2*k+1) \to \mathbb{R}$,以及满足 pick_game_is_spe u (block_snake_seq_two k) F 的结果-延续函数 $F$,并断言 is_nel_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F) 与 is_ef1_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F) 的合取。

其他形式化结果为主定理提供了结构支撑和边界背景:

1. picking_reverse_crossout_exists:对于任意有限物品数 $n$、任意估值配置 $u$ 以及任意长为 $n$ 的挑选序列 $s$,存在至少一个有效的逆向划除序列 $\pi$,表明逆向划除过程可执行且不会陷入死胡同。

2. picking_two_agent_spe_eq_reverse_crossout:对于长为 $n$ 的任意挑选序列 $s$ 以及正且相异的可加估值 $u$,每个子博弈完美均衡配置 $F$ 所产生的根分配与任意有效逆向划除置换 $\pi$ 所生成的分配完全相同,从而将逆向归纳与构造性的自底向上消除等同起来。

3. block_snake_reverse_crossout_nel_ef1:对于任意估值配置以及块蛇形次序下的任意有效逆向划除序列,逆向划除分配在成对占优下直接满足 NEL 和 EF1,从而在逆向消除结构上确立了组合公平性质。

4. block_snake_two_agent_spe_nel_ef1_three_items:$k = 1$(三个物品)的情形已单独证明,确认了两个参与者在块蛇形 $(0, 1, 1)$ 下分配三个物品时在均衡中能够获得 EF1 和 NEL 的根分配。

5. round_robin_five_item_spe_not_nel:对于在交替轮换次序 $(0, 1, 0, 1, 0)$ 下具有相同效用 $(16, 8, 4, 2, 1)$ 的五个物品,存在一个子博弈完美均衡配置,其根分配在成对占优下不满足 NEL。在价值相同时均衡即为真实行动,因此这仅在博弈模型中证实了该论文对真实行动所记录的轮换序列的失效。

定理 block_snake_two_agent_spe_nel_ef1 (Lean 4 已验证)
theorem block_snake_two_agent_spe_nel_ef1 (k : ℕ) (u : Fin 2 → Fin (2*k+1) → ℝ)
    (hu : ∀ i x, 0 < u i x)
    (hd : ∀ i x y, x ≠ y → u i x ≠ u i y)
    (F : List (Fin (2*k+1)) → Finset (Fin (2*k+1)))
    (hF : pick_game_is_spe u (block_snake_seq_two k) F) :
    is_nel_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F) ∧
    is_ef1_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F)

4. 证明

证明思路: 通过将博弈论问题转化为称为逆向划除的等价非策略性过程,广延形式挑选博弈中子博弈完美均衡的分析得到了简化。

在逆向划除中,挑选序列 $s$ 被倒置。从博弈的最后一次挑选开始并倒推至轮次 0,每个参与者在其分配的逆向轮次中贪心地选择使得对手价值最小的可用物品。在正且相异的可加估值下,这种自底向上的消除精确产生了由子博弈完美均衡行动所生成的分配。

一旦建立了这种等价性,公平性分析就简化为验证块蛇形选秀序列下的逆向划除分配在成对占优下满足 NEL 和 EF1。在 $2k+1$ 个物品上的块蛇形序列为参与者 0 分配 $k$ 个物品,为参与者 1 分配 $k+1$ 个物品。因为参与者 1 获得的物品严格更多,所以 NEL 仅适用于参与者 0 对参与者 1 物品组的比较。移除任意物品 $y$ 后,参与者 1 剩下 $k$ 个物品。自底向上的消除结构保证了在参与者 1 选择物品的每个阶段,该物品在可用物品池中对参与者 0 的价值都是最小的,从而能够构建从 $A(1) \setminus \{y\}$ 到 $A(0)$ 的单射,将每个物品映射到对参与者 0 弱偏好的物品。参与者 0 对参与者 1 的 EF1 可由同样的匹配得出。对于参与者 1 对参与者 0,需要移除一个物品:参与者 0 在正向中最早挑选的物品,即其在逆向中最后挑选的物品。参与者 0 的其他每个物品在逆向中被选出时,都在仍可用的物品中使得参与者 1 的价值最小,并与参与者 1 在下一个逆向轮次中拿走的物品相匹配。

现在陈述各条辅助引理。

引理 1(picking_reverse_crossout_exists)。设 $n \in \mathbb{N}$,设 $u : \text{Fin } 2 \to \text{Fin } n \to \mathbb{R}$,且设 $s : \text{List } (\text{Fin } 2)$ 的长度为 $n$。则存在一个有效的逆向划除序列 $\pi$: $$\exists \pi : \text{Fin } n \to \text{Fin } n, \quad \text{picking\_reverse\_crossout\_valid } u \, s \, \pi.$$

引理 1 的证明。 $\pi$ 的存在性通过对未挑选物品数量进行归纳来确立。在逆序的步骤 $t = 0, \dots, n-1$ 处,令 $R_t = \text{Fin } n \setminus \{\pi(0), \dots, \pi(t-1)\}$ 为剩余物品,其中 $R_0 = \text{Fin } n$。挑选者 $i_t = s^{\text{rev}}(t)$ 面对对手 $1 - i_t$。由于 $R_t$ 是有限非空集合,$u(1 - i_t, \cdot)$ 在 $R_t$ 上达到最小值。选取达到此最小值的 $\pi(t)$,可确保对所有 $j > t$ 均有 $u(1 - i_t, \pi(t)) \le u(1 - i_t, \pi(j))$。根据构造,每个物品恰好被选取一次,因此 $\pi$ 是双射。$\square$

引理 2(picking_two_agent_spe_eq_reverse_crossout)。设 $n \in \mathbb{N}$,设 $s : \text{List } (\text{Fin } 2)$ 为长为 $n$ 的挑选序列,设 $\pi$ 为 $u$ 和 $s$ 的有效逆向划除序列,且设 $F$ 满足 pick_game_is_spe u s F。假设对于两个参与者 $i \in \{0, 1\}$ 和所有物品 $x, y$:

1. $u(i, x) > 0$;

2. $x \ne y \implies u(i, x) \ne u(i, y)$。

则逆向划除分配等于 $F$ 的根分配: $$\text{picking\_reverse\_crossout\_allocation } s \, \pi = \text{pick\_game\_root\_allocation } F.$$

引理 2 的证明。 这是均衡的经典自底向上刻画;形式化证明是对历史长度进行逆向归纳。在具有严格正可加效用和相异价值的双参与者序贯挑选博弈中,逆向归纳产生剩余物品的唯一轨迹。在逆向视角下,正向行动的最后一位挑选者是逆向行动的最早挑选者($t = 0$)。通过拿走使得对手价值最小的物品,逆向挑选者留给对手最有价值的备选项。归纳验证了在任意历史之后,参与者 0 在子博弈完美行动下获得的延续物品组与 $\pi$ 在剩余轮次中分配给参与者 0 的物品一致。在 $h = []$ 处,$F([]) = A_\pi(0)$,其补集与参与者 1 匹配。$\square$

引理 3(block_snake_reverse_crossout_nel_ef1)。设 $k \in \mathbb{N}$,设 $u : \text{Fin } 2 \to \text{Fin } (2k+1) \to \mathbb{R}$,且设 $\pi$ 为 $u$ 和 block_snake_seq_two k 的有效逆向划除序列。则 $A_\pi = \text{picking\_reverse\_crossout\_allocation (block\_snake\_seq_two k) } \pi$ 在成对占优下同时满足 NEL 和 EF1: $$\text{is\_nel\_pd } (\lambda i \, x \, y \Rightarrow u(i, x) \le u(i, y)) \, A_\pi \;\land\; \text{is\_ef1\_pd } (\lambda i \, x \, y \Rightarrow u(i, x) \le u(i, y)) \, A_\pi.$$

引理 3 的证明。 序列 $s = \text{block\_snake\_seq\_two } k$ 的长度为 $2k+1$,对于偶数 $t < 2k$ 有 $s(t) = 0$,否则 $s(t) = 1$。参与者 0 在轮次 $\{0, 2, \dots, 2k-2\}$ 挑选($k$ 个物品),而参与者 1 在轮次 $\{1, 3, \dots, 2k-1, 2k\}$ 挑选($k+1$ 个物品)。

倒置序列 $s^{\text{rev}}$ 指定轮次:

  • $s^{\text{rev}}(0) = 1$ 且 $s^{\text{rev}}(1) = 1$;
  • 对于 $r \ge 1$,$s^{\text{rev}}(2r) = 0$ 且 $s^{\text{rev}}(2r+1) = 1$,以 $s^{\text{rev}}(2k) = 0$ 结束。

因此参与者 1 拥有最初两个逆向轮次,随后严格交替:参与者 0 处于偶数轮次 $2, 4, \dots, 2k$,参与者 1 处于奇数轮次 $3, 5, \dots, 2k-1$。因此,$|A_\pi(0)| = k$ 且 $|A_\pi(1)| = k+1$。

对于 NEL,由于 $|A_\pi(0)| < |A_\pi(1)|$,我们检验参与者 0 对参与者 1。对于任意 $y \in A_\pi(1)$,移除 $y$ 后在 $A_\pi(1) \setminus \{y\}$ 中留下 $k$ 个物品。设这 $k$ 个物品按逆向轮次排列为 $t_1 < \dots < t_k$。$A_\pi(0)$ 的 $k$ 个物品对应逆向轮次 $\tau_m = 2m$(其中 $m \in \{1, \dots, k\}$)。因为参与者 1 的逆向轮次为 $\{0, 1, 3, 5, \dots, 2k-1\}$,所以第 $m$ 个剩余轮次满足 $t_m < 2m = \tau_m$。根据逆向划除的有效性,参与者 1 在轮次 $t_m$ 处的选择使得参与者 0 在 $t_m$ 处可用的物品中的效用最小。由于 $\tau_m > t_m$,物品 $\pi(\tau_m)$ 在轮次 $t_m$ 处可用,所以 $u(0, \pi(t_m)) \le u(0, \pi(\tau_m))$。映射 $\pi(t_m) \mapsto \pi(\tau_m)$ 提供了见证 NEL 所需的单射。

对于 EF1,参与者 0 对参与者 1 可对任意被移除的 $y$ 使用 NEL 单射。对于参与者 1 对参与者 0,在不移除物品的情况下嫉妒未必消失(在价值相同且 $k = 1$ 时,参与者 0 获得最佳物品),因此证明使用 EF1 的第二项子句。移除 $y = \pi(2k)$,即参与者 0 的最后一次逆向挑选。在 $m < k$ 的逆向轮次 $2m$ 处,参与者 0 在剩余物品中最小化参与者 1 的效用,并且 $\pi(2m+1)$ 仍然可用,所以 $u(1, \pi(2m)) \le u(1, \pi(2m+1))$。对 $m = 1, \dots, k-1$ 的映射 $\pi(2m) \mapsto \pi(2m+1)$ 是从 $A_\pi(0) \setminus \{y\}$ 到 $A_\pi(1)$ 的所需单射。$k = 0$ 的情形是显然的。因此 $A_\pi$ 同时满足 NEL 和 EF1。$\square$

作为对比,轮换次序在仅有五个物品时就不满足 NEL。

反例(round_robin_five_item_spe_not_nel)。 考虑 $n = 5$ 个物品($k = 2$)以及具有相同效用的两个参与者: $$u(0, x) = u(1, x) = (16, 8, 4, 2, 1) \quad \text{for } x \in \{0, 1, 2, 3, 4\}.$$ 轮换序列为 $s_{\text{RR}} = [0, 1, 0, 1, 0]$。参与者 0 在轮次 0、2 和 4 挑选;参与者 1 在轮次 1 和 3 挑选。唯一的子博弈完美均衡产生: $$A(0) = \{0, 2, 4\}, \quad A(1) = \{1, 3\},$$ 参与者 0 的价值为 $\{16, 4, 1\}$,参与者 1 的价值为 $\{8, 2\}$。 此处 $|A(1)| = 2 < 3 = |A(0)|$。为使 NEL 成立,对于每个 $y \in A(0)$,必须存在单射 $f : A(0) \setminus \{y\} \to A(1)$,满足对所有 $z$ 均有 $z \le_1 f(z)$。 选取 $y = 4$(效用 1)后留下 $A(0) \setminus \{4\} = \{0, 2\}$,其效用为 16 和 4。 任意单射 $f : \{0, 2\} \to \{1, 3\}$ 都必须将物品 0(效用 16)分配给 $A(1)$ 的某个元素。 成对占优要求 $16 \le u(1, f(0))$,但 $\max_{w \in A(1)} u(1, w) = 8$。由于 $16 > 8$,不存在这样的单射,从而违反了 NEL。

定理证明(block_snake_two_agent_spe_nel_ef1)。 现在综合以上引理:

1. 根据 block_snake_seq_two k 的定义,序列 $s = \text{block\_snake\_seq\_two } k$ 的长度为 $2k+1$。

2. 引理 1(picking_reverse_crossout_exists)给出一个满足 picking_reverse_crossout_valid u s π 的置换 $\pi$。

3. 引理 2(picking_two_agent_spe_eq_reverse_crossout)结合 $hu$、$hd$、$h\pi$ 和 $hF$ 表明: $$\text{picking\_reverse\_crossout\_allocation } s \, \pi = \text{pick\_game\_root\_allocation } F.$$

4. 引理 3(block_snake_reverse_crossout_nel_ef1)结合 $h\pi$ 说明 picking_reverse_crossout_allocation s π 对于由 $u$ 诱导的关系满足 is_nel_pd 和 is_ef1_pd。

5. 利用步骤 3 中的等式进行重写,即证明了 pick_game_root_allocation F 同时满足 is_nel_pd 和 is_ef1_pd。$\square$

5. 讨论

定理 block_snake_two_agent_spe_nel_ef1 直接回应了 arXiv:2611.09685 第 7 节中提出的关于挑选博弈中策略均衡的补偿性公平这一公开问题。该论文询问了当参与者在完全信息下进行策略行动时,补偿性挑选序列是否能保证至多一个物品的无嫉妒(EF1)以及对更大捆绑包至多任意物品的无嫉妒(NEL)。

该论文已经指出轮换序列在真实行动下不满足 NEL,而在均衡中同样不满足(round_robin_five_item_spe_not_nel,具有相同价值 $(16, 8, 4, 2, 1)$ 的五个物品)。block_snake_two_agent_spe_nel_ef1 证明了对于所有奇数个物品 $2k + 1$,块蛇形选秀序列在成对占优下均能保证 EF1 和 NEL。造成这种差异的结构性原因在于选秀次序:块蛇形序列将第 $(2k+1)$ 次挑选分配给参与者 1,导致物品组基数分别为 $k$ 和 $k+1$。在逆向划除过程中,参与者 1 拿走的每个物品都是参与者 0 在剩余物品中最不看重的,并且参与者 1 的逆向轮次足够靠前,能够将参与者 1 的每个剩余物品匹配到参与者 0 的更晚挑选。

该形式化涵盖了具有严格正且相异的可加估值的双参与者全部实例。然而,仍有若干方面在此定理的探讨范围之外:

1. 三个或更多参与者:均衡的自底向上刻画是一个双参与者结果,在有三个或更多参与者时均衡分配未必唯一。

2. 无差异与平局:该定理假设每个参与者在不同物品上的价值相异($x \ne y \implies u(i, x) \ne u(i, y)$)。当参与者在物品之间存在无差异时,可能存在多条子博弈完美均衡路径,需要在逆向划除规范中引入精细的决胜规则。

3. 报告博弈:除了广延形式的序贯挑选外,arXiv:2611.09685 还考虑了报告博弈,其中参与者同时向执行挑选序列的调解人提交偏好排序。虽然已知轮换下的纯纳什均衡满足 EF1,但确定块蛇形下的纯纳什均衡关于真实价值是否能同时保证 EF1 和 NEL 仍是未决的。

4. 非可加偏好:虽然成对占优是纯序数的,但 picking_two_agent_spe_eq_reverse_crossout 中的均衡刻画利用了可加表示。该保证是否适用于非可加估值在此未作讨论。

为什么是研究级成果

  • settles OP-1323 (Compensatory fairness of subgame-perfect equilibria in two-agent picking games)

Lean 声明

  • block_snake_two_agent_spe_nel_ef1For any two agents with positive additive values that are distinct across the items for each agent, every subgame-perfect continuation…
  • round_robin_five_item_spe_not_nelFor two agents with identical item values 16, 8, 4, 2 and 1 and the round-robin order 0,1,0,1,0, there is a subgame-perfect continuation…
  • block_snake_two_agent_spe_nel_ef1_three_itemsFor two agents with positive additive values that are distinct across three items for each agent, every subgame-perfect continuation…
  • block_snake_seq_twoThe block-snake picking sequence for two agents (Fin 2) dividing 2k + 1 items, represented as a List (Fin 2) of length 2k + 1 constructed…
  • pick_game_is_speAn outcome-continuation function is subgame-perfect for a fixed finite two-agent picking order if, after every duplicate-free history, its…
  • pick_game_root_allocationThe root allocation from the continuation assigns its root bundle to agent 0 and all remaining objects to agent 1.
  • is_nel_pdAn allocation A : Agent → Finset Object satisfies NEL under pairwise dominance with respect to item preferences le : Agent → Object →…
  • is_ef1_pdAn allocation A : Agent → Finset Object satisfies EF1 under pairwise dominance with respect to item preferences le : Agent → Object →…
  • picking_reverse_crossout_validA reverse crossout sequence visits every item once and, at every reversed turn, selects an available item of minimum value for the other…
  • picking_reverse_crossout_allocationThe allocation produced by a prescribed reverse picking order and a list of distinct selected goods: an agent receives exactly the…
  • picking_reverse_crossout_existsFor any finite number of items, any two real-valued item functions, and any picking sequence of matching length, there is a valid reverse…
  • picking_two_agent_spe_eq_reverse_crossoutIn a finite two-agent sequential picking game with any fixed order and positive additive item values distinct for each agent, every…
  • block_snake_reverse_crossout_nel_ef1For any two real item-value functions and any valid reverse crossout sequence for the two-agent block-snake picking order, the resulting…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2611.09685 — Who Picks First? Compensatory Fairness When Equal Division Is Impossible

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。