AFTD Auto-Formalizing Theoretical Domains

Research Blogs

循环选择机制的纯纳什均衡对至多出现两次的任何参与者消除至多一个物品的嫉妒

low tier2026-10-19审阅: Claude CodeEnglish

摘要

当参与者具有非负可加估价时,循环选择机制的每个纯纳什均衡(PNE)是否都能保证至多一个物品的无嫉妒(EF1)?虽然已发表的一项论断断言循环选择的所有纯纳什均衡都满足 EF1,但最近构造出的一个具有三个参与者和八个物品的反例表明这一普遍论断是错误的。我们表明该性质部分得以保留:在具有非负可加估价的循环选择机制的任何纯纳什均衡中,对于在选择序列中至多出现两次的任何其他参与者,参与者对其产生的嫉妒至多为一个物品。证明通过分析目标参与者的物品束以及在评估参与者的初始轮次之前的部分分配来进行。若目标参与者分得至多一个物品,则移除该物品后嫉妒显然满足 EF1。若目标参与者分得两个物品,则物品数量严格大于参与者数量,并且分配给目标参与者的物品中至少有一个在评估参与者的初始轮次之前尚未被分配。通过偏离策略将该未分配物品置于其报告排名的顶端位置,评估参与者可以确保获得该物品;纯纳什均衡确保他们在均衡中的物品束价值至少等于该物品,从而在移除另一个物品后界定了对目标参与者的嫉妒。这推导出在至多 $2n$ 个物品的情形下所有均衡都是 EF1 的。这些结果已在 Lean 4 中形式化并得到验证。

1. 引言

在策略性参与者之间进行不可分物品的公平分配中,循环选择机制是最著名的协议之一。在该机制中,参与者按循环顺序排列,并根据其报告的偏好轮流选择单个剩余物品。当参与者是非策略性的并真实报告其真实偏好时,在可加估价下,循环选择会产生满足至多一个物品的无嫉妒(EF1)的分配:从任何参与者的物品束中移除至多一个物品后,没有其他参与者会嫉妒他们。

然而,在序贯分配机制中,真实报告通常不是占优策略。当参与者采取策略行为时,他们可能会虚报自己的偏好以操纵选择序列并获得更偏好的物品束。这种策略性互动诱导了一个正规形式博弈,其中每个参与者提交对物品集合的严格排序,机制通过反复向当前行动的参与者分配其排名最高且可用的物品来进行分配。算法博弈论和社会选择中的一个核心问题是,循环选择的理想公平性质在策略博弈下是否仍然成立。具体而言,每个纯纳什均衡(PNE)——即任何参与者都无法通过单方面改变其报告来严格增加其真实物品束估价的报告排名配置——是否都能保证 EF1 分配?

文献中已发表的一项论断断言,具有非负可加估价的循环选择机制的每个纯纳什均衡都会产生 EF1 分配。然而,这一断言最近被一个具有三个参与者和八个物品的反例所否定,在该反例中纯纳什均衡未能满足 EF1。在那个反例中,遭受过度嫉妒的参与者嫉妒的是在序列中选择了三个物品的参与者。

这一否定留下了一个开放问题:循环选择均衡中公平性的确切范围和边界是什么?先前的研究证明,当物品总数 $m$ 满足 $m \le 2n$ 时,每个纯纳什均衡确实都是 EF1 的,形式化为 round_robin_pne_ef1_of_card_le_two_mul。在这一受限情况下,总轮数至多为两轮,因此每个参与者在选择序列中至多获得两个轮次。这提出了一个基础的结构性问题:EF1 的失效是大物品数量下均衡涌现出的全局缺陷,还是均衡条件能够根据参与者各自的轮次数,在成对意义上保护参与者免受对特定参与者的嫉妒?

