AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Equal-Marginal Chore Lotteries for Two Agents with Bivalued Costs

low tier2026-11-06OP-1112reviewed by Codex中文版

Abstract

For two agents with additive chore costs, suppose that each chore costs agent $i$ either a positive baseline $a_i$ or $r a_i$, with a common ratio $1\le r\le2$. We prove that there is a lottery assigning each chore to each agent with probability $1/2$ and giving each agent at most $(r+1)/2$ times her two-agent chore maximin share in every allocation in the lottery's support. The construction balances the number of chores and each agent's number of high-cost chores across one partition, then mixes that allocation equally with its swap. This gives a ratio-sensitive improvement over the general two-agent equal-marginal $3/2$ guarantee when $r<2$. The upper bound is verified in Lean; the statement does not establish a matching lower bound.

1. Introduction

A collection of indivisible chores must be assigned to two agents. Each agent has additive costs and evaluates a bundle by summing the costs of its chores. A useful benchmark is the two-agent chore maximin share: an agent partitions the chores into two bundles and minimizes the cost of the more expensive bundle. We write this value as $M_i$ for agent $i$.

A deterministic allocation may treat individual chores asymmetrically. A lottery supplies a distribution over complete allocations. It has equal marginals if each chore is assigned to either agent with probability exactly $1/2$. Equal marginals imply that, from the perspective of either agent, the expected cost assigned to each agent is the same. An ex-post guarantee is stronger in a different direction: it bounds the cost in every allocation that receives positive probability, rather than only in expectation.

The general equal-marginal mechanism in arXiv:2609.35280 gives a $3/2$-maximin-share guarantee for two agents. Here we study a restricted cost model in which each agent has a positive baseline $a_i$ and evaluates every chore at either $a_i$ or $r a_i$, where the ratio $r$ is common to the two agents. The upper bound proved here varies continuously with $r$: it is $1$ at $r=1$ and $3/2$ at $r=2$. For $1\le r<2$ it is strictly smaller than the general guarantee.

The larger question asks for a corresponding equal-marginal guarantee for arbitrary numbers of agents. The Lean theorem discussed here concerns only the two-agent upper bound. It neither proves the all-agent statement nor proves that $(r+1)/2$ is the smallest possible factor for every ratio. The proof works by finding one partition whose two bundles are both safe for both agents; with two agents, swapping the bundles then supplies equal marginals.

2. Preliminaries

We establish the setting and formal definitions following the Lean 4 formalization.

Definition 1 (bundle_of). Let $m, n \in \mathbb{N}$. Given an allocation function $\sigma : \text{Fin } m \to \text{Fin } n$ assigning each item $x \in \text{Fin } m$ to an agent $\sigma(x) \in \text{Fin } n$, the bundle assigned to agent $i \in \text{Fin } n$ is the finset $$ \text{bundle\_of } \sigma\ i = \{x \in \text{Fin } m \mid \sigma(x) = i\}. $$ Remark: The chores are indexed by the finite type $\text{Fin } m = \{0, 1, \dots, m-1\}$ and agents by $\text{Fin } n = \{0, 1, \dots, n-1\}$. If no chore is assigned to agent $i$, the bundle is the empty finset $\emptyset$.

Definition 2 (additive_valuation). Let $m \in \mathbb{N}$ and let $u : \text{Fin } m \to \mathbb{R}$ assign a real value to each chore. The additive valuation associated with $u$ is the function mapping any finset $S \subseteq \text{Fin } m$ to the sum of its chore values: $$ \text{additive\_valuation } u\ S = \sum_{j \in S} u(j). $$ Remark: Although the Lean identifier uses the standard name additive_valuation, in the chore setting $u = c_i$ represents an agent's cost function, where costs are non-negative. An empty bundle evaluates to $\sum_{j \in \emptyset} u(j) = 0$.

Definition 3 (chore_maximin_share). Let $m, n \in \mathbb{N}$ and let $u : \text{Fin } m \to \mathbb{R}$ be an additive chore cost function. The $n$-agent chore maximin share of an agent with cost function $u$ is defined as $$ \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). $$ Remark: In the chore setting, an agent partitions the chores into $n$ bundles to minimize the cost of the heaviest bundle. In Lean, this is defined noncomputably using ⨅ and ⨆ over the function space $\text{Fin } m \to \text{Fin } n$ and bundle indices $\text{Fin } n$. Since the space of allocations and the set of agents are finite and non-empty (for $n \ge 1$), the infimum and supremum coincide with the minimum and maximum over all $n$-partitions.

