Fairness and efficiency for probabilistic allocations with participation constraints

Antonio Miralles; Federico Echenique; Jun Zhang

REVIEW 1 major objections 4 minor 1 cited by

Fairness and efficiency for probabilistic allocations with participation constraints

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that with reservation utilities, fairness and efficiency can coexist if envy is defined as justified envy.

desk verdict Worth engaging with, but the proof of Theorem 1 has a false strict-convexity claim; the fix (squared norm) is easy, so accept with major revision. read the letter →

arxiv 1908.04336 v3 pith:TP3ZCANA submitted 2019-08-12 econ.TH cs.GT

Federico Echenique , Antonio Miralles , Jun Zhang This is my paper · ORCID

classification econ.THcs.GT MSC 91B3291B2691B68

keywords justifiedenvyindividualrationalityParetooptimalitypseudo-marketequilibriumprice-dependentincomesrandomallocationschoolchoiceparticipationconstraints

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that the classic tension between fairness and respect for outside options can be bypassed by changing the fairness standard. Instead of demanding absence of envy, it demands absence of justified envy: Alice may envy Bob, but the envy is unfair only if Bob could take Alice's assignment without falling below his reservation utility. With this standard, the paper proves existence of allocations that are fair, efficient, and individually rational, and in many cases it shows they arise from a competitive market with carefully chosen price-dependent incomes. The result matters because allocation problems with rights, such as school choice, course allocation, and time banks, have no general way to reconcile envy-free fairness with participation constraints; this concept gives a principled resolution.

What carries the argument

The load-bearing construction is a family of price-dependent income functions. For each price vector, each agent's income is the median of three magnitudes: a common income level, the minimum expenditure needed to satiate that agent, and the minimum expenditure needed to reach her reservation utility. This median-income rule keeps total income equal to the value of the objects, guarantees individual rationality, and through Lemma 4 makes any envied agent exactly at her reservation utility, so the envy is unjustified. The existence proof for Theorem 1 instead works on welfare weights and uses the Knaster-Kuratowski-Mazurkiewicz (KKM) lemma: each vertex of the weight simplex corresponds to a weighted utilitarian maximization, and a KKM covering shows that some weights produce an allocation where no one has approximate justified envy.

What would settle it

Construct a two-agent, two-object allocation problem with concave utilities, capacities matching demand, and reservation utilities that admit an individually rational allocation. Compute the set of individually rational and Pareto-optimal allocations; if any such allocation has an agent $i$ with $u_i(x_j)>u_i(x_i)$ and $u_j(x_i)\ge \tilde{u}_j$, or if for some $\varepsilon>0$ no $\varepsilon$-IR, $\varepsilon$-PO, $\varepsilon$-NJE allocation exists, then Theorem 1's first statement fails. Exhaustive search over piecewise-linear concave utilities and reservation levels could settle this directly.

Watch

Extended reading notes

Core claim

The paper establishes that when fairness is defined as the absence of justified envy, defined as envy whose obvious remedy, a pairwise swap, would not violate the envied agent's participation constraint, there is no inherent conflict among fairness, efficiency, and individual rationality. For concave utilities, Theorem 1 gives, for any $\varepsilon>0$, an allocation that is $\varepsilon$-individually rational, $\varepsilon$-Pareto optimal, and free of $\varepsilon$-justified envy, and in the limit an allocation that is exactly individually rational, weakly Pareto optimal, and free of strong justified envy. With linear utilities the limit allocation is fully Pareto optimal. Under additional assumptions, Theorem 2 supports such an allocation as a competitive pseudo-market equilibrium with price-dependent incomes, and Theorem 3 extends the result to allocations subject to quantitative constraints.

Load-bearing premise

For the main theorem, the load-bearing assumptions are that each agent's utility is concave and that at least one allocation meets all reservation utilities; if either fails, this paper does not establish the existence of a fair, efficient, individually rational allocation.

Editorial extensions

If this is right

