| paper | Slot-specific priorities with capacity transfers |
| authors | Michelle Avataneo, Bertan Turhan |
| venue | GEB 2021 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proponent supplies a plausible high-multiplicity mass version of COM, but explicitly concedes that Theorem 1 is not a computational result. Theorem 3 is likewise a Pareto comparative-static theorem, not an algorithm, complexity bound, hardness result, or computational formulation. Therefore bit (a) fails for every anchor, even if the proposed continuum evaluation problem would be a sensible new Class A project.
fails bit a — no named computational result to mirror
The proposed mirror covers aggregate evaluation of COM and mass analogues of Theorems 1 and 3; it leaves the comparative-static claims of Theorems 2, 4, 5, and 6 without computational mirrors.
The best positive case is a high-multiplicity continuum version of the paper’s cumulative-offer mechanism for SSPwCT markets. It is a genuine population mirror, although the paper itself contains no numbered theorem asserting \( \mathrm{P} \), NP-hardness, FPT, or any other computational-complexity classification. Its numbered results are mechanism and comparative-static results. I therefore use those as structural anchors, while being explicit that the computational question is a new continuization of the underlying matching problem.
My lead anchor is Theorem 1, proved in this paper: “The COM with respect to SSPwCT choice rules is stable and strategy-proof.” In full, for every finite matching-with-contracts market in which branches use SSPwCT choice rules, the cumulative offer mechanism produces an individually rational outcome with no blocking coalition, and no agent can obtain a strictly preferred assignment by misreporting her preference order. This is not a cited computational result; it is the paper’s main mechanism theorem.
The continuous mirror is Continuum-SSPwCT-COM Evaluation. An instance contains a finite set of contract classes \(X\), branches \(B\), and complete applicant types \(\Theta\). A type \(\theta\) has mass \(\mu_\theta\), with \(\sum_{\theta\in\Theta}\mu_\theta=1\), a preference order \(P_\theta\) over its available contracts and \(\emptyset\), and every attribute relevant to eligibility or priority. Each branch has original and shadow capacity blocks, precedence orders, slot-specific priorities, and a transfer vector \(q_b\). Capacities are measured as fractions of the population: an original block of capacity \(\kappa\) can transfer its unfilled mass to its associated shadow block when the corresponding coordinate of \(q_b\) equals \(1\).
The mechanism runs the cumulative-offer process on mass. Unmatched mass of each type offers its most-preferred not-yet-rejected contract. A branch applies its SSPwCT rule to offered mass, retaining the highest-priority mass at each active slot and rejecting the rest. If a type is split at a capacity boundary, the accepted mass is held and only the rejected mass continues. Every infinitesimal agent receives one integral contract or \(\emptyset\); \(y_{\theta x}\) merely records how much mass of type \(\theta\) receives contract \(x\).
The requested solution is the exact aggregate assignment \(y\), together with the proposal/rejection transcript, or equivalently the answer to a query such as whether \(y_{\theta_0x_0}\ge r\). A direct continuum analogue of Theorem 1 would additionally certify individual rationality, absence of positive-mass blocking coalitions, and strategy-proofness against preference misreports by any positive mass of a type.
This is naturally Class A. With explicit finite priority lists and rational input, each type advances through its contract list at most once, so there are at most \(O(|\Theta||X|)\) aggregate proposal events. Each SSPwCT choice can be evaluated by scanning finite priority orders and subtracting rational masses. The main further questions are whether order independence survives exactly at the mass level, how to round the solution to a finite electorate, and whether compressed representations of priorities avoid explicitly listing all types.
The regime is plausible in centralized college admissions or government-job allocation with affirmative-action categories. The many agents are applicants, while a type records a preference order over programs, eligibility category, contract terms, and the finite priority band relevant to the institution. A national admissions market may have millions of applicants but only a moderate number of recurring preference-and-eligibility types. The type must include every feature used by the mechanism; if exact individual exam scores determine priority, they may generate too many types, but category-and-band priority systems provide a credible high-multiplicity regime.
A second, worthwhile anchor is Theorem 3, also proved here. It states that if one branch’s capacity-transfer scheme is made strictly more flexible—coordinatewise weakly larger, with at least one newly transferable original slot—while everything else remains fixed, then the new COM outcome \( \widetilde Z \) Pareto dominates the old outcome \(Z\). Thus every agent weakly prefers her new assignment, even though the branch’s stability notion changes with its choice rule.
Its continuous counterpart is Continuum Transfer-Expansion Evaluation. Given \(\mu\), the SSPwCT market, a branch \(b\), and transfer schemes \(q_b\le \widetilde q_b\), compute both continuum COM assignments \(y\) and \(\widetilde y\). A valid solution must also provide, for each type \(\theta\), a coupling \(\pi_{\theta,a,a'}\) between its old and new assignment masses such that
\[ \sum_{a'}\pi_{\theta,a,a'}=y_{\theta,a},\qquad \sum_a\pi_{\theta,a,a'}=\widetilde y_{\theta,a'}, \]
and
\[ \pi_{\theta,a,a'}>0 \quad\Longrightarrow\quad a' R_\theta a. \]
Here \(a,a'\) range over contracts and \(\emptyset\), and \(R_\theta\) is the weak preference relation of type \(\theta\). The coupling is a certificate that no mass is made worse; it can also report the amount of mass that strictly improves.
This too should be Class A: run the aggregate COM twice and construct the typewise couplings by finite transportation checks. A natural follow-on optimization is to choose at most \(K\) additional transferable slots to maximize a declared welfare function, but that policy problem is an extension rather than a theorem stated in the paper.
The high-multiplicity dictionary is clean. A finite market with \(N\) applicants and \(N\mu_\theta\) applicants of type \(\theta\) becomes the distribution \(\mu\); capacities are divided by \(N\), and multiplying the continuum allocation by \(N\) recovers aggregate seat counts. The fractional quantities are masses of agents, not lotteries or fractional bundles for individuals. This is therefore population continuization, with per-capita capacities as the necessary co-modification.
The weakest point is important: this paper is primarily axiomatic and economic, not computational. There is no honest hardness anchor, so the mirror cannot yet answer the programme’s flagship question of whether discrete hardness dissolves. Moreover, the mirror only becomes persuasive when the application has genuinely repeated complete types; a market with applicant-specific priorities and preferences may have \(|\Theta|\) close to the number of agents.
Still, the positive case survives that weakness. The paper’s finite-agent SSPwCT/COM model is not already a continuous-population model, and its admissions and affirmative-action applications admit credible high-multiplicity regimes. The strongest continuous question is therefore: can the SSPwCT cumulative-offer mechanism, together with its stability, strategy-proofness, and transfer-expansion guarantees, be computed and certified exactly on a distribution of applicant types? That is a coherent Class A mirror of the paper’s central problem, even though it does not provide a hardness-driven continuization result.
The negative case is unusually strong at the outset: this paper contains no numbered computational result. Theorems 1–6 concern stability, strategy-proofness, respect for improvements, and comparative statics. The cumulative-offer procedure is an algorithm, but the paper gives no complexity theorem, input-encoding result, optimization problem, or hardness boundary for it. Thus a continuous COM evaluation problem would be a new project inspired by the model, not a continuization of a computational result. Under ChoCo’s gate, that is decisive.
The strongest possible version of the first anchor is nevertheless coherent. Let a type record the complete preference list, contract terms, eligibility attributes, and all priority-relevant information; let capacities scale with population; and run COM on masses. Admissions markets with repeated preference and eligibility types are a plausible high-multiplicity regime. I do not object that high-multiplicity matching is already known, nor that individual agents receive integral contracts while type masses are fractional.
But this does not preserve the content of Theorem 1. Individual strategy-proofness becomes vacuous at the aggregate level: one agent has mass zero, so changing that agent’s report cannot change the continuum allocation. If a positive mass of a type misreports, the claim is no longer the theorem’s individual strategy-proofness; it is a new coalitional property, which Theorem 1 does not establish. Stability has the same problem: finite blocking by an individual must be replaced by positive-mass blocking, again creating a new property. Adding a tagged infinitesimal agent restores the original semantics only by reintroducing the individual-level object that the proposed mirror was supposed to eliminate.
If all priorities and contract lists are explicitly type-compressible, the mass procedure is simply a batching of the paper’s finite COM algorithm. If they are not, then the type description must distinguish essentially every individual contract and priority position, so the continuum has not produced a finite high-multiplicity representation. This is not an objection that the answer happens to be easy; it is that the proposed object contributes no new computational question corresponding to the paper’s theorem.
The second anchor, Theorem 3, has a more fundamental limiting problem. Its perturbation is the transferability of one additional slot. In a sequence with \(N\) applicants and capacities scaled by \(N\), one slot has normalized mass \(1/N\), and
\[ \frac{1}{N}\longrightarrow 0. \]
The theorem’s local Pareto improvement therefore disappears in the population limit. The best repair is to compare positive fractions of transferable slots. But that replaces “one more associated shadow slot” by a continuum of slot blocks. With finitely many repeated blocks, the model becomes an aggregate reserve/quota rule rather than the paper’s general slot-specific structure. With genuinely independent slot priorities, one needs a growing or measure-valued space of slot identities and priority orders, so the finite-type mirror disappears.
The proposed coupling \(\pi_{\theta,a,a'}\) also weakens the original claim. Theorem 3 compares the assignment of the same named agent before and after the policy change. A coupling of aggregate assignments certifies only that the new mass can be relabelled favorably. To retain same-agent Pareto improvement, the continuum model must carry a common identity space and assignments across both runs; to avoid that, it must replace the theorem by an existence-of-coupling statement.
A block-level continuum version could be a sensible standalone matching project. That is the point at which the negative case is weakest. But it would be a new population-capacity model, not a computational mirror of either numbered theorem. The paper’s anchors are individual-level mechanism properties, and under continuization they either become vacuous, become new coalitional/transport claims, or lose the defining one-slot structure. Since the paper supplies no computational result to mirror in the first place, there is no worthwhile ChoCo continuization here.
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.