本文介绍了形式化定理 round_robin_pne_ef1_pair_of_count_le_two,该定理通过表明已发表的论断在逐个参与者的层面上依然成立,回答了这一问题。具体而言,在具有非负可加估价且物品数量 $m$ 任意的循环选择的任何纯纳什均衡中,对于在选择序列中至多出现两次的任何目标参与者 $j$,评估参与者 $i$ 均保证满足对其的 EF1 条件。

这一结果表明,无论物品总数 $m$ 或参与者总数 $n$ 是多少,违背 EF1 条件的嫉妒绝不可能指向选择至多两次的参与者。任何对 EF1 的反例必然存在一个被嫉妒的参与者获得了三个或更多物品。该成对定理直接推导出了当 $m \le 2n$ 时的全局 EF1 保证 round_robin_pne_ef1_of_card_le_two_mul,并分离出了分析 $m = 2n + 1$ 个物品的边界情况所需的精确机制。

2. 预备知识

我们遵循材料中的 Lean 定义对策略性公平分配设定进行形式化。在整篇讨论中,设 $n$ 和 $m$ 为正整数,分别表示参与者和物品的数量。在 Lean 中,参与者由带有非零约束的有限类型 $\text{Fin } n$ 表示,物品由 $\text{Fin } m$ 表示。

定义 1(估价与可加估价)。抽象估价由结构 SocialChoice.FairDivision.Indivisible.Valuation 定义,它由一个估价函数组成: $$v : N \to \mathcal{P}(G) \to \mathbb{R}$$ 为每个参与者 $i \in N$ 和物品束 $S \subseteq G$ 分配一个实数值 $v_i(S)$。可加估价由结构 SocialChoice.FairDivision.Indivisible.AdditiveValuation 定义,由单物品权重 $w : N \to G \to \mathbb{R}$ 参数化,其中 $w(i, g)$ 表示参与者 $i$ 赋予物品 $g$ 的权重。定义 SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation 通过下式将可加估价提升为抽象估价: $$v_i(S) = \sum_{g \in S} w(i, g).$$ 假定估价权重是非负的:对于所有 $i \in N$ 和 $g \in G$,$w(i, g) \ge 0$。

注 1。按照惯例,空和的值为零,因此对每个参与者 $i$ 都有 $v_i(\emptyset) = 0$。权重的非负性保证了弱单调性:若 $S \subseteq T \subseteq G$,则 $v_i(S) \le v_i(T)$。估价针对 $G$ 的所有子集定义,估价因参与者而异,而物品权重 $w$ 在整个博弈过程中保持固定。

定义 2(选择轮次与机制结果)。分配过程的状态是一个对 $(A, U) \in (N \to \mathcal{P}(G)) \times \mathcal{P}(G)$,其中 $A(i)$ 是参与者 $i$ 当前持有的物品束,而 $U = \bigcup_{i \in N} A(i)$ 是迄今为止已分配的所有物品的集合。机制的每个轮次由 picking_turn 决定:给定报告的偏好列表 $l \in \text{List } G$、当前行动的参与者 $i \in N$ 以及状态 $st = (A, U)$,该函数在 $l$ 中搜索满足 $g \notin U$ 的最靠前的物品 $g$。若存在这样的物品 $g$,则状态更新为 $(A[i \mapsto A(i) \cup \{g\}], U \cup \{g\})$;若 $l$ 中的每个物品均已在 $U$ 中,则状态保持为 $st$。

给定参与者轮次序列 $seq \in \text{List } N$ 和报告排名配置 $rank : N \to (\text{Fin } m \simeq G)$,其中 $rank(i)$ 是指定参与者 $i$ 排名的等价(索引 $0$ 为最顶端物品),机制的结果由 picking_sequence_outcome 定义: $$\text{picking\_sequence\_outcome}(seq, rank) = \left( seq.\text{foldl } \left( \lambda st\ a \implies \text{picking\_turn } (\text{List.ofFn } (rank(a)))\ a\ st \right) (\lambda \_ \implies \emptyset, \emptyset) \right).1$$ 它返回最终的物品束分配 $A : N \to \mathcal{P}(G)$。

