至多 $2n+1$ 个物品时循环机制的每个纯纳什均衡都满足至多一个物品的无嫉妒
low tier2026-10-26审阅: Claude CodeEnglish
摘要
在可加估值下的不可分物品公平分配中,当智能体诚实行动时,循环机制保证满足至多一个物品的无嫉妒(EF1)。然而,策略性智能体会通过报告偏好排序来最大化其所分配物品包的价值。在 arXiv:2610.23686 中已确立,虽然对于两个智能体,循环机制的每个纯纳什均衡(PNE)都是 EF1 的,但在一般情况下均衡可能不满足 EF1:该论文给出了一个包含三个智能体和八个物品的反例,并证明了一般的 $1/2$-EF1 近似界。该反例在 $n = 3$ 时使用了 $m = 8 = 2n + 2$ 个物品;而对于任意数量的智能体,物品少至多少即可保证 EF1 在该文中并未讨论。我们证明了对于任意数量的智能体 $n \ge 1$ 以及任意数量的物品 $m \le 2n + 1$,非负可加估值下循环机制的每个纯纳什均衡都是 EF1 的。证明通过轮数分解分析:当 $m \le 2n$ 时,每个智能体至多选择两次,且均衡条件阻止了嫉妒程度超过一个物品;当 $m = 2n + 1$ 时,只有智能体 $0$ 分得三个物品,而所有其他智能体至多分得两个物品,且一个与估值无关的偏离论证表明,一旦移除智能体 $0$ 最初挑选的物品,所有其他智能体对智能体 $0$ 都是 EF1 的。对于三个智能体,该界是紧的:该论文中的八物品反例是最小的可能反例。这些结果已在 Lean 4 中形式化并验证。
1. 引言
在具有可加估值的智能体之间公平分配不可分物品的问题,是社会选择理论与算法博弈论中的基础课题。在为此设计的机制中,循环协议因其操作简便以及在真实行为下的优良公平性质而受到广泛研究。在循环协议中,智能体按循环次序轮流选择——智能体 $0$,接着是智能体 $1$,直至智能体 $n-1$,并循环往复——每个人从包含 $m$ 个物品的公共池中挑选自己最偏好的可用物品。循环协议的一个众所周知的经典性质是,当智能体报告其真实估值并近视地挑选时,所得到的分配保证满足至多一个物品的无嫉妒(EF1):从被嫉妒的物品包中移除某个物品后,没有任何智能体嫉妒另一个智能体的物品包。
然而,在现实的分散式场景中,通常不能假定智能体会诚实行事。当智能体了解彼此的偏好时,他们可能会策略性地报告物品排序,而不是报告真实的序数偏好。报告的严格排序配置文件决定了选择序列的结果:每个智能体在轮到自己时,都会分得剩余物品中在其报告排序中排名最高的物品。这导出了一个范式博弈,即选择序列博弈,其中智能体的策略是其报告的物品排列。如果没有任何智能体能够通过单方面偏离到另一个不同的报告排序来获得具有严格更大真实可加价值的物品包,则报告排序的配置文件构成一个纯纳什均衡(PNE)。
策略性行为是否能保持循环机制的公平性保证,在 arXiv:2610.23686 中得到了研究。该论文表明,策略性相互作用确实会降低公平性。虽然该论文证明了对于 $n = 2$ 个智能体,循环机制的每个纯纳什均衡都会产生一个满足 EF1 的分配,但同样的保证并不能无条件地推广到三个或更多智能体的情形。具体而言,arXiv:2610.23686 在命题 1 中给出了一个包含 $n = 3$ 个智能体和 $m = 8$ 个物品的明确反例,其中某个纯纳什均衡不满足 EF1。在积极的一面,arXiv:2610.23686 证明了对于任意数量的智能体和物品,循环机制的每个纯纳什均衡都满足 $1/2$-EF1 近似界。
arXiv:2610.23686 的反例对 $3$ 个智能体使用了 $8$ 个物品,即在 $n = 3$ 时满足 $m = 2n + 2$。这引发了一个关于物品数量作用的自然问题:对于 $n$ 个智能体,物品数量最多达到多少时,循环机制的每个纯纳什均衡都保证满足 EF1?当 $m \le n$ 时,每个智能体至多挑选一次,EF1 是显然成立的;问题在于一旦智能体挑选多次会发生什么。
在本博文中,我们通过 Lean 4 形式化证明了:对于任意 $n \ge 1$ 以及任意 $m \le 2n + 1$,非负可加估值下循环机制的每个纯纳什均衡都是 EF1 的(round_robin_pne_ef1_of_card_le_two_mul_add_one)。这是对一个包含无限多个实例族的积极保证,涵盖了任意数量的智能体。
对于 $n = 3$,该界是紧的:在 $7$ 个物品时每个均衡都是 EF1 的,而论文中具有 $8$ 个物品的实例存在一个非 EF1 均衡。因此,arXiv:2610.23686 中的 $8$ 物品反例对于三个智能体而言是最小的可能反例。对于每个 $n \ge 4$ 是否 $2n + 2$ 个物品就足以打破 EF1,在此尚未得到证明,仍是一个公开问题。
2. 预备知识
我们定义定理中使用的形式化背景和概念,与 Lean 4 的结构和定义保持一致。
我们考虑基数为 $n \ge 1$ 的智能体有限集 $N$,以及基数为 $m \ge 0$ 的不可分物品有限集 $G$。在 Lean 中,它们分别由标准有限类型 Fin $n$ 和 Fin $m$ 表示。
定义 1(估值与可加估值)。抽象估值由结构体 SocialChoice.FairDivision.Indivisible.Valuation 形式化,它由一个为每个“智能体-物品包”对指定一个实数的价值函数组成。可加估值由 SocialChoice.FairDivision.Indivisible.AdditiveValuation 形式化,由一个为每个“智能体-物品”对指定一个实数权重的权重函数定义。物品包的估值通过提升映射 SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation 获得,对于任意智能体 $i \in N$ 和物品包 $S \subseteq G$,它设定 $$ v_i(S) = \sum_{g \in S} w(i, g) $$ 在我们的整个分析中,假定估值是非负的,即对所有 $i \in N$ 和 $g \in G$,均有 $w(i, g) \ge 0$。
定义 2(至多一个物品的无嫉妒)。给定估值 $v$ 和将物品子集分配给智能体的分配 $A : N \to \text{Finset } G$,至多一个物品的无嫉妒(EF1)性质由 SocialChoice.FairDivision.Indivisible.IsEF1 形式化: $$ \forall i, j \in N, \ i \ne j \implies (A_j \text{ is nonempty} \implies \exists g \in A_j, \ v_i(A_j \setminus \{g\}) \le v_i(A_i)). $$ 关于 Lean 定义的说明:Lean 中的定义包含了 $A_j$ 非空的守卫条件。如果智能体 $j$ 分得空物品包($A_j = \emptyset$),则无法移除任何物品,而在非负估值下智能体 $i$ 不会嫉妒空物品包($v_i(\emptyset) = 0 \le v_i(A_i)$)。该定义还采用了弱不等式($\le$)。
定义 3(循环选择序列)。包含 $n$ 个智能体和 $m$ 个物品的循环序列在 Lean 中由 round_robin_sequence 定义。给定 $n$ 和 $m$,round_robin_sequence n m 会生成一个长度为 $m$ 的智能体索引列表,其中在步骤 $t \in \{0, \dots, m-1\}$ 处于行动轮次的智能体由 $t \pmod n$ 给出。智能体按固定的循环次序挑选: $$ (0, 1, \dots, n-1, 0, 1, \dots, n-1, 0, \dots). $$
定义 4(选择序列结果)。智能体的策略是关于物品集合的报告严格排序,形式化为物品的排列,其中位置 $0$ 表示该智能体最偏好的物品,位置 $m-1$ 表示其最不偏好的物品。给定智能体轮次序列和报告排序的配置文件,机制 picking_sequence_outcome 决定了分配 $A : N \to \text{Finset } G$。该机制从左到右遍历轮次序列;在每一步中,处于行动轮次的智能体从尚未被任何智能体在先前步骤中挑选的物品中,选择在其报告排序中排名最高的物品。
定义 5(选择序列的纯纳什均衡)。如果没有任何智能体可以通过单方面报告替代排序来获得具有严格更大真实价值的物品包,则报告严格排序的配置文件是选择序列博弈的纯纳什均衡(PNE),由 is_picking_sequence_pne 形式化: $$ \forall i \in N, \ \forall r, \ v_i(\text{picking\_sequence\_outcome } \text{seq } (\text{rank}[i \mapsto r])(i)) \le v_i(\text{picking\_sequence\_outcome } \text{seq } \text{rank}(i)). $$ 关于 Lean 定义的说明:均衡条件要求任何单方面偏离所产生结果的真实估值都弱小于或等于均衡结果的估值。这是范式博弈中纯纳什均衡的标准定义。
3. 主要结果
在 Lean 4 中形式化的主要结果是:只要物品数量不超过 $2n + 1$,循环机制的每个纯纳什均衡都是 EF1 的。
定理(round_robin_pne_ef1_of_card_le_two_mul_add_one)。设 $n, m \in \mathbb{N}$,满足 $n \ge 1$ 且 $m \le 2n + 1$。设 $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 为满足对所有 $i \in \text{Fin } n$ 和 $g \in \text{Fin } m$ 均有 $w(i, g) \ge 0$ 的权重矩阵,并诱导出可加估值 $v = \text{toValuation}(\langle w \rangle)$。设 $\text{rank} : \text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m)$ 为报告排序的配置文件,它构成了长度为 $m$ 的循环序列的选择序列博弈的纯纳什均衡: $$ \text{is\_picking\_sequence\_pne } v \ (\text{round\_robin\_sequence } n \ m) \ \text{rank}. $$ 那么该选择序列所得的分配满足至多一个物品的无嫉妒: $$ \text{SocialChoice.FairDivision.Indivisible.IsEF1 } v \ (\text{picking\_sequence\_outcome } (\text{round\_robin\_sequence } n \ m) \ \text{rank}). $$
在 Lean 中,round_robin_pne_ef1_of_card_le_two_mul_add_one 对自然数 $n$ 和 $m$ 进行了全称量化,并带有断言 $n$ 非零的类型类实例、不等式假设 $m \le 2n + 1$、带有非负性假设的物品权重矩阵 $w$、报告排序置换的配置文件以及纯纳什均衡假设,得出选择序列结果满足 SocialChoice.FairDivision.Indivisible.IsEF1 的结论。
形式化开发中的进一步结果为均衡的结构以及该界的锐度提供了额外的见解:
round_robin_pne_ef1_of_card_le_two_mul: Proves that when $m \le 2n$, every pure Nash equilibrium of Round-Robin is EF1 under nonnegative additive valuations. In this regime, every agent appears at most twice in the picking sequence.round_robin_pne_envy_zero_ef1_of_two_mul_add_one: Establishes that when $m = 2n + 1$, in every pure Nash equilibrium, every agent $i \ne 0$ is EF1 towards agent $0$. Here, agent $0$ is the unique agent who receives three goods, while all other agents receive at most two.round_robin_pne_ef1_pair_of_count_le_two: Demonstrates that in any pure Nash equilibrium of Round-Robin, an agent $i$ is EF1 towards any agent $j$ who appears at most twice in the sequence.round_robin_three_agents_seven_goods_pne_ef1: Proves that for $n = 3$ agents and $m = 7$ goods, every pure Nash equilibrium of Round-Robin is EF1. This shows that the $8$-good counterexample of arXiv:2610.23686 is minimal: seven goods are never sufficient to break EF1.
theorem round_robin_pne_ef1_of_card_le_two_mul_add_one (n m : ℕ) [NeZero n] (hm : m ≤ 2 * n + 1)
(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) :
SocialChoice.FairDivision.Indivisible.IsEF1
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
(picking_sequence_outcome (round_robin_sequence n m) rank)4. 证明
我们现在给出在 Lean 中形式化的 round_robin_pne_ef1_of_card_le_two_mul_add_one 的证明。
证明概述:
我们首先概述证明思路,然后陈述证明所依赖的引理,最后将它们结合以确立该定理。分析根据物品数量 $m$ 分为两种情形。
在 $m \le 2n$ 的情形下,物品总数至多是智能体数量的两倍。在循环序列中,每个智能体至多轮到两次。当一个智能体至多挑选两个物品时,均衡激励机制会阻止任何其他智能体对该智能体的嫉妒超过一个物品。这种情形由 round_robin_pne_ef1_of_card_le_two_mul 解决。
在 $m = 2n + 1$ 的情形下,恰好有一个智能体——智能体 $0$——挑选三个物品(在轮次 $0$、$n$ 和 $2n$)。所有其他智能体 $j \in \{1, \dots, n-1\}$ 至多挑选两个物品(具体在轮次 $j$ 和 $n + j$)。为验证整个分配的 EF1,我们考虑任意一对不同的智能体 $i$ 和 $j$:
- 如果被嫉妒的智能体 $j$ 满足 $j \ne 0$,那么 $j$ 在序列中至多挑选两次。由
round_robin_pne_ef1_pair_of_count_le_two可知,智能体 $i$ 对 $j$ 的嫉妒不会超过一个物品。 - 如果被嫉妒的智能体 $j$ 是智能体 $0$($j = 0$),那么 $j$ 挑选三个物品。然而,由于 $i \ne j$,我们有 $i \ne 0$。专用引理
round_robin_pne_envy_zero_ef1_of_two_mul_add_one确立了任何智能体 $i \ne 0$ 对智能体 $0$ 都是 EF1 的。
将这些情形结合起来便覆盖了所有可能的配对,并确立了完整分配的 EF1。
我们现在陈述在形式化中确立并用于主定理的支持引理。
引理 1(round_robin_pne_ef1_of_card_le_two_mul)。 设 $n, m \in \mathbb{N}$,满足 $n \ge 1$ 且 $m \le 2n$。设 $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 对所有 $i, g$ 满足 $w(i, g) \ge 0$,并设 $\text{rank}$ 为在由 $w$ 诱导的可加估值下循环机制的纯纳什均衡。那么 picking_sequence_outcome 在 round_robin_sequence 上返回的分配是 EF1 的。
在 Lean 中的作用:该引理处理 $m \le 2n$ 的子情形。当每个智能体在序列中至多出现两次时,没有任何智能体能分得三个或更多物品。如果智能体 $i$ 在从 $A_j$ 中移除任何单个物品后仍嫉妒智能体 $j$,则智能体 $j$ 必然持有两个物品 $\{g_1, g_2\}$ 使得 $v_i(\{g_1\}) > v_i(A_i)$ 且 $v_i(\{g_2\}) > v_i(A_i)$。然而,如果智能体 $i$ 偏离,选择机制允许其在自己的行动轮次中确保获得这些高价值物品中的至少一个,这与均衡假设 is_picking_sequence_pne 矛盾。
引理 2(round_robin_sequence_count_le_two_of_ne_zero)。 设 $n \in \mathbb{N}$ 且 $n \ge 1$。在包含 $n$ 个智能体且长度为 $2n + 1$ 的循环序列中,每个满足 $j \ne 0$ 的智能体 $j$ 至多出现两次: $$ (\text{round\_robin\_sequence } n \ (2n + 1)).\text{count } j \le 2. $$
Lean 中的证明:该序列由索引 $t \in \{0, 1, \dots, 2n\}$ 组成,其中轮次 $t$ 分配给智能体 $t \pmod n$。智能体 $0$ 分得轮次 $t \in \{0, n, 2n\}$,共计 $3$ 轮。对于任意智能体 $j \in \{1, \dots, n-1\}$,分配给 $j$ 的轮次是满足 $t \equiv j \pmod n$ 的值 $t \in \{0, \dots, 2n\}$。这些恰好是 $t = j$ 和 $t = n + j$。下一个潜在轮次将是 $2n + j$;然而,因为 $j \ge 1$,我们有 $2n + j \ge 2n + 1$,超过了序列长度 $m = 2n + 1$。因此,智能体 $j$ 恰好出现两次,从而以 $2$ 为界。
引理 3(round_robin_pne_ef1_pair_of_count_le_two)。 设 $n, m \in \mathbb{N}$ 且 $n \ge 1$。设 $w$ 定义非负可加估值,并设 $\text{rank}$ 为循环机制的纯纳什均衡。对于任意不同的智能体 $i, j$,如果智能体 $j$ 在选择序列中至多出现两次, $$ (\text{round\_robin\_sequence } n \ m).\text{count } j \le 2, $$ 且 $A_j$ 非空,则智能体 $i$ 对智能体 $j$ 是 EF1 的: $$ \exists g \in A_j, \ v_i(A_j \setminus \{g\}) \le v_i(A_i). $$
Lean 中的证明:由于 $j$ 在序列中至多出现两次,物品包 $A_j$ 至多包含两个物品:$|A_j| \le 2$。若 $|A_j| = 1$,设 $A_j = \{g\}$。移除 $g$ 后留下空集 $A_j \setminus \{g\} = \emptyset$。在非负权重($w \ge 0$)下,$v_i(\emptyset) = 0 \le v_i(A_i)$, 立即满足 EF1 条件。若 $|A_j| = 2$,设 $A_j = \{g_1, g_2\}$。不失一般性,假定 $w(i, g_1) \ge w(i, g_2)$。选择 $g = g_1$ 进行移除,我们有 $A_j \setminus \{g_1\} = \{g_2\}$,且 EF1 条件要求 $v_i(\{g_2\}) \le v_i(A_i)$。如果该条件不满足,则 $w(i, g_2) > v_i(A_i)$,进而 $w(i, g_1) \ge w(i, g_2) > v_i(A_i)$。这意味着 $A_j$ 中的两个物品单独对智能体 $i$ 产生的价值,都严格大于智能体 $i$ 均衡物品包 $A_i$ 的全部价值。在选择序列机制下,这两个物品中的至少一个在智能体 $i$ 的某个选择轮次中是可用的。智能体 $i$ 可以单方面改变其报告排序,将该物品置于其排序首位,从而确保获得一个价值严格大于 $v_i(A_i)$ 的物品,从而严格提高其总物品包价值。这与纯纳什均衡条件 is_picking_sequence_pne 矛盾。因此,$v_i(\{g_2\}) \le v_i(A_i)$,证明了智能体对 $(i, j)$ 满足 EF1。
引理 4(round_robin_pne_envy_zero_ef1_of_two_mul_add_one)。 设 $n \in \mathbb{N}$ 且 $n \ge 1$。在包含 $n$ 个智能体和 $2n + 1$ 个物品的循环序列中,在非负可加估值下,在每个纯纳什均衡 $\text{rank}$ 中,每个智能体 $i \ne 0$ 对智能体 $0$ 都是 EF1 的: $$ \exists g \in A_0, \ v_i(A_0 \setminus \{g\}) \le v_i(A_i), $$ 其中 $A_k = \text{picking\_sequence\_outcome } (\text{round\_robin\_sequence } n \ (2n+1)) \ \text{rank } k$。
Lean 中的证明:当 $m = 2n + 1$ 时,智能体 $0$ 在轮次 $0$、$n$ 和 $2n$ 挑选;记其挑选的物品为 $a_1$、$a_2$、$a_3$,其中 $a_1$ 为其报告中排名最高的物品。智能体 $i \ne 0$ 在轮次 $i$ 和 $n + i$ 挑选并分得 $A_i = \{b_1, b_2\}$;注意 $0 < i < n < n + i < 2n$。从 $A_0$ 中移除的物品始终是 $a_1$,因此断言为 $w(i, a_2) + w(i, a_3) \le v_i(A_i)$。
证明首先确立了关于该机制的一个纯组合学事实,与估值无关:对于任何报告,要么 (a) 仅智能体 $i$ 的某个报告 $r$ 就使智能体 $i$ 获得同时包含 $a_2$ 和 $a_3$ 的物品包,要么 (b) 智能体 $i$ 的两个报告 $r_1$、$r_2$ 分别给出物品包 $D_1$、$D_2$,它们按重数共同覆盖 $A_i$ 和 $\{a_2, a_3\}$:每个物品在 $D_1$ 和 $D_2$ 中被计数的次数至少与在 $A_i$ 和 $\{a_2, a_3\}$ 中一样多。这是通过跟踪机制在智能体 $i$ 的最初挑选与智能体 $0$ 的最后挑选之间的轮次窗口中的运行,比较智能体 $i$ 提前拿走 $a_2$ 或 $a_3$ 时哪些物品仍可用而证明的。
然后由均衡条件完成论证。在情形 (a) 中,利用非负权重以及 $r$ 不是有利偏离的事实,有 $w(i, a_2) + w(i, a_3) \le v_i(\text{bundle under } r) \le v_i(A_i)$。在情形 (b) 中,覆盖关系给出 $v_i(A_i) + w(i, a_2) + w(i, a_3) \le v_i(D_1) + v_i(D_2) \le 2 v_i(A_i)$,同样由非负性以及对 $r_1$ 和 $r_2$ 应用均衡条件得出,因此 $w(i, a_2) + w(i, a_3) \le v_i(A_i)$。
结合各引理证明主定理:
我们现在追踪 round_robin_pne_ef1_of_card_le_two_mul_add_one 的 Lean 证明过程:
证明首先对不等式 $m \le 2n$ 进行分支。在 $m \le 2n$ 成立的分支中,证明直接应用 round_robin_pne_ef1_of_card_le_two_mul,从而立即完成目标。
在 $m \le 2n$ 不成立的分支中,我们有 $m > 2n$。结合假设 $m \le 2n + 1$,Lean 的算术策略确立了确切的等式 $m = 2n + 1$。证明将 $m$ 替换为 $2n + 1$。
为了证明 SocialChoice.FairDivision.Indivisible.IsEF1,证明引入了任意智能体 $i, j$、相异性假设 $i \ne j$ 以及 $A_j$ 非空的假设。
证明随后对 $j = 0$ 是否成立进行分支。当 $j = 0$ 时,代入 $j = 0$ 剩下展示智能体 $i$ 对智能体 $0$ 是 EF1 的目标。由于 $i \ne j$ 且 $j = 0$,我们有 $i \ne 0$。证明调用了引理 4,即 round_robin_pne_envy_zero_ef1_of_two_mul_add_one,该引理给出了所需的物品 $g \in A_0$。当 $j \ne 0$ 时,智能体 $j$ 不是智能体 $0$。证明应用了引理 2,即 round_robin_sequence_count_le_two_of_ne_zero,确认智能体 $j$ 在序列中至多出现两次。有了该计数界以及非空假设,证明调用了引理 3,即 round_robin_pne_ef1_pair_of_count_le_two,该引理给出了所需的物品 $g \in A_j$。
由于两种子情形都提供了一个在移除后可消除嫉妒的物品,因此该分配满足 EF1 条件。Lean 证明至此完整且完全通过验证。
5. 讨论
结果 round_robin_pne_ef1_of_card_le_two_mul_add_one 为策略性循环机制的公平性提供了一个积极保证:只要物品数量满足 $m \le 2n + 1$,每个纯纳什均衡都是 EF1 的。这针对任意数量的智能体,将 arXiv:2610.23686 的双智能体 EF1 定理推广到了除智能体 $0$ 分得三个物品外、每个智能体至多分得两个物品的情形。
作为对比,arXiv:2610.23686 表明对于两个以上智能体,每个纯纳什均衡都是 $1/2$-EF1 的,精确的 EF1 可能会失效(命题 1,包含 $n = 3$ 个智能体和 $m = 8$ 个物品),并且通过一个智能体和物品数量递增的实例族,证明了无法保证高于 $2/3$ 的因子。
对于 $n = 3$,round_robin_three_agents_seven_goods_pne_ef1(主定理在 $n = 3$ 时的特例)表明具有 $7$ 个物品的每个纯纳什均衡都是 EF1 的,因此 arXiv:2610.23686 中的 $8$ 物品反例是最小的可能反例,且 $2n + 2$ 是三个智能体时的确切阈值。对于 $n \ge 4$,是否存在某个具有 $2n + 2$ 个物品的实例具有非 EF1 均衡仍是公开的;该阈值至少为 $2n + 2$。
仍有若干问题悬而未决:
- $n \ge 4$ 时的确切阈值:三智能体反例是否能推广到 $n$ 个智能体和 $2n + 2$ 个物品?
- 保证的因子:对于每个均衡所保证的 EF1 因子,arXiv:2610.23686 留下了 $1/2 \le \alpha \le 2/3$ 的差距。此处的论证提示人们去探究所保证的因子如何取决于每个智能体平均分得的物品数量,而不仅取决于智能体的数量。
- 替代选择序列:此处的结果涉及标准的循环次序。其他递归平衡的序列可能具有不同的阈值。
为什么是研究级成果
- Proves exact EF1 for every number of agents when m <= 2n+1, a positive guarantee beyond the general 1/2-EF1 bound and the three-agent/eight-good counterexample in arXiv:2610.23686
Lean 声明
- round_robin_pne_ef1_of_card_le_two_mul_add_oneWith n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- 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…
- 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…
- 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…
- round_robin_pne_envy_zero_ef1_of_two_mul_add_oneWith n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1…
- 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_three_agents_seven_goods_pne_ef1With three agents and seven goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1; so the eight-good…
- round_robin_sequence_count_le_two_of_ne_zeroIn the Round-Robin sequence of n agents and 2n + 1 goods, every agent other than agent 0 picks at most twice.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.23686 — Revisiting the Fairness of Pure Nash Equilibria of Round-Robin
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。