Partitioning Friends Fairly (aaai23-25713)

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 society is atomless and given by its support: a list of \(\tau\) types with positive binary rational masses \(\mu_a\), summing to \(1\). The support size \(\tau\) counts listed types, not possible types. Input also includes a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\) and an integer \(k\ge2\). Here \(m=\tau\) is the matrix dimension, and \(L\) is the total input bit length; state running times in \(m,\tau,k,L\).
The entry \(A_{ab}\) specifies friendship between distinct individuals of types \(a,b\); diagonal entries may be either binary value. A type-\(a\) individual's utility for a group with type masses \(x_b\) is \(\sum_b A_{ab}x_b\).
A balanced assignment is a rational matrix \(p\ge0\) satisfying \(\sum_{j=1}^k p_{aj}=\mu_a\) and \(\sum_{a=1}^{\tau}p_{aj}=1/k\); types may be split among groups.
A coalition is any real matrix \(\zeta\) with \(0\le\zeta_{aj}\le p_{aj}\) and \(\sum_{a,j}\zeta_{aj}=1/k\). Write \(z_a=\sum_j\zeta_{aj}\). It blocks at factor \(2k-1\) if \(\sum_b A_{ab}z_b>(2k-1)\sum_b A_{ab}p_{bj}\) for every pair \((a,j)\) with \(\zeta_{aj}>0\). An assignment with no such coalition is in the \((2k-1,0)\)-core.

Can a balanced assignment in the \((2k-1,0)\)-core always be computed in time polynomial in \(m,\tau,k,L\), or is this search problem NP-hard?

