PaperlayerView exact revision on arXiv

Source-linked AI summary

Truthful-in-Expectation MMS Allocations for Chores

Zehan Lin, Biaoshuai Tao, Xiaowei Wu, Yuhao Zhang

arXiv:2609.35280v1cs.GTcs.DS

TL;DR

The paper asks whether truthful-in-expectation mechanisms can guarantee a constant MMS approximation for every realized allocation of indivisible chores. It presents mechanisms with constant ex-post guarantees, including a tight 4/3 ratio for two agents, and establishes lower bounds on achievable ratios.

  • Problem

    Can a truthful-in-expectation mechanism for indivisible chores guarantee a constant MMS approximation for every realized allocation?

    Source: §1 · p. 3

  • Method

    The paper combines a k-nomination mechanism with separate two-agent and equal-marginal mechanisms for additive chores.

    Source: §6 · p. 28

  • Results

    4/3 is the tight ratio for two agents, while the equal-marginal mechanism achieves 1.97 for large n; lower bounds are 4/3 for two agents and 13/12 for every n ≥3.

    Source: §6 · p. 28

  • Takeaways & Limitations

    Constant ex-post MMS guarantees are achievable together with truthfulness-in-expectation for additive chores.

    Source: §6 · p. 28

    The k-nomination approximation guarantee requires k ≤⌊(n −1)/2⌋, although the mechanism remains well-defined and TIE for 1 ≤k < n.

    Source: §3.3 · p. 12

Abstract

from arXiv · show

We study truthful-in-expectation (TIE) mechanisms for allocating indivisible chores alongside ex-post maximin share (MMS) guarantees. For goods, Bu and Tao (FOCS 2025) established a (1/n)-approximation for TIE mechanisms, and this was substantially improved by Babaioff, Feige, and Manaker Morag (FOCS 2026), who established an \Omega(1/\log n) approximation, where n is the number of agents. The corresponding problem for chores has received less attention. The best-known result is due to Aziz, Li, and Wu (MAPR 2024), who gave a TIE mechanism with an O(\sqrt{\log n}) MMS approximation guarantee that holds only in expectation. They also established a 6/5 lower bound for TIE mechanisms for two agents. In this paper, we present the first TIE mechanism for chores that achieves a constant ex-post MMS approximation guarantee. Specifically, our mechanism guarantees an ex-post ratio of 1.97 for any number of agents n, which improves to 4/3 for n=2 and 3/2 for n=3. On the hardness side, we tighten the two-agent lower bound to 4/3, showing that our mechanism is optimal for n=2. More generally, we establish a lower bound of 13/12 on the ex-post MMS approximation ratio achievable by TIE mechanisms for every n\ge 3.

1 Introduction

The paper asks whether TIE mechanisms can give every realized allocation a constant MMS approximation for indivisible chores, improving on prior guarantees that were nonconstant and only in expectation. It answers yes with constant ex-post guarantees and develops fractional-allocation and rounding techniques, alongside lower bounds.

1 Introduction

  • The main question is whether a TIE mechanism can guarantee a constant MMS approximation for every realized allocation of indivisible chores.The prior chores guarantee was O(√log n) and held only in expectation.Source: §1 · pp. 2–3

1.1 Our Results

  • The two-agent mechanism achieves 4/3-MMS, matching the 4/3 lower bound; for every n ≥2, no TIE mechanism can guarantee better than 13/12.For n=3, the lower bound is 8/7.Source: §1.1 · p. 3
  • Randomizing complementary allocation rules balances large and small chores while preserving each agent’s 1/n marginal probability for every chore.Fractional allocations are rounded into integral assignments while controlling each agent’s realized cost.Source: §1.1 · p. 3
  • For every n ≥2, the paper gives an ex-post 1.97-MMS TIE mechanism that is also ex-ante EF.The guarantee is for additive costs and every realized allocation.Source: §1.1 · p. 3

1.2 A Technical Overview

  • Prescribing fractional marginals before decomposing them into integral allocations coordinates chores, allowing every allocation in the lottery’s support to satisfy a cost bound.The uniform fractional allocation yields a (2−1/n)-MMS mechanism; nomination-based marginals yield an ex-post (2−1/(n−k))-MMS guarantee.Source: §1.2 · p. 4
  • For hard agents, complementary roles trade higher fractional cost against lower rounding error, and Birkhoff–von Neumann decomposition converts that trade-off into a 1.97-MMS ex-post guarantee.The roles preserve the designed average marginals.Source: §1.2 · pp. 4–5