Definition 4 (is_ex_post_alpha_mms_chores). Let $m, n \in \mathbb{N}$, $\alpha \in \mathbb{R}$, and let $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ be a chore cost profile. A lottery $p : (\text{Fin } m \to \text{Fin } n) \to \mathbb{R}$ satisfies is_ex_post_alpha_mms_chores $\alpha\ c\ p$ if every allocation $\sigma$ in its support (that is, with $p(\sigma) > 0$) is $\alpha$-MMS for $c$, meaning that for every agent $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). $$ Remark: The approximation inequality is weak ($\le$). The ex-post condition quantifies strictly over allocations in the support ($p(\sigma) > 0$), requiring that whichever deterministic allocation is realized, no agent incurs a cost exceeding $\alpha$ times her maximin share.

Definition 5 (is_equal_marginal_lottery). Let $m, n \in \mathbb{N}$. The predicate is_equal_marginal_lottery applied to a function $p : (\text{Fin } m \to \text{Fin } n) \to \mathbb{R}$ requires that for every chore $g \in \text{Fin } m$ and every agent $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}. $$ Remark: In the theorem, membership in the standard simplex is a separate requirement, ensuring that $p$ is a probability distribution on allocations: $p(\sigma) \ge 0$ for all $\sigma$ and $\sum_{\sigma} p(\sigma) = 1$. The equal-marginal condition requires that the marginal probability of allocating any chore $g$ to any agent $i$ is identically $1/n$, regardless of chore or agent.

Definition 6 (is_scaled_bivalued_chores). Let $m, n \in \mathbb{N}$, $r \in \mathbb{R}$, and $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$. The chore cost profile $c$ is scaled bivalued with ratio $r$ if there exists a scaling vector $a : \text{Fin } n \to \mathbb{R}$ such that:

1. For every agent $i \in \text{Fin } n$, $0 < a_i$;

2. For every agent $i \in \text{Fin } n$ and every chore $g \in \text{Fin } m$, either $c(i, g) = a_i$ or $c(i, g) = r \cdot a_i$.

Remark: The scaling values $a_i$ are strictly positive. The ratio $r$ is identical across all agents, whereas the base cost $a_i$ may vary across agents. Chores where $c(i, g) = a_i$ are called low chores for agent $i$, and chores where $c(i, g) = r \cdot a_i$ are called high chores for agent $i$.

3. Main result

Theorem (two_agent_bivalued_equal_marginal_sharp_mms). Let $1\le r\le2$, let $m$ be a natural number, and let $c_i(g)$ be the additive cost of chore $g$ to agent $i\in\{0,1\}$. Suppose that for each agent there is a number $a_i>0$ such that every $c_i(g)$ is either $a_i$ or $r a_i$. Then there is a probability distribution over allocations of the $m$ chores to the two agents with both properties:

  1. Every chore is assigned to each agent with marginal probability $1/2$.
  2. For each allocation with positive probability, agent $i$ receives a bundle of cost at most $((r+1)/2)M_i$, where $M_i$ is her two-agent chore maximin share.

The theorem includes the empty set of chores and the endpoint $r=1$. Its conclusion is an upper bound. Although the Lean declaration's identifier contains the word “sharp”, this statement alone does not include a lower-bound or optimality claim. The conjectured extension to three or more agents is not part of the theorem.

Theorem two_agent_bivalued_equal_marginal_sharp_mms (Lean 4, verified)
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. Proof

Write $d=r-1\ge0$. For a given agent, divide all costs by her positive scale. A bundle with $q$ chores, of which $h$ are high for that agent, then costs $q+dh$. We first construct a partition that balances the relevant counts for both agents, and then compare the resulting bound with each agent's maximin share.

