d4-conf-ijcai-2009-0284 (d4-conf-ijcai-2009-0284)

Given a finite type set \(T\), rational masses \(\mu\) summing to one, a coalition-slot limit \(K\), and explicit rational piecewise-linear nonnegative coalition values \(u(x,\Pi)\) satisfying positive externalities, find a feasible mass partition \(\Pi=\{x^1,\ldots,x^r\}\), with \(r\le K\) and \(\sum_j x^j=\mu\), whose value \(W(\Pi)\) is at least \(\mathrm{OPT}/K\). Can this guarantee be achieved by optimizing over the one- and two-block mass partitions?

A society is specified by its support \(T\): the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(m=\tau=|T|\) is the mass-vector dimension, not the number of possible types.
Given an integer \(K\ge1\), a feasible partition is an unordered multiset \(\Pi=[x^1,\ldots,x^r]\), where \(1\le r\le K\), each \(x^j\in\mathbb R_{\ge0}^{T}\) is nonzero, and \(\sum_jx^j=\mu\); identical vectors represent distinct blocks and are counted separately.
Represent partitions using \(K\) ordered slots, padding with zero vectors. The input gives nonnegative continuous piecewise-linear functions \(f_j(x^1,\ldots,x^K)\), explicitly by rational polyhedral cells and rational affine formulas covering the feasible slot domain. Slot permutations permute the values correspondingly; zero slots have value zero, and their placement does not affect other values. Write \(u(x^j,\Pi)=f_j(x^1,\ldots,x^K)\).
Positive externalities mean that merging any two nonzero blocks \(y,z\) into \(y+z\) weakly increases the value of every other block: \(u(x,\Pi')\ge u(x,\Pi)\). No restriction is imposed on the merged block's value.
Define \(W(\Pi)=\sum_{j=1}^r u(x^j,\Pi)\) and \(\mathrm{OPT}=\max_{\Pi\text{ feasible}}W(\Pi)\). Let \(L\) be the total binary input length, including all value descriptions and \(K\).

Can a feasible rational partition satisfying \(W(\Pi)\ge\mathrm{OPT}/K\) be found in time polynomial in \(m,\tau,K,L\), or is attaining this approximation guarantee NP-hard?
Does maximizing \(W\) over feasible partitions with at most \(\min\{2,K\}\) nonzero blocks always achieve that guarantee?

For finite societies of \(n\) agents with nonnegative coalition values and positive externalities, exhaustive search over all one- and two-block partitions guarantees value at least \(\mathrm{OPT}/n\), using \(2^{n-1}\) partitions; this is an approximation result, not a polynomial-time claim. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ijcai2009.pdf)
A later treatment retains the discrete approximation guarantee. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2012a.pdf) No result settling this exact mass-partition approximation problem was located.

Result

The requested approximation is polynomial-time solvable under the stated explicit representation. Moreover, maximizing welfare over partitions with at most \(\min\{2,K\}\) nonzero blocks always achieves welfare at least \(\mathrm{OPT}/K\).

The proof separates the approximation guarantee from the algorithm for optimizing over two blocks.

1. Existence of an optimal partition

Let the feasible ordered-slot domain be
\[ D=\left\{(x^1,\ldots,x^K)\in(\mathbb R_{\ge0}^{T})^K:\ \sum_{j=1}^{K}x^j=\mu\right\}. \]

This set is nonempty, closed, and bounded: every coordinate satisfies \(0\le x_t^j\le\mu_t\). Consequently, \(D\) is compact.

The function \(F(X)=\sum_{j=1}^{K}f_j(X)\) is continuous on \(D\), so it attains a maximum. Removing zero slots produces a feasible partition, because their values are zero and \(\sum_t\mu_t=1\) ensures that some slot is nonzero. Conversely, every feasible partition has an ordered-slot representation. Permutation equivariance makes its welfare independent of the ordering.

Thus the maximum of \(F\) on \(D\) is precisely \(\mathrm{OPT}\).

2. The two-block approximation guarantee

Choose an optimal partition \(\Pi^\star=[x^1,\ldots,x^r]\), where \(1\le r\le K\). There is an occurrence \(i\) such that
\[ u(x^i,\Pi^\star)\ge\frac{1}{r}\sum_{j=1}^{r}u(x^j,\Pi^\star)=\frac{\mathrm{OPT}}{r}. \]