注 2。每个参与者的排名被形式化为一个等价 $\text{Fin } m \simeq G$,这保证了报告的排名是物品集合的严格排列。机制通过从初始状态 $(\lambda \_ \implies \emptyset, \emptyset)$ 开始在 $seq$ 上对 picking_turn 进行折叠来确定性地运行。

定义 3(循环选择序列)。在 $n$ 个参与者上长度为 $m$ 的循环选择序列由 round_robin_sequence 定义: $$\text{round\_robin\_sequence } n\ m = \text{List.ofFn } \left( \lambda (t : \text{Fin } m) \implies \langle t.val \bmod n, \dots \rangle \right).$$ 轮次 $t \in \{0, 1, \dots, m-1\}$ 被分配给参与者 $t \bmod n \in \text{Fin } n$。

注 3。选择序列完全由参数 $n$ 和 $m$ 确定。参与者按循环顺序 $0, 1, \dots, n-1, 0, 1, \dots$ 出现,直到所有 $m$ 个物品都被分配了轮次。

定义 4(纯纳什均衡)。如果没有任何参与者能够通过单方面偏离到另一个报告排名来获得真实价值严格更高的物品束,则报告严格排名的配置 $rank : N \to (\text{Fin } m \simeq G)$ 是选择序列机制的纯纳什均衡,记作 is_picking_sequence_pne。形式上,对所有 $i \in N$ 以及所有偏离 $r : \text{Fin } m \simeq G$: $$v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r])(i)) \le v_i(\text{picking\_sequence\_outcome}(seq, rank)(i)).$$

注 4。均衡条件使用估价上的弱不等式表述,这意味着参与者 $i$ 的均衡物品束弱占优于通过单方面偏离可获得的任何物品束。序列 $seq$ 以及其他参与者在 $j \ne i$ 时的排名 $rank(j)$ 均保持固定。

定义 5(至多一个物品的无嫉妒)。给定分配 $A : N \to \mathcal{P}(G)$ 和估价配置 $v$,如果满足 $A(j) = \emptyset$ 或者存在物品 $g \in A(j)$ 使得: $$v_i(A(j) \setminus \{g\}) \le v_i(A(i)).$$ 则称参与者 $i \in N$ 对参与者 $j \in N$ 满足至多一个物品的无嫉妒(EF1)。若对所有参与者对 $i, j \in N$ 该不等式均成立,则分配 $A$ 满足 EF1,记作 SocialChoice.FairDivision.Indivisible.IsEF1。

注 5。当 $A(j) = \emptyset$ 时,不需要移除物品:根据非负性,$v_i(\emptyset) = 0 \le v_i(A(i))$ 成立。当 $A(j)$ 非空时,EF1 要求至少存在一个物品 $g \in A(j)$,其被移除后可以消除嫉妒。

3. 主要结果

主定理刻画了对在循环选择序列中至多出现两次的任何参与者所产生的成对嫉妒。

定理 1(round_robin_pne_ef1_pair_of_count_le_two)。设 $n, m \ge 1$ 为自然数。设 $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 为非负物品权重矩阵,且设 $v = \text{SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation } \langle w \rangle$ 为相关的可加估价配置。设 $seq = \text{round\_robin\_sequence } n\ m$ 为循环选择序列。设 $rank : \text{Fin } n \to \text{Fin } m \simeq \text{Fin } m$ 为一个纯纳什均衡的报告排名配置,满足 is_picking_sequence_pne $v\ seq\ rank$。

设 $i, j \in \text{Fin } n$ 为两个互不相同的参与者,满足:

1. 参与者 $j$ 在选择序列中至多出现两次: $$seq.\text{count } j \le 2;$$ 2. 参与者 $j$ 分得的物品束 $A(j) = \text{picking\_sequence\_outcome}(seq, rank)(j)$ 非空。

则参与者 $i$ 对参与者 $j$ 满足至多一个物品的无嫉妒:存在一个物品 $g \in A(j)$ 使得 $$v_i(A(j) \setminus \{g\}) \le v_i(A(i)).$$

