AFTD Auto-Formalizing Theoretical Domains

Research Blogs

具有二值成本的双主体等边际家务抽签

low tier2026-11-06OP-1112审阅: CodexEnglish

摘要

对于具有可加家务成本的两个主体,假设每件家务对主体 $i$ 的成本要么是正基准值 $a_i$,要么是 $r a_i$,具有公共比率 $1\le r\le2$。我们证明存在一种抽签,它以概率 $1/2$ 将每件家务分配给每个主体,并且在该抽签支撑集中的每个分配中,赋予每个主体的成本至多为其双主体家务最大化最小值份额(MMS)的 $(r+1)/2$ 倍。该构造在一个划分中平衡了家务数量以及每个主体的高成本家务数量,然后将该分配与其对调分配进行等权重混合。当 $r<2$ 时,这相对于一般的双主体等边际 $3/2$ 保证给出了一个对比率敏感的改进。该上界已在 Lean 中得到验证;该命题并未建立相匹配的下界。

1. 引言

一组不可分家务必须分配给两个主体。每个主体具有可加成本,并通过将其中的家务成本求和来评估一个捆。一个有用的基准是双主体家务最大化最小值份额:主体将家务划分为两个捆,并使成本较高捆的成本最小化。对于主体 $i$,我们将该值记为 $M_i$。

确定性分配可能会不对称地对待单个家务。抽签给出了完全分配上的概率分布。如果每件家务以恰好 $1/2$ 的概率分配给任一主体,则称其具有等边际。等边际意味着,从任一主体的角度来看,分配给每个主体的期望成本都是相同的。事后保证在另一个方向上更强:它对获得正概率的每个分配中的成本进行界定,而不仅仅是在期望意义下。

arXiv:2609.35280 中的一般等边际机制为两个主体给出了 $3/2$-最大化最小值份额保证。在此,我们研究一种受限成本模型,其中每个主体具有正基准值 $a_i$,并对每件家务评估为 $a_i$ 或 $r a_i$,其中比率 $r$ 对两个主体是公共的。此处证明的上界随 $r$ 连续变化:在 $r=1$ 时为 $1$,在 $r=2$ 时为 $3/2$。对于 $1\le r<2$,它严格小于一般保证。

更广泛的问题是寻求针对任意数量主体的相应等边际保证。此处讨论的 Lean 定理仅涉及双主体上界。它既未证明任意多主体的情形,也未证明 $(r+1)/2$ 是对每个比率而言可能最小的因子。该证明通过寻找一个划分来实现,其两个捆对两个主体都是安全的;在两个主体的情况下,对调这两个捆即可提供等边际性。

2. 预备知识

按照 Lean 4 的形式化,我们确立问题设定与形式定义。

定义 1(bundle_of)。设 $m, n \in \mathbb{N}$。给定将每个物品 $x \in \text{Fin } m$ 分配给主体 $\sigma(x) \in \text{Fin } n$ 的分配函数 $\sigma : \text{Fin } m \to \text{Fin } n$,分配给主体 $i \in \text{Fin } n$ 的捆为有限集 $$ \text{bundle\_of } \sigma\ i = \{x \in \text{Fin } m \mid \sigma(x) = i\}. $$ 注:家务由有限类型 $\text{Fin } m = \{0, 1, \dots, m-1\}$ 索引,主体由 $\text{Fin } n = \{0, 1, \dots, n-1\}$ 索引。若没有家务分配给主体 $i$,则该捆为空有限集 $\emptyset$。

定义 2(additive_valuation)。设 $m \in \mathbb{N}$,且令 $u : \text{Fin } m \to \mathbb{R}$ 为每件家务赋予一个实数值。与 $u$ 相关的可加估值是将任意有限子集 $S \subseteq \text{Fin } m$ 映射为其家务价值之和的函数: $$ \text{additive\_valuation } u\ S = \sum_{j \in S} u(j). $$ 注:尽管 Lean 标识符使用了标准名称 additive_valuation,但在家务设定中,$u = c_i$ 表示主体的成本函数,其中成本为非负。空捆的估值为 $\sum_{j \in \emptyset} u(j) = 0$。

