pith. sign in

arxiv: 2411.11131 · v2 · submitted 2024-11-17 · 💻 cs.GT · econ.TH

On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness

Moshe Babaioff , Noam Manaker Morag This is my paper

Pith reviewed 2026-05-23 16:47 UTC · model grok-4.3

classification 💻 cs.GT econ.TH
keywords strategy-proofnon-bossyneutralityserial-quota mechanismsindivisible goodsadditive valuationslexicographic preferencesfair allocation
0
0 comments X

The pith

For rich domains of strict ordinal and additive preferences, serial-quota mechanisms are the only strategy-proof, non-bossy, and neutral allocation rules, even without Pareto efficiency.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a characterization of truthful mechanisms for allocating indivisible goods without money. It proves that under lexicographic preferences, all strict preferences, and valuation classes containing additive ones, the only mechanisms that are strategy-proof, non-bossy, and neutral are serial-quota mechanisms. This holds even if the mechanism is not required to be Pareto efficient. The result implies strong limitations on the existence of other truthful mechanisms for fair allocation.

Core claim

Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. We show that for important classes of strict ordinal preferences (lexicographic and all strict preferences), these are the only mechanisms that are strategy-proof, non-bossy, and neutral. This holds even for mechanisms that are not Pareto-efficient. The results generalize to cardinal preferences including any valuation class that contains additive valuations, with negative implications for truthful fair allocation mechanisms.

What carries the argument

Serial-quota mechanisms, defined by a fixed order of agents and a quota of goods each picks from the remaining pool.

Load-bearing premise

The preference domain must include all strict orders or all additive valuations, and the mechanism must satisfy the axioms for every possible preference profile.

What would settle it

Finding a mechanism that is strategy-proof, non-bossy, and neutral but not equivalent to any serial-quota mechanism when preferences are all strict orders would falsify the characterization.

read the original abstract

We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties? We show that for important classes of strict ordinal preferences (as lexicographic preferences, and as the class of all strict preferences), these are the only mechanisms with these properties. Importantly, unlike previous work, we can prove the claim even for mechanisms that are not Pareto-efficient. Moreover, we generalize these results to preferences that are cardinal, including any valuation class that contains additive valuations. We then derive strong negative implications of this result on truthful mechanisms for fair allocation of indivisible goods to agents with additive valuations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript characterizes strategy-proof, non-bossy, and neutral mechanisms for allocating indivisible heterogeneous goods without transfers. It proves that, on the domains of lexicographic preferences, all strict ordinal preferences, and any cardinal valuation class containing the additive valuations, the only mechanisms satisfying these three axioms are the serial-quota mechanisms; the characterization is obtained without assuming Pareto efficiency. Negative corollaries are then derived for truthful mechanisms in the fair allocation setting with additive valuations.

Significance. If the characterization holds, the result is significant because it removes the Pareto-efficiency axiom that appeared in prior characterizations of serial mechanisms, showing that strategy-proofness, non-bossiness, and neutrality alone suffice on the stated rich domains. The explicit negative implications for additive valuations strengthen the case that truthful fair-division rules are severely restricted. The paper supplies a clean, axiomatically tight description of a natural family of mechanisms that is already known to be strategy-proof.

major comments (1)
  1. [Theorem statements (presumably §3–4)] The central claim (that SP + non-bossiness + neutrality pins down serial-quota mechanisms even without Pareto efficiency) rests on domain richness. The abstract and theorem statements should explicitly record whether the same three axioms admit additional mechanisms on any proper subdomain; if the proof propagates constraints via richness, a brief tightness discussion or counter-example on a restricted domain would make the scope of the result precise.
minor comments (2)
  1. [Preliminaries] Notation for serial-quota mechanisms (order over agents and quota vector) should be introduced once, with a single running example, before the characterization theorems.
  2. [Implications section] The negative implications for additive valuations (final section) would benefit from a short table listing which fairness notions become incompatible with the three axioms.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive comment on clarifying the scope of the characterization with respect to domain richness. We address the point below and will make the suggested revision.

