| paper | Balanced and Fair Partitioning of Friends |
| authors | Argyrios Deligkas, Eduard Eiben, Stavros D. Ioannidis, Dušan Knop, Šimon Schierreich |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 9
statement extracted from the paper’s text layer
Given finite forest templates \(F_q=(V_q,E_q)\), rational component masses \(\lambda_q\), an integer \(k\), and monotone or additive local utilities \(u_{q,v}\), let \(Z=\sum_q \lambda_q|V_q|\). Decide whether there are nonnegative masses \(y_{q,\chi}\) over \(k\)-colourings \(\chi\) of each template such that \(\sum_\chi y_{q,\chi}=\lambda_q\), every group has mass \(Z/k\), and every positive-mass colouring satisfies the limiting EFX inequalities \(u_{q,v}(\chi^{-1}(\chi(v))) \ge u_{q,v}(\chi^{-1}(j) \setminus \{c\})\) for every local agent \(v\), group \(j\), and friend \(c\) in \(\chi^{-1}(j)\).
A nonatomic population of repeated finite forest components, with integral local k-colourings and continuous masses over component-colouring configurations; utilities are intra-component, and feasibility requires equal global group masses plus support-wise limiting EFX.
The mirror requires a coupling into finite friendship components, so it is not recoverable from a bare mass vector over individual agent types and its EFX limit needs an explicit convention for the removed agent.
fatal: False
The mirror covers the EFX existence and additive linear-time construction in Theorem 9; it leaves the MMS clause, Theorem 10, and the paper's hardness and parameterized results untouched.
The strongest honest case is a mirror of the paper’s forest results, specifically the EFX part of Theorem 9. I would not lead with the NP-hardness theorems: their reductions use individually tuned gadget positions, whereas repeated local friendship structures give a much more credible high-multiplicity regime.
The anchor is Theorem 9, proved in this paper:
If \(G\) is a forest and \(k\in\mathbb N\), there always exists a \(k\)-partition that is MMS and EFX, even for monotone utilities. If utilities are additive, such a partition can be found in linear time.
My continuous problem would be Continuum-Forest-EFX.
An instance contains finitely many forest templates
\[
F_q=(V_q,E_q),\qquad q=1,\ldots,h,
\]
together with a rational mass \(\lambda_q\) of copies of each template, an integer \(k\), and the same monotone utility functions used in the paper. A copy of \(F_q\) is a small social unit—say a recurring class, branch office, training cohort, or camp house. It contains one agent for each \(v\in V_q\), and agents are friends exactly when their corresponding vertices are adjacent. Copies are mutually non-adjacent.
The agent type is \((q,v)\): the template, the local role, its friends in that template, and its utility function. Thus all copies of the same local role are genuinely indistinguishable. If \(Z=\sum_q\lambda_q|V_q|\), the mass of type \((q,v)\) is \(\lambda_q/Z\). The regime is \(N\) very large and \(h\), \(|V_q|\), and hence the number of role types \(\tau=\sum_q|V_q|\), relatively small.
The decision variable is not a fractional assignment of individual friends. It is a distribution \(y_{q,\chi}\) over ordinary \(k\)-colourings \(\chi:V_q\to[k]\). Here \(y_{q,\chi}\) is the mass of copies of template \(q\) receiving local partition \(\chi\). It must satisfy
\[
\sum_{\chi}y_{q,\chi}=\lambda_q
\]
and, for every group \(j\),
\[
\sum_{q,\chi}y_{q,\chi}\,|\chi^{-1}(j)|
=\frac{Z}{k}.
\]
Every copy still receives an ordinary discrete partition; only the population of indistinguishable copies is continuous. This is therefore population continuization, not merely fractionalizing the outcome.
The continuous fairness condition is the literal large-population limit of the paper’s EFX definition. For a local agent \(v\) in a copy with colouring \(\chi\), write \(S_j=\chi^{-1}(j)\). Since a target group contains agents from many other copies, one can choose the removed agent \(b\) outside \(v\)’s copy. Removing \(b\) has no effect on \(v\)’s utility, so the limiting EFX condition becomes
\[
u_v(S_{\chi(v)})\geq u_v(S_j\setminus\{c\})
\]
for every group \(j\) and every local friend \(c\in S_j\cap F_q(v)\). Every configuration \(\chi\) receiving positive mass must satisfy this condition for every local agent.
The objective is feasibility: output such a mass distribution \(y\), or report that none exists.
I expect this problem to be Class A. For bounded template size, it is directly a finite configuration LP. For larger forests, the natural algorithmic question is whether the configurations can be priced or generated by a tree dynamic programme. Theorem 9 gives strong evidence that they can. More fundamentally, take a finite instance consisting of many copies of the templates. The whole graph is still a forest, so Theorem 9 supplies an EFX partition. Record the empirical distribution of the local colourings and let the number of copies tend to infinity. Because there are finitely many local configurations, a convergent subsequence gives exactly a feasible \(y\). With additive utilities, the paper’s linear-time constructive algorithm supplies the finite approximations; the continuous version should admit a compressed configuration or dynamic-programming implementation.
This is a credible authors’ mirror. The paper itself motivates tables, student teams, training groups, and camp houses—all settings where many repeated local communities are plausible. The continuous regime is not “millions of agents with arbitrary friendships”; it is millions of participants distributed among a small number of recurring friendship environments. That is precisely the kind of high-multiplicity scenario the programme asks us to identify.
The main weakness is that the mirror must retain the anonymous copy structure. A bare distribution over individual role types loses which agents belong to the same friendship component. If one instead uses only aggregate friend masses, sparse friendships disappear in the limit and PROP, MMS, and envy conditions can become artificially easy under proportional splitting. The component mark is therefore extra structure, but it is not an arbitrary repair: it is the information needed to make pairwise friendship meaningful under high multiplicity.
I would claim only this scope: Theorem 9’s EFX existence and additive algorithm on repeated forest populations. I would not claim that this automatically mirrors the paper’s hardness results, nor that the MMS clause transfers without a separate definition and proof. The natural follow-up questions are whether the full MMS+EFX mirror remains tractable, whether bounded-treewidth templates yield an XP or FPT configuration algorithm, and where cross-component friendships or directed/enemy utilities create genuinely continuum-specific hardness.
The strongest objection is that Theorem 9 is not really a theorem about population multiplicity. It is a theorem about preserving unit-level adjacency inside a finite forest. That distinction defeats the proposed mirror unless one changes the continuous object substantially.
In ChoCo’s central model, a society is a mass vector over agent types. If type \((q,v)\) has positive mass, that vector does not say which type-\((q,w)\) agent is the particular friend of a given \(v\). Treating all type-\((q,w)\) mass as friends turns the sparse forest into a dense interaction model; treating friendship as a matching requires an additional coupling between copies. The coupling is not recoverable from the population distribution. Moreover, under an ordinary measure model, removing one agent has zero mass, so the “up to one friend” correction underlying EFX disappears. The natural limit is an aggregate envy condition, not the paper’s EFX.
The proponent’s template construction repairs this by retaining whole finite components. But that changes the continuous primitive from a distribution over people to a distribution over already-structured micro-instances. The variable \(y_{q,\chi}\) is then a lottery over discrete colourings of each component; the population masses only implement that lottery. The friendship combinatorics and all meaningful utility comparisons remain inside each indivisible copy. This is outcome randomization or a relational mixture model in disguise, rather than a continuous society of the kind used by ChoCo.
The repair also makes the computational anchor collapse. For rational template masses, take a sufficiently large finite disjoint union of copies, with total size divisible by \(k\), and apply Theorem 9. Its partition induces the required empirical distribution \(y\). Thus feasibility follows immediately from the finite theorem for every such forest population. If templates are bounded, one can enumerate their colourings directly; if one insists on expected rather than support-wise fairness, one has defined a different, lottery-based fairness notion. If one removes a positive fraction rather than one friend, that is likewise a new robustness notion unsupported by Theorem 9.
One could certainly study continuous distributions over rooted forest components, and repeated classes or training cohorts are plausible applications. That is the weakness in the negative case: under a sufficiently broad relational notion of type, the construction is defensible. But within the programme’s population-as-type-distribution framework, Theorem 9 supplies no genuine continuous mirror. The ordinary type-mass model loses the friendships; the repaired component model preserves them by keeping the discrete problem intact, while its “continuous” variable merely mixes deterministic solutions.
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.