| paper | d4-conf-ijcai-2021-0063 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Corollary 2
Given finite supported proposer and receiver type sets \(I,J\), positive rational masses \(a_i,b_j\) each summing to \(1\), strict rankings over opposite-side types, and designated positive-mass types \(i^\star,j^\star\), compute a strict ranking reported by all of type \(i^\star\) and the resulting rational fluid deferred-acceptance matching \(x\). In each round, unheld proposer mass advances to its next ranked receiver type, and each receiver type holds its highest-ranked incoming mass up to capacity \(b_j\), rejecting excess. Minimize \(S_{j^\star}(x)=\sum_i x_{ij^\star}s_{j^\star}(i)/b_{j^\star}\), subject to \(R_{i^\star}(x)=\sum_j x_{i^\star j}r_{i^\star}(j)/a_{i^\star}\le R_{i^\star}(x^0)\), where \(x^0\) is the truthful fluid deferred-acceptance outcome; determine whether this exact optimization is solvable in \(\operatorname{poly}(|I|+|J|,L)\) time, for input bit length \(L\).
A balanced market has rational masses \(a_i,b_j\) on fully specified preference types and a mass-valued matching \(x\). Type \(i^\star\) makes one common reported ranking; its per-capita expected rank must not worsen from truthful fluid deferred acceptance, while the per-capita expected rank of target type \(j^\star\) is minimized.
The type-level no-regret condition protects average expected rank, so it can allow some cohort members to lose while others gain; this departs from the paper's individual guarantee and remains the main semantic cost of the mirror.
fatal: False
The mirror covers Corollary 2 and its analogous with-regret variant from Corollary 4; it does not carry over the paper's stability results or empirical findings.
My strongest honest case is a type-cohort extension of the paper’s manipulation problem. Consider a large applicant–opening market with many agents but relatively few recurring preference types: each type specifies a strict ranking over the other side’s types and every other feature relevant to matching. Let the supported proposer types be \(I\), the receiving-side types be \(J\), and their rational masses be \(a_i\) and \(b_j\), each summing to \(1\). A type-mass version of deferred acceptance lets unmatched mass propose in its type’s order; each receiving type holds mass up to its capacity, keeping the proposals it ranks highest. The outcome is a matching matrix \(x\), where \(x_{ij}\) is the mass of type \(i\) matched to type \(j\).
The scenario has many agents relative to \(|I|+|J|\), such as recurring placement markets where many applicants and one-slot openings share preference templates. The target is a positive-mass receiving-side cohort \(j^\star\); its accomplice is a positive-mass proposer-side cohort \(i^\star\). The accomplice type submits one common altered ranking. A single agent’s action would have vanishing influence in an atomless market, so this mirror makes the accomplice a cohort. That is a substantive, but recognizable, population-level extension of the paper’s setup.
The lead anchor is Corollary 2. In the paper’s fixed-pair problem, given the preference profile and a designated manipulating pair \((m,w)\), an optimal no-regret accomplice manipulation can be computed in \(O(n^3)\) time. This corollary is proved in the paper: its algorithm tests the relevant single-woman promotions and runs deferred acceptance for each. It is an algorithmic result, not a citation to earlier work.
The corresponding question, No-Regret Type Accomplice Manipulation, is: given the rational type masses, true rankings, designated types \(i^\star,j^\star\), and their truthful type-mass DA outcome \(x^0\), find a strict reported ranking for \(i^\star\) and the resulting DA matching \(x\). For type \(i\), let \(r_i(j)\) be its rank of type \(j\); for type \(j\), let \(s_j(i)\) be its rank of type \(i\). Define the per-capita average ranks \(R_i(x)=\sum_j x_{ij}r_i(j)/a_i\) and \(S_j(x)=\sum_i x_{ij}s_j(i)/b_j\). The report must satisfy \(R_{i^\star}(x)\le R_{i^\star}(x^0)\), and among such reports it must minimize \(S_{j^\star}(x)\). A solution is the optimal report and its exact rational matching matrix. The complexity question is whether this can be solved in \(\operatorname{poly}(|I|,|J|,L)\) time, where \(L\) is the input bit length and only supported types are listed.
I expect Class A, conditional on a type-mass analogue of the paper’s structural simplification: if an optimal no-regret report can be reduced to promoting one receiving type, testing the \(|J|\) candidates and running type-mass DA would give a polynomial algorithm. The further question is whether this one-promotion property survives when a cohort can split fractionally across receiving types.
The second anchor is Corollary 4, also proved in the paper. For the same fixed-pair problem but allowing accomplice regret, an optimal manipulation strategy can be computed in \(O(n^3)\) time. Its corresponding With-Regret Type Accomplice Manipulation problem has the same input, type-mass DA semantics, and average-rank objective, but removes the constraint \(R_{i^\star}(x)\le R_{i^\star}(x^0)\). Its solution is again an optimal report and matching matrix, with complexity measured in \(|I|,|J|,L\). I also expect Class A: the paper proves a single-promotion structural result in the with-regret case too. The open issue is again whether that structure survives fractional type-level matches.
These mirrors cover the paper’s two polynomial-time manipulation results. The paper gives no named hardness result for accomplice manipulation, so the downstream question here is whether tractability survives population modeling, not whether a hardness result dissolves.
The weakest point is the semantic change: the paper’s strategic actors are one woman and one man, while this mirror gives a whole type a common report and evaluates welfare by average rank. The average no-regret constraint can permit losses to some cohort members offset by gains to others; that is not the paper’s individual no-regret guarantee. The case rests on the cohort scenario being a sensible market analogue: deferred acceptance, proposer-side misreporting, a receiving-side beneficiary, and the accomplice’s regret remain central, while type masses make the market’s scale and aggregate welfare explicit.
The paper has two genuine computational anchors: Corollary 2, which computes an optimal no-regret accomplice manipulation in \(O(n^3)\), and Corollary 4, which does the same when regret is allowed. The strongest objection to both is that the strategic actors are individual agents. In an atomless market, one man’s changed ranking has zero mass, and one woman’s improved match is not an aggregate outcome. So the literal continuous versions of both corollaries degenerate: the accomplice cannot move the matching, and the target has no positive-mass welfare to improve. Continuous DA itself is well defined in established continuum matching models; that supplies a mass-valued matching outcome, but does not restore the influence of a single agent ([Azevedo and Leshno](https://www.aeaweb.org/conference/2012/retrieve.php?pdfid=90), [Arnosti](https://arxiv.org/abs/2205.12881)).
That objection applies to both anchors, but it does not defeat the proponent’s cohort repair. Giving a positive-mass proposer type one shared report restores influence, and a receiving type’s assignment can be read as a lottery for its otherwise indistinguishable members. Average rank is a defensible objective for that lottery, though a rank-distribution or stochastic-dominance formulation would make the ordinal interpretation cleaner.
The more serious objection is that this repair changes the strategic unit. Corollaries 2 and 4 concern one accomplice acting for one woman; the cohort version has a bloc of accomplices acting for a positive-mass beneficiary group. A cohort-level no-regret constraint is therefore a group welfare condition, not the paper’s individual guarantee. But this is not a clean basis for rejecting the mirror: the paper itself names multiple accomplices and coalition manipulation as future work. A coordinated cohort is a plausible high-multiplicity version of that open direction, and testing whether the one-promotion structure survives fractional assignments is a real computational question.
So the negative case is strongest against a *literal* mirror of either corollary: unilateral manipulation disappears at zero mass. It is much weaker against the best repaired mirror. I cannot honestly argue that every sensible population-level version fails; the cohort problem changes the unit of agency, but the paper gives reason to think its authors would recognize that extension as relevant.
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.