In any allocation problem with concave utilities and at least one individually rational allocation, approximately fair, efficient, and individually rational allocations exist, so the impossibility results that plague envy-free fairness do not bite for justified envy.
For linear (expected) utilities, exact Pareto optimality is recovered, so random allocation problems with outside options can be solved by market-generated lotteries with the desired properties.
When quantitative constraints such as school composition bounds or minimum course loads are imposed, fairness survives among agents of equal type: constraints do not force justified envy within a type.
The result extends to more general remedies than pairwise swaps: if envy can be justified by a chain of exchanges whose last step respects participation, the same existence theorems hold.
The pseudo-market version gives a concrete normative story: incomes deviate from equal incomes only to the extent required by reservation utilities and satiation, making the allocation implementable by prices rather than by planner's fiat.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: If the pseudo-market equilibrium were implemented algorithmically, the income functions depend only on reservation utilities and satiation levels, making the mechanism transparent about which rights are being protected; the paper does not, however, specify a selection mechanism or prove strategy-proofness.
Inference: The $\varepsilon$ in Theorem 1 is likely not a purely technical artifact: strict concavity of the perturbed objective is used to make the maximizer single-valued, so with merely quasi-concave utilities the same KKM strategy breaks down and a genuinely different argument would be needed.
Inference: In finite random-allocation problems with linear utilities, the equilibrium is a solution of a finite-dimensional fixed-point problem, so one could test numerically whether the median-income construction converges under a tatonnement process; the paper does not supply such an algorithm.
Inference: The common-favorite-object condition in Theorem 2 is restrictive, as the authors themselves note; a natural extension is to test whether it can be relaxed to a condition such as each type of agent having a favorite object, or a favorite object holding only at equilibrium prices.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Let me give you my read on Echenique-Miralles-Zhang, 'Fairness and efficiency for probabilistic allocations with participation constraints.'

The paper is worth your time. The central idea—define fairness as no justified envy, where envy is only justified if the remedy (a swap) does not violate the other agent's participation constraint—is a genuinely useful way to think about unequal reservation utilities. It cleanly separates justified from unjustified envy and yields nice implications for equal treatment of equals. The paper then shows (Theorem 1) that under concavity one can get ε-IR, ε-PO, and ε-NJE, and in the limit IR, wPO, and no strong justified envy. The competitive equilibrium foundation (Theorem 2) with price-dependent incomes is a clever construction that generalizes Hylland-Zeckhauser, and the extensions to quantitative constraints (Theorem 3) and exchange-based remedies (Theorem 4) are natural and broaden the applicability.

Now the soft spot. The proof of Theorem 1 in Section 8 asserts that the penalty Σ||x_i − 1|| is strictly convex and therefore the perturbed utilitarian objective is strictly concave, making φ(λ) singleton-valued. That's false: the Euclidean norm is convex but not strictly convex. The stress-test example is correct—with two identical linear preferences you can get a continuum of maximizers for balanced weights. This breaks the KKM argument as written, because Λ_i is defined in terms of the function φ, and the contradiction in Lemma 2 requires that any alternative allocation strictly improve the objective. The gap is real, and it sits in the central existence theorem.

The good news is that the fix is obvious and does not change the architecture: replace the penalty by Σ||x_i − 1||^2, which is strictly convex. Then the strict concavity claim holds, and Lemmas 1–2 and the KKM application go through. I checked the surrounding steps; nothing else seems to depend on the specific form of the penalty. So I expect the theorem is true, but the written proof is not correct as it stands.

Other quibbles: the common-favorite-object condition in Theorem 2 is restrictive, but the authors say so. There is no incentive-compatibility analysis, which they acknowledge. These are not dealbreakers.

My recommendation: send it to a serious referee, but ask for a revision that fixes the proof of Theorem 1. The conceptual contribution is solid, and the paper is clearly written. I would bring it to our reading group to discuss the concept and the repair.

Serious thinker: yes, clearly. Would I cite it? Probably yes for the notion of justified envy, once the proof is patched.

Referee Report

1 major / 4 minor

