PaperlayerView exact revision on arXiv

Source-linked AI summary

Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee

Mengfan Ma, Biaoshuai Tao, Fangxiao Wang

arXiv:2609.35670v1cs.GT

TL;DR

For arbitrary additive goods valuations, the open question is whether cardinal information can support a constant ex-post MMS guarantee while preserving TIE. The paper combines a truthful fractional rule with balanced edge coloring and proves a 1/7 ex-post MMS guarantee alongside ex-ante envy-freeness and polynomial-time implementation.

  • Problem

    Prior ordinal TIE mechanisms offered only a nonconstant MMS guarantee, leaving open whether cardinal information can yield a constant guarantee for arbitrary numbers of agents while preserving TIE.

    Source: §1 · p. 3

  • Method

    The mechanism combines a truthful fractional rule with balanced edge coloring to decompose its probabilities into feasible allocations while preserving marginals.

    Source: §1.1.2 · p. 5, §6.2 · p. 34, §7 · p. 34

  • Results

    1/7 MMS ex post, with ex-ante envy-freeness and a polynomial-time explicit distribution supported on at most n·m allocations.

    Source: §1.1 · p. 3, §7 · p. 34

  • Takeaways & Limitations

    A constant ex-post MMS guarantee is achievable for arbitrary numbers of agents while retaining TIE and ex-ante envy-freeness.

    Source: §7 · p. 34

    The paper does not claim 1/7 is optimal; it notes a 2/13 improvement with a longer case analysis.

    Source: §7 · p. 34

Abstract

from arXiv · show

