| paper | d4-conf-atal-2011-0331 |
| 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 in \(\tau,k,L\) by setting \(x_{tj}=\mu_t/k\). A succinct solution is computable in polynomial time in \(L\); explicit output necessarily depends on \(k\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a finite type set \(T\), rational masses \(\mu_t\), symmetric rational weights \(w_{ts}\), an integer \(k\ge2\), and a rational threshold \(\theta\in[0,1)\), find a rational allocation \(x_{tj}\ge0\) to at most \(k\) teams with \(\sum_j x_{tj}=\mu_t\). Define \(U_t(j)=\sum_s w_{ts}x_{sj}\) and \(q_t(j)=\frac{\sum_{s:w_{ts}<0}x_{sj}}{\sum_{s:w_{ts}\ne0}x_{sj}}\), taking \(q_t(j)=1\) when the denominator is zero. Require that for every type \(t\) with \(x_{tj}>0\), no available destination \(\ell\)—including an empty team if fewer than \(k\) teams are occupied—has both \(U_t(\ell)>U_t(j)\) and \(q_t(j)\ge\theta\).
A nonatomic hedonic coalition game with at most \(k\) teams: \(x_{tj}\) is type \(t\)'s mass in team \(j\), and \(U_t(j)=\sum_s w_{ts}x_{sj}\) is its utility. A type may infinitesimally switch teams when the vote-out rule permits leaving its current team; the task is to find a stable allocation.
The mirror covers Theorem 2's \(k\)-VoteOut search problem. It does not cover Theorem 1, the polynomial-time results, or unrestricted VoteOut.
The strongest mirror I believe in is for a large organization that repeatedly forms project teams: a workforce of, say, hundreds of thousands of people, drawn from a few dozen roles with stable, role-based affinities. A type is a person’s complete interaction profile: their role and their symmetric utility weight \(w_{ts}\) toward every type \(s\). People of the same type are interchangeable for the model, and the population is described by rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\). This is a narrow regime, but a plausible one: \(n\) can be much larger than the number \(\tau\) of distinct types.
For a team \(j\), let \(x_{tj}\) be the mass of type \(t\) assigned to it. A member of type \(t\) gets utility \(U_t(j)=\sum_s w_{ts}x_{sj}\). This is the paper’s sum-of-peer-weights utility, divided by population size; that positive scaling preserves preferences. Each person still belongs to one team. It is the mass of an identical type that can be divided across teams.
My lead anchor is Theorem 1, proved in this paper: *VoteIn is PLS-complete for every voting threshold \(0\le T_{\mathrm{in}}<1\).* The proof reduces from OneEnemyPartyAffiliation*, whose PLS-completeness the paper attributes to Gairing and Savani [17, Corollary 1].
The corresponding problem is Type-Mass VoteIn Stability. Given \(T,\mu,W\) and a rational threshold \(\theta\in[0,1)\), find a stable assignment of type mass to teams. For each type \(t\) in a team \(j\), and each possible destination \(k\), define the entrant approval fraction as
\[
a^{\mathrm{in}}_t(k)=
\frac{\sum_{s:w_{ts}>0}x_{sk}}{\sum_s x_{sk}},
\]
taking it to be \(1\) for an empty destination, as the paper’s “no edge” exception requires. Stability means there is no \(t,j,k\) with \(x_{tj}>0\), \(U_t(k)>U_t(j)\), and \(a^{\mathrm{in}}_t(k)\ge\theta\). A type can also move to a fresh singleton team. To represent the continuum analogue of individuals who remain single, the output may include residual singleton mass: each such agent belongs to a measure-zero coalition and has utility \(0\). A solution is a finite list of positive-mass team compositions, plus any such residual mass, with rational entries. Bounding the number of listed teams, or proving that this representation always suffices, is an initial structural question for the mirror.
This asks the same question as the paper—whether there is an improving, vote-permitted unilateral move—but for type masses. The natural potential is \(\Phi=\tfrac12\sum_j\sum_{t,s}x_{tj}x_{sj}w_{ts}\). Any attained maximum is stable against strictly profitable infinitesimal moves, so the potential gives a route to existence and perhaps computation. It does not by itself provide an efficient algorithm for finding that maximum or a stable point.
A second, distinct anchor is Theorem 2, also proved here: *\(k\)-VoteOut is PLS-complete for every voting threshold \(0\le T_{\mathrm{out}}<1\) and every \(k\ge2\).* The theorem’s reduction proceeds through OneEnemyNashStable and begins from the OneEnemyPartyAffiliation benchmark discussed in the paper.
Its mirror, Type-Mass \(k\)-VoteOut Stability, has the same type masses and utility matrix, but assigns all mass to at most \(k\) teams. Define the fraction of type \(t\)’s negative-affinity mass in its current team \(j\) by
\[
a^{\mathrm{out}}_t(j)=
\frac{\sum_{s:w_{ts}<0}x_{sj}}{\sum_s x_{sj}},
\]
with the paper’s no-edge exception treated as approval. The assignment is stable if no type \(t\) with mass in \(j\) has a strictly better destination and \(a^{\mathrm{out}}_t(j)\ge T_{\mathrm{out}}\). If fewer than \(k\) teams are occupied, forming a fresh team is also a possible move. The output is at most \(k\) rational team-composition vectors summing to \(\mu\). A fixed team cap fits settings where the organization has a prescribed number of project teams.
For both mirrors, I would tentatively investigate continuum-specific hardness (Class C). The type-interaction matrix and the choice of coalition compositions still contain combinatorial structure, so a population continuum need not remove every hard part. But I would not claim that either PLS-hardness result transfers: the paper’s reductions do not prevent a type’s mass from splitting across teams. That may dissolve the discrete local-search obstacle. Whether a potential-based method then yields a polynomial algorithm, and whether hardness survives as \(\tau\) grows, are the main questions. The paper’s scope mirrored here is its voting-based search results; I am not claiming to mirror its polynomial cases or the open unrestricted VoteOut problem.
The weakest point is that the paper’s PLS-completeness concerns finite improving moves, while the proposed model uses infinitesimal deviations and can split each type across teams. That is a substantive change in the search landscape, not a cosmetic relaxation. The positive case is that the scenario makes those type masses meaningful, preserves the same utility and voting rules, and puts the computational question—finding a stable coalition structure—squarely within the authors’ problem.
The strongest negative case is that the two theorems are about *individual deviations*, and their PLS results do not pass cleanly to a society with divisible mass. In an atomless population, one person has measure zero. Their move changes neither team’s composition, utility averages, nor vote fractions. The finite game’s improvement step—and thus the search landscape behind PLS—disappears. Moving a positive mass \(\varepsilon\) restores a changing state, but now a block of agents moves together. That is a different deviation concept.
For Theorem 1, the best repair is the proponent’s type-level equilibrium: no type present in a team has a profitable, vote-permitted alternative. This is a coherent population question, and maximizing the stated potential can establish existence. But it does not preserve the theorem’s computational question: the potential’s existence argument supplies no algorithm, while finding a stable point in a continuous, potentially nonconvex space is a new problem. Keeping moves at one-person granularity instead restores the finite high-multiplicity game, with a discrete mass grid and individual transitions; it no longer tests the atomless mirror.
For Theorem 2, capping the number of teams at \(k\) makes the output finite-dimensional, but leaves the same gap. A single person’s departure does not change the vote-out fraction in the continuum. A positive-mass departure can change it, but asks whether a bloc can leave, rather than whether one player can. The pointwise-equilibrium repair remains possible, and for fixed \(k\) and a small number of types it may even be approachable as a finite-dimensional problem. When the number of types grows, its complexity is open; the paper’s PLS-completeness does not settle it.
The role-based workforce makes these models plausible enough that I cannot dismiss them on multiplicity grounds. Nor is “already done” a sound objection: recent work studies majority-consent stability in finite additively separable hedonic games, and earlier work studies convergence in finite anonymous and fractional hedonic games, but neither answers the continuous-population computational question. [Brandt, Bullinger, and Tappe (2024)](https://www.sciencedirect.com/science/article/pii/S0004370224000961), [Brandt, Bullinger, and Wilczynski (2021)](https://ojs.aaai.org/index.php/AAAI/article/view/16658).
So the negative case is that neither anchor yields a direct continuation of its PLS result: the continuous model changes the deviation and search objects. That is a real warning about what these mirrors can claim, but it does not establish that the repaired equilibrium problems are unworthy. The proposed type-mass models still ask computational questions about a continuous population, and their difficulty is not known in advance. I cannot honestly defend the universal claim that no worthwhile mirror exists in any scenario; these two anchors survive that stronger challenge.
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.