pith. sign in

arxiv: 2606.18574 · v1 · pith:KKIULCHCnew · submitted 2026-06-17 · 💰 econ.TH · cs.GT

Stable and Fair Random Allocations in a Two-Sided Discrete-Concave Market

Kenzo Imamura , Yasushi Kawase This is my paper

Pith reviewed 2026-06-26 19:11 UTC · model grok-4.3

classification 💰 econ.TH cs.GT
keywords discrete concave valuationsex ante stabilityfairnessrandom allocationstwo-sided marketsAlkan-Gale stabilitymatroid constraintsmatching with contracts
0
0 comments X

The pith

When agents have discrete concave valuations, ex ante stable and fair random allocations exist in two-sided markets.

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

The paper establishes that in two-sided markets where agents have discrete concave valuations, there exists a fractional allocation that is stable and fair from an ex ante perspective. This matters because standard random tie-breaking procedures often fail to deliver both properties simultaneously. The authors characterize such allocations exactly as Alkan-Gale stable outcomes generated by choice functions from concave closures paired with a symmetric strictly convex tie-breaking rule. They further show that any ex ante stable fractional allocation decomposes into a lottery over stable deterministic allocations and extend the existence result to an ordinal setting under matroid constraints.

Core claim

When agents have discrete concave (M♮-concave) valuations, there exists an ex ante stable and fair allocation. Ex ante stable and fair fractional allocations are exactly characterized as Alkan-Gale stable outcomes under choice functions induced from concave closures together with a symmetric strictly convex tie-breaking rule. Any ex ante stable fractional allocation can be decomposed into a lottery over stable deterministic allocations using a generalization of the Birkhoff-von Neumann theorem. In an ordinal framework with matroid constraints, an ex ante stable and fair fractional allocation also exists.

What carries the argument

Choice functions induced from concave closures of M♮-concave valuations, paired with a symmetric strictly convex tie-breaking rule, that yield Alkan-Gale stable outcomes.

If this is right

  • Any ex ante stable fractional allocation decomposes into a lottery over stable deterministic allocations.
  • Ex ante stable and fair fractional allocations exist in the ordinal preferences setting under matroid constraints in the matching-with-contracts model.
  • The framework covers one-to-many random allocation with responsive choice correspondences and controlled school choice with lotteries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Algorithms developed for Alkan-Gale stable outcomes could be adapted to compute the ex ante stable fair fractional allocations directly.
  • The decomposition result implies that randomization preserves stability by mixing only over already-stable deterministic assignments.
  • The matroid-constraint formulation may allow similar existence results in other constrained matching environments beyond the paper's examples.

Load-bearing premise

Valuations must be discrete concave so that choice functions from their concave closures, together with the symmetric strictly convex tie-breaking rule, produce the required stability characterization.

What would settle it

A concrete two-sided market with M♮-concave valuations in which no ex ante stable and fair fractional allocation exists would falsify the existence claim.

read the original abstract

Random allocations are widely used to handle ties and indifferences in two-sided environments. In such environments, commonly used procedures such as random tie-breaking may fail to ensure stability and fairness from an ex ante perspective. We show that when agents have discrete concave (M$^\natural$-concave) valuations, there exists an ex ante stable and fair allocation. To establish this result, we relate our framework to the model of stability introduced by Alkan and Gale. In particular, we show that ex ante stable and fair fractional allocations are exactly characterized as Alkan--Gale stable outcomes under choice functions induced from concave closures together with a symmetric strictly convex tie-breaking rule. We further prove that any ex ante stable fractional allocation can be decomposed into a lottery over stable deterministic allocations, using a generalization of the Birkhoff--von Neumann theorem. Finally, we study a setting that does not rely on cardinal valuations and instead assumes ordinal preferences. Within this ordinal framework, we establish the existence of an ex ante stable and fair fractional allocation. This setting is formulated within the matching-with-contracts framework under matroid constraints. The resulting class includes existing models, such as one-to-many random allocation with responsive choice correspondences, and captures a wide range of applications, including controlled school choice with lotteries.

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

