Approximating the Core via Iterative Coalition Sampling (aamas24-00080)

Given rational type weights \(w_a>0\), masses \(\mu_a\) with \(\sum_a\mu_a=1\), quota \(q\), and accuracy \(\eta>0\), let mass coalitions be \(z\in\prod_a[0,\mu_a]\) with \(\nu_\mu(z)=1\) exactly when \(\sum_a w_a z_a\ge q\). Find a payoff density \(y\ge0\) with \(\sum_a\mu_a y_a=1\) and an \(\eta\)-accurate estimate of \(\min_y\max_{z}(\nu_\mu(z)-\langle y,z\rangle)\), together with a payoff whose every mass-coalition deficit is within \(\eta\) of optimal.

A society is given by its support: the list of \(\tau\ge1\) types with positive mass, each mass \(\mu_a\) a binary rational, with \(\sum_a\mu_a=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a positive binary rational voting-weight density \(w_a\). The binary rational quota satisfies \(0<q\le\sum_a\mu_aw_a\), and the binary rational accuracy is \(\eta>0\). Let \(L\) be the total input bit length; there is no separate alternative-count parameter \(m\).
A mass coalition is any real vector \(z\in\prod_a[0,\mu_a]\), including the empty and grand coalitions; its value is \(\nu_\mu(z)=\mathbf{1}\{\sum_aw_az_a\ge q\}\).
A feasible payoff density is \(y\in\mathbb{R}_{\ge0}^{\tau}\) with \(\sum_a\mu_ay_a=1\); coalition payments are \(\sum_ay_az_a\). Define \(D(y)=\max_z(\nu_\mu(z)-\sum_ay_az_a)\) and \(\varepsilon^*=\min_yD(y)\).
The approximation problem asks for a rational estimate \(\widehat\varepsilon\) and a rational feasible density \(\widehat y\) satisfying \(|\widehat\varepsilon-\varepsilon^*|\le\eta\) and \(D(\widehat y)\le\varepsilon^*+\eta\).

Does this additive approximation problem admit an algorithm running in \(\operatorname{poly}(\tau,L,1/\eta)\) time, or is achieving these guarantees NP-hard?

For finite games, the verified approximation guarantee says that bounding every nonempty coalition's loss \([\max\{0,v(C)-\varepsilon-\sum_{i\in C}p_i\}]^2/(2|C|)\) by \(\gamma^2\) bounds every deficit by \(\varepsilon+\sqrt{2n}\gamma\), where \(n\) is the number of players ([source](https://arxiv.org/pdf/2402.03928)).
For measurable player spaces, least-core containment in the Mas-Colell bargaining set is known when the grand coalition has maximal worth ([source](https://holzman.technion.ac.il/files/2012/09/leastcore.pdf)); no result settling the stated mass approximation problem was located.

Exact solution

The problem is polynomial-time solvable, even exactly. Define the total voting weight \(W=\sum_{a=1}^{\tau}\mu_aw_a\). Then

\(\displaystyle \varepsilon^*=1-\frac{q}{W},\qquad y_a^*=\frac{w_a}{W}\quad(a=1,\ldots,\tau).\)

The proof uses the stated real-mass coalition model, in which every type can be included in an arbitrary fraction.

Proof

Because all masses and voting-weight densities are positive, \(W>0\). The quota assumption gives \(r:=q/W\in(0,1]\).

Lower bound for every feasible density. Let \(y\) be any feasible payoff density, and consider the coalition \(z_a=r\mu_a\). Since \(0<r\le1\), this coalition satisfies \(0\le z_a\le\mu_a\). Its voting weight is

\(\displaystyle \sum_aw_az_a=r\sum_aw_a\mu_a=rW=q,\)

so it is winning. Its payment is

\(\displaystyle \sum_ay_az_a=r\sum_a\mu_ay_a=r,\)

where the last equality follows from payoff feasibility. Consequently, \(D(y)\ge1-r\). Since this holds for every feasible \(y\), we have \(\varepsilon^*\ge1-r\).

A density attaining the bound. Set \(y_a^*=w_a/W\). These coordinates are positive, and

\(\displaystyle \sum_a\mu_ay_a^*=\frac{\sum_a\mu_aw_a}{W}=1,\)

so \(y^*\) is feasible.

For any winning coalition \(z\), its payment satisfies

\(\displaystyle \sum_ay_a^*z_a=\frac{\sum_aw_az_a}{W}\ge\frac qW=r.\)

Thus its deficit is at most \(1-r\). For any losing coalition, the deficit is \(-\sum_ay_a^*z_a\le0\le1-r\). These two cases cover every coalition, including the empty and grand coalitions. Therefore \(D(y^*)\le1-r\).

The lower bound already proved applies to \(y^*\), giving \(D(y^*)=1-r\). Hence \(\varepsilon^*=1-q/W\), as claimed. The boundary case \(q=W\) is included and yields \(\varepsilon^*=0\).

Algorithm and bit complexity

Compute \(W\) by exact rational arithmetic and return

\(\displaystyle \widehat\varepsilon=1-\frac qW,\qquad \widehat y_a=\frac{w_a}{W}.\)

These outputs are rational. They satisfy both requested guarantees with zero error:

\(\displaystyle |\widehat\varepsilon-\varepsilon^*|=0,\qquad D(\widehat y)=\varepsilon^*.\)

For completeness, write each input rational as an integer numerator divided by a positive integer denominator. A common denominator for the products \(\mu_aw_a\) is the product of their input denominators. Its bit length is bounded by the sum of those denominator bit lengths, hence by \(O(L)\). The corresponding numerators and their sum have bit length \(O(L+\log\tau)\). Forming \(q/W\) and every \(w_a/W\) likewise produces rational numbers of polynomial bit length.

Thus polynomially many integer arithmetic operations on polynomial-length integers suffice. The running time and total output length are polynomial in \(\tau\) and \(L\), independently of \(1/\eta\), and therefore meet the requested bound.

⟨structured verdict parsed — rendered above⟩

Verification verdict

The output fully resolves the assigned problem. The proposed exact value and payoff density are correct under the stated real-mass coalition model. The proof is rigorous, includes the boundary cases, and establishes polynomial running time and output length. No major or minor issues were found.

Step-by-step audit

• Normalization and domain restrictions.

The definition \(W=\sum_a\mu_aw_a\) gives \(W>0\), since every mass and voting-weight density is positive. The quota assumption implies \(r=q/W\in(0,1]\). Both divisions and the subsequent coalition construction are therefore valid.

• Universal lower bound.

For every feasible density \(y\), the vector \(z_a=r\mu_a\) belongs to the permitted coalition box. The voting-weight calculation
\[ \sum_aw_az_a=rW=q \]
is correct. Equality at the quota makes this coalition winning under the specified weak inequality.

Its payment is exactly
\[ \sum_ay_az_a=r\sum_a\mu_ay_a=r. \]
Thus its deficit is \(1-r\), establishing \(D(y)\ge1-r\) for every feasible \(y\). The quantifier and the resulting lower bound on \(\varepsilon^*\) are correct.

• Feasibility of the proposed optimizer.

Each coordinate \(y_a^*=w_a/W\) is positive, and
\[ \sum_a\mu_ay_a^*=\frac{W}{W}=1. \]
This verifies all payoff feasibility requirements.

• Upper bound over every coalition.

For a winning coalition, the payment under \(y^*\) is its voting weight divided by \(W\), hence at least \(r\). Its deficit is consequently at most \(1-r\).

For a losing coalition, the value is zero and the payment is nonnegative, so its deficit is at most zero. Since \(1-r\ge0\), the asserted upper bound also holds in this case. These cases exhaust the coalition domain.

• Attainment and exact optimality.

Applying the universal lower bound to \(y^*\) and combining it with the upper bound establishes
\[ D(y^*)=1-r,\qquad \varepsilon^*=1-\frac qW. \]
The construction supplies an actual optimizer; there is no unresolved issue concerning attainment of the minimum.

• Edge cases.

The proof covers support size \(\tau=1\). It also covers \(q=W\): then \(r=1\), the lower-bound coalition is the grand coalition, and the optimum is zero. The empty coalition has deficit zero, and the grand coalition has deficit zero for every feasible density. No excluded endpoint is needed.

• Rational outputs and approximation guarantees.

The proposed outputs are rational because all input masses, weights, and the quota are rational, and \(W>0\). They achieve zero estimation error and an optimal feasible density, so both requested inequalities hold for every \(\eta>0\).

• Bit complexity.

The common-denominator argument is valid: multiplying the denominators appearing in the mass-weight products uses at most the sum of their bit lengths. Scaling the numerators and summing \(\tau\) terms gives the stated \(O(L+\log\tau)\) bound. Forming the output ratios preserves polynomial bit length. The number of arithmetic operations is polynomial, and exact integer arithmetic on these lengths takes polynomial time.

Consequently, the claimed polynomial running time in \(\tau\) and \(L\) establishes the requested bound in \(\tau,L,1/\eta\).

Repair feedback

None is required. The proof is self-contained and does not rely on either background result mentioned in the task.

⟨structured verdict parsed — rendered above⟩