If \(r\le2\), the optimal partition itself already has at most \(\min\{2,K\}\) blocks.

Suppose \(r\ge3\). Keep the selected occurrence \(x^i\) separate and successively merge all other blocks. Each merge involves two nonzero blocks, and \(x^i\) is an unaffected block. Positive externalities therefore imply that its value never decreases.

The resulting partition is
\[ \widehat\Pi=\left[x^i,\ \sum_{j\ne i}x^j\right]. \]
Both blocks are nonzero. By nonnegativity of the second block’s value,
\[ W(\widehat\Pi)\ge u(x^i,\widehat\Pi) \ge u(x^i,\Pi^\star) \ge\frac{\mathrm{OPT}}{r} \ge\frac{\mathrm{OPT}}{K}. \]

Identical vectors cause no difficulty: the argument selects and preserves one block occurrence, as required by the multiset definition.

Hence the maximum welfare over partitions with at most \(\min\{2,K\}\) nonzero blocks satisfies the requested guarantee.

3. Exact optimization over at most two blocks

For \(K=1\), output the unique partition \([\mu]\). It is optimal.

Assume \(K\ge2\). Define
\[ B=\{x\in\mathbb R^{T}:0\le x_t\le\mu_t\text{ for every }t\in T\}, \qquad S(x)=(x,\mu-x,0,\ldots,0). \]

Every partition with at most two nonzero blocks has a representation \(S(x)\) for some \(x\in B\). The choices \(x=0\) and \(x=\mu\) represent the one-block partition. Permutation equivariance justifies placing the active blocks in the first two slots.

Since the remaining slots have value zero, the welfare represented by \(S(x)\) is
\[ G(x)=f_1(S(x))+f_2(S(x)). \]

Write the explicit descriptions of these two functions as follows:

• \(f_1=\ell_{1,a}\) on the rational polyhedral cell \(C_{1,a}\), for \(1\le a\le N_1\).
• \(f_2=\ell_{2,b}\) on the rational polyhedral cell \(C_{2,b}\), for \(1\le b\le N_2\).

Here each \(\ell_{j,a}\) is a rational affine function. For every pair \((a,b)\), form the rational linear program
\[ \text{maximize }\ell_{1,a}(S(x))+\ell_{2,b}(S(x)) \quad\text{subject to }x\in B,\ S(x)\in C_{1,a},\ S(x)\in C_{2,b}. \]

These are linear constraints and an affine objective because \(S\) is an affine map. Every feasible region is bounded by \(B\).

The pairs cover \(B\): for every \(x\in B\), the point \(S(x)\) belongs to a cell for \(f_1\) and a cell for \(f_2\). On each pair’s feasible region, its objective equals \(G(x)\). Therefore, the largest optimum among the feasible linear programs equals \(\max_{x\in B}G(x)\).

For boundary conventions, rational polyhedral cells can be taken closed. If the input instead uses relatively open cells, first intersect each cell with \(D\), discard empty intersections, and take closures. Continuity extends its affine formula to that closure. These operations are polynomial-time: emptiness with strict inequalities is checked by maximizing a common positive slack; for a nonempty intersection, replacing strict inequalities by weak ones gives its closure. Thus this convention does not change the argument.

4. Running time and rational output

We use the standard rational linear-programming theorem: feasibility and bounded optimization for explicitly given rational linear programs can be solved exactly in time polynomial in their binary encoding length, returning a rational optimizer of polynomial encoding length. This applies also to feasible regions of lower dimension. See the treatment of feasibility and optimization in [MIT’s linear-programming notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).

There are \(N_1N_2\) linear programs. Because the cell lists are explicit parts of the input, this number is polynomial in \(L\). Each program has \(m=\tau\) variables, and its encoding length is polynomial in \(m,K,L\): substituting \(S(x)\) requires only rational arithmetic on the supplied coefficients and \(\mu\).

Solve these programs exactly, discard infeasible ones, and choose a rational optimizer \(x^\star\) with the largest objective value. Output the multiset \([x^\star,\mu-x^\star]\), deleting zero vectors but retaining both occurrences if the vectors are identical.

