| paper | d4-conf-atal-2016-0151 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard; polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\). A deterministic algorithm runs in \(2^{2^{O(\tau)}}L^{O(1)}\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a finite set of complete peer-value types \(T\), rational population masses \(\mu_t\) summing to \(1\), and rational values \(a_{ts}\), define \(u_t(q)=\sum_{s\in T}a_{ts}q_s\) and \(g_t=\max\{0,u_t(\mu)\}\). Does there exist a finite family of coalition mass vectors \(q^j\ge 0\) such that \(\sum_j q_t^j\le\mu_t\), every type \(t\) with \(q_t^j>0\) satisfies \(u_t(q^j)\ge g_t\), and any unassigned mass belongs only to types with \(g_t=0\) and is assigned to singleton agents?
A continuous population is a distribution \(\mu\) over complete peer-value types. Each coalition is described by its type-mass vector \(q\), giving type \(t\) utility \(\sum_s a_{ts}q_s\); its threshold is the better of singleton utility \(0\) and whole-population utility. Population mass may be divided among teams, while each individual still belongs to one team.
The mirror applies when role-based peer-value profiles remain few and team compositions are meaningfully described by mass; the proposed workforce scenario is plausible, but its prevalence is not established.
fatal: False
The mirror covers the existence result in Theorem 7; Theorem 6 establishes that grand-coalition and max-min fairness coincide in ASHGs. It leaves aside the threshold-computation results, other fairness relations, and the price-of-fairness results.
The strongest mirror is the paper’s existence question for grand-coalition fairness. Theorem 7, proved in this paper, says that GRAND-COALITION-EXIST and MAX-MIN-EXIST are NP-complete for additively separable hedonic games: given such a game, decide whether it has a coalition structure satisfying the relevant fairness notion. The authors prove membership in NP and reduce from PARTITION. Theorem 6 shows that the two fairness notions coincide in additively separable hedonic games, so the theorem supplies one strong anchor for the shared existence question.
Call the continuous problem Grand-Coalition-Fair Mass Partition. Its input is a finite set \(T\) of types, rational masses \(\mu_t\ge 0\) summing to \(1\), and rational values \(a_{ts}\). A type is a complete peer-value profile: two agents of type \(t\) value every type \(s\) alike. A coalition containing mass vector \(q\) gives each of its type-\(t\) members normalized utility
\[
u_t(q)=\sum_{s\in T}a_{ts}q_s.
\]
The grand-coalition threshold for type \(t\) is \(g_t=\max\{0,u_t(\mu)\}\), corresponding to the better of being alone and joining everyone.
A solution is a family of coalition mass vectors \(q^S\), one for each selected nonempty support \(S\subseteq T\). It must satisfy \(q_t^S>0\) exactly for \(t\in S\), \(\sum_S q_t^S\le\mu_t\), and \(u_t(q^S)\ge g_t\) for every \(t\in S\). Any leftover mass of type \(t\) is assigned to singleton agents and is allowed only when \(g_t=0\). The family can be finite and rational: in any measurable partition, positive-mass coalitions are at most countable, and coalitions with the same type support can be joined while preserving fairness, since each participating type’s utility from each such coalition is at least its nonnegative threshold. Thus the question has a concrete witness: coalition compositions and the residual singleton mass.
A plausible regime is a large project platform or workforce repeatedly forming teams from a much larger pool of workers than there are complete peer-value profiles. For instance, many workers may share a specialization and the same valuations toward each other specialization. Here \(\mu_t\) means the fraction of the population in type \(t\), and \(q_t^S\) the fraction assigned to a particular team. Dividing finite-population additive utilities by population size preserves their preference ordering and leads to the stated integral utility in the limit. The model keeps the paper’s question—whether a locally fair coalition structure exists—while making each type’s population divisible.
I tentatively expect this mirror to be Class A, with its tractability depending on the pricing or support-selection problem over coalition compositions. The PARTITION reduction assigns each item player wholly to one of two coalitions; the corresponding mass can split here, so that reduction does not establish hardness for the mirror. A natural prover’s task is to find a polynomial-time formulation and algorithm in \(\tau\) and the input bit length, or to identify the obstruction in selecting admissible coalition supports.
The soft spot is that divisibility alone does not make the existence question an LP: coalition support choices may retain hard combinatorics, and exponential support enumeration would not give the desired polynomial bound. Still, the anchor is unusually well aligned with the mirror: the theorem concerns fair coalition structures in additively separable hedonic games, and the continuous version retains the same fairness threshold and partition decision. The case covers Theorem 7’s existence result, not the paper’s other results on threshold computation or price of fairness.
The strongest case against the proposed mirror is that the workforce story needs a narrow regime: many workers must share the same value toward every worker type, and the fairness question must concern teams large enough for their composition to be measured as population mass. In many team-formation settings, workers have idiosyncratic complementarities and teams are small. Then either the “complete types” proliferate until \(\tau\) is close to the number of workers, or the mass model stops describing the teams people actually form.
That objection does not defeat the better version of the mirror. A large workforce with role-based peer values is coherent: workers of the same type can be indistinguishable for the model’s purposes, while each worker still belongs to one team. The continuous question—whether the population can be partitioned into teams meeting each type’s grand-coalition threshold—remains well-defined and recognizable as the paper’s fairness-existence question. Theorem 7 gives it a named computational anchor.
The paper’s PARTITION reduction does not carry over just by replacing players with masses: its item players are indivisible, whereas type mass can split. But that only leaves the continuous problem’s complexity open; it is not a reason the question is unworthy. Likewise, related work on fractional hedonic games does not, on the material here, already answer this continuous-population existence question.
So I cannot honestly defeat this anchor. The negative case is limited to saying the mirror is valuable only in a genuine high-multiplicity regime. Since such a regime is plausible for role-based workforces, that qualification is not enough to support the universal claim that no worthwhile mirror exists.
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.