| paper | Partitioning Friends Fairly |
| authors | — |
| venue | AAAI 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given rational type masses \(\mu\), a symmetric binary type-adjacency matrix \(A\), and \(k\), compute \(p_{aj} \ge 0\) with row sums \(\mu\) and column sums \(1/k\) such that no coalition represented by \(\zeta_{aj} \le p_{aj}\) of total mass \(1/k\) satisfies \(\sum_b A_{ab} z_b > (2k-1) \sum_b A_{ab} p_{bj}\) for every participating type \(a\) assigned from group \(j\), where \(z_a = \sum_j \zeta_{aj}\).
A finite-type atomless block society with masses μ; p assigns each type’s mass across k equal groups; ζ describes a deviating mass coalition; the objective is to find a (2k−1,0)-core partition, or optimize the smallest multiplicative core factor.
The finite-type complete block-adjacency assumption is substantially narrower and less socially realistic than the paper’s arbitrary identity-level friendship graphs, so the proposed application regime may have limited empirical reach.
fatal: False
Covers the balanced approximate-core and balanced envy-freeness results of Theorems 3 and 6 for finite-type block societies; it leaves arbitrary graphs, min-cut and local-search structure, discrepancy mechanisms, and the remaining exact, negative, imbalanced, and open results untreated.
I think there is a genuine positive case, strongest for Theorem 3 and secondarily for Theorem 6. It is narrow: it applies to large, structurally repetitive social networks, not arbitrary graphs.
Take a finite-type friendship continuum. There are \(\tau\) types, rational masses \(\mu_a\) summing to one, and a symmetric binary matrix \(A\), where \(A_{ab}=1\) means that every type-\(a\) agent is friends with every type-\(b\) agent. The type therefore includes the agent’s complete friendship profile, including within-type friendships. A rational finite instance with \(N\mu_a\) copies of type \(a\) is exactly a blow-up of this model; utilities are divided by \(N\), so one-agent effects vanish as \(N\) grows.
A partition is represented by \(p_{aj}\), the mass of type \(a\) assigned to group \(j\). Thus
\[ \sum_j p_{aj}=\mu_a,\qquad \sum_a p_{aj}=1/k. \]
This does not split an individual: each point of the nonatomic population belongs to one group. It only permits a large type cohort to be divided across groups. Type \(a\)’s utility for group \(j\) is
\[ U_a(j)=\sum_b A_{ab}p_{bj}. \]
This is precisely the high-multiplicity version of the paper’s balanced graph-partition problem. The scenario could be a large university orientation programme, onboarding event, or residential system with thousands of people in each of a relatively small number of recurring cohorts, where cohort membership determines the relevant friendship profile. If the network is personally idiosyncratic, then \(\tau\) is close to \(N\) and this mirror is not useful; that is an instance-regime limitation, not a failure of the formulation.
My lead anchor is Theorem 3, proved in this paper: when \(n\ge k^2+k\), every min \(k\)-cut is in the \((2k-1,0)\)-core, and Algorithm 1 returns a \(k\)-partition in the \((2k-1,0)\)-core in polynomial time.
The corresponding problem is Balanced Core\(_\infty\). Given \((A,\mu,k)\), output a mass partition \(p\) with every group of mass \(1/k\), such that there is no coalition of mass \(1/k\) that is \((2k-1,0)\)-blocking. Formally, a coalition is described by masses \(\zeta_{aj}\le p_{aj}\), with total mass \(1/k\). Writing \(z_a=\sum_j\zeta_{aj}\), it blocks if, for every \((a,j)\) with \(\zeta_{aj}>0\),
\[ \sum_b A_{ab}z_b > (2k-1)\sum_b A_{ab}p_{bj}. \]
The decision variable is \(p\); the objective is to find a feasible partition, or, in an optimization version, to minimize the multiplicative core violation.
This problem is in Class A in the strongest possible sense. Set
\[ p_{aj}=\mu_a/k \]
for every type and group. If \(D_a=\sum_b A_{ab}\mu_b\), then every type-\(a\) agent receives utility \(D_a/k\) in its own group. Any coalition has utility at most \(D_a\), so it cannot give that agent utility strictly greater than \(k(D_a/k)=D_a\). Thus the partition is already in the \((k,0)\)-core, and hence in the paper’s weaker \((2k-1,0)\)-core. The algorithm is just the construction of this rational matrix, polynomial in \(\tau,k\), and the threshold \(n\ge k^2+k\) disappears in the continuum regime.
This is not a different fairness notion or a welfare surrogate. It retains exact balance, friendship-induced individual utilities, coalitions of the prescribed macroscopic size, and the same multiplicative blocking condition. What disappears is only the indivisibility of individual agents. In a finite blow-up, the same construction can be rounded whenever the type counts permit it, with discrepancies of order \(1/N\).
A second, independent anchor is Theorem 6, also proved here, which says that for every \(k\ge2\), an \(EF\)-\(O(\sqrt{(n/k)\ln k})\) balanced partition exists and can be computed in polynomial time. The theorem uses a cited discrepancy result, but the stated partitioning theorem is proved in this paper.
Its continuous counterpart is Balanced EF\(_\infty\). Given \((A,\mu,k)\), output a balanced mass partition minimizing \(r\) such that, for every type \(a\), every group \(j\) receiving positive type-\(a\) mass, and every group \(\ell\),
\[ U_a(j)\ge U_a(\ell)-r. \]
The individual being swapped out has vanishing mass, so this is the precise continuum limit of the paper’s swap-based envy definition. Again, the uniform type split gives \(U_a(j)=D_a/k\) for every \(j\), so \(r=0\). Hence this mirror is also Class A. After normalizing the paper’s utilities by \(n\), its \(O(\sqrt{(n/k)\ln k})\) guarantee becomes \(O(\sqrt{\ln k/(nk)})\), which tends to zero in the high-multiplicity limit.
The authors should recognize both as their problem’s continuous form: the input remains a social network, the action remains a partition into exactly \(k\) groups, and the fairness criteria remain core and envy-freeness. The paper’s own discussion also identifies symmetric weighted preferences as a natural extension; replacing \(A\) by a symmetric rational friendship-intensity matrix \(W\) gives the same formulation.
The mirror does not cover every result in the paper. I would not claim it settles Theorems 1, 2, 4, 5, or 7, nor the open questions about exact cores or \(EF1\). Its strongest contribution is instead to show that the paper’s two principal approximation guarantees are integrality-sensitive: in a legitimate high-multiplicity regime, balanced grouping can be exactly envy-free and achieve a stronger core guarantee.
The weakest point is also clear. For EF, and partly for the core, the continuum makes the problem almost too easy: a type can be distributed evenly across groups, and the one-agent swap central to the discrete definition disappears. If the authors regard indivisible cohort assignments as essential, they may reject this as too relaxed. But that would be an objection to the chosen instance regime, not to continuization itself. In the large-cohort scenario, mass is the honest object, and the resulting collapse from discrepancy bounds to exact fairness is precisely a meaningful Class A conclusion. The natural follow-up questions are whether exact \((1,0)\)-core partitions exist in this model, how much rounding loss is necessary for finite \(N\), and where the boundary lies between splittable high-multiplicity types and atomic types where discrete hardness returns.
The strongest case against begins by granting that Theorems 3 and 6 are genuine computational anchors. The objection is instead that the proposed continuum removes the objects those theorems study.
For Theorem 3, the proposed finite-type network is an extremely restrictive blow-up graph: every pair of types is either completely connected or completely disconnected. More importantly, allowing each type to be split fractionally across all groups makes the core guarantee collapse independently of the graph. With \(p_{aj}=\mu_a/k\), type \(a\)'s utility in every group is \(D_a/k\), while its utility in any coalition is at most \(D_a\). Hence the partition is automatically in the \((k,0)\)-core, and therefore in the paper’s \((2k-1,0)\)-core, for every nonnegative additive utility system—not merely friendship graphs.
That is not a continuous analogue of the theorem’s min-cut or local-search phenomenon. The graph, its cuts, and the paper’s combinatorial argument have disappeared. The result is an artefact of distributing every cohort identically among every group. Replacing \(A\) by a weighted affinity matrix does not repair this: the same uniform split gives the same bound for every nonnegative matrix.
The natural rescue is to prohibit splitting a type cohort, or to retain finite atoms so that rounding matters. But then the population is no longer a nonatomic continuous society: one has a finite weighted graph-partition problem, with precisely the indivisibility that the proposed mirror was meant to remove. Asking instead for an exact \((1,0)\)-core or minimizing the core factor could be interesting, but that is a new fractional stable-partition problem, not a continuous counterpart of Theorem 3’s stated result.
Theorem 6 is weaker still. The paper’s envy-freeness notion is defined by swapping one named agent with another. In an \(N\)-agent blow-up, after normalizing utilities by \(N\), that swap changes utility by only \(O(1/N)\):
\[ U_a(\ell)+\frac{\text{effect of adding }i\text{ and removing }i'}{N}. \]
The correction vanishes in the continuum. Thus the proposed condition \(U_a(j)\ge U_a(\ell)-r\) is not the limit of swap-based envy-freeness in any substantive sense; it is a different group-level comparison. The paper’s discrepancy bound is precisely an integrality error from assigning individual vertices to one color. Once type mass may be fractionally copied into every group, uniform splitting gives exact equality and discrepancy theory is no longer doing any work.
Keeping a nonvanishing swap effect requires retaining positive-mass agents or atomic cohort representatives. That restores indivisibility and abandons the atomless model. Allowing positive-mass deviations instead produces a coalition or group-stability notion, not the paper’s individual envy relation.
The proposed orientation-day scenario also does not establish a convincing regime by itself. A repeated cohort label does not make all members have identical complete friendship neighborhoods; realistic social networks have local, identity-specific ties. A block model with complete cross-type friendship is better interpreted as institutional compatibility or aggregate affinity than friendship. A stochastic block or graphon model could be plausible, but it would be a new probabilistic model whose guarantees are not Theorems 3 or 6.
So the negative case decisively rejects the proposed EF mirror and shows that the stated core mirror degenerates into universal fractional equalization. But the universal claim is too strong to defend honestly: a continuous exact-core problem on finite-type block societies might still be worthwhile. The strongest defensible verdict is therefore not “no mirror exists,” but “the two mirrors offered here do not preserve the paper’s substantive fairness problems; only a substantially strengthened, newly formulated core question remains viable.”
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.