定义 3(chore_maximin_share)。设 $m, n \in \mathbb{N}$,且令 $u : \text{Fin } m \to \mathbb{R}$ 为可加家务成本函数。具有成本函数 $u$ 的主体的 $n$ 主体家务最大化最小值份额定义为 $$ \text{chore\_maximin_share } n\ u = \inf_{P : \text{Fin } m \to \text{Fin } n} \sup_{k \in \text{Fin } n} \text{additive\_valuation } u\ (\text{bundle\_of } P\ k). $$ 注:在家务设定中,主体将家务划分为 $n$ 个捆,以使最重捆的成本最小化。在 Lean 中,这是在函数空间 $\text{Fin } m \to \text{Fin } n$ 与捆索引 $\text{Fin } n$ 上使用 ⨅ 和 ⨆ 进行非可计算定义的。由于分配空间和主体集合都是有限且非空的(对于 $n \ge 1$),因此下确界和上确界与所有 $n$-划分上的最小值和最大值重合。

定义 4(is_ex_post_alpha_mms_chores)。设 $m, n \in \mathbb{N}$,$\alpha \in \mathbb{R}$,且令 $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 为家务成本配置文件。若抽签 $p : (\text{Fin } m \to \text{Fin } n) \to \mathbb{R}$ 其支撑集中的每个分配 $\sigma$(即满足 $p(\sigma) > 0$)对于 $c$ 都是 $\alpha$-MMS 的,则称 $p$ 满足 is_ex_post_alpha_mms_chores $\alpha\ c\ p$,这意味着对每个主体 $i \in \text{Fin } n$, $$ \text{additive\_valuation } (c\ i)\ (\text{bundle\_of } \sigma\ i) \le \alpha \cdot \text{chore\_maximin_share } n\ (c\ i). $$ 注:近似不等式是弱不等式($\le$)。事后条件严格对支撑集中的分配($p(\sigma) > 0$)进行量化,要求无论实现哪个确定性分配,任何主体承担的成本都不会超过其最大化最小值份额的 $\alpha$ 倍。

定义 5(is_equal_marginal_lottery)。设 $m, n \in \mathbb{N}$。作用于函数 $p : (\text{Fin } m \to \text{Fin } n) \to \mathbb{R}$ 的谓词 is_equal_marginal_lottery 要求对于每件家务 $g \in \text{Fin } m$ 和每个主体 $i \in \text{Fin } n$, $$ \sum_{\sigma : \text{Fin } m \to \text{Fin } n} (\text{if } \sigma(g) = i \text{ then } p(\sigma) \text{ else } 0) = \frac{1}{n}. $$ 注:在定理中,属于标准单纯形是一个独立的要求,确保 $p$ 是分配上的概率分布:对所有 $\sigma$ 有 $p(\sigma) \ge 0$ 且 $\sum_{\sigma} p(\sigma) = 1$。等边际条件要求将任意家务 $g$ 分配给任意主体 $i$ 的边际概率恒为 $1/n$,无论家务或主体为何。

定义 6(is_scaled_bivalued_chores)。设 $m, n \in \mathbb{N}$,$r \in \mathbb{R}$,且 $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$。若存在缩放向量 $a : \text{Fin } n \to \mathbb{R}$ 使得:

1. 对每个主体 $i \in \text{Fin } n$,$0 < a_i$;

2. 对每个主体 $i \in \text{Fin } n$ 以及每件家务 $g \in \text{Fin } m$,要么 $c(i, g) = a_i$,要么 $c(i, g) = r \cdot a_i$。

则家务成本配置文件 $c$ 称为比率为 $r$ 的按比例缩放二值成本。

注:缩放值 $a_i$ 严格为正。比率 $r$ 在所有主体间相同,而基础成本 $a_i$ 在不同主体间可以不同。满足 $c(i, g) = a_i$ 的家务称为主体 $i$ 的低成本家务,满足 $c(i, g) = r \cdot a_i$ 的家务称为主体 $i$ 的高成本家务。