This is a feasible rational partition maximizing welfare over at most two blocks. Section 2 proves that its welfare is at least \(\mathrm{OPT}/K\). The entire algorithm runs in time polynomial in \(m,\tau,K,L\).

⟨structured verdict parsed — rendered above⟩

The prover resolves both questions correctly under the stated explicit representation. The approximation argument is valid, and the proposed algorithm finds a rational partition attaining the guarantee in polynomial time. No major or minor mathematical issues were found.

1. Existence and interpretation of the optimum

The ordered-slot domain \(D\) is nonempty: placing \(\mu\) in one slot and zero vectors in the remaining slots is feasible. Its defining constraints are closed, and the coordinate bounds stated in the proof make it bounded. Compactness therefore follows.

The objective \(F=\sum_{j=1}^{K}f_j\) is continuous, so the extreme-value theorem applies. Its hypotheses are satisfied exactly as written.

The passage between slot representations and feasible multisets is correct:

• The positive total mass ensures at least one nonzero slot.
• Deleting zero slots preserves welfare.
• Permutation equivariance preserves the sum of slot values.
• Repeated nonzero vectors remain separate occurrences.

Consequently, the attained maximum on \(D\) is precisely \(\mathrm{OPT}\). This step does not assume the existence of a rational global optimizer.

2. The approximation guarantee

Selecting a block occurrence whose value is at least the average is valid for the finite list of \(r\) block values.

If \(r\le 2\), the optimal partition satisfies the required block bound because it also has \(r\le K\).

If \(r\ge 3\), every proposed merge combines two nonzero blocks other than the selected occurrence. Their sum is nonzero, the selected occurrence remains an unaffected block, and the number of blocks decreases. Thus every intermediate partition is feasible, and positive externalities apply at every merge.

The resulting second block is nonzero. Nonnegativity justifies bounding total welfare below by the selected block’s value. The final comparison
\[ \frac{\mathrm{OPT}}{r}\ge\frac{\mathrm{OPT}}{K} \]
is valid because \(r\le K\) and \(\mathrm{OPT}\ge 0\).

The occurrence-based interpretation also handles identical vectors correctly. No claim about the merged block’s value is needed beyond its stipulated nonnegativity.

3. Optimization over at most two blocks

For \(K=1\), the unique feasible partition is correctly identified.

For \(K\ge 2\), the map \(S(x)\) parametrizes every feasible partition with at most two nonzero blocks, up to slot permutation. Its endpoints represent the one-block partition, and all other zero slots contribute zero welfare. Hence the formula for \(G\) is correct.

For each cell pair, affine substitution produces rational linear constraints and a rational affine objective. The feasible region is bounded by \(B\). On that region, the objective equals the actual welfare \(G\).

Coverage of the slot domain ensures coverage of \(B\) by these pairwise feasible regions. Therefore, selecting the largest feasible linear-program optimum gives exactly the maximum two-block welfare. Overlapping cells cause no inconsistency because their formulas describe the same functions on overlaps.

4. Cell boundaries

The optional treatment of relatively open cells is sound. Intersecting with \(D\) before taking closures keeps the extension within the domain where continuity is assumed.

The nonemptiness check is essential and is explicitly included. For a nonempty region defined by linear equalities and weak and strict inequalities, weakening the strict inequalities describes its closure. Continuity then preserves the affine formula on that closure.

The stated common-slack feasibility check is a standard polynomial-size linear-programming operation. This paragraph introduces no unresolved boundary gap.

5. Complexity and rational output

The rational linear-programming theorem is stated with the properties needed here: exact feasibility and bounded optimization, polynomial bit complexity, rational optimizers, and applicability to lower-dimensional regions. The cited [MIT notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) address arbitrary-polyhedron feasibility, polynomial precision, and optimization.

All applications satisfy the theorem’s hypotheses. The cell lists are explicit, so the number \(N_1N_2\) of programs is polynomial in \(L\). Rational substitution has polynomial encoding length, and exact comparison of the resulting rational objective values is polynomial-time.

Deleting zero output vectors produces a feasible rational partition; retaining identical nonzero occurrences respects the multiset definition. Combining exact two-block optimization with Section 2 establishes the requested guarantee.

Repair feedback: None is required.

⟨structured verdict parsed — rendered above⟩