在 Lean 中,该定理陈述将英文断言表述为:将 $n$ 和 $m$ 取为自然数且 $n$ 非零,物品权重 $w$ 满足非负性,报告排名为等价,假设 h 断言 is_picking_sequence_pne,对互不相同的参与者 $i$ 和 $j$、轮次数界 hj : (round_robin_sequence n m).count j ≤ 2 以及 $A(j)$ 的非空性进行全称量化,并以存在性断言作为结论,即在 $A(j)$ 中存在一个物品,移除该物品即可消除嫉妒。

进一步结果所补充的内容:

定理 1 中建立的成对保证直接给出了针对小规模实例的全局公平性结果。在长度为 $m \le 2n$ 的任何循环选择序列中,每个 $n$ 个参与者至多出现两次,因为该序列由至多两个完整循环 $(0, 1, \dots, n-1)$ 组成。将定理 1 应用于所有参与者对,可得:

推论 1(round_robin_pne_ef1_of_card_le_two_mul)。设 $n, m \ge 1$ 且 $m \le 2n$。设 $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 为非负物品权重,且设 $rank$ 为循环选择机制的一个纯纳什均衡。则生成的分配满足 SocialChoice.FairDivision.Indivisible.IsEF1:每个参与者对每个其他参与者都满足至多一个物品的无嫉妒。

此外,定理 1 划定了已知反例的确切边界。该构造证明了在 $n = 3$ 个参与者、$m = 8 = 2n + 2$ 个物品时,循环选择的纯纳什均衡可能不满足 EF1。在那个反例中,被嫉妒的参与者获得了三个物品。定理 1 表明这一特征是必需的:违背 EF1 的嫉妒绝不可能指向选择至多两个物品的参与者。

最后,定理 1 是分析中间情况 $m = 2n + 1$ 的核心归纳步骤。当 $m = 2n + 1$ 时,恰好有一个参与者(参与者 $0$)出现三次,而所有其他参与者出现至多两次。定理 1 直接保证了没有任何参与者会对任何参与者 $j \in \{1, \dots, n-1\}$ 产生违背 EF1 的嫉妒,从而将参与者 $0$ 孤立为过度嫉妒的唯一潜在目标。

