| paper | d4-conf-aaai-2017-0609 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; the problem belongs to \(\mathsf{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given discrete time slots and a finite support \(Q\) of types \(q=(A_q,B_q)\), each with rational mass \(\mu_q\), where \(B_q\le A_q\in\{0,1\}^m\) is its current report and true availability, decide whether a positive mass can coordinate on new reports. Choose masses \(x_{q,D}\ge 0\) for reports \(D\le A_q\), with \(\sum_D x_{q,D}\le\mu_q\); all remaining mass keeps report \(B_q\). Let \(S_j\) be the resulting average reported attendance at slot \(j\), let \(W=\arg\max_j S_j\), and let \(u_q\) be type \(q\)'s current payoff, computed from \(B_q\) and the current co-winners by the paper's maximin rule. Does there exist such an allocation with positive total deviating mass for which every report \(D\) used by positive mass of type \(q\) yields \(\min_{j\in W}D_j/S_j>u_q\), with winning-slot denominators positive?
A continuous population of teams with finite support over types \((A_q,B_q)\) and rational masses \(\mu_q\). Decision variables \(x_{q,D}\) allocate type mass among its allowed reports \(D\le A_q\); the rest retains its current report. Aggregate slot attendance determines the co-winners, and each deviating mass receives the paper's relative-attendance payoff under the maximin tie rule. Reports remain discrete; the population and coordinating coalition become continuous.
A team type can split between deviating and nondeviating mass, changing the strategic granularity and potentially erasing the discrete Set Cover selection barrier; this bounds any claim of hardness transfer but does not invalidate the explicitly defined mass-coalition question.
fatal: False
The mirror covers Theorem 3's unrestricted-coalition improvement question. It does not establish analogues of the parameterized \(\mathrm{W[2]}\)-hardness result, Theorems 1 and 2 on finding a deviation for a fixed coalition, or the Nash-equilibrium results.
The strongest mirror is the coalition-improvement question, because it keeps the paper’s strategic object intact: teams coordinate, change their availability reports, and try to improve their relative power at the winning time slots.
The anchor is Theorem 3, proved in this paper by reductions from Set Cover (the cited Set Cover parameterized-complexity fact supplies the source hardness). It says that, given an input and a strategy profile, deciding whether a coalition of size \(t\) has an improvement step is \(\mathrm{W[2]}\)-hard with parameter \(t\), even when \(a_{\max}=1\); with no restriction on coalition size, the decision problem is \(\mathrm{NP}\)-complete. Here \(a_{\max}=1\) means every true availability entry is binary. The theorem’s proof uses a Set Cover reduction for the parameterized result, and the paper gives the unrestricted-size hardness proof in Appendix A.4.
I would mirror its unrestricted-coalition question as Continuous Team-Power Improvement. An instance has \(m\) discrete time slots and a finite support \(Q\) of team types. A type \(q\) is a pair \((A_q,B_q)\): its binary true-availability vector and its current binary declared-availability vector, with \(B_q\le A_q\). The type has rational mass \(\mu_q\), with \(\sum_{q\in Q}\mu_q=1\). Including \(B_q\) in the type ensures that all teams of a type have the same current payoff.
A solution chooses, for each type \(q\), masses \(x_{q,D}\ge0\) of teams to deviate to each allowed binary report \(D\le A_q\), subject to \(\sum_D x_{q,D}\le\mu_q\). The remaining mass keeps report \(B_q\). Let \(S_j\) be the resulting average reported attendance at slot \(j\), and let \(W=\arg\max_j S_j\). Define a team’s power using \(D_j/S_j\), and its payoff as the minimum of that quantity over \(j\in W\), just as in the paper’s maximin tie rule. The initial payoff of type \(q\) is defined from \(B_q\) and the initial co-winners in the same way. The decision question is whether there is a positive total mass of deviators for whom every chosen report strictly improves that payoff. A solution is the mass allocation and reports witnessing such an improvement, with the payoff denominators positive wherever required.
This normalization preserves the finite game’s incentives: if a finite population has \(N\) teams and type masses \(n_q/N\), then \(D_j/S_j\) is \(N\) times the paper’s payoff \(D_j/(N S_j)\). Strict improvement is unchanged. The mirror therefore makes only the population continuous: slots and each team’s report remain discrete, while homogeneous teams can split by mass among deviating and nondeviating behavior.
A plausible regime is a large federation of local groups, each represented by one delegate, choosing among a short list of meeting times. Standardized work schedules and repeated poll responses can leave many delegates with the same true and current availability vectors: \(N\) teams but only \(\tau\ll N\) supported types. The one-member-team restriction in Theorem 3 is especially useful here, since binary availability is natural for an individual representative.
I expect this mirror to have a tractable fixed-\(m\) slice, but to be a candidate for continuum-specific hardness when \(m\) varies. For any fixed proposed winner set \(W\), an improving deviator must report availability at every slot in \(W\); reporting zero outside \(W\) can only lower nonwinning totals. Thus its new payoff is \(1/M\), where \(M\) is the common average attendance at the winning slots. For fixed \(W\), the mass choices and winner conditions reduce to rational linear constraints, with type eligibility determined by whether its true availability covers \(W\) and its old payoff is below \(1/M\). Enumerating \(W\) gives a direct algorithm exponential in \(m\) and polynomial in the support and bit length. Whether that search can be avoided, or whether choosing the co-winner set itself yields hardness, is the central further question. I would not predict that Theorem 3’s discrete \(\mathrm{NP}\)-hardness transfers unchanged. The fractional population may remove the integral selection logic in its Set Cover reduction; any hardness result for the mirror may need to exploit the agenda or co-winner structure afresh.
The mirror covers Theorem 3’s coalition-improvement result, especially its unrestricted-coalition \(\mathrm{NP}\)-complete case. A bounded-mass variant, with an input cap \(\rho\) on deviating population mass, would be a useful companion, but I would not equate \(\rho\) directly with the paper’s parameter \(t\) or claim the \(\mathrm{W[2]}\)-hardness transfers.
My weakest point is the change in coalition granularity. In the paper, a one-member team is indivisible; here, any positive fraction of a type may deviate. That can erase the reduction’s set-selection barrier, and a referee could regard a fractional coalition of representatives as a different strategic model. Still, the paper’s central question is precisely whether a coalition can jointly improve, and this mirror preserves the players’ information, legal reports, winners, and payoff rule. The fractional coalition is the high-multiplicity relaxation to investigate—not a claim that the discrete hardness survives.
The only substantial case against this mirror is a mismatch in what the population counts. In this paper, the players are teams: each is an autonomous strategic unit, while the people inside it are already aggregated into availability counts. In ordinary scheduling polls, there may be many attendees but only a few teams, each with its own interests and schedule. Making the attendees continuous would not create more players who can independently change a team’s report. Making the teams continuous instead requires a setting with many strategically separate, near-identical teams—a less routine regime.
That objection weakens against the best version of the mirror. A federation of local chapters could have many chapters with the same true availability and current report, each acting independently. Under the paper’s model, those chapters with the same \((A,B)\) are indistinguishable for the payoff calculation, so they form a legitimate type. The apparent vanishing of an individual team’s share can also be handled naturally: with \(N\) teams and average attendance \(S_j\), a team reporting \(D_j\) has power \(D_j/(N S_j)\). Multiplying every team’s payoff by \(N\) gives \(D_j/S_j\), preserving every strict-improvement comparison.
Theorem 3 is a real computational anchor, and its unrestricted-coalition question survives this objection. Its parameterized result is a weaker fit: a cap of \(t\) teams becomes a mass cap of \(t/N\), which tends to zero as the population grows. The Set Cover reduction also uses many distinct availability patterns, so it does not itself demonstrate a hard instance with small support. But those are limits on what this paper’s reduction carries over, not reasons the continuous question is ill-posed; the proponent explicitly leaves the hardness open.
So the negative case is weak where the universal claim matters. The paper’s usual setting gives little evidence that many teams share a type, but a plausible regime can be constructed, and the model’s own payoff definition supports it. I cannot defeat the strongest mirror without treating a genuine change in coalition granularity as disqualifying—which would rule out the high-multiplicity relaxation the programme is meant to examine.
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.