Partition the chores into four joint types: low for both agents, low for the first and high for the second, high for the first and low for the second, and high for both. Within each type, put one member of each pair into each side of the partition. This leaves at most one unassigned chore of each type. The contribution of such a chore to the three counts—total chores, high chores for agent 0, and high chores for agent 1—is respectively one of $$ (1,0,0),\quad (1,0,1),\quad (1,1,0),\quad (1,1,1). $$ Choose a sign for each remaining vector, where the sign determines which side receives that chore. With zero or one remaining vector there is nothing to arrange. With two, give them opposite signs. With four, use the relation $$ (1,0,0)+(1,1,1)-(1,0,1)-(1,1,0)=0. $$ With three, restrict the signs in that relation to the three present vectors. The resulting signed sum is the negative of the missing signed vector. In every case the absolute value in each coordinate is at most one. Thus both sides contain at most $\lceil m/2\rceil$ chores and, for each agent separately, at most $\lceil h/2\rceil$ of her $h$ high chores.

For one agent with baseline $a$, either side consequently costs at most $$ U=a\left(\left\lceil\frac m2\right\rceil+d\left\lceil\frac h2\right\rceil\right). $$ Let $M$ be this agent's two-agent chore maximin share. The proof of $U\le(1+d/2)M$ uses different lower bounds on $M$ according to the parity of $m$.

If $m=2k>0$, the more costly bundle in any partition costs at least half the total. Hence $M\ge a(k+dh/2)$. Put $\epsilon=\lceil h/2\rceil-h/2$; it lies between zero and $1/2$. Since $k\ge1$, $$ (1+d/2)(k+dh/2)-(k+d\lceil h/2\rceil) =d(k/2-\epsilon)+d^2h/4\ge0. $$ This proves the desired comparison in the even case.

If $m=2k+1$, every partition has a bundle containing at least $K=k+1$ chores. Its complement contains at most $k$ chores, so the larger bundle contains at least $t=\max(0,h-k)$ high chores. Therefore $M\ge a(K+dt)$. The elementary inequality $\lceil h/2\rceil\le K/2+t$ follows by considering $h\le k$ and $h>k$ separately. It gives $$ U\le a\{K+d(K/2+t)\}\le (1+d/2)a(K+dt)\le(1+d/2)M. $$ The empty case $m=0$ has zero bundle cost. Restoring the positive scale gives the same comparison for each agent. In particular, both sides of the constructed partition meet the stated bound for both agents.

Finally, assign one side to agent 0 and the other to agent 1, each with probability $1/2$ after including the swapped assignment. Every chore goes to either agent in exactly one of the two assignments, so its marginal for each agent is $1/2$. Each agent receives one of the two already bounded bundles in either assignment. When there are no chores the two allocation functions coincide; adding the two probability masses gives the unique allocation total mass one. This also verifies the standard-simplex and support conditions. The Lean proof implements the balancing, the even and odd share bounds, and this swap construction with private auxiliary lemmas.

5. Discussion

The conclusion supplies a ratio-sensitive upper bound for every number of chores in the two-agent model. It is exact as an upper guarantee when $r=1$, where all costs of an individual agent are equal, and agrees with the general $3/2$ equal-marginal guarantee at $r=2$. For intermediate ratios it yields a strictly smaller factor than $3/2$.

The proof separates a combinatorial fact from a cost calculation. The four joint types allow total size and both high-chore counts to be balanced simultaneously. The cost bound then depends only on those three balanced counts and on lower bounds for the two-agent maximin share. The swap is possible because there are exactly two agents: either of the two bundles can be assigned to either agent without leaving a chore unallocated.

This result does not settle whether the displayed factor is optimal for each intermediate ratio. A matching lower-bound statement for the broader problem is a separate, unproved declaration in the knowledgebase and is not used in the theorem. Nor does the proof settle the analogous question for three or more agents, where one partition and its swap are not available as the same two-outcome construction.

The related result in arXiv:2609.35280 treats general additive chore costs and establishes a two-agent equal-marginal factor of $3/2$. The present theorem imposes a common ratio on the two possible costs for each agent and improves that general factor when the ratio is below two. The statement and proof have been checked in Lean; the discussion of other market sizes is a statement of scope, not an additional formal result.

Why it is research-level

  • 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 declarations

  • 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.

References

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

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Codex. Only the Lean is verified; the prose is a reading of it.