定理 round_robin_pne_ef1_pair_of_count_le_two (Lean 4 已验证)
theorem round_robin_pne_ef1_pair_of_count_le_two (n m : ℕ) [NeZero n]
    (w : Fin n → Fin m → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin m ≃ Fin m)
    (h : is_picking_sequence_pne
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
      (round_robin_sequence n m) rank)
    (i j : Fin n) (hij : i ≠ j) (hj : (round_robin_sequence n m).count j ≤ 2)
    (hne : (picking_sequence_outcome (round_robin_sequence n m) rank j).Nonempty) :
    ∃ g ∈ picking_sequence_outcome (round_robin_sequence n m) rank j,
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
          (picking_sequence_outcome (round_robin_sequence n m) rank j \ {g}) ≤
        (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
          (picking_sequence_outcome (round_robin_sequence n m) rank i)

4. 证明

我们先概述证明思路,随后介绍在 Lean 中形式化的辅助引理,最后给出完整的逐步论证。

证明思路。 设 $seq = \text{round\_robin\_sequence } n\ m$,$L(a) = \text{List.ofFn } (rank(a))$,并设 $A = \text{picking\_sequence\_outcome}(seq, rank)$ 为最终分配。 若 $|A(j)| \le 1$,则该物品束至多包含一个物品。移除该物品后留下的为空集,其价值为零。由于物品权重非负,参与者 $i$ 的物品束估价至少为零,因此 EF1 显然成立。

若 $|A(j)| > 1$,则由于参与者获得的物品数量不可能超过其在选择序列中出现的次数,且参与者 $j$ 至多出现两次,我们必有 $|A(j)| = 2$ 且 $seq.\text{count } j = 2$。该等式迫使 $n < m$,因为若 $m \le n$,则序列的长度 $m \le n$,而在长度至多为 $n$ 的任何前缀中,每个参与者至多出现一次,这将迫使 $seq.\text{count } j \le 1$。

由于 $n < m$,参与者 $i$ 的初始轮次发生在索引 $i.val < n < m$ 处,这严格位于序列之内。设 $st_0$ 为紧接在参与者 $i$ 的初始轮次之前的中间分配状态,该状态在前缀 $seq.\text{take } i.val$ 之后得到。在长度为 $i.val < n$ 的这一前缀中,参与者 $j$ 至多出现一次,因此参与者 $j$ 在 $st_0$ 中至多持有一个物品。

由于 $|A(j)| = 2$,存在一个物品 $b \in A(j)$ 使得参与者 $j$ 在 $st_0$ 中并不持有 $b$。根据在整个执行过程中物品束保持不相交且单调扩大的不变量,物品 $b$ 在 $st_0$ 中也不能被任何其他参与者持有;因此物品 $b$ 在参与者 $i$ 的初始轮次之前完全未被分配。

参与者 $i$ 可以单方面偏离到将物品 $b$ 置于位置 $0$ 的报告排名 $r'$。因为参与者 $i$ 在索引 $i.val$ 之前的前缀中并未出现,所以更新参与者 $i$ 的排名使得直至状态 $st_0$ 的执行过程完全不受影响。在轮次 $i.val$ 处,参与者 $i$ 行动:由于物品 $b$ 可用且位于位置 $0$,参与者 $i$ 立即选择 $b$。由分配累积的单调性,物品 $b$ 在该偏离下的最终物品束中仍然保留给参与者 $i$。

根据纯纳什均衡条件,参与者 $i$ 的均衡估价 $v_i(A(i))$ 必须至少为其在这一偏离下的估价,由权重的非负性,该估价至少为 $w(i, b)$。最后,由于 $|A(j)| = 2$ 且 $b \in A(j)$,存在另一个不同于 $b$ 的物品 $a \in A(j)$。移除 $a$ 后留下单元素集合 $A(j) \setminus \{a\} = \{b\}$,其对参与者 $i$ 的价值恰好为 $w(i, b) \le v_i(A(i))$。这就确立了 EF1。

辅助引理。 该论证依赖于六个结构性引理:

引理 1(物品束估价的非负性)。对于任何参与者 $i \in \text{Fin } n$ 和任何子集 $S \subseteq \text{Fin } m$, $$0 \le \sum_{g \in S} w(i, g) = v_i(S).$$ Lean 通过对有限集 $S$ 上的非负权重求和来解决此问题。

引理 2(物品束大小受出现次数限制)。在从初始状态 $(A_{init}, U_{init})$ 开始的任何选择序列执行中,对于任何参与者 $k$,在序列 $seq$ 执行期间添加到 $k$ 的物品束中的物品数量至多为 $seq.\text{count } k$: $$|A(k)| \le |A_{init}(k)| + seq.\text{count } k.$$ 特别地,从空初始状态 $init = (\lambda \_ \implies \emptyset, \emptyset)$ 开始,最终物品束满足 $|A(k)| \le seq.\text{count } k$。 Lean 通过使用折叠操作的轮次数界对序列进行归纳来解决此问题。

引理 3(长度至多为 $n$ 的前缀中的出现次数)。设 $n, m \ge 1$ 且 $seq = \text{round\_robin\_sequence } n\ m$。对于任何前缀长度 $k \le n$ 和任何参与者 $k' \in \text{Fin } n$, $$(seq.\text{take } k).\text{count } k' \le 1.$$ 证明:长度为 $k \le n$ 的前缀由轮次 $t \in \{0, \dots, k-1\}$ 组成。在每个轮次 $t$ 处,被分配的参与者为 $t \bmod n$。由于 $t < k \le n$,故 $t \bmod n = t$。轮次序列为 $[0, 1, \dots, k-1]$,其中包含两两互不相同的元素。因此任何参与者 $k'$ 在该前缀中至多出现一次。Lean 利用初始块中的索引模 $n$ 互不相同的性质解决了这一引理。

引理 4(机制不变量与单调性)。机制状态 $st = (A, U)$ 满足一个不变量,断言:

  1. 对所有参与者 $a$,$A(a) \subseteq U$;
  2. 对所有物品 $g \in U$,存在参与者 $a$ 使得 $g \in A(a)$;
  3. 对所有互不相同的参与者 $a \ne b$,$A(a) \cap A(b) = \emptyset$。

空初始状态 $init$ 满足该不变量。每次应用 picking_turn 以及序列上的折叠操作都会保持该不变量。此外,分配是单调增长的:对于任何序列和中间状态,每个参与者在中间状态的物品束都是其在最终状态的物品束的子集。

引理 5(单方面偏离下的前缀不变性)。设 $seq_1 \in \text{List } (\text{Fin } n)$ 为参与者 $i$ 未在其中出现的序列前缀。对于任何偏离 $r' : \text{Fin } m \simeq \text{Fin } m$,在更新后的排名配置 $rank[i \mapsto r']$ 下在 $seq_1$ 上折叠 picking_turn 所产生的中间状态与在 $rank$ 下完全相同。Lean 通过观察到在分配给其他参与者的轮次上从不查询参与者 $i$ 的偏好列表来解决此问题。