read point-by-point responses

  1. Referee: [Theorem statements (presumably §3–4)] The central claim (that SP + non-bossiness + neutrality pins down serial-quota mechanisms even without Pareto efficiency) rests on domain richness. The abstract and theorem statements should explicitly record whether the same three axioms admit additional mechanisms on any proper subdomain; if the proof propagates constraints via richness, a brief tightness discussion or counter-example on a restricted domain would make the scope of the result precise.

    Authors: We agree that the proofs rely on domain richness to propagate the constraints from the axioms to force serial-quota mechanisms. The theorems and abstract already specify the domains (lexicographic, all strict ordinal, and cardinal classes containing additive valuations), but we will add an explicit remark in the introduction and immediately following each main theorem (Theorems 1–3) noting that the result is tight to these rich domains: on proper subdomains the three axioms may admit additional mechanisms. A brief tightness paragraph will be included, with a simple counter-example on a highly restricted domain (e.g., two agents and two goods with only a subset of the preference profiles) to illustrate that the richness assumption is necessary for uniqueness. This revision will be made without altering the main claims. revision: yes

Circularity Check

0 steps flagged

No circularity: direct axiomatic characterization from stated assumptions

full rationale

The paper establishes a characterization theorem by proving that strategy-proofness, non-bossiness, and neutrality on rich domains (all strict orders or additive valuations) force serial-quota mechanisms, without Pareto efficiency. This proceeds via explicit domain-richness arguments that propagate local constraints to global form; no step reduces a claimed mechanism to a fitted parameter, renames a known result, or relies on a self-citation chain whose uniqueness theorem is itself unverified. The derivation is self-contained against the listed axioms and domain assumptions, with no equations or citations that make the target equivalent to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The characterization rests on standard axioms of mechanism design (strategy-proofness, non-bossiness, neutrality) plus domain assumptions on preferences; no free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption Preferences are strict ordinal or additive cardinal over subsets of indivisible goods.
    Stated in the abstract as the classes for which the characterization holds.
  • domain assumption The mechanism must satisfy strategy-proofness, non-bossiness, and neutrality on the entire domain.
    These are the three properties used to characterize the serial-quota mechanisms.