1.3 Related Work

  • Prior chores work includes approximate MMS allocations and strategic mechanisms, while the broader literature also studies truthful allocation for goods and divisible items.The cited chores literature reports cardinal and ordinal guarantees, and work on divisible goods and cake cutting considers other settings.Source: §1.3 · pp. 5–6

2 Preliminaries

The preliminaries specify the additive-cost allocation model and define MMS, TIE, ex-post MMS approximation, and equal marginals. Equal marginals implement a uniform fractional allocation and imply ex-ante EF.

2 Preliminaries

  • Each agent has a nonnegative additive cost function over chores, and an allocation partitions all chores among the agents.The mechanism allocates every chore and uses no payments.Source: §2 · p. 6
  • An agent’s MMS for a chore set is the maximum, over partitions into n bundles, of the minimum cost bundle for that agent.Empty bundles are allowed in the ordered partitions.Source: §2 · p. 6
  • TIE means truthful reporting gives an agent the lowest expected cost, while ex-post α-MMS requires every allocation in the mechanism’s support to satisfy the approximation.Source: §2 · p. 6
  • An equal-marginal mechanism gives every agent–chore pair unconditional probability 1/n, implementing the uniform fractional allocation and ensuring ex-ante EF.Each agent’s expected cost for her own bundle equals her expected cost for any other agent’s bundle.Source: §2 · p. 6
  • The paper assumes every agent’s MMS is positive; when an agent’s MMS is zero, the stated basic bound implies her total chore cost is zero.In that case, all chores can be assigned to that agent while preserving TIE.Source: §2 · p. 7

3 k-Nomination Mechanism

The section develops truthful-in-expectation chore mechanisms with ex-post MMS guarantees, first using equal assignment marginals and then nominations to improve the bound. It also establishes where the nomination guarantee is tight and where the mechanism’s parameter restriction matters.

3.1 The 0-Nomination Mechanism

  • Mechanism 1 is TIE, ex-ante EF, and ex-post (2−1/n)-MMS; under uniform sampling, each chore e is allocated to agent i with probability 1/n, independent of the reported profile.Source: §3.1 · p. 7

3.2 The k-Nomination Mechanism

  • Mechanism 1’s tight example reaches (2−1/n) times MMS when an agent receives her largest chore plus one chore from each remaining block.This motivates nomination: agents identify their k most costly chores so the allocation can avoid pairing large chores with many others.Source: §3.2 · p. 9

k-Nomination Mechanism.

  • The k-nomination mechanism samples n−k agents for block-based allocation, then assigns the k remaining chores by a random bijection to the unselected agents.Every realization is safe: selected agents avoid nominated chores and receive at most one chore per residual block; unselected agents receive one chore each.Source: k-Nomination Mechanism · pp. 9–10
  • For n≥3 and 1≤k≤⌊(n−1)/2⌋, the k-nomination mechanism is TIE, ex-ante EF, and ex-post (2−1/(n−k))-MMS.The guarantee is tight: for every ε>0, some instance has a realization with an agent’s cost at least 2−1/(n−k)−ε times her MMS.Source: k-Nomination Mechanism · p. 11, §3.3 · p. 13
  • For two agents, a separate nomination construction achieves TIE and ex-post 4/3-MMS, matching the lower bound and making the mechanism optimal.The general construction applies for n≥3; its approximation ratio decreases as k increases within the permitted range.Source: k-Nomination Mechanism · p. 12

3.3 Limitations of the Nomination Mechanism

  • The k restriction is essential for the claimed guarantee: when k>n/2, the example’s ratio exceeds 2 and approaches n as k→n−1.Within the valid range, the mechanism’s approximation ratio is tight, with instances approaching 2−1/(n−k).Source: §3.3 · pp. 12–13

4 1.97-MMS Mechanism

This section develops sorted-slot rounding and fraction rebalancing for the hard-agent cases, then combines the constructions into a randomized equal-marginal mechanism. For n ≥ 19, the mechanism guarantees an ex-post 1.97-MMS approximation, is truthful in expectation, and is ex-ante envy-free.

4.1 Sorted Slot Rounding with Unequal Fractions

  • Sorted-slot rounding preserves assigned fractions in expectation and gives each agent at most one chore per slot, with a cost bound based on the largest positive-fraction chore and fractional costs of preceding full slots.The strengthened bound applies when |M| > n and the first n slots have total assigned fraction 1; for uniform fractions, the stated bound is ci,(1) + ci(M)/n.Source: §4.1 · pp. 13–15

4.2 Easy and Hard Agents

  • The uniform-allocation rounding bound Γi is at most 2; agents with Γi ≤1.95 are easy, while those above 1.95 are hard.After normalization, ci(M) ≤n, ci,(1) ≤1, and ci,(n+1) ≤0.5; easy agents therefore have 0.02 slack relative to the 1.97 target.Source: §4.2 · p. 15, Easy and Hard Agents · p. 15