引理 6(两元素集合的差集为单元素集)。若 $S$ 为满足 $|S| \le 2$ 的有限集,且 $a, b \in S$ 是互不相同的元素,则 $S \setminus \{a\} = \{b\}$。 证明:显然 $b \in S \setminus \{a\}$,因为 $b \in S$ 且 $b \ne a$。若存在任何元素 $x \in S \setminus \{a\}$ 且 $x \ne b$,则 $\{a, b, x\}$ 将是包含三个互不相同元素的 $S$ 的子集,这意味着 $|S| \ge 3$,与 $|S| \le 2$ 矛盾。Lean 通过验证子集包含关系和基数约束来解决此问题。

定理 1 的逐步证明。 现在我们遵循 round_robin_pne_ef1_pair_of_count_le_two 的形式化证明将这些引理结合起来。

设 $seq = \text{round\_robin\_sequence } n\ m$,$L(a) = \text{List.ofFn } (rank(a))$,且 $init = (\lambda \_ \implies \emptyset, \emptyset)$。设 $A(a) = \text{picking\_sequence\_outcome}(seq, rank)(a)$。由引理 1,对任何集合 $S \subseteq \text{Fin } m$,均有 $v_i(S) \ge 0$。

情形 1:$|A(j)| \le 1$。 根据假设 hne,$A(j)$ 非空,故存在元素 $g \in A(j)$。因为 $|A(j)| \le 1$,所以移除 $g$ 后留下 $A(j) \setminus \{g\} = \emptyset$。空集的估价为 $v_i(\emptyset) = 0$。由引理 1,$0 \le v_i(A(i))$。因此 $v_i(A(j) \setminus \{g\}) \le v_i(A(i))$,这证明了情形 1 的断言。

情形 2:$|A(j)| > 1$。 我们有 $|A(j)| \ge 2$。由引理 2,$|A(j)| \le seq.\text{count } j$。由假设 hj 知 $seq.\text{count } j \le 2$,从而得到: $$2 \le |A(j)| \le seq.\text{count } j \le 2,$$ 这迫使 $|A(j)| = 2$ 且 $seq.\text{count } j = 2$。

我们证明 $n < m$。反设 $m \le n$。则 $seq$ 的长度(即 $m$)至多为 $n$。由引理 3 取 $k = m \le n$,有: $$seq.\text{count } j = (seq.\text{take } m).\text{count } j \le 1,$$ 这与 $seq.\text{count } j = 2$ 矛盾。因此 $n < m$。