Summary. The paper studies allocation problems with participation constraints (reservation utilities) and proposes a fairness notion called "no justified envy" (NJE), which rules out envy only when a pairwise switch would not violate the envied agent's participation constraint. The main results are: Theorem 1, which asserts existence of (approximate) efficient, individually rational, and NJE allocations under concave utilities; Theorem 2, which provides a competitive-equilibrium foundation with price-dependent income functions under additional conditions; Theorem 3, which extends the existence result to constrained allocation environments; and Theorem 4, which generalizes the fairness notion to envy remedied by exchanges. The paper also discusses applications to school choice. The central technical tool is a KKM-based proof using a perturbed weighted utilitarian objective.

Significance. The notion of justified envy is a natural and important adaptation of envy-freeness to environments with different outside options or property rights. If the main existence results hold, the paper resolves a real tension between fairness, efficiency, and individual rationality, and the market-equilibrium foundation in Theorem 2 gives a credible bridge to the pseudo-market literature. The extension to constraints (Theorem 3) and exchange-based remedies (Theorem 4) broadens applicability to school choice and course allocation. The proofs are detailed and mostly standard (KKM lemma, Kakutani fixed-point theorem, expenditure functions). However, the proof of the central existence theorem contains a specific technical error in the claimed strict convexity of the penalty term, which is repairable at modest cost. With that repair, the contribution would be solid and likely to influence subsequent work on fair allocation with participation constraints.

major comments (1)

[Section 8, definition of φ(λ) and the subsequent KKM argument] The proof of Theorem 3 (and hence Theorem 1, parts 1 and 2) asserts that the objective Σ_i λ_i u_i(x_i) − δ Σ_i ‖x_i − 1‖ is strictly concave because Σ_i ‖x_i − 1‖ is “continuous and strictly convex.” This assertion is false: the Euclidean norm is convex but not strictly convex (for example, on the segment between (1,0) and (2,0), the norm is affine). Consequently, φ(λ) need not be singleton-valued, and the subsequent construction of the KKM sets Λ_i, which treats φ as a continuous single-valued function, is not justified as written. A concrete counterexample is given by two agents, two goods, Q=(6,2), c_1=c_2=5, u_1(x)=u_2(x)=x_1+x_2, and reservation utilities low enough that the relevant allocations are ε-IR; for λ=(1/2,1/2), both x=((3,1),(3,1)) and z=((2,1),(4,1)) attain the same objective value, and so does every convex combination, so φ(λ) is the whole segment. The issue is repairable: replace the penalty with Σ_i ‖x_i − 1‖^2, which is strictly convex and invariant under permutations of agents’ bundles, and adjust the choice of δ so that δ max Σ_i ‖x_i − 1‖^2 < ε. The rest of the proof, including the ε-PO bound and the cycle argument in Lemma 2, goes through unchanged. This fix affects the proofs of Theorem 1(1), Theorem 1(2), Theorem 3, and the Theorem 4 extension, and should be made explicitly.

minor comments (4)

[Section 9.2, definition of ¯π] In the definition of ¯π(x,p) = argmax { p · (Σ_i x_i − Q) : p ∈ Δ^L }, the use of the same symbol p inside the set as in the argument is confusing; the maximization should be over a separate variable p′ in Δ^L.
[Section 9.2, quasi-equilibrium proof] The sentence “since preferences are monotonic, it is wlog to assume that Σ_i x_i^* − Q = 0 by consuming the remaining units of underdemanded objects for free” is informal; the argument would benefit from an explicit construction showing that free disposal preserves the quasi-equilibrium conditions.
[Section 8, statement of δ bound] If the squared norm is adopted as suggested, the bound should be written as δ max_{x∈A^*} Σ_i ‖x_i − 1‖^2 < ε, and the accompanying text should be updated accordingly.
[Section 3.6 and Section 4] The terminology “ε-NJE is stronger than NJE” is correct but can be a source of confusion; a brief intuitive explanation would help the reader see why allowing slack in the participation constraint makes the no-justified-envy condition more demanding.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the existence and efficiency results are derived from stated assumptions by self-contained arguments.

full rationale

