| paper | Fair and Truthful Mechanisms for Dichotomous Valuations |
| authors | Moshe Babaioff, T. Ezra, U. Feige |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
MRFpolytime
Given finite agent types \(T\) with rational masses \(\mu_t\), succinct reported matroid rank functions \(r_t\) on \(m\) item categories, and rational per-capita supplies \(b_j\), compute masses \(x_{t,S}\) assigned to integral independent bundles \(S\subseteq M\), satisfying \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S\ni j}x_{t,S}\le b_j\), whose induced utility distribution Lorenz-dominates every feasible assignment; a priority refinement may select among equivalent allocations.
A high-multiplicity course- or service-allocation market in which finite types \(t\) carry masses \(\mu_t\), each type has a matroid-rank valuation \(r_t\), item categories have per-capita supplies \(b_j\), and \(x_{t,S}\) assigns mass to integral independent bundles; the objective is a Lorenz-dominating utility distribution.
The variables \(x_{t,S}\) forget named-agent priorities and the report-deviation structure used by faithfulness, strong faithfulness, and monotonicity, so they do not implement the paper's full truthful direct mechanism.
fatal: False
The mirror covers polynomial-time computation of a Lorenz-dominating allocation for succinct MRF reports in a recurring multi-unit market. It does not establish transfer of dominant-strategy truthfulness, priority-sensitive tie-breaking, stochastic envy-freeness, or the other fairness guarantees to a nonatomic mechanism.
My strongest honest case is a Class A mirror for the paper’s computational core: implementing the Prioritized Egalitarian mechanism in a high-multiplicity allocation market. The paper contains no named hardness result, so this cannot be a hardness-dissolution argument; it is an argument that the paper’s polynomial-time MRF allocation result has a natural continuous-population form.
My lead anchor is the restatable theorem labelled MRFpolytime and referenced in the excerpt as thm:MRF-poly-time—the pasted TeX suppresses its auto-generated numeral. It is proved in this paper. Its full content is: if agents have matroid-rank-function valuations with succinct representations, where value queries can be answered in polynomial time, then the prioritized egalitarian mechanism can be implemented in polynomial time. The mechanism receives reported MRFs, replaces illegal reports by the zero valuation, and computes a non-redundant Lorenz-dominating allocation respecting a fixed priority order.
The continuous problem I would hand to a prover is PE\(_\infty\)-MRF Allocation.
There are \(m\) item categories \(M=\{1,\ldots,m\}\), a finite explicit set of agent types \(T=\{1,\ldots,\tau\}\), rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), and rational per-capita supplies \(b_j\) of each item category \(j\). A type \(t\) is completely described by a matroid \(\mathcal M_t\) on \(M\), with rank valuation \(r_t(S)\). Thus agents of type \(t\) are indistinguishable in their preferences and in every parameter used by the allocation problem. The supply convention means that a population of size \(N\) has \(Nb_j\) copies of category \(j\); each individual still receives an integral bundle of categories.
The decision variable is \(x_{t,S}\), the mass of type-\(t\) agents receiving the integral bundle \(S\subseteq M\). It must satisfy
\[ \sum_{S\subseteq M}x_{t,S}=\mu_t \]
for every \(t\), and
\[ \sum_{t\in T}\sum_{S\ni j}x_{t,S}\le b_j \]
for every item category \(j\). We restrict to non-redundant bundles, so \(x_{t,S}>0\) only when \(S\) is independent in \(\mathcal M_t\). The utility distribution induced by \(x\) places mass \(x_{t,S}\) at utility \(r_t(S)\). A solution is a feasible \(x\) whose utility distribution Lorenz-dominates that of every other feasible allocation: writing \(u_x^\uparrow\) for its increasing utility quantile function,
\[ \int_0^q u_x^\uparrow(z)\,dz \ge \int_0^q u_y^\uparrow(z)\,dz \]
for every feasible \(y\) and every \(q\in[0,1]\), with equality at \(q=1\). A fixed priority rule may select among allocations with the same utility distribution; it is not part of the feasibility question.
This is recognisably the same problem. The population has been continuized, but \(m\) remains discrete, every agent receives an integral bundle, and the valuation of every type is still exactly a matroid rank function. The fractional variables describe the distribution of integral bundles across a population; they do not give an individual a fractional bundle. This is precisely the kind of co-modification that a high-multiplicity mirror requires.
The regime is plausible in, for example, a large course-allocation or public-service market. There may be millions of students or applicants but only a few dozen recurring eligibility profiles. A profile can encode a matroid constraint such as substitutable course requirements, category quotas, or eligibility constraints. Course seats or service slots are supplied in quantities proportional to population. Then \(N\gg\tau\), while the same finite collection of matroid types recurs at high multiplicity.
The computational reason to expect a positive result is especially strong. The natural LP has variables \(x_{t,S}\) for exponentially many bundles \(S\), but its pricing problem has the form
\[ \max_{S\in\mathcal I_t} \left( a\,r_t(S)-\sum_{j\in S}p_j \right) \]
for a type-dependent coefficient \(a\) and dual item prices \(p_j\). On independent sets, \(r_t(S)=|S|\), so this becomes maximum-weight independent-set optimization in a matroid, solvable greedily from an independence or value oracle. The Lorenz refinement introduces only polynomially many utility layers because utilities lie in \(\{0,\ldots,m\}\). Thus column generation or separation should give an exact algorithm polynomial in \(m\), \(\tau\), the input bit length, and the succinct matroid representations, rather than in the expanded population size \(N\).
The high-multiplicity dictionary is exact for rational instances. Given \(N\mu_t\) agents of each type and \(Nb_j\) copies of each item category, any rational \(x\) can be denominator-cleared into an ordinary finite allocation. Conversely, every such finite allocation induces the normalized variables \(x_{t,S}\). The continuous problem is therefore not merely an analogy: it is the compressed limit of repeated finite instances.
The expected classification is tractable, for a reason tied directly to the paper’s structure. The paper’s PE algorithm exploits matroid structure to select a particular Lorenz-dominating allocation. In the continuous version, the same structure controls the exponentially large bundle space through pricing. The further questions are whether the priority refinement itself admits a strongly polynomial compressed implementation, whether the paper’s EFX and maximin guarantees survive the continuum utility distribution, and whether a non-vacuous incentive notion can be defined for positive-mass deviations.
I would not claim that dominant-strategy truthfulness transfers automatically to a nonatomic population. A unilateral infinitesimal report may have zero effect, making truthfulness vacuous. The honest formulation is that every rational continuous instance has finite high-multiplicity lifts on which the paper’s PE mechanism remains dominant-strategy truthful, while the continuous theorem concerns the compressed allocation computation. A separate theorem would be needed for coalition- or positive-mass truthfulness.
The weakest point is the scaled-supply interpretation. If the authors insist that the paper concerns a one-off collection of \(m\) unique items, then letting the number of agents grow makes almost everyone receive nothing, and the mirror is poor. The positive case depends on a credible recurring-market interpretation in which item categories have many copies. That is a genuine modelling extension, but it preserves the paper’s essential object—integral bundles evaluated by MRFs—and is exactly the sort of per-capita supply modification that makes a continuous population meaningful.
The proponent’s only serious anchor is MRFpolytime, but their proposed LP does not actually mirror that theorem. The PE mechanism is not merely “find a Lorenz-dominating allocation.” It is a direct mechanism over named agents, with a fixed priority order and a carefully chosen tie-breaking rule. The paper explicitly shows that an arbitrary Lorenz-dominating allocation need not be truthful. The proof of truthfulness uses faithfulness, strong faithfulness, and monotonicity under a single agent’s report changing—information absent from \(x_{t,S}\), which records only mass assigned to bundles.
If we preserve the paper’s actual resource model, there are \(m\) unique items. For a population of size \(N\), each item has mass \(1/N\). Hence only \(O(1/N)\) of the population can receive positive utility, and the limiting utility distribution is concentrated at zero. Lorenz comparisons and welfare become degenerate almost everywhere, while the strategic behaviour of the exceptional recipients disappears from the atomless model.
The proposed repair—giving each item category \(Nb_j\) copies—is mathematically sensible, but it is a substantive new market model. It replaces allocation of \(m\) distinct items by allocation of recurring item categories, effectively introducing parallel copies and a per-capita supply system that the paper never studies. A course-allocation interpretation may make that extension plausible, but plausibility of the extension does not make it a mirror of the named PE implementation theorem.
The strategic content cannot be restored cheaply. Adding individual priority ranks destroys finite type multiplicity; collapsing priorities into finitely many classes changes the mechanism’s tie-breaking rule. Leaving priority out makes a unilateral deviation have zero mass, so truthfulness becomes vacuous. Requiring a positive-mass group to deviate produces a coalition or type-level incentive problem, not the dominant-strategy theorem proved in the paper. Saying that every rational mass allocation has a finite PE lift establishes only a compression of an anonymous allocation problem; it does not establish a continuous truthful mechanism.
Thus the surviving object is a potentially worthwhile high-multiplicity problem for computing a Lorenz-dominating distribution of integral bundles. But that is an anonymous multi-unit allocation problem, not the paper’s priority-sensitive truthful mechanism, and the paper supplies no other computational anchor. The negative case is not airtight: if the programme accepts mirroring only the allocation-computation component of MRFpolytime, the matroid-pricing argument is a genuine Class A mirror. Against the theorem as a mechanism result, however, the proponent has dropped its essential identity-dependent content.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.