由于 $n < m$,参与者 $i$ 的索引满足 $i.val < n < m = seq.\text{length}$。我们将序列分解为: $$seq = seq.\text{take } i.val ++ (seq[i.val] :: seq.\text{drop } (i.val + 1)).$$ 根据序列的定义,在索引 $i.val$ 处行动的参与者为 $i.val \bmod n = i$。

设 $st_0$ 为前缀 $seq.\text{take } i.val$ 之后的中间状态: $$st_0 = (seq.\text{take } i.val).\text{foldl } (\lambda st\ a \implies \text{picking\_turn } (L(a))\ a\ st)\ init.$$ 因为 $i.val < n$,引理 3 意味着 $(seq.\text{take } i.val).\text{count } j \le 1$。将引理 2 应用于该前缀可得 $|st_0.1(j)| \le 1$。

由引理 4(单调性),中间分配是最终分配的子集:对每个参与者 $a$ 均有 $st_0.1(a) \subseteq A(a)$。由于 $|A(j)| = 2$ 且 $|st_0.1(j)| \le 1$,存在物品 $b \in A(j)$ 使得 $b \notin st_0.1(j)$。

我们证明物品 $b$ 在状态 $st_0$ 处完全未被分配,即 $b \notin st_0.2$。反设 $b \in st_0.2$。由引理 4,分配不变量在 $st_0$ 处成立,故存在参与者 $a$ 使得 $b \in st_0.1(a)$。 若 $a = j$,这与 $b \notin st_0.1(j)$ 矛盾。 若 $a \ne j$,则由单调性知 $b \in st_0.1(a) \subseteq A(a)$。但 $b \in A(j)$,这意味着 $b \in A(a) \cap A(j)$。然而,最终的不变量保证了 $A(a)$ 和 $A(j)$ 是不相交的,产生矛盾。因此 $b \notin st_0.2$。

现在考虑参与者 $i$ 的单方面偏离。由于 $m > n \ge 1$,我们有 $m > 0$。设 $r' : \text{Fin } m \simeq \text{Fin } m$ 为交换索引 $0$ 与物品 $b$ 的置换。因此 $r'(0) = b$。

在前缀 $seq.\text{take } i.val$ 中,每个轮次 $t < i.val < n$ 都被分配给参与者 $t \bmod n = t \ne i.val$。因此参与者 $i$ 未在 $seq.\text{take } i.val$ 中出现。由引理 5,在 $rank[i \mapsto r']$ 下运行序列直到索引 $i.val$ 会产生完全相同的中间状态 $st_0$。

在索引 $i.val$ 处,参与者 $i$ 行动。在 picking_turn 中,偏好列表的最前端项为 $r'(0) = b$。由于 $b \notin st_0.2$,线性搜索在位置 $0$ 处找到 $b$。参与者 $i$ 获得物品 $b$,其物品束更新为 $st_0.1(i) \cup \{b\}$。对剩余后缀 $seq.\text{drop } (i.val + 1)$ 应用单调性可知,在偏离 $r'$ 下的最终结果中物品 $b$ 仍保留在参与者 $i$ 的物品束中: $$b \in \text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i).$$

由引理 1 和权重的非负性,单个物品 $b$ 的价值被偏离后物品束的总价值所下界约束: $$w(i, b) \le v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i)).$$ 由纯纳什均衡假设 $h$(is_picking_sequence_pne),参与者 $i$ 的均衡物品束弱占优于偏离后的物品束: $$v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i)) \le v_i(A(i)).$$ 结合这些不等式得到 $w(i, b) \le v_i(A(i))$。

最后,由于 $|A(j)| = 2$ 且 $b \in A(j)$,存在物品 $a \in A(j)$ 使得 $a \ne b$。由引理 6,$A(j) \setminus \{a\} = \{b\}$。缩减后物品束的估价为: $$v_i(A(j) \setminus \{a\}) = v_i(\{b\}) = w(i, b).$$ 由于 $w(i, b) \le v_i(A(i))$,我们得出 $v_i(A(j) \setminus \{a\}) \le v_i(A(i))$。这证明了存在满足 EF1 条件的物品 $a \in A(j)$,从而完成了定理 1 的证明。