We study the truthful and fair allocation of indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag [FOCS 2026] gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful in expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=\Theta(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism guarantees every agent at least $1/7$ of her MMS in every realized allocation; moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time. Our mechanism has two key technical ingredients, both of which may be of independent interest. The first is a truthful fractional allocation rule specifying each agent's probability of receiving each good: it favors each agent on her top $n-1$ goods and reduces her probability of receiving a good for each other agent who also ranks it among her top $n-1$ goods. The second is the balanced edge coloring: we decompose these probabilities into equally likely matchings from agents to high-value goods, those that alone meet an agent's guarantee, and balance these matchings in a fine-grained way without changing any marginal probability, so that every agent who receives no high-value good can obtain sufficient value from the remaining goods without over-allocating any good.

1 Introduction

The introduction frames the challenge as achieving ex-post fairness for indivisible goods without sacrificing truthful reporting. The paper answers with a TIE mechanism combining a truthful fractional rule and a balanced edge coloring to obtain a constant MMS guarantee.

1 Introduction

  • MMS relaxes proportionality for indivisible goods, while TIE asks whether fairness can hold in every realized allocation despite strategic reporting.The introduction notes that full MMS allocations need not exist and that deterministic truthful mechanisms can have guarantees that vanish as the number of goods grows.Source: §1 · pp. 1–2

1.1 Our contribution and techniques

  • The mechanism guarantees every agent 1/7 of her MMS ex post, is ex-ante envy-free, and has a polynomial-time implementation.For rational binary-encoded valuations, its explicit distribution is supported on at most n·m allocations.Source: §1.1 · p. 3

1.1.1 Overview of our mechanism

  • The design separates a truthful fractional allocation from a distribution over integral allocations that implements its probabilities and guarantees at least 1/7 of TPS in every outcome.TPS is at least MMS, so the TPS guarantee implies the same MMS guarantee.Source: §1.1.1 · p. 4

1.1.2 Our fractional allocation mechanism

  • The top-set rule gives each agent a 1/n base probability per good, adds 1/n on her top n−1 goods, and subtracts 1/(n·(n−1)) per competing agent.For agents whose high-good probabilities total less than one, scaled low-good probabilities provide additional value.Source: §1.1.2 · p. 5

1.1.3 Balanced edge coloring

  • Alternating-path recolorings balance reserved-good blockage and dummy loads without changing marginals, producing feasible per-color allocations that give deficient agents at least 2/7 of TPS.The residual fractional suballocation is distributed among the unassigned portions of goods to assemble allocations averaging exactly to the original probabilities.Source: §1.1.3 · p. 6

1.2 Related work

  • For arbitrary additive goods valuations, closest prior TIE results give ex-ante envy-freeness with ex-post PROP1 and 1/n-MMS, or ex-post 1/(Hn−1 + 2)-TPS; this work achieves constant ex-post TPS with TIE and ex-ante envy-freeness.Source: §1.2 · p. 7

2 Preliminaries

The paper models indivisible-good allocation with private, nonnegative additive valuations and studies truthful mechanisms and fairness guarantees. It uses randomized mechanisms and share benchmarks, then introduces implementation and edge-coloring tools for its construction.

2 Preliminaries

  • Agents have private, nonnegative additive valuations over indivisible goods, and allocations assign every good to exactly one agent.Fractional allocations record portions of goods; fractional suballocations may leave some goods partly or wholly unassigned.Source: §2 · p. 8

2.1 Mechanisms and truthfulness

  • A randomized mechanism maps reported valuations to a distribution over integral allocations; it is truthful in expectation when truthful reporting maximizes expected value.For additive valuations, a randomized or distributional mechanism is TIE exactly when its induced fractional mechanism is truthful.Source: §2.1 · pp. 9–10

2.2 Fairness

  • The paper uses MMS and TPS as own-valuation fairness benchmarks, and ex-post guarantees must hold in every supported allocation.TPS is efficiently computable, and any fraction of TPS guarantees the same fraction of MMS; ex-ante envy-freeness is evaluated in expectation.Source: §2.2 · pp. 10–12

2.3 Technical lemmas

  • A faithful implementation preserves fractional marginals while ensuring each supported allocation gives an agent her fractional value minus at most one partially held good.A bipartite multigraph of maximum degree K admits a proper K-edge-coloring in polynomial time, whose color classes are matchings.Source: §2.3 · pp. 12–13

3 The Top-Set Competitive Fractional Mechanism

The top-set competitive fractional mechanism assigns equal base probabilities, bonuses for an agent’s top n−1 goods, and penalties when others also rank a good in their top sets. Its truthful fractional allocation is feasible and ex-ante envy-free, so any distributional implementation is TIE and ex-ante envy-free.

3 The Top-Set Competitive Fractional Mechanism

  • The mechanism gives each agent a 1/n base probability per good, adds 1/n on her top n−1 goods, and subtracts 1/(n·(n−1)) per other agent competing for that good.Top sets use reported valuations, with ties broken by a public order.Source: §3 · p. 14
  • The resulting fractional allocation is feasible: each good’s probabilities sum to one, and each agent’s probabilities sum to m/n.The construction assumes m ≥ n ≥ 2 after handling the stated boundary cases.Source: §3 · p. 14
  • Truthful reporting maximizes an agent’s expected value because her report affects her marginal probabilities only through the bonus on her selected top set.The bonus goes to her n−1 highest-valued goods under truthful reporting.Source: §3 · p. 15
  • Every randomized implementation is ex-ante envy-free because agents’ marginal differences arise only on goods exclusive to one of their equal-sized top sets.Each agent values goods in her own top set at least as highly as goods exclusive to another agent’s top set.Source: §3 · p. 16
  • Any distributional implementation is TIE and ex-ante envy-free, while later sections construct one with a 1/7-TPS guarantee in every supported allocation.Additive valuations make truthful fractional mechanisms equivalent to TIE distributional implementations.Source: §3 · pp. 14, 17

4 Reserving High Goods

The mechanism reserves high goods, defined by a 1/7-TPS threshold, and builds a feasible fractional suballocation from their marginals. A proper edge-coloring converts that suballocation into equally likely integral matchings, while dummy assignments identify deficient agents who need low goods.

4 Reserving High Goods

  • High goods are worth at least 1/7 of an agent’s TPS; deficient agents have less than one total marginal probability on them, while nondeficient agents have at least one.The high-good suballocation retains all high-good marginals for deficient agents and exactly one total probability for nondeficient agents, prioritizing top-set goods.Source: §4 · p. 17
  • The high-good suballocation is feasible and coordinatewise no greater than the original fractional allocation.It is supported only on high goods.Source: §4 · p. 17

4.1 Implementing xH by integral suballocations

  • With K = n·(n−1), the high-good-dummy graph encodes each retained marginal as parallel edges and gives each deficient agent dummy edges for her remaining probability.Every agent has degree K and each good or dummy has degree at most K, so a proper K-edge-coloring exists.Source: §4.1 · pp. 18–19
  • Each color is a matching assigning every agent either one whole reserved high good or her dummy, with no good assigned twice.The running example’s Figure 1 shows the multigraph and one proper K = 6 coloring; its colors contain one edge incident to each agent and distinct goods.Source: §4.1 · p. 19, Figure 1 · p. 19
  • A uniform draw among the K colors recovers the high-good fractional suballocation’s exact marginals, and every nondeficient agent receives a high good in each color.A deficient agent receives her dummy in K·(1−xi(Hi)) colors; low goods must then be allocated to deficient agents in those colors.Source: §4.1 · pp. 19–20

5 Allocating Low Goods to Deficient Agents

This section constructs and scales low-good fractional allocations for deficient agents, balancing their availability and dummy loads across colors to ensure feasibility. The resulting allocations preserve an average marginal bound relative to unused truthful marginals and give each dummy agent at least twice her required value.

5 Allocating Low Goods to Deficient Agents

  • Feasibility holds in every color, average allocation stays within the unused truthful marginal, and each deficient agent receiving her dummy obtains at least twice her required value.These guarantees allow the colors to be completed to the truthful marginal and implemented faithfully.Source: §5 · p. 20

5.1 The low-good fractional bundles

  • Each deficient agent’s low-good fractional bundle is worth a constant fraction of her TPS value, using the larger of two candidate allocations, capped at one whole good.The candidates concentrate her marginal probability in dummy colors or rescale it by n; the construction addresses both blocked goods and possible over-allocation.Source: §5.1 · pp. 21, 23

5.2 Bounding unblocked value

  • A popular-set bound controls blocked portions, while a reservation-balanced coloring makes reserved-good counts outside that set differ by at most one across colors.The coloring is obtained in polynomial time by exchanging colors along alternating paths, yielding a color-independent average bound for unblocked value.Source: §5.2 · pp. 24–26

5.3 Scaling the unblocked low-good portions

  • Scaling each deficient agent’s unblocked low-good portions by ℓ_i, where 0 < ℓ_i ≤ 1/2, gives at least 2/7 of her TPS value in every color where she receives her dummy.The scaling factor is chosen from the reservation-balanced coloring’s lower bound on unblocked value.Source: §5.3 · p. 26
  • Scaling factors do not depend on the coloring, but each color’s scaled low-good allocation varies with its dummy-agent set and reserved-good set.Each entry of a scaled low-good fractional bundle lies in [0, 1/2].Source: §5.3 · pp. 26–27
  • Although each agent’s scaled bundle is feasible, a color’s combined allocation may over-allocate a good; bounding its dummy load by one suffices for feasibility.The dummy load bounds the total amount assigned to each good in that color.Source: §5.3 · pp. 27–28
  • A reservation-balanced coloring can be converted in polynomial time to one with dummy load at most one in every color, making each color’s scaled low-good allocation feasible.The method transfers dummy load between colors through alternating-path exchanges while preserving reservation balance.Source: §5.3 · p. 28
  • Each color’s scaled low-good allocation is feasible, gives every dummy agent at least twice her required value, and averages to no more than the unused truthful marginal allocation.Together with the high-good integral allocation, these guarantees let the next section add portions to each color so that the colors average exactly to x.Source: §5.3 · p. 30

6 Assembling and Implementing Fractional Allocations

The section completes each color’s fractional allocation by assigning leftover amounts, then implements the allocations as a distribution over integral outcomes. The resulting mechanism preserves the top-set competitive fractional allocation while guaranteeing every supported allocation at least 1/7 of MMS.

6.1 Allocating leftovers and assembling fractional allocations

  • Residual shares divide each color’s unassigned good amounts among agents in proportion to their residual shares, completing the leftovers while averaging to the residual allocation.The residual shares are nonnegative and balance the unassigned amounts.Source: §6.1 · p. 31

6.2 Proof of Theorem 1

  • Faithful implementation and a uniform mixture over colors produce the distribution; reducing its support preserves marginals and retains the guarantee on every supported allocation.The final distribution is computed in polynomial time and has at most n·m allocations.Source: §6.1 · p. 32, §6.2 · pp. 33–34

6.1 Allocating leftovers and assembling fractional allocations

  • Each color’s assembled allocation is feasible, and averaging the colors recovers the top-set competitive fractional allocation exactly.The assembled allocation adds the residual suballocation to the high-good and scaled low-good parts.Source: §6.1 · p. 32
  • In every color, nondeficient agents receive a high good in full, while deficient dummy recipients get at least 2/7 TPS with only low goods held fractionally.These properties support the subsequent faithful implementation guarantee.Source: §6.1 · pp. 32–33

6.2 Proof of Theorem 1

  • Every supported allocation gives each agent at least 1/7 MMS; the mechanism remains TIE and ex-ante envy-free, with a polynomial-time output supported on at most n·m allocations.The support reduction preserves agent–good marginals, so the incentive and envy-freeness properties are retained.Source: §6.2 · pp. 33–34

7 Discussion

The paper establishes a constant ex-post fairness guarantee with a truthful-in-expectation mechanism, and identifies the optimal guarantee as an open question. Its 1/7 bound is not claimed to be optimal.

7 Discussion

  • The mechanism gives each agent at least 1/7 of her maximin share in every realized allocation, with a factor independent of the numbers of goods and agents.It is also ex-ante envy-free and has a polynomial-time, polynomial-support implementation.Source: §7 · p. 34
  • The capacity analysis scales low-good fractional bundles so they remain feasible in every color while preserving the average marginal needed for exact completion.It uses the popular set to control blocking and reserved amounts, and balancing keeps every dummy load below one.Source: §7 · p. 34
  • The authors do not claim that 1/7 is optimal; sharing dummy vertices and tightening the capacity analysis raises the factor to 2/13.They retain 1/7 because the improvement requires a considerably longer case analysis.Source: §7 · p. 34
  • A substantially larger constant may require a different truthful fractional rule or a new way to decompose its marginals into integral allocations.How close such mechanisms can come to the best MMS guarantees known without incentive constraints remains open.Source: §7 · pp. 34–35

AI Methodologies Statement

The authors report substantive use of generative AI tools in preparing the paper. They describe using the tools for construction exploration, proof drafting, text revision, related-work searches, and citation checks, while taking responsibility for the paper's contents.

AI Methodologies Statement

  • OpenAI's GPT-6 Astra and GPT-5.6 Sol, and Anthropic's Claude, were used substantively in preparing the paper.The authors state that all authors are human and take full responsibility for the paper's correctness, originality, and integrity.Source: AI Methodologies Statement · p. 35
  • The OpenAI models helped explore candidate constructions and draft proofs for both the main result and the refined 2/13 analysis..Source: AI Methodologies Statement · p. 35
  • All three tools helped draft and revise text, search for related work, and check citations; the authors say they checked every argument by hand and verified every reference.Source: AI Methodologies Statement · p. 35

A.1 Proof of Lemma 2.11

The faithful implementation preserves fractional marginals while producing integral allocations whose value loss for each agent is bounded by one strictly fractional good. Goods fully assigned fractionally remain assigned to the same agent in every supported allocation.

A.1 Proof of Lemma 2.11

  • Coordinates with x_ig = 1 are fixed before rounding and preserved in every supported allocation.Source: §A.1 · p. 35
  • The proof packs each agent's fractional portions into value-ordered slots, then decomposes the fractional matching into integral matchings with weights summing to one.This gives a finite distribution with exact marginal x; auxiliary zero-valued goods are removed from each resulting allocation.Source: §A.1 · pp. 35–36
  • The slot ordering ensures each realized bundle is worth at least the fractional bundle's value minus the value of its largest strictly fractional good.The fixed full coordinates are added back without loss.Source: §A.1 · p. 36

B.1 Proof of Lemma 5.4

The appendix explains why low-good fractional value is useful for deficient agents, then records reservation estimates and a bound on the popular set's non-top counts. The faithful-implementation result relies on packing and matching arguments to preserve marginals and control value loss.

B.1 Proof of Lemma 5.4

  • Lemma 5.4 gives intuition that a deficient agent's low-good fractional bundle is worth at least a constant fraction of her TPS, but it is not used in subsequent proofs.Source: §B.1 · p. 36
  • The proof uses the capped low-good allocation: low top goods receive full low-good allocation, while goods outside the top set receive at least their scaled fractional amount.The derivation also uses the bound x_ig ≤ 2/n on top goods outside the high-good set.Source: §B.1 · p. 37

C Missing proofs in Section 5.3

C.1 Proof of Lemma C.1

  • The popular-set bound follows by choosing a deficient agent with a largest high-good set and applying the minimality of the popular set's total non-top count.The argument uses the relation between the popular-set size and the minimum high-good-set size among deficient agents.Source: §C.1 · p. 37

C.2 Proof of Lemma C.2

Lemma C.2 bounds high-good reservations outside the popular set, including a stronger bound for deficient agents. Lemma 5.12 then bounds the ceiling of the total amount assigned outside that set.

C.2 Proof of Lemma C.2

  • For each deficient agent i, 2·|Ti\S|−n·xH_i(Ti\S) ≥ max{0, n·(1−xi(Hi))−(|S|−|Hi|)−1}.The difference is nonnegative for every agent, and the displayed stronger bound applies to deficient agents.Source: §C.2 · p. 38
  • The exact top-set contribution is 2·(n−|S|−1)+2·t(S).Here the contribution sums the reservation differences over agents’ top goods outside the popular set.Source: §C.2 · p. 39
  • Reservations outside agents’ top sets contribute at most max{0, 1−t(S)/(n−1)} to the second sum in eq. (13).The proof combines this bound with the exact top-set contribution to establish eq. (11).Source: §C.2 · p. 39

C.3 Proof of Lemma 5.12

  • The ceiling of the total high-good allocation outside S is at most 4·(n−|S|)−2.This follows by bounding the sum and using the strict upper bound in eq. (10).Source: §C.3 · p. 40

C.4 Proof of Lemma C.3

Lemma C.3 estimates the denominator used to scale a deficient agent’s allocation. Its lower bound combines the popular-set and high-good-set sizes, the scaled missing marginal, and the popular set’s non-top count.

C.4 Proof of Lemma C.3

  • The scaling denominator is at least 5·(|S|−|Hi|)+n·(1−xi(Hi))+σ+3+(n−|S|)−t(S).The proof obtains this bound by substituting the second denominator estimate and rewriting n−|Hi| as (|S|−|Hi|)+(n−|S|).Source: §C.4 · pp. 41–42
  • The proof bounds the sum of an agent’s unallocated low-good amount and the low-good amount she holds in S.One bound retains her scaled missing marginal; an integer bound controls loss on goods outside her top set.Source: §C.4 · p. 41

C.5 Proof of Lemma 5.13

Lemma 5.13 shows that each deficient agent’s scaling factor is positive and at most one half. Lemma C.4 then bounds the products of the scaled missing marginals and these factors, both individually and on average.

C.5 Proof of Lemma 5.13

  • 0<ℓi≤2/(σ+4)≤1/2 for every deficient agent i.The denominator is positive because |S|≥|Hi| and σ≥0.Source: §C.5 · p. 42

C.6 Proof of Lemma C.4

  • For each deficient agent, the product n·(1−xi(Hi))·ℓi is bounded individually; the proof derives this from denominator estimates.It treats the case eqi≤s+1 separately, where eqi·ℓi≤2/5, and combines cases to prove the individual bound.Source: §C.6 · pp. 43–45
  • The mean product bound is obtained by averaging over deficient agents while retaining their reservation differences from Lemma C.2.The proof extends the corresponding sums to all agents because the reservation differences are nonnegative.Source: §C.6 · pp. 43, 45

C.7 Proof of Lemma 5.14

When deficient agents exist, Lemma 5.14 bounds a coloring-related quantity for every proper K-edge-coloring. The proof combines the average dummy-load identity with bounds on scaling factors and their products.

C.7 Proof of Lemma 5.14

  • For nonempty D, the proof bounds the average dummy load by 34/35 for every proper K-edge-coloring of G.It uses the average dummy-load identity, the mean product bound from Lemma C.4(ii), and the bound on each scaling factor from Lemma 5.13.Source: §C.7 · p. 46

C.8 Proof of Lemma 5.8

Lemma 5.8 balances the number of reserved goods outside the popular set across colors while preserving a proper coloring. The resulting coloring is constructed in polynomial time.

C.8 Proof of Lemma 5.8

  • At termination, any two colors’ reserved-good counts outside the popular set differ by at most one.This is the reservation-balanced coloring Cres.Source: §C.8 · pp. 46, 48
  • Exchanging colors along a suitable alternating path transfers one reserved good outside the popular set while preserving properness.The path exchange decreases the larger color’s count and increases the smaller color’s count by one.Source: §C.8 · pp. 46–47
  • The balancing procedure performs at most K · n exchanges and runs in polynomial time.Each iteration selects two colors and recolors a path; the exchange bound follows from a potential of at most K · n.Source: §C.8 · p. 48

C.9 Proof of Proposition 5.15

Proposition 5.15 balances dummy loads while preserving reservation balance, making the scaled low-good allocation feasible in every color. Its balancing procedure terminates in polynomial time.

C.9 Proof of Proposition 5.15

  • Because the average dummy load plus the largest scaling factor is below 34/35, each selected transfer leaves the receiving color’s load below one.The procedure transfers load from an overloaded color to a minimum-load color without creating another overloaded color.Source: §C.9 · pp. 49–50
  • The load-balancing exchanges preserve reservation balance by grouping zero-change paths, cancelling path pairs, and at most one count-changing path.A remaining count-changing path swaps counts that differ by one.Source: §C.9 · pp. 49–50
  • The procedure terminates after fewer than 35 · n · K exchanges, and runs in polynomial time for rational scaling factors.Each exchange transfers more than 1/(35 · n); the polynomial-time argument also bounds arithmetic encoding length.Source: §C.9 · pp. 50–51
  • Every good’s total assigned amount in each color is below one once every dummy load is below one.The dummy load bounds each good’s assigned amount in that color.Source: §C.9 · pp. 49, 51
Loading 2609.35670v1…