| paper | d4-conf-ijcai-2021-0414 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Every instance admits a \(2\)-improvement-core stable allocation. Existence decision and construction are polynomial-time solvable; a stable allocation with at most \(\tau\) templates is computable in \(O(\tau^3L^2)\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and a symmetric nonnegative rational affinity matrix \(W\), does every instance admit, and can one compute in time polynomial in \(|T|\) and the input bit length, a finite-support allocation that is \(2\)-improvement-core stable? Represent an allocation by masses \(\alpha_q\) assigned to finite coalition templates \(q\in\mathbb{Z}_{\ge 0}^{T}\setminus\{0\}\), with \(\sum_q \alpha_q q_t/|q|=\mu_t\); a type-\(t\) member in template \(q\) has utility \(u_t(q)=(\sum_s W_{ts}q_s-W_{tt})/|q|\). A blocker may draw either finitely many members or positive mass from source cohorts \((q,t)\); in both cases, every participant must receive strictly more than twice their utility in that source cohort. For a positive-mass block drawing \(y_{q,t}\le\alpha_q q_t/|q|\), its type-\(t\) utility is \(\sum_s W_{ts}y_s/\sum_s y_s\), where \(y_s=\sum_q y_{q,s}\); the diagonal affinity applies to other members of the same type, while an individual’s self-value is zero.
Use role types \(T\) with rational population masses \(\mu\) and symmetric affinities \(W\). Allocate mass among finite coalition-composition templates, retaining each template as a source cohort so current utilities are known. Ask for a \(2\)-improvement-core-stable allocation against finite and positive-mass blocks; greedy pairing by maximum remaining affinity is a plausible algorithmic route.
A type-mass vector alone does not determine participants’ current utilities when members of the same type occupy different coalition templates; blockers must record the source template and type of each participant.
fatal: False
The mirror covers Theorem 6’s polynomial-time construction for weighted symmetric fractional hedonic games, at the limiting factor \(k=2\). It leaves aside the \(q\)-size results, the tighter simple-game guarantee in Theorem 7, and the efficiency bounds; the paper’s existing discrete algorithm also means this is not a hardness-dissolution claim.
The strongest mirror here is the constructive \(k\)-improvement-core result for weighted symmetric fractional hedonic games.
My anchor is Theorem 6, proved in this paper: for every \(n\)-agent symmetric fractional hedonic game, and every \(k\ge 2(1-1/n)\), there is a \(k\)-improvement-core-stable coalition structure, and one can compute it in polynomial time. A coalition blocks when every member would get strictly more than \(k\) times their current utility by forming it.
A plausible high-multiplicity regime is a large federation, workplace, or community whose members fall into a modest number \(\tau\) of roles or interest groups. Many people share each type, and their affinities depend on the types involved: every type-\(t\) member values a type-\(s\) member at the same amount. That gives a symmetric matrix \(W=(w_{ts})\), where \(w_{tt}\) is the value for another member of the same type. The society is a rational mass vector \(\mu\), with \(\sum_t\mu_t=1\) and \(\tau\ll n\). This is a block-structured instance regime, rather than a claim that every social network has few types.
Here is the continuous problem I would hand to a prover. The input is \(T\), the rational mass vector \(\mu\), the nonnegative rational affinity matrix \(W\), and \(k\). An outcome assigns the population mass to coalition templates. A template \(q\in\mathbb{Z}_{\ge0}^{\tau}\setminus\{0\}\) records the number of members of each type in a finite coalition; let \(\alpha_q\) be the population fraction assigned to copies of that template. Feasibility requires \(\sum_q \alpha_q q_t/|q|=\mu_t\) for every type \(t\). This is a deterministic allocation of atomless type masses across coalitions, not a lottery over outcomes. A type-\(t\) member in template \(q\) gets \(u_t(q)=(\sum_s w_{ts}q_s-w_{tt})/|q|\), where the subtraction accounts for that member’s zero value for themself.
The question is: compute a finite-support feasible outcome with no \(k\)-improvement block. A block may be a finite group drawn from the population, or a positive mass of members drawn from the outcome’s cohorts. Finite groups use the template utility above. For a positive-mass block with type-mass vector \(y\), a type-\(t\) member’s new utility is \(\sum_s w_{ts}y_s/\sum_s y_s\). In either case, every participating member must strictly exceed \(k\) times their current utility for the group to block. This keeps the paper’s multiplicative, per-member gain criterion and makes mass the population quantity being continuized.
The expected answer is tractable. The finite theorem’s threshold tends to \(2\) as \(n\) grows, so the continuous question asks for a \(2\)-improvement-stable outcome. A natural candidate algorithm repeatedly pairs remaining type masses with maximum affinity, placing them in two-person coalition templates; any leftover mass with no positive-affinity partner becomes singletons. It needs only polynomially many steps in \(\tau\). The proof intuition matches the paper’s greedy construction: a selected pair has utility \(w/2\), while any new coalition drawn only from the remaining population can give either member at most \(w\). Earlier paired cohorts cannot join a blocking coalition by the same argument. The output has polynomial-size support and rational masses.
This scope is deliberately narrow: it mirrors Theorem 6’s computation of \(k\)-improvement-core outcomes. It does not claim a continuous version of the paper’s \(q\)-size results; a bound such as “at most three agents” does not become a population-mass bound. Nor does it claim that the paper proves a named hardness result. The introduction cites hardness of deciding core nonemptiness from earlier work, but there is no numbered in-paper hardness theorem to anchor a hardness-dissolution question here. Further questions include whether \(2\) is the sharp universal threshold in this mass model, and how its stable outcomes relate to finite high-multiplicity instances.
The weakest point is that this mirror restricts the source network to a small number of exact affinity types, and its outcome records mass assigned to finite coalition templates. Those choices are plausible for repeated organizational roles, but they are a narrower regime than arbitrary S-FHGs. Also, Theorem 6 already gives a polynomial algorithm for the discrete problem, so this mirror is not a case where continuization might dissolve known hardness. Its value is a clean population-level formulation of the paper’s constructive stability guarantee, not a claim that the continuous version resolves the paper’s central computational challenge.
I do not think there is an honest way to defeat this anchor. Theorem 6 is a named computational result, and a role based affinity model is a sensible high multiplicity regime for it: many interchangeable members of each type, with values determined by counterpart type. In the proposer’s finite template model, mass records how many copies of each coalition composition the population can supply. That is a recognizable continuous population question, not outcome space continuity.
The proposed blocking definition needs one correction: if members of a type are spread across templates, they can have different current utilities. A valid mass block must specify which source cohorts its participants come from; a type mass vector alone cannot determine whether every participant gains by the required factor. But that is a repair to the formulation, not a defeat of the mirror. One can track mass by source template and type while retaining finite coalition templates and individual utility comparisons.
The strongest negative point is that the population continuum may add little to this particular result. With finite deviations, any type of positive mass supplies arbitrarily many interchangeable agents, so the set of possible blocking templates depends mainly on the support and affinity matrix; proportions chiefly constrain how much mass can be assigned to each outcome template. A positive mass deviation avoids that issue, but changes the paper’s finite-coalition notion of blocking. This makes the bridge less direct than the proponent suggests.
Still, neither point rules out a worthwhile mirror. Theorem 6’s pair construction plausibly extends to mass allocations, and a simple or already tractable answer is not a reason to reject a well-posed question. My negative case is therefore weak: the anchor survives, subject to repairing the block definition.
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.