| paper | The vigilant eating rule: A general approach for probabilistic economic design with constraints |
| authors | H. Aziz, F. Brandl |
| venue | GEB 2022 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm{P}\)): compute an \(\mathrm{FS\text{-}VER}\) allocation whenever one exists, and otherwise report infeasibility. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 3
statement extracted from the paper’s text layer
Given finite object types \(O\), applicant types \(\Theta\), rational applicant mass \( \mu \), per-capita object supplies \(q\), and type data specifying preferences and priorities, compute a feasible mass allocation \(x_{\theta,o}\) with \( \sum_o x_{\theta,o}=\mu_\theta \), \( \sum_\theta x_{\theta,o}=q_o \), and \(p_{\theta,o}=x_{\theta,o}/\mu_\theta\) satisfying \( \sum_{o'\succeq_\theta o,\;o'\ne o}p_{\theta,o'}+\frac{1}{q_o}\sum_{\theta':\,\theta'\succeq_o\theta}x_{\theta',o}\ge 1 \); return the resulting \( \mathrm{FS\text{-}VER} \), equivalently the constrained ordinally egalitarian allocation.
An explicit-support high-multiplicity allocation market where \( \mu \) is applicant mass, \(q\) is seat mass, \(x\) is assigned mass, and \(p\) is the common type-level allotment; compute the VER point of the fractional-stability polytope.
With explicit type support, \( \mathrm{FS\text{-}VER}_\infty \) is an exact orbit quotient of the finite FS-VER computation, so the population parameter contributes little population-specific computational content.
fatal: False
The mirror covers the FS-VER component of Corollary 3 and its LP computation via Theorem 3. It leaves CWS-VER, the impossibility propositions, and the unresolved ex-ante and ex-post stability complexity questions open.
The strongest honest case is a qualified yes: the paper admits a natural high-multiplicity mirror for its fractional-stability mechanism. It is a Class A mirror, not a new hardness result.
My lead anchor is Corollary 3, proved in this paper: “FS-VER and CWS-VER can be computed in polynomial time.” I use the FS-VER part. The result rests on Theorem 3, also proved here, which states that if the feasible set \(X\) is a finite union of polytopes, then VER can be computed in polynomial time in the number of inequalities describing \(X\). The paper contains no comparable named NP-hardness theorem of its own, so this is necessarily an algorithmic anchor.
The continuous problem is Fractionally Stable VER over a Population, \(\mathrm{FS\text{-}VER}_\infty\).
There is a finite set \(O\) of school, hospital, or programme types and a finite set \(\Theta\) of applicant types. A type \(\theta\) completely specifies an applicant’s weak preference relation \(\succeq_\theta\) over \(O\), together with the priority class that the applicant occupies at every object. The society is given directly by a rational distribution \(\mu\in[0,1]^\Theta\), with \(\sum_{\theta}\mu_\theta=1\). Thus \(\mu_\theta\) is the mass of applicants of type \(\theta\), not a probability over outcomes.
Each object type \(o\) has a per-capita supply \(q_o\), with \(\sum_o q_o=1\). This is the natural scaling in a large school-choice or hospital-allocation market: \(q_on\) identical seats of type \(o\) serve \(n\) applicants. Applicants of the same type have the same preferences, capacities, and priorities.
The decision variable is a mass allocation \(x_{\theta,o}\ge 0\), where \(x_{\theta,o}\) is the mass of type \(\theta\) assigned to object \(o\). Equivalently, for \(\mu_\theta>0\), write \(p_{\theta,o}=x_{\theta,o}/\mu_\theta\) for the common per-agent allotment of that type. The allocation must satisfy
\[ \sum_o p_{\theta,o}=1 \qquad\text{and}\qquad \sum_\theta x_{\theta,o}=q_o. \]
For every type \(\theta\) and object \(o\), impose the type-level version of the paper’s fractional-stability constraint:
\[ \sum_{\substack{o'\succeq_\theta o\\o'\neq o}} p_{\theta,o'} + \frac{1}{q_o} \sum_{\theta':\,\theta'\succeq_o\theta} x_{\theta',o} \ge 1. \]
The second term is the fraction of seats of category \(o\) consumed by applicants with at least as high a priority as \(\theta\). When \(q_o n\) is replaced by one object, this reduces to the paper’s finite-agent constraint after normalization.
The objective is to compute the VER allocation over this feasible set. Concretely, in each round, every active type identifies its most-preferred equivalence class whose per-capita allotment can still be increased while preserving feasibility; the algorithm then maximizes the common increment \(\delta\) for all selected types. Because the feasible set is convex, this is equivalently the type-level ordinally egalitarian allocation described by Theorem 4. The output is \(p\), or its mass form \(x=\mu p\).
This is a genuine population mirror. The society is not represented by \(n\) named applicants, and the output is not merely a fractional lottery over a finite population. It is a measure allocation from applicant mass to seat mass. A finite high-multiplicity instance with \(n_\theta\) identical applicants and \(q_on\) identical seats maps to \(\mu_\theta=n_\theta/n\); conversely, rational \(\mu\) and \(p\) can be expanded into such a finite instance. The fractional entries describe population shares or ex-ante assignments, while the continuous object being modelled is the applicant population itself.
The regime is plausible in precisely the high-multiplicity sense relevant here: a national school-choice cohort, a large hospital intake, or a centralized training allocation may contain millions of applicants but only a few hundred or thousand distinct combinations of preference order, eligibility, residency, priority tier, and capacity. The number of agents is enormous relative to \(|\Theta|=\tau\), and targeting one named applicant is not the intended operation. Per-capita seat supplies \(q_o\) are the honest analogue of the paper’s object capacities.
The expected complexity is polynomial in \(m=|O|\), \(\tau=|\Theta|\), and the encoding length \(L\). The feasible region is one explicitly described polytope with \(O(\tau m)\) variables and polynomially many constraints, including \(O(\tau^2m)\) priority inequalities. The VER rounds can therefore be implemented by the same LP computations used in Theorem 3. This is a direct Class A mirror.
The authors should recognise this as their problem. Nothing essential has been replaced by utilitarian welfare or a simpler assignment rule: weak ordinal preferences, priority relations, fractional stability, constrained efficiency, and equal treatment of equal types all remain. The paper itself explicitly motivates probabilistic allocations as time-sharing, and its Theorem 5 gives the relevant symmetry principle for equal types under convex symmetric feasibility constraints.
The mirror covers Corollary 3’s FS-VER result emphatically. It does not claim to continuize the paper’s impossibility propositions, nor does it settle the paper’s open computational questions for ex-ante or ex-post stability. Those generate useful follow-up problems: whether ex-ante-stable VER remains tractable under a compact type-level representation, whether weak-priority ex-post stability has an efficient separation oracle, and how accurately a continuous solution can be rounded to a finite assignment while preserving stability.
The weakest point is that this paper already studies probabilistic and fractional allocations. An opponent can therefore argue that \(\mathrm{FS\text{-}VER}_\infty\) is merely an aggregation of identical rows in an LP, or that its apparent continuity belongs to the outcome space. That criticism has force, and this is not the strongest possible mirror for the programme. The defence is that \(\mu\) is now the primitive society, supplies scale with population, and the finite-agent index disappears from the computational problem. So the mirror is legitimate, but modest: it demonstrates that the paper’s constrained probabilistic mechanism has a sensible continuous-population formulation, rather than showing a dramatic discrete-hardness collapse.
The strongest attack is not that the proposed model is incoherent. It is coherent, and the paper does contain a genuine computational anchor: Theorem 3 and Corollary 3 explicitly establish polynomial-time computation. The better objection is that this is almost entirely a symmetry quotient of the paper’s existing fractional allocation problem, rather than a worthwhile continuous-population problem.
For a rational instance, choose \(D\) clearing all denominators and create \(D\mu_\theta\) identical agents of type \(\theta\) and \(Dq_o\) identical copies of object \(o\). A type allocation \(p_{\theta,o}\) lifts to the finite allocation in which every copy of type \(\theta\) receives the same row. Conversely, any symmetric finite allocation projects to
\[ x_{\theta,o}=\mu_\theta p_{\theta,o}. \]
Fractional stability is linear and invariant under permutations of agents with the same preferences, priorities, and capacities. Since the feasible set is convex, Theorem 5 already implies that VER treats such copies equally. The VER optimization steps therefore commute with this aggregation. The proposed \(\mathrm{FS\text{-}VER}_\infty\) is consequently the exact orbit quotient of the finite FS-VER computation.
That makes the population parameter algorithmically inert in the anchor being claimed. Once the support of \(\mu\) is explicitly listed, the continuous problem is one ordinary LP with \(O(\tau m)\) variables and polynomially many constraints. Its tractability comes directly from the paper’s already explicit polyhedral formulation, not from a new population-level structural insight, a separation problem, or a complexity phenomenon. The mass vector changes multiplicities and the right-hand sides; it does not create a new computational object.
The proponent can strengthen the mirror by making the type support implicit—for example, allowing all preference orders and priority profiles and giving a compressed distribution. But then Theorem 3 no longer supplies the result. One needs a new representation of the distribution and a new separation or aggregation theorem for the priority sums. Any resulting algorithm or hardness result would be a new study, not a continuous version of Corollary 3. Conversely, if the support remains explicit so that Corollary 3 transfers immediately, the result is mainly a high-multiplicity encoding observation.
A different rescue would use atomless strict priority scores. That makes the aggregate priority constraints less trivial, but it abandons the paper’s high-multiplicity notion: an agent’s exact priority rank is part of her type and is essentially unique. If priorities are instead coarsened into finitely many tiers so that many agents really do share a type, the problem collapses back to the finite polytope quotient above. Similarly, requiring integral bundles for each population unit could produce an interesting configuration or decomposition problem, but that would no longer be the FS-VER anchor; it would be a new integral-population model.
Thus the negative case is that the proposed anchor has no population-specific computational content. It is a plausible high-multiplicity reformulation, but the theorem it mirrors is already a polynomial LP theorem whose finite formulation contains the relevant structure. That is a respectable compression result, but a weak fit for a programme whose point is to discover a new complexity landscape.
This negative case is not airtight. The school-choice and hospital examples make the high-multiplicity regime genuinely plausible, and per-capita supplies are a legitimate co-modification. Under a broad standard that accepts any meaningful high-multiplicity extension, the proponent’s mirror survives. I would therefore not honestly claim that this paper has no worthwhile continuous mirror in any scenario; I would claim only that FS-VER is too mechanically inherited from the paper’s fractional LP to be a strong ChoCo anchor.
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.