| paper | d4-conf-ecai-2025-0400 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact computation of the aggregate cohort serial dictatorship outcome is polynomial-time solvable in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given worker types \(T_W\) and firm types \(T_F\), rational masses \(\mu_i\) and \(\nu_j\) on a common population scale, a strict preference order for each type over opposite-side types and \(\bot\), and a fixed order over \(T_W \cup T_F\), compute the aggregate matching produced by cohort serial dictatorship. At each type's turn, its remaining mass takes the highest-ranked available opposite-side mass in preference order, pairing up to the smaller residual mass; any remainder assigned to \(\bot\) leaves the process. Output the flows \(x_{ij}\) and unmatched masses, with running time polynomial in \(|T_W|+|T_F|\) and the input bit length.
A large placement market with repeated applicant and employer-slot types. Each type has a rational mass and common public context and preference order; a fixed priority order processes whole cohorts. The decision variables are aggregate pair flows \(x_{ij}\) and unmatched masses. There is no optimization objective: the task is to compute the deterministic outcome.
For arbitrary paper instances, encoding individual priority positions or distinctions among named partners in types can make the support size grow with the headcount; the mirror relies on the restricted cohort-priority regime.
fatal: False
The mirror covers Proposition 3's exact SD outcome computation and its running-time result. It leaves the context-based ranking learner, training from examples, and the paper's experimental claims unmirrored.
My strongest honest case is a narrow mirror of the paper’s SD outcome computation, not of its full learning framework. The paper contains no NP-hardness result. Its useful computational anchor is Proposition 3, proved in Appendix B: given workers’ and firms’ preference tensors \(P_W,P_F\) and a ranking matrix \(R\) encoding an order \(r\), TSD outputs exactly the matching matrix produced by SD on that instance with ranking \(r\). Section 5.2 states that this computation takes \(O(n^4)\) time when \(n\ge m\). The proposition proves correctness; the accompanying bound supplies the polynomial-time result.
I would mirror it with Continuous Cohort Serial Dictatorship Outcome. An instance gives finite sets of worker and firm types, each with a nonnegative rational mass. A worker type specifies its public context and its common strict preference order over firm types and the unmatched option; a firm type specifies the corresponding information on the other side. The input also gives a fixed priority order over the type cohorts. The question is to compute the unique aggregate matching produced by serial dictatorship in that order.
The procedure is the type-level greedy version of SD. When a cohort gets its turn, its still-unmatched mass chooses its most preferred available opposite-side type, in preference order, stopping at the unmatched option. Matched mass is removed from both cohorts; any mass choosing the unmatched option is no longer available to later cohorts. The solution is a rational flow \(x_{ij}\), where \(x_{ij}\) is the mass matched between worker type \(i\) and firm type \(j\), together with unmatched masses. Every unit of mass represents people who each receive one partner or remain unmatched; fractional entries describe population totals, not fractional partners for individuals.
This should be tractable. With the type order supplied, scan each type’s preference list once, updating the remaining masses. For \(\tau_W\) worker types and \(\tau_F\) firm types, this takes \(O(\tau_W\tau_F)\) type-level operations, with rational arithmetic polynomial in the input bit length. This is a high-multiplicity computation: the runtime depends on the number of distinct supported types, not the headcount represented by their masses.
A plausible regime is a large centralized placement market with repeated applicant and employer-slot profiles: for example, tens of thousands of applicants and slots, but hundreds of recurring combinations of public priority category and ranked program types. Employers’ slots likewise share preference types. The mass of a type is its fraction of applicants or slots. In this setting, cohort priority and type-level rankings can describe the allocation rule directly.
This is a recognizable continuous version of the subproblem the authors actually compute: execute serial dictatorship on reported preferences and a predetermined priority order. It does not mirror NeuralSD’s training from example matchings, its attention-based ranking learner, or the paper’s experimental claims. The continuous question is an execution problem, not an optimization problem with a separate objective.
The soft spot is that the paper orders named agents, while this mirror orders cohorts. A block priority rule and preferences over types are a real restriction: if priority interleaves otherwise identical agents with other cohorts, or agents care about distinctions among named partners inside a type, this aggregate procedure may change the outcome. And although the paper proves SD is strategy-proof for a fixed individual ranking in Proposition 1, this outcome-computation mirror does not by itself establish a continuous strategy-proofness theorem for individual deviations. I would present it as a credible, tractable mirror of Proposition 3’s computational kernel, not as a mirror of the whole paper or as evidence that any discrete hardness dissolves.
The strongest negative case is a scope mismatch around Proposition 3, the sole anchor raised. It proves that TSD returns the exact matching produced by SD on a finite, named-agent profile; the paper gives an \(O(n^4)\) bound for that implementation. Its input contains each agent’s preferences over named agents, and its output records which particular pairs are matched.
Grouping people by context and preference generally loses information needed for that output. Preserving it requires adding each agent’s priority position to their type; with an arbitrary SD order, that can make the support size \(\tau\) grow with \(n+m\). The proposed cohort version avoids that by ordering whole types in blocks. It is a coherent tier-priority rule, but it agrees with the paper’s SD computation only under substantive restrictions: cohort members must share the relevant preferences, and their priority positions must behave as a block. The paper instead ranks every agent and gives agents strict preferences over individual partners. The cohort algorithm therefore answers a related question about a different mechanism.
A stronger continuous proposal could use a priority score over contexts and process an atomless population in score order. That could yield a useful fluid matching model. To mirror Proposition 3, though, it would need a rule assigning individual partners and a proof that the fluid process corresponds to the paper’s named-agent SD. Aggregate flows alone cannot recover the paper’s matching matrix or its example-matching loss. Defining the individual allocation and handling ties could make a worthwhile new model; it would not establish a continuous version of the result Proposition 3 proves.
The paper’s other computational statement, Proposition 6, bounds the cost of computing the ranking block from a finite list of contexts. A mass-weighted attention model over a distribution of contexts is possible, but it changes that computation too. The paper gives no complexity result for training, convergence, or learning from a distribution of examples that such a mirror could carry over.
This is a limited case against the mirror, not a proof that no useful continuous matching model exists. Cohort-based or fluid serial dictatorship may be worthwhile in its own right. The negative case is strongest when asking whether either model is a population relaxation of this paper’s computational results; it is weak against the broader claim that an author would recognize one of them as a worthwhile extension.
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.