5. 讨论

结果 round_robin_pne_ef1_pair_of_count_le_two 确立了在具有非负可加估价的循环选择机制的任何纯纳什均衡中,参与者对选择至多两次的任何参与者的嫉妒始终受限于 EF1。这分离出了普遍 EF1 公平性的已发表论断依然成立的精确结构性条件。

与已发表论断和否定的关系。 此前的已发表文献曾断言,在可加估价下,循环选择的所有纯纳什均衡都是 EF1 的。最近构造出的一个具有三个参与者和八个物品且违背 EF1 的均衡反例否定了这一断言。在那个反例中,被嫉妒的参与者获得了三个物品。定理 1 表明这一特征是不可避免的:不可能存在被嫉妒的参与者获得两个或更少物品的反例。

此外,当物品总数满足 $m \le 2n$ 时,循环选择序列由至多两个完整循环组成,确保每个参与者至多出现两次。因此,定理 1 直接推导出 round_robin_pne_ef1_of_card_le_two_mul,确立了具有 $m \le 2n$ 个物品的每个纯纳什均衡在全局上都是 EF1 的。

该结果未涵盖的内容。 定理 1 未涵盖目标参与者 $j$ 在序列中出现三次或更多次的参与者对 $(i, j)$。对于此类参与者,证明技术遇到了本质障碍:当 $|A(j)| \ge 3$ 时,参与者 $j$ 持有至少两个物品,移除单个物品 $a \in A(j)$ 并不能将剩余物品束缩减为单元素集 $\{b\}$。因此,通过偏离来夺取单个未分配物品 $b$ 不再足以对 $A(j) \setminus \{a\}$ 的价值给出上界。已知的反例证实了这一障碍是数学上的,而不仅仅是证明技术上的:当参与者获得三个或更多物品时,均衡确实可能产生超过 EF1 的嫉妒。

边界情况与后续问题。 在已确认的 EF1 范围($m \le 2n$)与三个参与者的反例所用的八个物品之间,存在着 $m = 2n + 1$ 个物品的边界情况;对 $n \ge 4$,目前不知道是否存在具有 $2n + 2$ 个物品的反例。在长度为 $2n + 1$ 的循环选择序列中,参与者 $0$ 出现三次(分别在轮次 $0$、$n$ 和 $2n$),而每个其他参与者 $j \in \{1, \dots, n-1\}$ 恰好出现两次。

定理 1 直接适用于所有目标 $j \ge 1$,保证了没有任何参与者对任何参与者 $j \in \{1, \dots, n-1\}$ 的嫉妒超过一个物品。因此,在 $m = 2n + 1$ 的情况下,过度嫉妒只可能指向参与者 $0$。这使得 $2n + 1$ 个物品设定下的全局 EF1 问题完全归结为分析对参与者 $0$ 的嫉妒。这一问题此后已经解决:物品数至多为 $2n + 1$ 时,每个纯纳什均衡都是 EF1 的(round_robin_pne_ef1_of_card_le_two_mul_add_one,见 2026 年 10 月 26 日的文章)。

在循环选择协议之外,一个自然的问题是,类似的轮次数界是否同样支配着其他序贯选择机制(例如蛇形选秀或任意选择序列)中的纯纳什均衡。

为什么是研究级成果

  • Shows the published claim corrected by arXiv:2610.23686 survives in part: at every Round-Robin pure Nash equilibrium, envy towards any agent with at most two goods is already EF1, for any number of agents (so every equilibrium with at most 2n goods is EF1, while the paper's counterexample has three agents and eight goods)

Lean 声明

  • round_robin_pne_ef1_pair_of_count_le_twoIn a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears…
  • round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
  • picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
  • picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
  • round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
  • is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…

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

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