Easy and Hard Agents.

  • To target a 1.97-MMS bound while retaining equal marginals, the mechanism samples adjusted intermediate fractional allocations whose average is uniform, then rounds the selected allocation.For hard agents, increasing fractions on large chores can reduce fractional cost, while setting fractions on large chores to zero can reduce the largest cost among positive-fraction chores; zeroing the top ⌊n/4⌋ fractions reduces that largest cost below 0.7.Source: Easy and Hard Agents · pp. 16–17

4.3 Two Hard Agents

  • For two hard agents, the paired construction preserves their average fractions at 1/n and gives both members cost strictly below 1.95 in every rounded allocation.The bound on the union of their most costly chores does not require the agents to rank chores similarly; when they are the only hard agents, all other agents keep uniform fractions and also have cost at most 1.95.Source: §4.3 · p. 18

4.4 More Than Two Hard Agents

  • For settings with at least two hard agents, the paired and triple constructions preserve equal marginals and ensure every realized allocation gives each agent normalized cost at most 1.95.Easy agents retain fractions of 1/n, and the hard agents are grouped into pairs and, when needed, one triple; the intermediate allocations average to the uniform allocation before rounding.Source: §4.4 · p. 20

4.5 Exactly One Hard Agent

  • When exactly one agent is hard, the construction spreads her adjustment among the n−1 easy agents and requires n ≥19 so each helper absorbs less than her 0.02 slack.It introduces two equally likely intermediate allocations and sets the unique hard agent's fraction to zero on chores costing her more than 0.94 in the second allocation.Source: §4.5 · p. 20
  • 1.97: In the exactly-one-hard-agent case, fraction exchanges reduce agent 1’s fractional cost by 0.03 and keep every agent’s rounded cost at most 1.97.For easy agents, the bound is less than Γj + 0.02 ≤ 1.95 + 0.02 = 1.97.Source: §4.5 · p. 21

4.6 Complete Mechanism and Truthfulness

  • The mechanism computes Γi and the hard-agent set, rounds the uniform allocation if none are hard, and otherwise samples an intermediate allocation for the one-hard or multiple-hard case before rounding.Source: §4.6 · p. 22
  • Each chore is assigned to each agent with probability 1/n at every reported profile, so expected cost is ci(M)/n regardless of the report, establishing TIE and ex-ante EF.Source: §4.6 · p. 22
  • For every n ≥19, a polynomial-time randomized equal-marginal mechanism is TIE, ex-ante EF, and ex-post 1.97-MMS.Every resulting allocation gives each agent normalized cost at most 1.97, and Li ≤ μi yields the ex-post MMS guarantee.Source: §4.6 · p. 22
  • Combining this mechanism with the small-n mechanisms from Section 3 gives a uniform approximation ratio strictly below 2 for all n.Source: §4.6 · p. 22
  • The mechanism runs in polynomial time, including the slot construction and Birkhoff–von Neumann decomposition used to sample the final integral allocation.The sorted-slot construction creates at most m + n slots.Source: §4.6 · p. 22

5 Lower Bounds

The lower bounds show that truthful-in-expectation mechanisms cannot achieve arbitrarily strong ex-post MMS guarantees: the barriers vary by agent count and mechanism class. The proof uses hard instances and incentive constraints to rule out ratios below these bounds.

5 Lower Bounds

  • The proof presents two sets of hard instances, with a 1 + Θ(1/n) lower bound for every n ≥2.For two agents, the 4/3 lower bound matches the paper’s upper bound.Source: §5 · p. 22

5.1 TIE Mechanisms: Two Agents

  • 4/3 is the tight lower bound on the ex-post MMS ratio for complete TIE mechanisms with two agents.The paper’s two-agent mechanism achieves the matching ratio.Source: §5 · p. 22, §5.1 · p. 23

5.2 Generalizing to Three or More Agents

  • For n ≥3, the lower bound is 1 + 1/(3 · n −2) when n is odd and 1 + 1/(3 · n −1) when n is even.This bound follows from a three-step incentive argument generalized to n agents.Source: §5.2 · pp. 24–26

5.3 TIE Mechanisms: Large n

  • 13/12 is a lower bound for ex-post MMS mechanisms that are TIE when n ≥4.The proof uses a two-report construction and a single-agent deviation argument.Source: §5 · p. 22, §5.3 · p. 26

5.4 Equal-Marginal Mechanisms

  • 3/2 is a lower bound for equal-marginal mechanisms for every n ≥2.Every allocation strictly better than 3/2-MMS avoids assigning e1 to agent 1, but an equal-marginal mechanism assigns it there with probability 1/n.Source: §5.4 · p. 28

