| paper | d4-conf-ijcai-2017-0283 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given rational mass distributions \(\mu_M\) and \(\mu_W\) over finite sets of strict ranking types, with a marked female submass \(\alpha>0\) sharing true ranking \(t\), find a common reported ranking \(r\) maximizing the cohort's average true utility under mass deferred acceptance, while all other agents report truthfully. Can an optimal report always be chosen so that the same cohort-to-male-type allocation flow results from changing \(t\) only by promoting the cohort's second male type with positive proposal flow to immediately below its first?
Use finite ranking types with rational population masses and a marked cohort of mass \(\alpha\), splitting its true type when needed. The cohort chooses one reported ranking; a stable mass matching records flows \(x_{Cj}\) from the cohort to male types \(j\), and its objective is \(\alpha^{-1}\sum_j x_{Cj}u_t(j)\), where \(u_t(j)\) is utility under its true ranking.
In a mass deferred-acceptance run, the cohort may receive positive proposal flow from several male types, so the individual second-proposer normalization may not preserve the cohort's full allocation flow.
fatal: False
The mirror concerns Theorem 4's report normalization; it leaves Theorems 3 and 5 aside and does not provide an algorithm for finding an optimal report.
I can’t make a rubric-compliant positive case from this paper: it has no numbered result asserting that a problem is in P, NP-hard, or otherwise classifying its computational complexity.
The nearest results are Theorems 3, 4, and 5, proved in this paper. Theorem 3 says that a woman’s optimal permutation manipulation of men-proposing Gale–Shapley produces a matching stable under the true preferences. Theorem 4 says that any optimal manipulation has an equivalent report yielding the same partner, formed by promoting the second man who proposes to her to just after the first. Theorem 5 says that for this inconspicuous optimal report, every matching stable under the manipulated preferences is also stable under the true preferences. These are substantive structural results, but none classifies a computational problem’s complexity. The \(O(n^3)\) algorithm mentioned in the paper is attributed to Teo et al. and appears as related work, not as a numbered result of this paper.
A possible research lead would be a continuum matching market with finitely many preference types and a positive mass of identical women acting as a strategic cohort. The cohort could choose a reported ranking to maximize its members’ average partner under continuum deferred acceptance; one could ask whether optimal reports preserve stability under true preferences. But that changes the paper’s single-woman problem into a cohort problem. If the manipulator remains one person in an atomless population, her report has zero mass and cannot affect the aggregate matching. The paper’s theorems do not establish that the cohort version inherits their conclusions.
So the paper offers an interesting direction for a new continuous model, but no eligible anchor for the requested mirror case.
The strongest case against starts with a gap the proponent identifies correctly: this paper proves no numbered result classifying the complexity of a computational problem. Theorems 3–5 are structural claims about a single woman’s manipulation and stability. The algorithmic claims in the text are attributed to earlier work, including Teo et al.’s \(O(n^3)\) algorithm. That makes these theorems poor anchors for ChoCo’s computational programme.
The best rescue for Theorem 3 is a positive-mass cohort of identical women who coordinate on one reported ranking and maximize their average partner. A unilateral manipulator cannot simply be carried into an atomless society: her mass is zero, so the aggregate deferred-acceptance outcome does not encode her individual assignment. Giving her a distinguished atom requires extra structure beyond a society represented solely by its type distribution. A cohort avoids that degeneracy, but its report changes the market at positive mass. The question then concerns coalition manipulation, rather than the single-agent result proved here. The paper mentions coalition manipulation as related work and future work, so this is a plausible research direction; it still supplies no computational result about the cohort problem.
Theorem 4’s inconspicuousness claim has the same problem. Promoting one man in a ranking is a finite combinatorial property of an individual report. For a cohort, every member could make that same edit, but the theorem does not establish anything about the cohort’s average gain or the complexity of finding its best report. Measuring inconspicuousness by the fraction of society that changes its report would require allowing subcohorts to deviate, which introduces a different coalition-selection problem.
Theorem 5 could inspire a question about whether the stable allocations under a cohort’s report are contained among those stable under its true preferences. That would require defining a continuum stable-allocation correspondence, likely over fractional flows between types. It may be a sound mathematical question, but the theorem is a structural set-inclusion result, not a computational classification. Asking for an algorithm to check the inclusion would be a new computational problem layered onto it.
So I would reject these as mirrors of the paper’s computational contribution. The negative case has a real weak point: a high-multiplicity coalition version could be a worthwhile ChoCo problem, especially given the paper’s own discussion of coalition manipulation. I cannot honestly rule out that version in every plausible scenario. But it would make the paper a motivation for a new problem, rather than provide the computational result the proponent was asked to mirror.
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.