Equal Treatment of Equals and Efficiency in Probabilistic Assignments
Pith reviewed 2026-05-21 22:54 UTC · model grok-4.3
The pith
An ETE reassignment turns any probabilistic assignment into one that satisfies equal treatment of equals while preserving rank-minimizing efficiency.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The ETE reassignment of a rank-minimizing assignment remains rank-minimizing efficient. Therefore assignments exist that satisfy both equal treatment of equals and ordinal efficiency. Under general upper bound constraints such assignments can be built in polynomial time by combining the serial dictatorship rule with suitable priority lists and the ETE reassignment step.
What carries the argument
The ETE reassignment procedure, which takes any probabilistic assignment and produces a new one that satisfies equal treatment of equals while attempting to keep the efficiency properties of the original.
If this is right
- Ex-post efficient assignments remain ex-post efficient after ETE reassignment.
- Rank-minimizing efficient assignments remain rank-minimizing efficient after ETE reassignment.
- Ordinal efficiency is not necessarily preserved by the reassignment.
- An assignment satisfying both ETE and ordinal efficiency exists in general.
- Under upper bound constraints the combination of serial dictatorship and ETE reassignment yields an efficient construction.
Where Pith is reading between the lines
- The same reassignment idea may apply to other fairness notions such as envy-freeness in probabilistic settings.
- The method could reduce the computational burden of finding fair and efficient allocations in large-scale systems like course registration or housing lotteries.
- It may connect to mechanism-design questions where both fairness and stochastic dominance efficiency must be satisfied simultaneously.
Load-bearing premise
The extended definition of equal treatment of equals remains well-defined and the reassignment step can always be performed without leaving the support of the original assignment.
What would settle it
A concrete multi-unit instance with upper bounds in which the ETE reassignment of a rank-minimizing assignment fails to remain rank-minimizing efficient.
read the original abstract
This paper studies general multi-unit probabilistic assignment problems involving indivisible objects, with a particular focus on achieving the fairness notion of equal treatment of equals (ETE) and satisfying various efficiency criteria. We extend the definition of ETE so that it accommodates a wide range of constraints and applications. We introduce the ETE reassignment procedure, which transforms any assignment into one that satisfies ETE, and examine whether the efficiency properties satisfied by the original assignment -- namely, ex-post efficiency, ordinal efficiency, and rank-minimizing efficiency -- are preserved under the ETE reassignment. We show that, while the ETE reassignment of an ex-post efficient assignment remains ex-post efficient, it may fail to preserve ordinal efficiency in general settings. However, since the ETE reassignment of a rank-minimizing assignment preserves rank-minimizing efficiency, there must exist an assignment satisfying both ETE and ordinal efficiency. Furthermore, we propose a computationally efficient method for constructing assignments that satisfy both ETE and ordinal efficiency under general upper bound constraints by combining the serial dictatorship rule with appropriately specified priority lists and the ETE reassignment procedure.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies general multi-unit probabilistic assignment problems with indivisible objects and arbitrary constraints. It extends the definition of equal treatment of equals (ETE) to these settings, introduces an ETE reassignment procedure that converts any feasible assignment into an ETE-satisfying one, and analyzes preservation of efficiency properties. The authors establish that ETE reassignment preserves ex-post efficiency but does not always preserve ordinal efficiency; however, it preserves rank-minimizing efficiency. This yields an existence result for assignments satisfying both ETE and ordinal efficiency. They further propose a computationally efficient construction for ETE and ordinal efficiency under general upper-bound constraints by combining serial dictatorship (with suitably chosen priority lists) and the ETE reassignment procedure.
Significance. If the preservation result for rank-minimizing efficiency holds under general constraints, the paper offers a useful contribution to the literature on fair probabilistic assignment mechanisms. The differential preservation findings (ex-post yes, ordinal no, rank-minimizing yes) clarify the relationship between fairness and efficiency notions, and the constructive method via serial dictatorship plus reassignment could support practical implementation in constrained allocation problems such as course assignment or housing lotteries.
major comments (2)
- [§4] §4 (main preservation theorem): The central claim that ETE reassignment preserves rank-minimizing efficiency is load-bearing for the existence result, yet the argument does not explicitly verify that the probability transfers required for equalization leave the total rank cost unchanged when upper bounds bind and restrict the support of the original rank-minimizing assignment. A concrete counterexample or inductive argument addressing binding constraints would strengthen this step.
- [§5] §5 (computational construction): The claim that combining serial dictatorship with ETE reassignment yields a computationally efficient method for general upper-bound constraints rests on the same unverified preservation property; without a formal argument that the reassignment step commutes with the rank-minimization objective under arbitrary feasibility sets, the efficiency guarantee for the output assignment remains conditional.
minor comments (2)
- [§2] §2 (preliminaries): The extended definition of ETE could benefit from an explicit statement of how it reduces to the standard definition when there are no upper-bound constraints.
- [Notation] Notation: The symbol for the reassignment operator is introduced without a dedicated display equation; adding one would improve readability when the operator is applied repeatedly in later sections.
Simulated Author's Rebuttal
We thank the referee for the detailed and constructive report. The comments highlight important aspects of the proof for rank-minimizing efficiency preservation and the computational construction. We address each point below and will make revisions to clarify the arguments where necessary.
read point-by-point responses
-
Referee: [§4] §4 (main preservation theorem): The central claim that ETE reassignment preserves rank-minimizing efficiency is load-bearing for the existence result, yet the argument does not explicitly verify that the probability transfers required for equalization leave the total rank cost unchanged when upper bounds bind and restrict the support of the original rank-minimizing assignment. A concrete counterexample or inductive argument addressing binding constraints would strengthen this step.
Authors: We thank the referee for pointing this out. The ETE reassignment procedure equalizes probabilities by transferring mass between agents who have the same preference ranking over the objects, as per the definition of ETE. Since agents with identical preferences assign the same rank to each object, any such transfer preserves the total rank cost exactly, because the contribution to the sum is rank * probability transferred, and ranks are the same. This invariance holds regardless of whether upper bounds are binding, because the procedure only reassigns within the feasible assignments and the original assignment is assumed to be rank-minimizing within the feasible set. The support restriction due to binding constraints is already accounted for in the original assignment's optimality. To address the concern explicitly, we will revise the proof in §4 to include a dedicated paragraph explaining this rank-invariance under binding constraints, perhaps with a brief inductive step on the number of equalized pairs. revision: partial
-
Referee: [§5] §5 (computational construction): The claim that combining serial dictatorship with ETE reassignment yields a computationally efficient method for general upper-bound constraints rests on the same unverified preservation property; without a formal argument that the reassignment step commutes with the rank-minimization objective under arbitrary feasibility sets, the efficiency guarantee for the output assignment remains conditional.
Authors: We agree that the computational efficiency relies on the preservation property established in §4. Since the serial dictatorship produces a rank-minimizing assignment (as it is a known efficient mechanism in these settings), and the ETE reassignment preserves rank-minimizing efficiency as argued above, the output satisfies both ETE and rank-minimizing efficiency, which by the paper's results implies the desired properties including existence of ETE and ordinally efficient assignments. To strengthen the presentation, we will add a corollary in §5 explicitly stating that the composition preserves the properties under general upper-bound constraints, referencing the clarified proof from §4. This will make the efficiency guarantee unconditional. revision: partial
Circularity Check
No circularity: derivation relies on explicit definitions and proofs of preservation properties
full rationale
The paper extends the ETE definition to handle general constraints, defines the ETE reassignment procedure as a transformation that equalizes treatment, and then proves (rather than assumes) that this procedure preserves rank-minimizing efficiency when started from a rank-minimizing assignment. This directly yields existence of an ETE + ordinal efficient assignment. The serial dictatorship construction is presented as a separate algorithmic method. No step reduces by definition to its own output, no fitted parameters are relabeled as predictions, and no load-bearing claim rests on self-citation chains; the argument is self-contained against the stated axioms and feasibility sets.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The extended definition of ETE accommodates a wide range of constraints and applications in multi-unit probabilistic assignment problems.
Forward citations
Cited by 1 Pith paper
-
A Simple Method for School Choice Lotteries
A polynomial-time method constructs an ex ante stable school-choice lottery with equal treatment of equals by reassigning from a constrained efficient stable matching, yielding a lottery not ordinally dominated by any...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.