The paper's main results are proved from explicit assumptions using standard tools, not by assuming the desired conclusions. Theorem 1 defines φ(λ) as the argmax of a perturbed weighted utilitarian objective over ε-individually rational allocations, then defines Λ_i as the set of welfare weights at which agent i has no ε-justified envy at φ(λ); Lemmas 1 and 2 prove that the Λ_i form a KKM covering, and the intersection yields weights whose φ-allocation has ε-IR, ε-PO, and ε-NJE. The ε-PO bound follows from the construction's explicit choice of δ with δ·max Σ||x_i−1|| < ε, while IR and NJE are checked directly from the definitions of A* and the covering argument. Theorem 2 constructs price-dependent incomes as medians of a common income level, the reservation expenditure ei(ũ_i,p), and the satiation expenditure ei(v_i,p); quasi-equilibrium existence is established independently via Kakutani's fixed point theorem, and IR, PO, and NJE are then derived as consequences of the income construction, e.g. through Lemma 4 and expenditure-function reasoning. The self-citations, such as Echenique–Miralles–Zhang (2019), are related-work references and are not load-bearing for the proofs. The possible strict-concavity issue in the φ(λ) penalty noted in the reader's take is a mathematical correctness concern, not a circularity, and does not affect this score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard domain assumptions about preferences, reservation utilities, and feasibility. No fitted parameters or invented physical entities are introduced. The main technical novelty, price-dependent income functions, is constructed from primitives rather than postulated.

assumptions (5)

domain assumption Reservation utilities are such that an IR allocation exists.
Section 3.4 states this assumption explicitly. It is necessary for the central claim, since otherwise no individually rational allocation exists.
domain assumption Utility functions are continuous and monotone on closed convex consumption spaces.
Section 3.2 defines the model with these assumptions; they are used throughout the proofs of Theorems 1, 2, and 3.
domain assumption For Theorem 1, utility functions are concave; for Theorem 2, they are quasi-concave with one of three additional conditions.
Theorem 1 assumes concavity; Theorem 2 assumes quasi-concavity plus at least one of: large consumption spaces, Inada property with reservation above zero, or common favorite object with strictly positive IR allocation. These assumptions are load-bearing for the proofs.
domain assumption No overall excess supply: sum of capacities q_l is at most sum of individual maxima c_i.
Assumed in Section 3.2. It guarantees feasibility of allocations and is used in the proof that markets clear in Theorem 2.
domain assumption The constraint set AC is closed and convex, and the underlying constraints satisfy the Budish-Che-Kojima-Milgrom condition for randomized feasibility.
Section 5.1 introduces AC and states this implicit assumption, which is used for the interpretation of feasible randomized allocations in Theorem 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fairness and efficiency for probabilistic allocations with participation constraints." pith.science (2026). https://pith.science/paper/TP3ZCANA

@misc{pith2026190804336,
  author       = {Pith},
  title        = {Pith review of: Fairness and efficiency for probabilistic allocations with participation constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TP3ZCANA}},
  note         = {Machine review of arXiv:1908.04336}
}

read the original abstract

We propose a notion of fairness for allocation problems in which different agents may have different reservation utilities, stemming from different outside options, or property rights. Fairness is usually understood as the absence of envy, but this can be incompatible with reservation utilities. It is possible that Alice's envy of Bob's assignment cannot be remedied without violating Bob's participation constraint. Instead, we seek to rule out {\em justified envy}, defined as envy for which a remedy would not violate any agent's participation constraint. We show that fairness, meaning the absence of justified envy, can be achieved together with efficiency and individual rationality. We introduce a competitive equilibrium approach with price-dependent incomes obtaining the desired properties.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Matching Markets with Chores
cs.GT 2024-12 conditional novelty 5.0 of 10

HZ pricing equilibria and earnings equilibria are equivalent, so the Hylland-Zeckhauser framework carries over from goods to chores and mixed manna.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages · cited by 1 Pith paper

[1]

Constrained Pseudo-market Equilibrium