0 major / 2 minor

Summary. The paper claims that when agents have discrete concave (M♮-concave) valuations in a two-sided market, there exists an ex ante stable and fair fractional allocation. Ex ante stable and fair fractional allocations are characterized exactly as Alkan-Gale stable outcomes under choice functions induced from concave closures together with a symmetric strictly convex tie-breaking rule. Any ex ante stable fractional allocation decomposes into a lottery over stable deterministic allocations via a generalized Birkhoff-von Neumann theorem. The paper also establishes existence of an ex ante stable and fair fractional allocation in an ordinal preference setting formulated as matching with contracts under matroid constraints, which includes responsive one-to-many allocation and controlled school choice with lotteries.

Significance. If the results hold, the work provides a clean extension of stability concepts to random allocations in discrete-concave markets, with direct applicability to school choice and other assignment problems that use lotteries. The explicit linkage to Alkan-Gale stability via concave closures and the decomposition result are technically useful; the matroid formulation broadens the ordinal case beyond responsive preferences. Credit is due for scoping the cardinal results precisely to M♮-concave valuations and for avoiding circularity by building on established choice-function and matroid frameworks rather than introducing ad-hoc fitted quantities.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'choice functions induced from concave closures' is introduced without a one-sentence gloss or forward reference to the relevant definition or section; readers outside the immediate subfield would benefit from a brief clarification here.
  2. [Abstract] The abstract states that the ordinal result 'captures a wide range of applications, including controlled school choice with lotteries,' but does not indicate whether the matroid constraint is shown to be tight or whether counter-examples exist outside the matroid class; a short remark on the boundary of the result would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary, recognition of the paper's significance, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation chain establishes existence of ex ante stable and fair allocations under M♮-concave valuations by relating the framework to Alkan-Gale stability via choice functions from concave closures plus a symmetric strictly convex tie-breaker, then applies a generalized Birkhoff-von Neumann theorem for the decomposition. These steps rest on external prior results (Alkan-Gale, matroid theory, Birkhoff-von Neumann) and the stated valuation assumption rather than reducing to self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations. The ordinal/matroid extension is presented as a separate weaker case. No quoted step equates a claimed output to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The results rest on the structural assumption of discrete concavity (M♮-concave valuations) and matroid constraints, plus standard mathematical results such as a generalized Birkhoff-von Neumann theorem; no free parameters or invented entities are introduced.

axioms (3)
  • standard math A generalization of the Birkhoff-von Neumann theorem applies to decompose ex ante stable fractional allocations into lotteries over stable deterministic allocations
    Invoked to establish the lottery decomposition result.
  • domain assumption Choice functions induced from concave closures of M♮-concave valuations together with a symmetric strictly convex tie-breaking rule induce Alkan-Gale stable outcomes
    Central modeling choice that equates ex ante stability and fairness to Alkan-Gale stability.
  • domain assumption Matroid constraints are compatible with the matching-with-contracts framework for the ordinal existence result
    Required for the ordinal-preference extension covering responsive choice and controlled school choice.

pith-pipeline@v0.9.1-grok · 5759 in / 1599 out tokens · 35895 ms · 2026-06-26T19:11:34.650659+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