6 Conclusion and Open Problems

The paper gives constant ex-post MMS guarantees for TIE mechanisms allocating additive chores, while establishing lower bounds that constrain achievable ratios. The gap remains large for n ≥3, and the tight ratio for three agents is unknown.

6 Conclusion and Open Problems

  • The k-nomination mechanism achieves ratio 2−1/(n −k) for k ≤⌊(n −1) /2⌋; separate mechanisms achieve 4/3 for two agents and 1.97 for large n.The two-agent ratio is tight; the large-n mechanism is equal-marginal.Source: §6 · p. 28
  • The lower bounds are 4/3 for two agents and 13/12 for every n ≥3.For n ≥3, the gap between the 1.97 guarantee and the lower bounds remains large, and the tight ratio for three agents is unknown.Source: §6 · p. 28
  • The paper leaves open whether richer nomination rules or new decompositions of truthful fractional allocations can substantially reduce the constant.A refined grouping and report-dependent number of large chores yields an upper bound of 15/8 = 1.875, but the analysis is more complex and remains far from the lower bound.Source: §6 · p. 28

A Proof of the Sorted-Slot Rounding Lemma

The rounding proof converts fractional chore-to-slot assignments into a lottery over integral matchings while preserving each chore’s assignment probability. It then bounds each agent’s cost using the first slot and the fractional costs of later slots.

A Proof of the Sorted-Slot Rounding Lemma

  • A fractional perfect matching is formed by connecting chores to slots in proportion to the fraction of each chore in each slot, then adding dummy chores to cover slot deficits.The graph has |M| to |M| + n slots; the resulting edge weights sum to one at each chore and at most one at each slot before dummy chores are added.Source: A Proof of the Sorted-Slot Rounding… · p. 32
  • Sampling an integral perfect matching from the Birkhoff–von Neumann decomposition assigns every chore exactly once and preserves its marginal probability xie of assignment to agent i.Dummy chores are discarded, and each chore goes to the owner of its matched slot.Source: A Proof of the Sorted-Slot Rounding… · p. 32
  • The first slot’s cost is bounded by the most expensive chore with positive fraction, while the later slots’ total cost is bounded by the fractional cost of the preceding slots.The argument uses that chores in a preceding slot are at least as expensive as those in a later slot and that each preceding slot has unit total fraction.Source: A Proof of the Sorted-Slot Rounding… · p. 32

B An Optimal 4/3-MMS Mechanism for Two Agents

The two-agent mechanism uses nominated largest chores and randomly assigns a partition, achieving TIE, ex-ante EF, and an ex-post 4/3-MMS guarantee. Its partition bounds cover coincident and distinct nominations, and the construction runs in polynomial time.

B An Optimal 4/3-MMS Mechanism for Two Agents

  • Each agent nominates her unique largest chore; if nominations coincide, the mechanism randomly assigns a suitable partition, and otherwise each agent receives the other’s nomination plus a random partition part.The parts are assigned in a uniformly random order in either case.Source: B An Optimal 4/3-MMS Mechanism for Two… · pp. 32–33
  • The balanced-partition lemma handles aligned chore rankings by replacing comparable chores with a virtual chore, and handles opposite rankings by alternating chores in sorted order.For opposite rankings, the resulting partition’s cost difference for agent 2 is bounded by her least costly chore in the sequence.Source: B An Optimal 4/3-MMS Mechanism for Two… · pp. 32–33
  • The mechanism and required partitions are computable in polynomial time using cost comparisons, scans, and a fair coin.The partition construction uses polynomial-time algorithms, including the balanced-partition lemma.Source: B An Optimal 4/3-MMS Mechanism for Two… · pp. 33–35
  • When nominations coincide, a partition exists whose parts each cost each agent at most 4/3 of her MMS; with distinct nominations, each resulting bundle costs at most 5/4 of her MMS.The bounds apply regardless of which part an agent receives.Source: B An Optimal 4/3-MMS Mechanism for Two… · p. 33
  • The mechanism is TIE, ex-ante EF, and ex-post 4/3-MMS for two agents.Its proof derives the ex-post guarantee from the cases where the nominations coincide or differ.Source: B An Optimal 4/3-MMS Mechanism for Two… · p. 35
  • Truthfulness follows because an agent’s expected cost depends on her report through the negative half-cost of her nominated largest chore; truthful reporting minimizes that expected cost.Under truthful reporting, expected cost is at most half the total cost, while the other agent’s expected cost is at least half.Source: B An Optimal 4/3-MMS Mechanism for Two… · p. 35
Loading 2609.35280v1…