For finite undirected friendship graphs with \(n\ge k^2+k\), a balanced \((2k-1,0)\)-core partition can be computed in polynomial time ([Li et al.](https://www.cs.toronto.edu/~nisarg/papers/fair-partition.pdf)).
For finite graphs with \(k=2\), a \((2+\varepsilon)\)-core partition can be computed in polynomial time for fixed \(\varepsilon>0\) ([Viswanathan](https://arxiv.org/abs/2605.03238)). No result settling the exact atomless search problem above was identified.

Result

The search problem is polynomial-time solvable. In fact, uniform type splitting produces a balanced assignment in the stronger \((k,0)\)-core.

This uses precisely the stated permission to split every type among all groups.

Construction and proof

For each type \(a\) and group \(j\), set \(p_{aj}=\mu_a/k\). These entries are nonnegative rational numbers, and balance follows from

\(\sum_{j=1}^k p_{aj}=\mu_a\), and \(\sum_{a=1}^{\tau}p_{aj}=(1/k)\sum_{a=1}^{\tau}\mu_a=1/k\).

Define \(d_a=\sum_{b=1}^{\tau}A_{ab}\mu_b\), the utility of a type-\(a\) individual for the whole society. Their utility in every assigned group is

\(\sum_b A_{ab}p_{bj}=d_a/k\).

Now consider any feasible real coalition \(\zeta\), and write \(z_b=\sum_j\zeta_{bj}\). Its capacity constraints imply, for every type \(b\),

\(0\le z_b\le\sum_jp_{bj}=\mu_b\).

Since every entry of \(A\) is nonnegative, for every type \(a\) and group \(j\),

\(\sum_b A_{ab}z_b\le\sum_b A_{ab}\mu_b=d_a=k\sum_b A_{ab}p_{bj}\).

Consequently, no pair \((a,j)\) can satisfy the strict blocking inequality at factor \(k\). In particular, no feasible coalition blocks at that factor.

Finally, \(k\le2k-1\) because \(k\ge2\). Assigned utilities are nonnegative, so the same inequality excludes blocking at factor \(2k-1\). This proves the required guarantee, including when some utilities are zero and regardless of the diagonal entries of \(A\).

Running time and encoding

Write each input mass as \(\mu_a=r_a/s_a\), with positive binary integers. Output each entry as the rational number \(r_a/(ks_a)\); reduction to lowest terms is unnecessary.

Every entry has bit length \(O(L+\log(k+1))\). Reading the input, multiplying denominators, and writing all \(\tau k\) entries takes, for example, the conservative bound

\(O\!\left(m^2+L+\tau k\bigl(L+\log(k+1)\bigr)^2\right)\)

bit operations using elementary integer arithmetic. Here \(m=\tau\). Thus the running time and output length are polynomial in \(m,\tau,k,L\), without expanding the masses into individual agents.

Sharpness of the stronger uniform guarantee

The factor \(k\) is tight for this construction. Take two types with masses \(\mu_1=1/k\) and \(\mu_2=1-1/k\), and let \(A_{11}=1\), with every other entry zero.

Under uniform splitting, every type-\(1\) individual receives utility \(1/k^2\). The coalition consisting of all type-\(1\) individuals is feasible, has mass \(1/k\), and gives each member utility \(1/k\). It therefore blocks at every nonnegative factor \(\alpha<k\).

This sharpness statement concerns uniform splitting only; the construction above already settles the requested factor \(2k-1\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover’s claim is correct. Uniform splitting yields a balanced assignment in the stronger \((k,0)\)-core and can be computed in time polynomial in the requested parameters \(m,\tau,k,L\). No gaps or false statements were found.

Step-by-step verification

• Construction and balance. The proposed entries \(p_{aj}=\mu_a/k\) are positive rational numbers. The stated row and column calculations correctly give

\[ \sum_{j=1}^{k}p_{aj}=\mu_a, \qquad \sum_{a=1}^{\tau}p_{aj}=1/k. \]
Thus the construction satisfies every requirement for a balanced assignment.

• Assigned utilities. With \(d_a=\sum_b A_{ab}\mu_b\), substitution gives

\[ \sum_b A_{ab}p_{bj}=d_a/k \]
for every type \(a\) and group \(j\). The utility is therefore independent of the assigned group, as claimed.

• Coalition capacity bound. For every feasible real coalition, summing \(0\le\zeta_{bj}\le p_{bj}\) over groups gives \(0\le z_b\le\mu_b\). This argument applies to real coalition entries without any rationality assumption.

• Utility bound and exclusion of blocking. Since \(A_{ab}\ge0\), the coordinatewise capacity bound implies

\[ \sum_b A_{ab}z_b\le d_a =k\sum_b A_{ab}p_{bj}. \]
This holds for every pair \((a,j)\), including all pairs with \(\zeta_{aj}>0\). Consequently, the strict inequality required for blocking at factor \(k\) cannot hold. Every feasible coalition has positive total mass \(1/k\), so it necessarily contains an occupied pair; there is no vacuous blocking case.

• Requested factor and edge cases. For \(k\ge2\), one has \(k\le2k-1\). All assigned utilities are nonnegative, so the preceding bound also excludes blocking at factor \(2k-1\). If \(d_a=0\), the coalition utility is also zero, which still excludes strict improvement. Either permitted diagonal value is covered by nonnegativity. Symmetry is not needed for the argument, but this does not affect its validity under the stated assumptions.

• Encoding and running time. The representation \(r_a/(ks_a)\) is exact and requires no reduction to lowest terms. Multiplication by \(k\) increases denominator bit length by at most \(O(\log(k+1))\). The claimed conservative running-time bound

\[ O\!\left(m^2+L+\tau k\bigl(L+\log(k+1)\bigr)^2\right) \]
accommodates reading the input, elementary integer multiplication, and writing all entries. It is polynomial in \(m,\tau,k,L\), as requested. Explicit output has \(\tau k\) entries; the task expressly permits polynomial dependence on \(k\).

• Sharpness claim. Both example masses are positive for \(k\ge2\), and the matrix satisfies the input conditions. Under uniform splitting, taking every available type-\(1\) portion yields a feasible coalition of mass \(1/k\). Its members’ assigned utility is \(1/k^2\), while their coalition utility is \(1/k\). The strict blocking inequality therefore holds exactly when \(\alpha<k\). The prover correctly limits this sharpness claim to the uniform construction.

Repair feedback

None is required. The construction, guarantee, complexity bound, and supplementary sharpness statement are all verifiable as written.

⟨structured verdict parsed — rendered above⟩