48 extracted references · 6 canonical work pages

  1. [1]

    25 Atila Abdulkadiroğlu and Tayfun Sönmez

    Strategy-proofness versus ef- ficiency in matching with indifferences: Redesigning the NYC high school match.American Economic Review99, 5 (2009), 1954–1978. 25 Atila Abdulkadiroğlu and Tayfun Sönmez

    2009

  2. [2]

    American Economic Review93, 3 (2003), 729–747

    School choice: A mechanism design approach. American Economic Review93, 3 (2003), 729–747. Mark Aizerman and Andrew Malishevski

    2003

  3. [3]

    General theory of best variants choice: Some aspects.IEEE Trans. Automat. Control26, 5 (1981), 1030–1040. Ahmet Alkan and David Gale

    1981

  4. [4]

    Orhan Aygün and Inácio Bó

    Stable schedule matching under revealed preference.Journal of Economic Theory112, 2 (2003), 289–306. Orhan Aygün and Inácio Bó

    2003

  5. [5]

    Haris Aziz and Florian Brandl

    College admission with multidimensional privileges: The Brazil- ian affirmative action case.American Economic Journal: Microeconomics13, 3 (2021), 1–28. Haris Aziz and Florian Brandl

    2021

  6. [6]

    KeisukeBando, KenzoImamura, andYasushiKawase.2025

    The vigilant eating rule: A general approach for probabilistic economic design with constraints.Games and Economic Behavior135 (2022), 168–187. KeisukeBando, KenzoImamura, andYasushiKawase.2025. PropertiesofPath-IndependentChoice Correspondences and Their Applications to Efficient and Stable Matchings. InProceedings of the 26th ACM Conference on Economics...

    2022

  7. [7]

    Impossibility results for weak strategy-proofness and respect for improvements in random assignment with priorities.Economics Letters257 (2025), 112700.https://doi.org/10.1016/j.econlet.2025.112700 Garrett Birkhoff

    work page doi:10.1016/j.econlet.2025.112700 2025

  8. [8]

    Serie A5 (1946), 147–151

    Three observations on linear algebra.Revista de la Universidad Nacional de Tucumán. Serie A5 (1946), 147–151. Anna Bogomolnaia and Hervé Moulin

    1946

  9. [9]

    Journal of Economic Theory100, 2 (2001), 295–328

    A new solution to the random assignment problem. Journal of Economic Theory100, 2 (2001), 295–328. Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom

    2001

  10. [10]

    Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos, and Rohit Vaish

    Designing random allocation mechanisms: Theory and applications.American Economic Review103, 2 (2013), 585–623. Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos, and Rohit Vaish

    2013

  11. [11]

    InProceedings of the 2019 ACM Conference on Economics and Computa- tion

    Stable fractional matchings. InProceedings of the 2019 ACM Conference on Economics and Computa- tion. Association for Computing Machinery, New York, NY, USA, 21–39. Benjamin Cookson and Nisarg Shah

    2019

  12. [12]

    InProceedings of the 26th ACM Conference on Economics and Computation (EC ’25)

    Fairly Stable Two-Sided Matching with Indifferences. InProceedings of the 26th ACM Conference on Economics and Computation (EC ’25). Associa- tion for Computing Machinery, New York, NY, USA, 1130–1130.https://doi.org/10.1145/ 3736252.3742675 Bo Cowgill and Rembrand Koning. 2018.Matching Markets for Googlers. Harvard Business School Case 718-487. Harvard B...

    arXiv 2018

  13. [13]

    Jack Edmonds

    Constrained pseudo-market equilib- rium.American Economic Review111, 11 (2021), 3699–3732. Jack Edmonds

    2021

  14. [14]

    Jack Edmonds

    Maximum matching and a polyhedron with 0,1-vertices.Journal of Research of the National Bureau of Standards Section B69B, 1–2 (1965), 125–130. Jack Edmonds

    1965

  15. [15]

    Matroids and the Greedy Algorithm.Mathematical Programming1, 1 (1971), 127–136.https://doi.org/10.1007/BF01584082 Akinobu Eguchi, Satoru Fujishige, and Akihisa Tamura

    work page doi:10.1007/bf01584082 1971

  16. [16]

    Aytek Erdil

    School choice with controlled choice constraints: Hard bounds versus soft bounds.Journal of Economic Theory 153 (2014), 648–683. Aytek Erdil

    2014

  17. [17]

    Aytek Erdil and Haluk Ergin

    Strategy-proof stochastic assignment.Journal of Economic Theory151 (2014), 146–162. Aytek Erdil and Haluk Ergin

    2014

  18. [18]

    Aytek Erdil and Taro Kumano

    What’s the matter with tie-breaking? Improving efficiency in school choice.American Economic Review98, 3 (2008), 669–689. Aytek Erdil and Taro Kumano

    2008

  19. [19]

    Tamás Fleiner

    Efficiency and stability under substitutable priorities with ties.Journal of Economic Theory184 (2019), 104950. Tamás Fleiner

    2019

  20. [20]

    InInternational Conference on Integer Programming and Combinatorial Optimization (Lecture Notes in Com- puter Science, Vol

    A matroid generalization of the stable matching polytope. InInternational Conference on Integer Programming and Combinatorial Optimization (Lecture Notes in Com- puter Science, Vol. 2081). Springer, Springer-Verlag, Berlin, 105–114. András Frank

    2081

  21. [21]

    Satoru Fujishige

    Generalized polymatroids and submodular flows.Mathemat- ical Programming42, 1 (1988), 489–563. Satoru Fujishige

    1988

  22. [22]

    Satoru Fujishige

    Lexicographically optimal base of a polymatroid with respect to a weight vector.Mathematics of Operations Research5, 2 (1980), 186–196. Satoru Fujishige. 2005.Submodular Functions and Optimization(2 ed.). Annals of Discrete Math- ematics, Vol

    1980

  23. [23]

    The Random Assignment Problem with Submodular Constraints on Goods.ACM Transactions on Economics and Computation6, 1 (2018), 1–28.https://doi.org/10.1145/3175496 Satoru Fujishige and Akihisa Tamura

    work page doi:10.1145/3175496 2018

  24. [24]

    Satoru Fujishige and Akihisa Tamura

    A general two-sided matching market with discrete concave utility functions.Discrete Applied Mathematics154, 6 (2006), 950–970. Satoru Fujishige and Akihisa Tamura

    2006

  25. [25]

    A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis.Mathematics of Operations Research32, 1 (2007), 136–155.https://doi.org/10.1287/moor.1070.0227 Satoru Fujishige and Zaifu Yang

    work page doi:10.1287/moor.1070.0227 2007

  26. [26]

    Mathematics of Operations Research28, 3 (2003), 463–469

    A note on Kelso and Crawford’s gross substitutes condition. Mathematics of Operations Research28, 3 (2003), 463–469. Martin Grotschel, Laszlo Lovasz, and Alexander Schrijver. 1988.Geometric Algorithms and Com- binatorial Optimization. Springer, Berlin, Heidelberg. 27 Isa E. Hafalir, M. Bumin Yenmez, and Muhammed A. Yildirim

    2003

  27. [27]

    Xiang Han

    Effective affirmative action in school choice.Theoretical Economics8, 2 (2013), 325–363. Xiang Han

    2013

  28. [28]

    Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan

    A theory of fair random allocation under priorities.Theoretical Economics19, 3 (2024), 1185–1221. Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan

    2024

  29. [29]

    Aanund Hylland and Richard Zeckhauser

    A pseudo-market approach to allocation with priorities.American Economic Journal: Microeconomics10, 3 (2018), 272–314. Aanund Hylland and Richard Zeckhauser

    2018

  30. [30]

    Journal of Political Economy87, 2 (1979), 293–314

    The efficient allocation of individuals to positions. Journal of Political Economy87, 2 (1979), 293–314. Kenzo Imamura and Yasushi Kawase

    1979

  31. [31]

    Karzanov

    Efficient and Strategy-proof Mechanism under General Constraints.Theoretical Economics20, 2 (2025), 481–509.https://doi.org/10.3982/TE6039 Alexander V. Karzanov

    work page doi:10.3982/te6039 2025

  32. [32]

    Discrete Applied Mathematics358 (2024), 112–135.https://doi.org/10.1016/j.dam.2024

    On stable assignments generated by choice functions of mixed type. Discrete Applied Mathematics358 (2024), 112–135.https://doi.org/10.1016/j.dam.2024. 06.037 Akshay-Kumar Katta and Jay Sethuraman

    work page doi:10.1016/j.dam.2024 2024

  33. [33]

    Yasushi Kawase, Hanna Sumita, and Yu Yokoi

    A solution to the random assignment problem on the full preference domain.Journal of Economic Theory131, 1 (2006), 231–250. Yasushi Kawase, Hanna Sumita, and Yu Yokoi

    2006

  34. [34]

    Onur Kesten and M

    Job matching, coalition formation, and gross substitutes.Econometrica50, 6 (1982), 1483–1504. Onur Kesten and M. Utku Ünver

    1982

  35. [35]

    Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo

    A theory of school-choice lotteries.Theoretical Economics 10, 2 (2015), 543–595. Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo

    2015

  36. [36]

    Kazuo Murota

    Designing matching mechanisms under constraints: An approach from discrete convex analysis.Journal of Economic Theory176 (2018), 803–833. Kazuo Murota. 2003.Discrete Convex Analysis. SIAM, Philadelphia. Kazuo Murota

    2018

  37. [37]

    Kazuo Murota and Akiyoshi Shioura

    Discrete Convex Analysis: A Tool for Economics and Game Theory.Journal of Mechanism and Institution Design1, 1 (2016), 151–273. Kazuo Murota and Akiyoshi Shioura

    2016

  38. [38]

    Kazuo Murota and Akiyoshi Shioura

    M-convex function on generalized polymatroid.Math- ematics of Operations Research24, 1 (1999), 95–105. Kazuo Murota and Akiyoshi Shioura

    1999

  39. [39]

    Kazuo Murota and Yu Yokoi

    Extension of M-Convexity and L-Convexity to Poly- hedral Convex Functions.Advances in Applied Mathematics25, 4 (2000), 352–427. Kazuo Murota and Yu Yokoi

    2000

  40. [40]

    Thành Nguyen, Alexander Teytelboym, and Shai Vardi

    On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market.Mathematics of Operations Research40, 2 (2015), 460–473. Thành Nguyen, Alexander Teytelboym, and Shai Vardi

    2015

  41. [41]

    arXiv:2509.13198 [econ.TH] 28 Charles R

    Efficiency, Envy, and Incentives in Combinatorial Assignment. arXiv:2509.13198 [econ.TH] 28 Charles R. Plott

    arXiv

  42. [42]

    Path Independence, Rationality, and Social Choice.Econometrica41 (1973), 1075–1091. Alvin E. Roth

    1973

  43. [43]

    The evolution of the labor market for medical interns and residents: a case study in game theory.Journal of Political Economy92, 6 (1984), 991–1016. Alvin E. Roth, Uriel G. Rothblum, and John H. Vande Vate

    1984

  44. [44]

    Stable matchings, optimal assignments, and linear programming.Mathematics of Operations Research18, 4 (1993), 803–

    1993

  45. [45]

    2003.Combinatorial Optimization: Polyhedra and Efficiency

    Alexander Schrijver. 2003.Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Vol

    2003

  46. [46]

    JohnvonNeumann.1953

    Affirmative action in India via vertical, horizontal, and overlapping reservations.Econometrica90, 3 (2022), 1143–1176. JohnvonNeumann.1953. Acertainzero-sumtwo-persongameequivalenttotheoptimalassignment problem. InContributions to the Theory of Games, Volume II. Annals of Mathematics Studies, Vol

    2022

  47. [47]

    A Proofs for Section 7 (Acknowledgment) B Examples for Applications This appendix provides two examples from the applications section

    Random assignment under weak preferences.Games and Economic Behavior 66, 1 (2009), 546–558. A Proofs for Section 7 (Acknowledgment) B Examples for Applications This appendix provides two examples from the applications section. Example B.1.LetI={i1,i 2,i 3}andJ={s}withqs =

    2009

  48. [48]

    Therefore,(i1,s 1)blocksx ′

    Replacingi 4 withi 1 keeps one typet2 student at s1 and respects the reserve. Therefore,(i1,s 1)blocksx ′. The projectionπalone does not determine this decomposition or the reserve usage behind it. C Incentive Properties We discuss strategy-proofness, an incentive requirement. As is standard in the literature, we focus on the incentives of unit-demand age...

    2015