| paper | Strategy-proof and envy-free mechanisms for house allocation |
| authors | Priyanka Shende, M. Purohit |
| venue | JET 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper's numbered results are impossibility theorems and structural or axiomatic characterizations; none asserts that an object can be computed or that computing it is hard. The proposed continuous rule-selection problem adds a welfare objective and rule-selection task absent from the paper. Therefore no named computational result has a qualifying continuous mirror.
fails bit a — no named computational result to mirror
The proposed formulation selects \(q\) using an added population-welfare objective, changing finite-market mechanism characterization into a new distribution-dependent design problem.
fatal: True
No named computational result is covered. The proposed construction concerns only a new population-level rule-selection problem and does not computationally mirror Theorems 3.1, 4.16, or 4.17.
The strongest honest case is qualified: the paper admits a sensible high-multiplicity mirror, but it has no qualifying computational anchor under ChoCo’s strict rule.
The closest anchor is Theorem 4.16, proved in the paper. It states that a pairwise-exchange mechanism is strategy-proof, envy-free, and neutral exactly when there is a vector \(v\in[0,1/(n(n-1))]^n\), with \(v[n]=0\) and \(v[k]\ge v[k+1]\), such that
\[ f(\succ,\succ',a) = v[\operatorname{rank}(\succ,a)] - v[\operatorname{rank}(\succ',a)]. \]
This is the paper’s strongest computationally suggestive result: it compresses an entire mechanism into \(n\) rank parameters. Theorem 4.17, also proved here, further says that within this family \(\mathcal F\), \(\phi_v\) is Pareto-efficient exactly when \(v[1]=1/(n(n-1))\).
A natural mirror would be Continuous Pairwise-Exchange Rule Selection\(_\infty\). Consider a large assignment market with \(m\) object categories, many copies of each category, and a population distribution \(\mu\) over complete ranking types \(T\subseteq S_m\). Each type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\); typically the population has \(N\gg |T|=\tau\) agents. Each agent still receives one indivisible object. Only the allocation of a type’s mass is fractional.
With equal per-capita supply \(1/m\) for each object, choose a nonincreasing vector
\[ 1\ge q_1\ge q_2\ge\cdots\ge q_m=0 \]
and define the type-level allocation
\[ p_{t,a}(q) = \frac{1}{m} \left( 1+ \sum_{s\in T}\mu_s \bigl(q_{\operatorname{rank}_t(a)} - q_{\operatorname{rank}_s(a)}\bigr) \right). \]
The induced mass assigned to \(a\) is \(\mu_t p_{t,a}(q)\). A solution must provide \(q\) and the resulting \(p\), satisfying
\[ \sum_a p_{t,a}=1, \qquad \sum_t\mu_t p_{t,a}=\frac1m, \qquad p_{t,a}\ge0. \]
Given a monotone rank-utility vector \(u_1\ge\cdots\ge u_m\), the objective is to choose \(q\) maximizing
\[ \sum_{t\in T}\mu_t\sum_{a\in O} u_{\operatorname{rank}_t(a)}p_{t,a}(q). \]
This is genuinely population-continuous: the input is a distribution over repeated agent types, while the micro-allocation remains integral. It is plausible in a large school-seat, housing-slot, or course-seat market with many agents sharing a small number of canonical preference rankings. The paper’s authors would recognize the rank-based transfer rule and the strategy-proofness/envy-freeness requirements as their problem, with pairwise sums replaced by population averages.
I would expect this mirror to be Class A. Theorem 4.16 reduces rule selection to a finite-dimensional isotonic linear program, and the coefficients can be computed in time polynomial in \(m\), \(\tau\), and the mass encoding length. Further questions include exact finite-population rounding, implicit or exponentially large type spaces, and whether optimizing over more general anonymous separable transfer functions remains tractable.
The weakness is decisive for grading: Theorem 4.16 and Theorem 4.17 are structural characterizations, not named results asserting membership in P, NP-hardness, FPT, or another complexity class. The paper’s numbered results are all axiomatic or impossibility results; cited complexity claims are not proved here. Thus this is a credible derived Class A research problem, but not a formally compliant ChoCo positive case under the stated anchor requirement.
The negative case is decisive under ChoCo’s stated gate: this paper contains no computational result to mirror. Its numbered results are axiomatic characterizations, impossibility theorems, and algebraic structure results. None defines a computational input, output, decision problem, optimization problem, encoding, or complexity claim.
Theorem 4.16 is therefore not a Class A, B, or C anchor. It says that, within a finite pairwise-exchange class, strategy-proofness, envy-freeness, and neutrality are equivalent to the existence of a monotone rank vector \(v\). The vector is a mechanism parameter, not an object to compute from a society. For any fixed \(v\), the proposed population formula is just an averaging of the already specified finite rule. The axioms do not depend on \(\mu\), and the theorem does not ask which \(v\) should be selected.
The proponent’s “Continuous Pairwise-Exchange Rule Selection” adds precisely the missing problem: a cardinal rank utility \(u\), a social-welfare objective, and the instruction to choose \(q\). That may be a sensible new large-market assignment problem, but it is not a continuization of a computational result in this paper. The paper never selects a rule by aggregate welfare, never introduces \(u\), and never treats the population distribution as an input to mechanism design. Calling this a mirror quietly changes the research question.
Theorem 4.17 does not rescue the anchor. Its Pareto order compares mechanisms by universal stochastic dominance at every finite preference profile. If that order is retained, \(\mu\) is irrelevant and the theorem already identifies the frontier by \(v[1]=1/(n(n-1))\). If it is replaced by society-weighted welfare or aggregate dominance, the result becomes a new distribution-dependent criterion, not the theorem’s continuous counterpart.
A more careful high-multiplicity construction is possible: use many agents with repeated rankings and scale object supplies, then define type-level lotteries and pointwise incentive constraints. I would not object merely because the paper’s outcomes are already fractional; that would confuse outcome continuity with population continuity. Nor would I object that the resulting problem might be easy. The fundamental issue is that this construction changes the primitive problem from characterizing finite-market mechanisms to designing or evaluating a mechanism in a new large-market environment. Any worthwhile complexity question comes from the added objective, representation, or rule class, not from continuizing a named computational claim of the paper.
Theorem 3.1 and the other impossibility results cannot supply a replacement anchor: they concern compatibility of axioms, not computational complexity. Thus the honest conclusion is qualified but firm. Large-market random assignment with type distributions could be worthwhile research in its own right, but this paper offers no computational result whose continuous population mirror ChoCo can grade as a genuine mirror. Under the programme’s strict standard, the proposed anchor fails.
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.