| paper | d4-conf-aaai-2015-0411 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a finite horizon, a shift set \(A\), per-capita capacities \(q_a\) with \(\sum_{a\in A}q_a=1\), and a finite support \(T\) of nurse types with rational masses \(\mu_\theta\), where each type specifies a strict ranking and a finite-state preference-transition rule, can one construct a finitely described history-dependent lottery over measurable assignments? Each realization must assign mass \(q_a\) to shift \(a\), each nurse must receive one indivisible shift, truthful reporting must sd-dominate unilateral misreports over the remaining horizon and in each period, and each realized assignment must be Pareto efficient.
An atomless population of nurses represented by a finite distribution over complete preference and transition types, with rational per-capita shift capacities. A policy maps reports and assignment histories to lotteries over measurable assignments; individual assignments remain integral while type-level masses may be fractional.
ARSD’s pairwise dominance history over named agents may have no finite-support representation that preserves its intertemporal incentives; the proponent flags this risk but gives no type-level state that resolves it.
fatal: False
The mirror covers Theorem 2’s global sd-strategyproofness, local sd-strategyproofness, and ex post efficiency guarantees. It leaves Theorem 1’s sequential RSD failure and the paper’s fairness results, including Theorem 3, aside.
The strongest mirror I can defend is the paper’s Theorem 2, proved here. It establishes that ARSD is globally sd-strategyproof for any preference dynamics, while each round’s matching is ex post efficient and locally sd-strategyproof. This is a constructive mechanism result, not a runtime or complexity classification: the paper gives no named result placing a problem in P or proving it hard.
A plausible regime is repeated shift assignment across a large hospital system. Nurses share a relatively small set of complete types—preferences, qualifications, and preference-transition behavior—while the number of nurses is much larger than the number of types. Shift categories and their capacities scale with the workforce. Each nurse still receives one indivisible shift; only the type-level averages are fractional.
I would pose the continuous question as Dynamic Mass Matching Policy Synthesis. An instance gives a finite set of shift categories \(A\), a finite horizon \(H\), a finite support \(T\) of nurse types with rational masses \(\mu_\theta\), and rational per-capita capacities \(q_a\), where \(\sum_a q_a=1\). Each type specifies a strict ranking of the categories and a public finite-state transition rule for how preferences change after an assignment. At each period, agents report rankings and the mechanism observes the realized assignment history.
The requested solution is a finitely described, history-dependent policy. For every report profile and history, it gives a lottery over measurable assignments of individual nurses to categories, with mass \(q_a\) assigned to category \(a\) in each realization. It must make truthful reporting sd-dominant both in the current round and over the remaining horizon: for every nurse and every rank cutoff \(\ell\), the paper’s continuation weight \(W_i^\pi(h,o_\ell)\) under truth must be at least its value under any unilateral reporting strategy. Each realized assignment must also be Pareto efficient: no feasible reassignment weakly improves almost every nurse and strictly improves a positive mass of them. Type-level flows \(x_{\theta a}\) may be fractional, but each nurse receives an integral category.
This is recognizably the paper’s dynamic matching problem: the decision is still how to assign alternatives over time when reports affect present and future outcomes. The continuous version changes the population representation and scales the capacities with it. Under the ChoCo trichotomy, I would expect a constructive, likely Class A result for finite support and finite horizon, though Theorem 2 does not establish a polynomial-time bound for this mirror.
The scope is deliberately just Theorem 2. I would not claim it mirrors all the paper’s fairness results or its discussion of static large markets. The main weakness is substantial: ARSD tracks pairwise dominance among named agents and samples priority orderings, while the proposed instance records masses. An exact continuum policy may not preserve the finite mechanism’s incentive guarantees, especially through preference changes. The mirror is still worth asking because it retains the paper’s central strategic question in a plausible large-cohort setting; whether that question survives continuization is precisely what the result should determine.
The only anchor is Theorem 2. It gives ARSD a strategyproofness and efficiency guarantee, but it is not a complexity result: the paper neither defines a computational problem with an input encoding nor classifies its runtime. A mass-policy synthesis problem would therefore be a new mechanism-design question, not a continuous mirror of a named computational result. On ChoCo’s stated computational-complexity brief, that is the strongest objection.
There is also a real compression problem in the closest mirror. ARSD’s state includes the pairwise dominance history \(d^t_{ij}\), and its policy adjusts permutations of named agents. A type-mass distribution does not record those \(n^2\) relationships. Encoding each agent’s relationships in their type makes the support depend on the population size; replacing them with type-level transitions changes the policy and the question. The proponent’s finite-horizon, finite-state version makes the new synthesis problem more tractable to state, but those restrictions are additional modelling choices.
Still, this does not support the universal claim that no worthwhile mirror exists. Large nurse cohorts with scaled shift capacities are plausible, and the paper itself points toward sequential matching in large markets with multiple capacities. A finite-type mass model can keep each nurse’s assignment indivisible while making incentives pointwise, so strategyproofness need not become vacuous. My negative case defeats the claim that Theorem 2 is already a computational result to mirror; it does not defeat the best continuous extension of the paper’s dynamic matching problem. If ChoCo includes new mechanism-synthesis problems, that anchor survives.
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.