3. 主要结果

定理(two_agent_bivalued_equal_marginal_sharp_mms)。设 $1\le r\le2$,$m$ 为自然数,且 $c_i(g)$ 为主体 $i\in\{0,1\}$ 对家务 $g$ 的可加成本。假设对每个主体存在数 $a_i>0$,使得每个 $c_i(g)$ 要么是 $a_i$ 要么是 $r a_i$。则存在将这 $m$ 件家务分配给两个主体的分配上的概率分布,同时满足以下两条性质:

  1. 每件家务以边际概率 $1/2$ 分配给每个主体。
  2. 对于每个具有正概率的分配,主体 $i$ 获得的捆的成本至多为 $((r+1)/2)M_i$,其中 $M_i$ 是该主体的双主体家务最大化最小值份额。

该定理包含空家务集以及端点 $r=1$。其结论是一个上界。尽管 Lean 声明的标识符包含单词“sharp”,但该命题本身并不包含下界或最优性断言。猜想向三个或更多主体的推广不属于该定理的一部分。

定理 two_agent_bivalued_equal_marginal_sharp_mms (Lean 4 已验证)
theorem two_agent_bivalued_equal_marginal_sharp_mms
    (r : ℝ) (hr1 : 1 ≤ r) (hr2 : r ≤ 2)
    (m : ℕ) (c : Fin 2 → Fin m → ℝ)
    (hc : is_scaled_bivalued_chores r c) :
    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),
      is_equal_marginal_lottery p ∧
      is_ex_post_alpha_mms_chores ((r + 1) / 2) c p

4. 证明

记 $d=r-1\ge0$。对于给定主体,将其所有成本除以其正缩放值。那么包含 $q$ 件家务、其中 $h$ 件对该主体为高成本家务的捆的成本为 $q+dh$。我们首先构造一个对两个主体平衡相关计数的划分,然后将所得的界与每个主体的最大化最小值份额进行比较。

将家务划分为四种联合类型:对两个主体均为低成本;对第一个主体为低成本、对第二个主体为高成本;对第一个主体为高成本、对第二个主体为低成本;对两个主体均为高成本。在每种类型内部,将每对成员中的一个分别放入划分的两侧。这样每种类型至多留下一个未分配的家务。这样一件家务对三个计数——总家务数、主体 0 的高成本家务数、主体 1 的高成本家务数——的贡献分别是下列之一: $$ (1,0,0),\quad (1,0,1),\quad (1,1,0),\quad (1,1,1). $$ 为每个剩余向量选择一个符号,其中符号决定哪一侧接收该家务。在有零个或一个剩余向量时,无需特别安排。在有两个时,赋予它们相反的符号。在有四个时,使用关系 $$ (1,0,0)+(1,1,1)-(1,0,1)-(1,1,0)=0. $$ 在有三个时,将该关系中的符号限制在出现的三个向量上。所得的带符号和即为缺失的带符号向量的相反数。在所有情况下,每个坐标上的绝对值至多为 1。因此,两侧均包含至多 $\lceil m/2\rceil$ 件家务,并且对每个主体分别而言,在其 $h$ 件高成本家务中至多包含 $\lceil h/2\rceil$ 件。

对于基准值为 $a$ 的单个主体,任一侧的成本因此至多为 $$ U=a\left(\left\lceil\frac m2\right\rceil+d\left\lceil\frac h2\right\rceil\right). $$ 设 $M$ 为该主体的双主体家务最大化最小值份额。$U\le(1+d/2)M$ 的证明根据 $m$ 的奇偶性使用 $M$ 的不同下界。

若 $m=2k>0$,则任何划分中成本较高的捆的成本至少为总成本的一半。因此 $M\ge a(k+dh/2)$。令 $\epsilon=\lceil h/2\rceil-h/2$;它介于零和 $1/2$ 之间。由于 $k\ge1$, $$ (1+d/2)(k+dh/2)-(k+d\lceil h/2\rceil) =d(k/2-\epsilon)+d^2h/4\ge0. $$ 这证明了偶数情况下的所需比较。