pith-pipeline@v0.9.0 · 5705 in / 1317 out tokens · 18092 ms · 2026-05-23T16:47:36.785833+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [1]

    Breaking the 3/4 Barrier fo r Approximate Maximin Share

    Hannaneh Akrami and Jugal Garg. “Breaking the 3/4 Barrier fo r Approximate Maximin Share”. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) . 2024, pp. 74–91

    work page 2024

  2. [2]

    On Truthful Mechanisms for Maximin Share Allocations

    Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. “On Truthful Mechanisms for Maximin Share Allocations”. In: International Joint Conference on Artificial Intelligence (IJCAI). 2016, pp. 31–37. 15When m ≤ n there is a trivial positive result: the n-agent Round Robin mechanism for allocating m ≤ n goods (which is a serial-quota mechanism) is EF...

    work page 2016

  3. [3]

    Allocating Indivisible Goods to Strategic A gents: Pure Nash Equilibria and Fairness

    Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Laz os, Stefano Leonardi, and Rebecca Reiffenh¨ auser. “Allocating Indivisible Goods to Strategic A gents: Pure Nash Equilibria and Fairness”. In: Web and Internet Economics (WINE) . 2021

    work page 2021

  4. [4]

    Fair Division of Indivisible Goods: A Survey

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and A lexandros A. Voudouris. “Fair Division of Indivisible Goods: A Survey”. In: The International Joint Conference on Artificial Intelligence - Survey Track (IJCAI) . July 2022, pp. 5385–5393

    work page 2022

  5. [5]

    Fair division of indivisible go ods: Recent progress and open questions

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Rats ikas, Bo Li, Herv´ e Moulin, Alexandros A. Voudouris, and Xiaowei Wu. “Fair division of indivisible go ods: Recent progress and open questions”. In: Artificial Intelligence 322 (2023), p. 103965

    work page 2023

  6. [6]

    Round-Robin Beyond Additive Agents: Existence andFairness of Approximate Equi- libria

    Georgios Amanatidis, Georgios Birmpas, Philip Lazos, Stefano Leo nardi, and Rebecca Reiff- enh¨ auser. “Round-Robin Beyond Additive Agents: Existence andFairness of Approximate Equi- libria”. In: The ACM Conference on Economics and Computation (ACM-EC) . 2023, pp. 67– 87

    work page 2023

  7. [7]

    Truth- ful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

    Georgios Amanatidis, Georgios Birmpas, George Christodoulou, a nd Evangelos Markakis. “Truth- ful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness”. In: ACM Conference on Economics and Computation (ACM-EC) . 2017, pp. 545–562

    work page 2017

  8. [8]

    Strategyproof and Approxima tely Maxmin Fair Share Allocation of Chores

    Haris Aziz, Bo Li, and Xiaowei Wu. “Strategyproof and Approxima tely Maxmin Fair Share Allocation of Chores”. In: International Joint Conference on Artificial Intelligence (IJCAI). July 2019, pp. 60–66

    work page 2019

  9. [9]

    Algorithmic Fair Allo cation of Indivisible Items: A Survey and New Questions

    Haris Aziz, Bo Li, Herv´ e Moulin, and Xiaowei Wu. “Algorithmic Fair Allo cation of Indivisible Items: A Survey and New Questions”. In: SIGecom Exch. 20.1 (2022), pp. 24–40

    work page 2022

  10. [10]

    Fair Shares: Feasibility, Dominat ion and Incentives

    Moshe Babaioff and Uriel Feige. “Fair Shares: Feasibility, Dominat ion and Incentives”. In: ACM Conference on Economics and Computation (ACM-EC) . 2022

    work page 2022

  11. [11]

    Share-Based Fairness for Arb itrary Entitlements

    Moshe Babaioff and Uriel Feige. “Share-Based Fairness for Arb itrary Entitlements”. In: (2024). arXiv: 2405.14575 [cs.GT] . url: https://arxiv.org/abs/2405.14575

    work page arXiv 2024

  12. [12]

    Fair Division: From cake-cutting to dispute resolution

    Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution . Cambridge University Press, 1996

    work page 1996

  13. [13]

    The Combinatorial Assignment Problem: Approxima te Competitive Equilibrium from Equal Incomes

    Eric Budish. “The Combinatorial Assignment Problem: Approxima te Competitive Equilibrium from Equal Incomes”. In: Journal of Political Economy 119.6 (2011), pp. 1061–1103

    work page 2011

  14. [14]

    Envy-freene ss up to any item with high Nash welfare: The virtue of donating items

    Ioannis Caragiannis, Nick Gravin, and Xin Huang. “Envy-freene ss up to any item with high Nash welfare: The virtue of donating items”. In: The ACM Conference on Economics and Computation (ACM-EC). 2019, pp. 527–545

    work page 2019

  15. [15]

    EF X Exists for Three Agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. “EF X Exists for Three Agents”. In: J. ACM 71.1 (2024), 4:1–4:27

    work page 2024

  16. [16]

    A Little Charity Guarantees Almost Envy-Freeness

    Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, an d Alkmini Sgouritsa. “A Little Charity Guarantees Almost Envy-Freeness”. In: SIAM J. Comput. 50.4 (2021), pp. 1336–1358

    work page 2021

  17. [17]

    Approximat ing Maximin Share Allocations

    Jugal Garg, Peter McGlaughlin, and Setareh Taki. “Approximat ing Maximin Share Allocations”. In: 2nd Symposium on Simplicity in Algorithms (SOSA 2019) . Vol. 69. 2019, 20:1–20:11

    work page 2019

  18. [18]

    Strategy-proof, efficient, and nonbossy quo ta allocations

    John Hatfield. “Strategy-proof, efficient, and nonbossy quo ta allocations”. In: Social Choice and Welfare 33 (Sept. 2009), pp. 505–515

    work page 2009

  19. [19]

    Strategyproof Quota Mechanisms for Multiple Assignment Problems

    Hadi Hosseini and Kate Larson. Strategyproof Quota Mechanisms for Multiple Assignment Pr ob- lems. 2016. url: https://arxiv.org/abs/1507.07064

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  20. [20]

    Fair En ough: Guaranteeing Approx- imate Maximin Shares

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. “Fair En ough: Guaranteeing Approx- imate Maximin Shares”. In: J. ACM 65.2 (2018), 8:1–8:27

    work page 2018

  21. [21]

    On approximately fair allocations of indivisible goods

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Am in Saberi. “On approximately fair allocations of indivisible goods”. In: ACM Conference on Electronic Commerce (ACM-EC) . 2004, pp. 125–131

    work page 2004

  22. [22]

    Strategy-proofness and the strict core in a mar ket with indivisibilities

    Jinpeng Ma. “Strategy-proofness and the strict core in a mar ket with indivisibilities”. In: Int. J. Game Theory 23.1 (Mar. 1994), pp. 75–83

    work page 1994

  23. [23]

    Fair Division and Collective Welfare

    Herv´ e Moulin. Fair Division and Collective Welfare . MIT press, 2004. 24

    work page 2004

  24. [24]

    Strategyproof and Nonbossy Multiple Assignmen ts

    Szilvia P´ apai. “Strategyproof and Nonbossy Multiple Assignmen ts”. In: Journal of Public Eco- nomic Theory 3.3 (2001), pp. 257–271

    work page 2001

  25. [25]

    Strategyproof Assignment by Hierarchical Exc hange

    Szilvia P´ apai. “Strategyproof Assignment by Hierarchical Exc hange”. In: Econometrica 68.6 (2000), pp. 1403–1433

    work page 2000

  26. [26]

    Strategyproof multiple assignment using quotas

    Szilvia P´ apai. “Strategyproof multiple assignment using quotas ”. In: Rev. Econ. Des. 5.1 (Mar. 2000), pp. 91–105

    work page 2000

  27. [27]

    Almost Envy-Freeness w ith General Valuations

    Benjamin Plaut and Tim Roughgarden. “Almost Envy-Freeness w ith General Valuations”. In: SIAM Journal on Discrete Mathematics 34.2 (2020), pp. 1039–1068

    work page 2020

  28. [28]

    On cores and indivisibility

    Lloyd Shapley and Herbert Scarf. “On cores and indivisibility”. In : Journal of Mathematical Economics 1.1 (1974), pp. 23–37

    work page 1974

  29. [29]

    Queue allocation of indivisible goods

    Lars-Gunnar Svensson. “Queue allocation of indivisible goods”. In: Social Choice and Welfare 11.4 (1994), pp. 323–330

    work page 1994

  30. [30]

    Strategy-proof allocation of indivis ible goods

    Lars-Gunnar Svensson. “Strategy-proof allocation of indivis ible goods”. In: Social Choice and Welfare 16 (Sept. 1999), pp. 557–567

    work page 1999

  31. [31]

    Non-bossiness

    William Thomson. “Non-bossiness”. In: Social Choice and Welfare 47.3 (2016), pp. 665–696. 25 A Missing Proofs from Section 3.1 Lemma 2. [Monotonicity] Let f be a truthful and non-bossy allocation mechanism for agents with preferences from a class P ⊆ P Mon ̸= (M) of strict preferences. Then for any pair of valuation profile s (≼1, . . . , ≼n) , (≼′ 1, . . ...

    work page 2016

  32. [32]

    the preferences are identical

    ( ≼ ⃗ e1, . . . , ≼ ⃗ en ) is a push-up of ( ≼, . . . , ≼) for f . 2. ( ≼ ⃗ e1, ≼ ⃗ e2 , ≼ ⃗e′ − 1, 2 ) is a push-up of ( ≼ ⃗ e1 , . . . , ≼ ⃗ en ) for f . We will first show that with both of these claims combined we can prove the claim. Since f is a truthful and non-bossy mechanism, Lemma 2 combined with the above claims implies: f ( ≼ ⃗ e1, ≼ ⃗ e2 , ≼ ⃗...

    work page

  33. [33]

    If x = b then agent 2 picks her single favorite good y from M \ {x} and agent 3 gets all remaining goods M \ {x, y }

    work page

  34. [34]

    The mechanism is truthful since lying can only cause an agent to get a less preferred good when choosing

    If x ̸= b then agent 3 picks her single favorite good y from M \ {x} and agent 2 gets all remaining goods M \ {x, y }. The mechanism is truthful since lying can only cause an agent to get a less preferred good when choosing. The mechanism is also non-bossy since the agents can only alter the overall allocation by altering the good they select at some step...

    work page