| paper | Strategy-proof allocation with outside option |
| authors | Jun Zhang |
| venue | GEB 2023 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The high-multiplicity object-assignment mirror is substantively sensible and preserves the paper’s outside-option and participation concepts. However, Proposition 2 is an axiomatic impossibility theorem rather than a computational result, so the paper supplies no qualifying anchor under the programme’s explicit gate.
fails bit a — no named computational result to mirror
Proposition 2 lacks computational character, and making mechanism representations or verification computational would introduce a new problem rather than mirror a result proved here.
fatal: True
The proposed mirror covers Proposition 2’s size-improvement impossibility in object assignment; the paper’s other structural results and applications receive no separate continuous-population formulation.
The strongest honest case is a qualified one. The paper has a very natural continuous-population analogue, but it has no qualifying computational-complexity anchor: none of its numbered results proves NP-hardness, membership in \(P\), parameterized tractability, approximation, or an algorithmic formulation with a complexity claim. Its computational remarks are literature summaries. Thus the mirror below is substantively strong but formally weaker than the ChoCo programme’s preferred cases.
The best anchor is Proposition 2, proved in this paper. In the object-assignment model with weak preferences, where no real object is indifferent to the outside option, it states:
An individually rational, unbidominated, truncation-invariant mechanism cannot be size-improved by any other individually rational, truncation-invariant mechanism.
Here “size improvement” means that the new mechanism assigns weakly more acceptable objects in total at every preference profile, strictly more at some profile, and, whenever total size is unchanged, preserves every agent’s participation size. The result is proved here from Lemma 1 and Lemma 3; it is not merely cited.
A natural continuous mirror is the following.
Let \(O\) be a finite set of destinations or objects and let \(\widetilde O=O\cup\{\emptyset\}\), where \(\emptyset\) is the outside option. A type \(t\in T\) is a complete preference ranking over \(\widetilde O\), including its acceptability relation. A society is a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\). Each \(q_o\in\mathbb{Q}_{\ge0}\) is the supply of object \(o\) per unit population.
An aggregate allocation is a matrix \(p=(p_{t,o})\) satisfying
\[ \sum_{o\in\widetilde O}p_{t,o}=\mu_t \quad\text{and}\quad \sum_{t\in T}p_{t,o}\le q_o. \]
Thus \(p_{t,o}\) is the mass of type \(t\) receiving object \(o\). Individuals still receive integral objects; the fractions arise because a continuum of identical agents can be split into submasses. For \(\mu_t>0\), \(p_{t,o}/\mu_t\) is the lottery received by a representative type-\(t\) agent.
A continuum mechanism \(M\) maps \(\mu\) to such an allocation and also specifies the lottery \(K_M(\mu,r)\) received by an infinitesimal agent who reports ranking \(r\). This kernel is needed because a single atomless agent does not change \(\mu\) by deviating. Individual rationality, truncation-invariance, and stochastic dominance are imposed on these representative lotteries exactly as in the paper.
Define the size of \(p\) by
\[ \lVert p\rVert=\sum_{t\in T}\sum_{o\in O}p_{t,o}, \]
and define type-\(t\) participation by
\[ s_t(p)=\frac{\sum_{o\in O}p_{t,o}}{\mu_t}. \]
The continuous problem is:
Given \(O,q,T\), a rich preference domain, an incumbent mechanism \(M\), and a candidate replacement \(M'\), does \(M'\) size-improve \(M\)? That is, does
\[ \lVert M'(\mu)\rVert\ge \lVert M(\mu)\rVert \]
hold for every \(\mu\), strictly for at least one \(\mu\), with \(s_t(M'(\mu))=s_t(M(\mu))\) for every positive-mass type whenever the total sizes coincide?
The expected answer is no whenever \(M\) is individually rational, unbidominated, and truncation-invariant and \(M'\) is individually rational and truncation-invariant. This is a structural Class-A-style outcome: the replacement problem collapses to an impossibility theorem rather than requiring search over a large population. It is not, however, a polynomial-time theorem about a finitely encoded computational problem unless one additionally specifies how mechanisms \(M\) and \(M'\) are represented.
The regime is plausible. Consider a national school-placement, refugee-resettlement, or city-assignment system with hundreds of thousands of applicants but a small number of destinations and recurring preference/acceptability patterns. The meaningful input is the fraction of applicants of each type, not the identities of \(n\) separately listed people. Per-capita capacities \(q_o\) are the natural scaling: doubling the population doubles available places. This is precisely a high-multiplicity regime, not merely a fractional-outcome model.
The authors should recognize this mirror as their problem. It preserves their outside option, weak preferences, individual rationality, participation size, truncation-invariance, and the objective of increasing the number of acceptable assignments while protecting already-served agents. It also uses the paper’s own motivating applications, especially refugee resettlement. The fractional aggregate matrix is a consequence of continuizing the population; the object received by each unit of mass remains integral.
The main further questions would be whether IR, truncation-invariance, and unbidominance can be verified efficiently from a finite description of a continuum mechanism; whether the impossibility survives group deviations by positive-mass types; and how rational finite elections approximate the continuum rule while preserving participation and welfare guarantees.
My weakest point is decisive under the strict ChoCo standard: Proposition 2 is an axiomatic impossibility result, not a computational result. The paper therefore supplies a convincing continuous-population question, but no named computational anchor from which to chart a complexity landscape. Under a broad “does the problem admit a sensible continuous mirror?” reading, the answer is yes for object assignment. Under the programme’s stricter requirement that the mirror be anchored in a named complexity theorem, this paper does not qualify.
The Proposition 2 anchor does not clear ChoCo’s computational gate. Proposition 2 is an axiomatic impossibility theorem about unrestricted mechanisms. It specifies no computational input, finite encoding, output, algorithm, or complexity parameter. Thus the proposed question,
\[ \text{“does }M'\text{ size-improve }M\text{?”}, \]
is not a computational problem. Once the stated hypotheses hold, its answer is already “no” by Proposition 2; checking those hypotheses is a new mechanism-verification problem that the paper neither formulates nor studies.
The strongest rescue would encode \(M\) and \(M'\) as finite circuits, tables, or piecewise-linear maps and ask whether the size inequalities hold for every population vector \(\mu\). But each choice creates a different problem. The domain of \(\mu\) contains infinitely many rational points, and the paper gives no canonical representation of mechanisms on that domain. Alternatively, asking whether some improving mechanism exists is a mechanism-synthesis problem, not a continuization of Proposition 2. It could be worthwhile research, but it would be new research without a computational result from this paper as its anchor.
There is also a substantive mismatch around strategy-proofness. In the proposed model, \(M\) observes only the aggregate distribution \(\mu\). A single atomless agent’s report has measure zero, so it does not change \(\mu\); aggregate strategy-proofness is therefore vacuous. The proposed kernel \(K_M(\mu,r)\) is an additional mechanism-level object absent from the paper. If instead a positive-mass type is allowed to deviate, the concept becomes group strategy-proofness for coordinated type masses, which is a different incentive requirement and would require a new theorem.
The same issue appears in size-equivalence. Proposition 2 preserves the participation size of every named agent whenever total size is unchanged. The proposed \(s_t(p)\) preserves only the average participation of type \(t\). That is a reasonable anonymous reformulation, but anonymity is an extra assumption. If identity-level guarantees are retained, the aggregate matrix \(p\) does not contain enough information; encoding identities or individual priorities as types destroys the intended finite high-multiplicity compression.
The proponent is right about one important point: repeated preference types in large school-placement, refugee-resettlement, or object-assignment markets are a sensible high-multiplicity regime. Per-capita capacities are natural, and “fractional mass” need not mean divisible objects. I would not reject the model on the grounds that allocations are fractional. But at the allocation layer, \(p_{t,o}\) is essentially the same kind of fractional assignment or lottery matrix already used in the paper. With finite \(T\) and \(O\), it is a transportation polytope; the population continuum introduces no new computational object unless one adds a separately specified mechanism-representation or incentive problem.
Nothing else in the paper repairs the gap. Theorem 1, Lemma 1, and the corollaries are likewise structural statements, while the computational claims in the introduction are summaries of prior literature rather than results proved here.
So the universal modelling claim—“no sensible continuous population interpretation exists”—would be too strong. The proposed object-assignment regime is genuinely sensible. The stronger and defensible negative verdict is that this paper supplies no worthwhile ChoCo mirror under the programme’s computational standard: its natural continuum restatement is an axiomatic high-multiplicity reformulation, and any genuinely computational version would be a new problem rather than a computational mirror of the paper.
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.