若 $m=2k+1$,则每个划分都存在一个至少包含 $K=k+1$ 件家务的捆。其补集至多包含 $k$ 件家务,因此较大的捆至少包含 $t=\max(0,h-k)$ 件高成本家务。因此 $M\ge a(K+dt)$。通过分别考虑 $h\le k$ 和 $h>k$,可得出初等不等式 $\lceil h/2\rceil\le K/2+t$。由此给出 $$ U\le a\{K+d(K/2+t)\}\le (1+d/2)a(K+dt)\le(1+d/2)M. $$ 空家务情况 $m=0$ 的捆成本为零。恢复正缩放值后,对每个主体给出相同的比较。特别地,所构造划分的两侧对两个主体均满足所述的界。

最后,将一侧分配给主体 0,另一侧分配给主体 1,在计入对调分配后,每种分配的概率均为 $1/2$。每件家务在两种分配中恰好有一种分配给任一主体,因此其对每个主体的边际概率均为 $1/2$。在任一分配中,每个主体接收两个已被界定的捆之一。当没有家务时,这两个分配函数重合;将两个概率质量相加赋予这唯一的分配以总质量 1。这也验证了标准单纯形和支撑集条件。Lean 证明使用私有辅助引理实现了平衡、偶数和奇数份额界,以及该对调构造。

5. 讨论

该结论为双主体模型中任意数量的家务提供了一个对比率敏感的上界。在 $r=1$ 时(此时单个主体的所有成本均相等),它作为上限保证是精确的;而在 $r=2$ 时,它与一般的 $3/2$ 等边际保证一致。对于介于其间的比率,它给出了严格小于 $3/2$ 的因子。

该证明将组合事实与成本计算分离开来。四种联合类型使得总大小和两个高成本家务计数能够同时得到平衡。随后,成本界仅依赖于这三个平衡计数以及双主体最大化最小值份额的下界。对调之所以可行,是因为恰好有两个主体:这两个捆中的任一个都可以分配给任一主体,而不会留下未分配的家务。

该结果并未解决所列出的因子对于每个中间比率是否是最优的。对于更广泛问题的匹配下界陈述是知识库中一个独立的、未证明的声明,且未在定理中使用。该证明也未解决三个或更多主体的类似问题,因为在那种情况下,单个划分及其对调无法作为同样的双结果构造来使用。

arXiv:2609.35280 中的相关结果处理了一般可加家务成本,并确立了双主体等边际因子 $3/2$。本定理对每个主体的两种可能成本施加了公共比率,并在比率低于 2 时改进了一般因子。命题和证明已在 Lean 中经过检验;对其他市场规模的讨论属于适用范围的说明,而非额外的形式化结果。

为什么是研究级成果

  • For two agents with bivalued costs of common ratio 1 ≤ r < 2, establishes an equal-marginal lottery with ex-post (r+1)/2 maximin-share guarantee, improving the general 3/2 equal-marginal guarantee in https://arxiv.org/abs/2609.35280

Lean 声明

  • two_agent_bivalued_equal_marginal_sharp_mmsFor two agents (n = 2), ratio r with 1 ≤ r and r ≤ 2, and m chores with a cost profile c : Fin 2 → Fin m → ℝ satisfying…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
  • is_ex_post_alpha_mms_choresAn allocation lottery p over allocations of m chores among n agents is ex-post α-MMS for chore costs c if every allocation σ in the…
  • is_equal_marginal_lotteryA lottery p over complete allocations of m chores to n agents has equal marginals if every chore g is assigned to every agent i with…
  • is_scaled_bivalued_choresGiven ratio r : ℝ and a chore cost profile c : Fin n → Fin m → ℝ over n agents and m chores, c is scaled bivalued with ratio r if there…

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

参考文献

  1. arXiv:2609.35280 — Truthful-in-Expectation MMS Allocations for Chores

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