| paper | First-Choice Maximality Meets Ex-ante and Ex-post Fairness |
| authors | Xiaoxi Guo, Sujoy Sikdar, Lirong Xia, Yongzhi Cao, Hanpin Wang |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper's numbered results establish mechanism properties and an axiomatic impossibility, not a named computational complexity result, so bit (a) fails under the strict rule. The proposed GEBM and GPBM mirrors require replicated-item assumptions, a new type representation, and an unproved ex-post lottery decomposition. A repeated-resource extension may be worthwhile, but it cannot supply the missing computational anchor for this paper.
fails bit a — no named computational result to mirror
The attempted mirrors cover the property guarantees of Theorems 1 and 2, while Proposition 1 and the paper's remaining mechanism-design results are not mirrored; none provides a qualifying complexity result.
The strongest honest positive case is narrow but real. Under the programme’s strictest anchor rule, this paper has no named complexity result: Theorems 1 and 2 prove properties of explicitly defined mechanisms, not membership in \(P\), NP-hardness, or parameterized complexity. Proposition 1 is an impossibility theorem. Thus, if “computational anchor” is read literally as a named complexity classification, this paper has no qualifying anchor.
If constructive mechanism theorems count as algorithmic anchors, the best case is the following.
The lead anchor is Theorem 1, proved in this paper: GEBM satisfies ex-post PE, ex-post EF1, ex-post FCM, and sd-WEF. A natural high-multiplicity regime is large course-allocation or resource-allocation markets. There are \(q\) agents, but only a fixed finite set \(T\) of complete ranking types, with \(q\mu_t\) agents of type \(t\), where \(\mu_t\in\mathbb{Q}_{\ge 0}\). Item supplies scale with the population: for a finite item catalogue \(O\), item \(o\) has \(q\sigma_o\) distinct copies, with \(\sigma_o\in\mathbb{Q}_{\ge0}\) and \(\sum_o\sigma_o=\kappa\in\mathbb N\). Thus \(q\) may be millions while \(|T|\) remains modest. This describes repeated cohorts of students with identical rankings over many seats, or repeated cloud, hospital, or referee-assignment resources.
Call the continuous problem GEBM-\(\infty\). Its input is
\[ (O,T,\mu,\sigma). \]
A solution is a mass assignment \(z_{t,b}\), where \(b\) is an indivisible \(\kappa\)-item bundle, satisfying
\[ \sum_b z_{t,b}=\mu_t \]
for every type \(t\), and
\[ \sum_{t,b} b_o z_{t,b}=\sigma_o \]
for every item \(o\). The output must also have a finite-support lottery decomposition into integral clone assignments after denominators are cleared. Consequently, each realized assignment still allocates whole indivisible items; \(z\) is an aggregate description of a lottery, not permission to split one item among agents.
The canonical solution is the mass version of GEBM: in each of \(\kappa\) rounds, every still-active unit of type \(t\) applies for its most-preferred remaining item; each item’s available copy mass is allocated among its applicants, and agents receiving one item leave that round. The solution must satisfy:
\[ p_u\succeq^{sd}_t p_t\quad\Longrightarrow\quad p_u=p_t. \]
This is a recognizable continuous analogue of Theorem 1: the ranking types, first-choice objective, Pareto condition, EF1 condition, and stochastic-dominance fairness condition are unchanged. Only the multiplicities are represented by rational masses, and both population and item supply scale together.
I would expect GEBM-\(\infty\) to be Class A in an explicit finite-type, explicit-\(\kappa\) representation. The round process is a finite mass-flow computation. The unresolved algorithmic issue is whether the required whole-bundle lottery can always be output compactly, or whether one needs an implicit sampler or a configuration-LP representation.
The second anchor is Theorem 2, also proved here: GPBM satisfies ex-post FCM, ex-post EF1, and sd-E. The continuous problem GPBM-\(\infty\) has the same input and the same indivisible-bundle output requirement. Its canonical process is the mass version of GPBM: during each allocation round, active type mass consumes its highest-ranked remaining item at equal rate until either that item’s supply is exhausted or the type mass has received one item in the round. The final expected shares \(p_t\) must satisfy sd-efficiency:
\[ \nexists q\neq p\ \text{such that}\ q_t\succeq^{sd}_t p_t\ \text{for every }t \]
with strict improvement for at least one positive-mass type. The lottery support must consist of assignments satisfying FCM and EF1.
This is also plausibly Class A for computing the expected type-share matrix, since the eating process is piecewise linear and has finitely many exhaustion events. The harder question is the ex-post implementation: preserving indivisible bundles and producing a valid EF1/FCM decomposition may require a configuration or matching computation. That is a genuine open technical question, not something the continuous notation resolves automatically.
I would not use Proposition 1 as a third anchor. A continuum version of its sd-WSP impossibility would require replacing unilateral deviations by positive-mass type deviations. An atomless individual has zero influence, so ordinary strategyproofness becomes vacuous; the replacement is a substantive new strategic model rather than a direct mirror.
The weakest point is therefore clear: the proposed mirrors need an explicit whole-bundle lottery representation. If one keeps only the fractional share matrix, the result risks becoming outcome-space continuity or probabilistic assignment rather than population continuization. The case survives because the paper already treats randomized assignments, and the rational clone expansion preserves the original indivisible assignment problem in the large-cohort regime. But the clone-consistency and compact ex-post-decomposition proofs would be necessary before claiming a finished ChoCo result.
So my positive verdict is: Theorem 1 supports a credible extension-level mirror, with Theorem 2 as a weaker second anchor. On the strict complexity-anchor rule, however, the paper supplies no qualifying named \(P\)/hardness result.
The negative case is strongest on the programme’s strict anchor rule: this paper has no qualifying computational result. Theorem 1 and Theorem 2 establish properties of two explicitly defined mechanisms; they do not classify a problem as polynomial-time, NP-hard, approximation-hard, or parameterized. Proposition 1 is an impossibility theorem about axioms, not a complexity result. Thus there is no named computational problem whose population-continuous complexity landscape this paper begins to chart.
Even granting constructive mechanism theorems as algorithmic anchors, the proposed GEBM mirror changes the model in two coupled ways. In the paper, \(m\) is a set of distinct indivisible items and preferences are complete strict rankings over those named items. If \(m\) is fixed while the agent population grows, the per-capita supply tends to zero. Almost every agent receives nothing; EF1 becomes essentially automatic, and the allocation of a finite number of items among type masses is not a nontrivial population-level assignment. FCM and PE concern a vanishing set of recipients.
To retain a meaningful bundle size, the proponent scales item supply with the population. That is a defensible repeated-course or repeated-resource model, but it is no longer the paper’s fixed-item assignment problem. The number of distinct item labels grows with the population, so a “type” is not a fixed complete ranking unless one adds a new copy-symmetric or parametric preference language. If item copies are instead treated as interchangeable supply, strict rankings over distinct items have been replaced by a different model. And if the copies are treated fractionally, the construction becomes outcome-space continuity, which the programme explicitly excludes.
The configuration formulation does not remove this problem. A mass \(z_{t,b}\) over whole bundles can indeed represent a legitimate high-multiplicity clone population; indivisible-bundle configurations are not intrinsically invalid. But the type-level share matrix does not determine the joint bundle allocation. Different couplings can have identical expected shares while differing in EF1 and Pareto efficiency. Therefore the ex-post part of Theorem 1 requires an actual finite-support lottery over clone assignments, not merely \(z\) or \(p_t\).
That is precisely the unresolved point in the positive case. If the lottery is omitted, the mirror retains only fractional or ex-ante properties and becomes probabilistic assignment. If it is required, one needs a new compact implementability theorem showing that the mass flow admits a round-consistent decomposition into integral assignments satisfying PE, EF1, and FCM. The paper proves no such theorem, and the proposed bundle alphabet may itself be exponentially large. Clearing denominators and expanding clones establishes semantic correspondence for a finite instance, but it does not yield a continuous computational result or a succinct algorithm.
Theorem 2 is weaker still as a population mirror. GPBM is already an eating process that produces probabilistic shares. Replacing equal-preference agents by type masses merely aggregates the same flow. Its natural continuous output is exactly the ex-ante assignment matrix for which sd-efficiency is defined. That is outcome-space/probabilistic continuity, not a computational theory of a continuous society. To recover ex-post FCM and EF1 one again needs Algorithm 3’s clone-level lottery, returning to the finite expanded assignment problem.
A better version cannot simply repair this by choosing the matching special case. With fixed \(m\), the continuum degenerates as above. With \(m\) scaling proportionally to \(n\), the proposed repeated-copy model may be sensible, but it requires new assumptions about item replication, ranking representation, and lottery coupling. One could certainly study optimization questions there—for example, finding a feasible type-bundle lottery with selected fairness guarantees—but those would be new mechanism-design problems, not computational mirrors of Theorems 1 or 2.
The same objection would apply if Proposition 1 were promoted to an anchor. Unilateral sd-strategyproofness becomes vacuous for an atomless individual; positive-mass type deviations or coalition deviations are meaningful, but they are new strategic notions rather than a continuous restatement of the paper’s impossibility.
I would not claim that every repeated-course interpretation is senseless. A carefully formalized repeated-item regime could become worthwhile. But that possibility depends on adding exactly the missing model and computation: a nondegenerate item-scaling regime, a compact type description, and an ex-post decomposition theorem. As this paper stands, it supplies no named complexity anchor, and its two proposed mirrors collapse either to ordinary probabilistic assignment or to an unproved clone-expansion extension. The strict verdict should therefore be negative.
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.