Abdulkadiro˘glu, A., P. A. Pathak, and A. E. Roth (2005): “The New York City High School Match,” The American Economic Review , 95(2), 364–367. Abdulkadiro˘glu, A., P. A. Pathak, A. E. Roth, and T. S ¨onmez (2005): “The Boston public school match,” American Economic Review , pp. 368–371. F AIRNESS AND EFFICIENCY 33 Abdulkadiro˘glu, A., and T. S ¨onmez (20...

work page Pith review arXiv 2005
[4]

Prices and eﬃcient assignments without transfers,

Oxford university press New York. Miralles, A., and M. Pycia (2014): “Prices and eﬃcient assignments without transfers,” Available at SSRN. Pathak, P. A., and T. S ¨onmez (2013): “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulat ion,” The American Economic Review , 103(1), 80–106. Schmeidler, D., an...

work page 2014
[91]

A certain zero-sum two-person game equivalent to the optimal assignment problem,

Von Neumann, J. (1953): “A certain zero-sum two-person game equivalent to the optimal assignment problem,” Contributions to the Theory of Games , 2, 5–12. Yılmaz, ¨O. (2010): “The probabilistic serial mechanism with private endowment s,” Games and Economic Behavior , 69(2), 475–491. Yu, J., and J. Zhang (2019): “Fractional Top Trading Cycle,” working pape...

work page 1953
[99]

Stability concepts in matching under distributional const raints,

(2017): “Stability concepts in matching under distributional const raints,” Journal of Economic Theory , 168, 107–142. (2019): “Fair matching under constraints: Theory and application s,” . Kojima, F. (2012): “School choice: Impossibilities for aﬃrmative action,” Games and Economic Behavior , 75(2), 685 –

work page 2017
[637]

Equity, envy, and eﬃciency,

V arian, H. R. (1974): “Equity, envy, and eﬃciency,” Journal of Economic Theory , 9(1), 63 –

work page 1974
[693]

Mas-Colell, A., M. D. Whinston, J. R. Green, et al. (1995): Microeco- nomic theory, vol

work page 1995

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Constrained Pseudo-market Equilibrium

Abdulkadiro˘glu, A., P. A. Pathak, and A. E. Roth (2005): “The New York City High School Match,” The American Economic Review , 95(2), 364–367. Abdulkadiro˘glu, A., P. A. Pathak, A. E. Roth, and T. S ¨onmez (2005): “The Boston public school match,” American Economic Review , pp. 368–371. F AIRNESS AND EFFICIENCY 33 Abdulkadiro˘glu, A., and T. S ¨onmez (20...

work page Pith review arXiv 2005

[2] [4]

Prices and eﬃcient assignments without transfers,

Oxford university press New York. Miralles, A., and M. Pycia (2014): “Prices and eﬃcient assignments without transfers,” Available at SSRN. Pathak, P. A., and T. S ¨onmez (2013): “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulat ion,” The American Economic Review , 103(1), 80–106. Schmeidler, D., an...

work page 2014

[3] [91]

A certain zero-sum two-person game equivalent to the optimal assignment problem,

Von Neumann, J. (1953): “A certain zero-sum two-person game equivalent to the optimal assignment problem,” Contributions to the Theory of Games , 2, 5–12. Yılmaz, ¨O. (2010): “The probabilistic serial mechanism with private endowment s,” Games and Economic Behavior , 69(2), 475–491. Yu, J., and J. Zhang (2019): “Fractional Top Trading Cycle,” working pape...

work page 1953

[4] [99]

Stability concepts in matching under distributional const raints,

(2017): “Stability concepts in matching under distributional const raints,” Journal of Economic Theory , 168, 107–142. (2019): “Fair matching under constraints: Theory and application s,” . Kojima, F. (2012): “School choice: Impossibilities for aﬃrmative action,” Games and Economic Behavior , 75(2), 685 –

work page 2017

[5] [637]

Equity, envy, and eﬃciency,

V arian, H. R. (1974): “Equity, envy, and eﬃciency,” Journal of Economic Theory , 9(1), 63 –

work page 1974

[6] [693]

Mas-Colell, A., M. D. Whinston, J. R. Green, et al. (1995): Microeco- nomic theory, vol

work page 1995