| paper | d4-conf-ijcai-2016-0688 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; the threshold decision version belongs to \(\mathrm{P}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite worker-type and job-type sets \(H,D\), strict preferences over opposite-side types and \(\varnothing\), rational masses \(a_h,b_d\) with equal total mass on each side, and rational edge weights \(w_{hd}\), compute an allocation \(x_{hd}\ge 0\) maximizing \(\sum_{h,d} w_{hd}x_{hd}\). Require \(\sum_d x_{hd}\le a_h\), \(\sum_h x_{hd}\le b_d\), and \(x_{hd}=0\) unless both types prefer each other to \(\varnothing\). For every mutually acceptable pair, define \(u_h=a_h-\sum_d x_{hd}\), \(v_d=b_d-\sum_h x_{hd}\), \(A_{hd}=\sum_{d':\,d\succ_h d'}x_{hd'}+u_h\mathbf{1}[d\succ_h\varnothing]\), and \(B_{hd}=\sum_{h':\,h\succ_d h'}x_{h'd}+v_d\mathbf{1}[h\succ_d\varnothing]\); require \(A_{hd}B_{hd}=0\).
An atomless market with finitely many complete preference types on each side and rational type masses. The decision variable \(x_{hd}\) is the mass matched between types; the objective is the linear weighted matching score used by WP rules, and stability rules out any pair of types with positive mass on both sides who would both prefer each other to their assignments.
Covers the stable-matching optimization underlying WP rules, extended to type-mass allocations. It leaves the WGM social-choice results and the paper’s sample-based learning pipeline aside.
The strongest mirror I see is the paper’s stable-matching branch, anchored by Theorem 2. It is attributed to Roth et al. (1993), so it is cited rather than proved here. For a finite preference profile \(\succ\), let \(\Omega(\succ)\) be the Boolean matchings satisfying the one-to-one capacity constraints and stability constraints: mutually unacceptable pairs cannot be matched, and for each mutually acceptable pair \((h,d)\),
\[
y_{hd}+\sum_{d'\succ_h d}y_{hd'}+\sum_{h'\succ_d h}y_{h'd}\ge 1.
\]
Let \(\tilde{\Omega}(\succ)\) replace Boolean matching variables with variables in \([0,1]\), keeping those constraints. Theorem 2 states that a matching is stable exactly when it is an extreme point of \(\tilde{\Omega}(\succ)\). The paper uses this characterization to optimize linear weights over stable matchings, including in the inference step for its structural SVM. It therefore qualifies as a formulation anchor under the question’s exception.
My proposed mirror is type-mass stable matching optimization. Take finite sets of worker types \(H\) and job types \(D\). Each type gives a complete description of the agent’s preferences over types on the other side and over remaining unmatched. Let \(a_h,b_d\) be positive rational masses, normalized so each side has total mass one, and let \(w_{hd}\) be a rational score for matching a unit of type \(h\) to a unit of type \(d\). The instance asks for an allocation \(x_{hd}\ge 0\) maximizing
\[
\sum_{h\in H,d\in D}w_{hd}x_{hd}
\]
subject to \(\sum_d x_{hd}\le a_h\) and \(\sum_h x_{hd}\le b_d\), and stability. Here stability means there is no pair of types with positive mass on both sides who would each prefer to be matched with the other type over their current assignment. More explicitly, if \(u_h=a_h-\sum_d x_{hd}\) and \(v_d=b_d-\sum_h x_{hd}\) are unmatched masses, define
\[
A_{hd}=\sum_{d':\,d\succ_h d'}x_{hd'}+u_h\mathbf 1[d\succ_h\varnothing],
\qquad
B_{hd}=\sum_{h':\,h\succ_d h'}x_{h'd}+v_d\mathbf 1[h\succ_d\varnothing].
\]
The stability condition is \(A_{hd}B_{hd}=0\) for every pair \((h,d)\). A solution is an exact optimal allocation \(x\), realizable by dividing each atomless type population into the assigned masses. For a closer match to the paper’s WP rules, the weights can be restricted to its rank-based form \(\alpha_{hd}r_h(d)+\beta_{hd}r_d(h)+\gamma_{hd}\).
A plausible regime is a large school-admissions or hiring market: many applicants and positions, but only a moderate number of complete preference and priority types. Type masses then represent population shares, while capacities scale with the market. This is high multiplicity in the relevant sense: members of a type are indistinguishable in every respect the matching problem uses. The paper’s school-choice example makes this setting natural. A fractional \(x_{hd}\) records how much of one cohort is assigned to another; it is the population-scale analogue of giving each individual one whole match.
I would expect at least fixed-parameter tractability in the number of type pairs. The stability condition is a choice, for each \((h,d)\), between the linear conditions \(A_{hd}=0\) and \(B_{hd}=0\). Enumerating those choices gives at most \(2^{|H||D|}\) linear programs, so the mirror has a direct \(2^{|H||D|}\operatorname{poly}(|H||D|,L)\) exact algorithm, where \(L\) is the bit length of masses and weights. Whether the optimum can be found in time polynomial in the type counts and \(L\) is the sharper question. A type-level polyhedral description extending Theorem 2 would put it in the tractable class; failure of such a description could expose continuum-specific hardness.
This mirror covers the weighted stable-matching optimization used by the paper’s WP rules, not its full machine-learning pipeline or the single-peaked WGM results. The paper’s distribution over preference profiles is a probability model over markets; it is not, by itself, the continuous-population mirror proposed here.
The weak point is that Theorem 2’s polytope is for named individuals in a finite one-to-one market. Aggregating agents into preference types changes the blocking condition, and the theorem does not establish that the type-mass stable set has a comparably useful polyhedral description. I think authors working on WP rules would recognize the optimization question, but they could reasonably regard the cohort-level stability model as a substantive new step rather than a consequence of their theorem.
The strongest case against starts with the result the proponent chose. Theorem 2 is a cited polyhedral characterization for a fixed, named-agent market. The paper’s own Theorems 1 and 3 characterize mechanism classes; the paper gives an SVM-based design method and experiments, but no complexity classification. A ChoCo study here would attach a new computational problem to the paper’s model, rather than continue a complexity result established by the paper.
That gap does not defeat the stable-matching mirror under the programme’s rules. Aggregating types changes the stability geometry: \(A_{hd}B_{hd}=0\) is a disjunction, not the named-agent polytope from Theorem 2. Enumerating the disjunction gives an exact \(2^{|H||D|}\operatorname{poly}(|H||D|,L)\) algorithm, leaving a real question about polynomial-time or approximation algorithms. A closer mirror could preserve the paper’s learning task too: learn type-shared WP weights from sample markets described by type masses, with loss measured between target and returned allocation masses. That is a precise computational problem, even though the paper does not already formulate it.
The social-choice branch gives a stronger objection. If a mechanism depends only on the society’s distribution \(\mu\), a single atomless agent’s report has zero effect on \(\mu\), so individual strategy-proofness becomes vacuous. Restoring individual influence requires leaving that continuum model or changing the incentive concept. This rules out a compelling direct mirror of the WGM result, but it does not remove the matching anchor.
Existing work also makes the matching regime credible. Greinecker and Kah define stability for large economies using distributions and characterize stable outcomes as limits of finite-market stable matchings; Meeks and Rastegari study stable-matching problems with repeated agent types and give parameterized algorithms. Those works do not settle weighted optimization over stable mass allocations or the paper’s learning objective, so they are support for the mirror rather than a novelty collision. ([Greinecker and Kah](https://onlinelibrary.wiley.com/doi/abs/10.3982/ECTA16228), [Meeks and Rastegari](https://arxiv.org/abs/1708.04109))
So the negative case is weak at its central burden. I can argue that this is not a direct continuization of a computational-complexity result in the paper. I cannot honestly argue that no worthwhile continuous mirror survives: the type-mass stable-matching question is coherent, and the strongest version remains open to meaningful complexity study. The stable-matching 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.