| paper | d4-conf-sagt-2021-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm{P}\)). Every \(K>0\) is feasible; for \(K=0\), feasibility holds exactly when \(x^B=x^G\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
Given finite supports of boy and girl types with rational masses summing to one on each side and strict rankings over opposite-side types, let \(x^G\) be the girl-proposing stable flow in the truthful market and \(A_g=\{b:x^G_{bg}>0\}\). For each girl type \(g\), choose strategic mass \(\lambda_g\in[0,\mu_g]\), split from its truthful mass, and have it blacklist boy types outside \(A_g\). Given a threshold \(K\), decide whether some choice with \(\sum_g\lambda_g\le K\) makes boy-proposing type-capacitated deferred acceptance on the split market return exactly \(x^G\).
A balanced market whose agents belong to finitely many preference types and carry masses. A strategic mass \(\lambda_g\) is split from each girl type and given a restricted report; the objective is to minimize total strategic mass so the resulting boy-proposing deferred-acceptance flow equals the truthful market’s girl-optimal flow.
It mirrors the winning-coalition characterization and minimum-coalition objective through strategic mass. It leaves the random-preference results in Theorems 5.1 and 5.2, random coalitions, and the discrete extremal constructions unaddressed.
The paper’s strict anchor list is thin: no numbered theorem states that the minimum winning coalition problem is NP-hard, in P, or in another complexity class. The closest substantive lead is Theorem 3.1, proved here: a set of girls is winning if and only if it contains at least one girl from each minimal rotation in the rotation poset. Section 3.2 says this characterization gives polynomial-time recognition and minimum-coalition algorithms, using rotation algorithms cited from Gusfield [8]. So it supports a tractability mirror, though the theorem itself is a structural characterization rather than a formal complexity-class statement. Theorem 5.1’s expected coalition size and Theorem 5.2’s random-coalition bound are probabilistic results, not complexity anchors.
My best positive candidate is Type-Mass Winning Coalition. Its instance has finite sets of boy and girl types, binary-rational masses summing to one on each side, and a strict ranking of opposite-side types for each type. A matching is a nonnegative flow \(x_{bg}\) with row and column sums equal to the input masses. It is stable if there is no pair \((b,g)\) for which both
\[
\sum_{g':\,g\succ_b g'}x_{bg'}>0
\quad\text{and}\quad
\sum_{b':\,b\succ_g b'}x_{b'g}>0.
\]
Let \(x^G\) be the outcome of girl-proposing, type-capacitated deferred acceptance on the truthful market. For each girl type \(g\), choose a strategic mass \(\lambda_g\in[0,\mu_g]\). That mass blacklists every boy type outside \(A_g=\{b:x^G_{bg}>0\}\); the remaining mass reports truthfully. Given a threshold \(K\), decide whether there is a vector \(\lambda\) with \(\sum_g\lambda_g\le K\) such that boy-proposing type-capacitated deferred acceptance on the split reported types returns \(x^G\). A solution is such a mass vector and its resulting flow.
The regime is a large placement market: many applicants and positions, but relatively few preference cohorts, each cohort sharing its full ranking over the opposite-side types. The type masses describe fractions of the market, and the decision variable is the fraction of each girl type that acts strategically. This seems recognizable to the authors as a population-level version of their coalition question, with type flows and fractional type allocations as the co-modification needed for a continuum.
My tentative prediction is Class A: if the rotation characterization has a type-mass counterpart, the problem may reduce to finite-support structure plus continuous optimization. That is a research hypothesis, not a consequence of this paper. The main risk is that strategic mass and type-level stability destroy the discrete rotation structure; then the action space may introduce new hardness, or the mirror may fail the authors’ recognition test.
That is also the weakest point. In Theorem 3.1, rotations are sets of named girls. In a continuum, a rotation may split across types, and requiring positive mass from each rotation can make the infimum of strategic mass zero. The paper does not establish a fractional rotation theorem or a nonzero mass threshold. This mirror therefore covers the structural winning-coalition result only; it does not claim to mirror the random-preference results, whose individual-level random rankings and random subsets do not directly become a moderate-support mass model.
The strongest objection is that Theorem 3.1 is not a complexity result. It characterizes a winning coalition by the minimal rotations it must intersect; Corollary 3.2 turns that into a formula for the minimum coalition size. Section 3.2 then says the resulting problems have \(O(n^2)\) algorithms. But the paper gives no numbered theorem classifying the complexity of a computational problem. Its main numbered results are structural and probabilistic. The proponent’s decision problem is therefore a plausible new research question, but it is not clearly a continuous mirror of a computational result this paper establishes.
The proposed type-mass model also changes what the coalition condition means. In the paper, a coalition wins by including at least one named girl from each minimal rotation. If a continuum version keeps that “hit every rotation” condition and the rotation sets have positive measure, arbitrarily small positive mass can hit each one. The minimum mass may then have infimum zero, with no smallest coalition. Requiring the exact girl-optimal aggregate flow instead can avoid that degeneracy, but then the question is how much strategic mass shifts a fractional matching—not the paper’s rotation hitting-set characterization.
The strongest repair is the one the proponent sketches: use a plausible large matching market with finitely many preference cohorts, allow a cohort to split into truthful and strategic mass, and ask for the least strategic mass that makes boy-proposing deferred acceptance return the girl-optimal flow. That is a recognizable computational question, and stable matching does have credible high-multiplicity settings. But it requires preferences over types and aggregate fractional allocations, whereas this paper ranks named participants and its rotations rearrange named partners. Those changes may be sensible, as the programme permits, but they supply the substance of a new continuum matching model rather than a translation of the theorem’s computation.
The random results do not provide a firmer computational anchor. Their random preferences are permutations of named individuals, and their random coalitions are samples of named girls. In an atomless version, a random subset of positive density intersects every positive-measure rotation with probability one; if rotations have measure zero, the intersection criterion has no mass cost. Either way, the discrete sampling phenomenon does not directly define a useful mass-based quantity. That is a limitation of the proposed bridge, not an argument that a changed answer is undesirable.
So the negative case is strongest on what this paper actually contributes: it does not establish a named complexity result for the continuous programme to mirror, and the natural extension of its central characterization either loses the one-agent trigger or becomes a different aggregate-control problem. The case is not airtight. A finite-cohort matching model with a carefully defined strategic-mass objective could still be worthwhile, and I cannot honestly rule out every scenario.
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.