d4-conf-ecai-2008-0090 (d4-conf-ecai-2008-0090)

Given a finite type set \(T\), rational mass vector \(\mu\) with \(\sum_{t\in T}\mu_t=1\), and a nonnegative value evaluator \(V(x;\Pi)\) for blocks \(x\in\mathbb{R}_{\geq 0}^{T}\) in finite partitions \(\Pi\) of \(\mu\), promised that every feasible merge of blocks \(x,y\) into \(x+y\) satisfies \(V(x+y;\Pi')\geq V(x;\Pi)+V(y;\Pi)\) and \(V(z;\Pi')\geq V(z;\Pi)\) for every other block \(z\), output a partition maximizing \(\sum_{x\in\Pi}V(x;\Pi)\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
A feasible partition \(\Pi\) is a finite multiset of nonzero blocks \(x\in\mathbb R_{\geq0}^{T}\) satisfying \(\sum_{x\in\Pi}x=\mu\); equal vectors may represent distinct blocks. Every pair of distinct block occurrences may merge.
The input includes a finitely described evaluator \(V(x;\Pi)\in\mathbb R_{\geq0}\), invariant under reordering blocks, with exact nonnegative rational outputs on rational inputs and polynomial-time evaluation in its description length and the query bit length. Let \(L\) be the total input bit length; there is no separate \(m\) parameter.
For every feasible partition and every merge of occurrences \(x,y\), let \(\Pi'\) replace them by \(x+y\). The input is promised to satisfy \(V(x+y;\Pi')\geq V(x;\Pi)+V(y;\Pi)\) and \(V(z;\Pi')\geq V(z;\Pi)\) for every unmerged occurrence \(z\). These promises apply also to real blocks.
Output a finite partition with binary-rational block coordinates maximizing \(\sum_{x\in\Pi}V(x;\Pi)\) over all feasible real partitions; any maximizer is acceptable.

Is this promised optimization problem solvable in polynomial time in \(\tau\) and \(L\), or is it NP-hard?

For finite agents, weak superadditivity and weak positive externalities guarantee that the grand coalition is optimal, yielding polynomial-time construction; weak subadditivity with weak negative externalities instead makes the singleton partition optimal. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2008.pdf)
No result for exactly the distributional problem specified here was verified.

Result

The promised optimization problem is solvable in polynomial time in \(\tau\) and \(L\). The algorithm outputs the one-block partition \(\Pi^\star=\{\mu\}\).

The grand-coalition argument applies directly to the distributional setting: every competing partition is finite, and every pair of distinct block occurrences may merge.

Proof of optimality

Define the welfare of a feasible partition by

\(W(\Pi)=\sum_{x\in\Pi}V(x;\Pi)\),

where the sum counts block occurrences, including repeated vectors.

Lemma. Every permitted merge weakly increases welfare.

Proof. Write the block occurrences of a partition with at least two blocks as \(\Pi=\{x_1,x_2,\ldots,x_k\}\). Merge the first two occurrences to obtain

\(\Pi'=\{x_1+x_2,x_3,\ldots,x_k\}\).

This partition is feasible: the sum of its blocks remains \(\mu\), and \(x_1+x_2\) is nonzero because its summands are nonnegative and nonzero.

The promised inequalities give

\(V(x_1+x_2;\Pi')\geq V(x_1;\Pi)+V(x_2;\Pi)\)

and, for every index \(i\) with \(3\leq i\leq k\),

\(V(x_i;\Pi')\geq V(x_i;\Pi)\).

Adding these inequalities yields

\(W(\Pi')=V(x_1+x_2;\Pi')+\sum_{i=3}^{k}V(x_i;\Pi')\geq V(x_1;\Pi)+V(x_2;\Pi)+\sum_{i=3}^{k}V(x_i;\Pi)=W(\Pi)\).

For \(k=2\), the sums over unmerged occurrences are empty. The calculation remains valid when vectors coincide, because the promises apply to distinct occurrences. This proves the lemma.

Theorem. The partition \(\Pi^\star=\{\mu\}\) maximizes welfare over all feasible real partitions.

Proof. Let \(\Pi\) be an arbitrary feasible real partition with \(k\) block occurrences. Because \(\sum_{t\in T}\mu_t=1\), the partition has at least one block.

If \(k=1\), feasibility forces its only block to equal \(\mu\). If \(k>1\), repeatedly merge any two occurrences. Each merge is permitted, preserves feasibility, and decreases the number of occurrences by one. After exactly \(k-1\) merges, the remaining block equals \(\mu\), by preservation of the sum.

Applying the lemma at each merge gives

\(W(\Pi)\leq W(\{\mu\})=V(\mu;\{\mu\})\).

The promises cover real blocks, so this argument includes partitions with irrational coordinates. Since \(\Pi\) was arbitrary and \(\{\mu\}\) is feasible, the claimed maximum is attained.

Algorithm and encoding complexity

Output one block whose coordinate for each type \(t\in T\) is the input mass \(\mu_t\). These coordinates are already positive binary rationals, so the output satisfies the required encoding restriction.

The algorithm merely copies the support coordinates and their masses. Its output length and running time are \(O(L+\tau)\) under the given explicit encoding. It does not need to evaluate \(V\) or verify the promises. If the optimal value is also desired, one evaluation of \(V(\mu;\{\mu\})\) takes polynomial time by the evaluator assumption.

Although feasible partitions have no uniform bound on their number of blocks, each competitor is finite. The merge sequence establishes the bound for each competitor; the algorithm itself constructs only the single optimal block. This is the direct distributional counterpart of the finite-agent merge argument in the [cited paper](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2008.pdf).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument resolves the specified optimization problem, including comparison with all feasible real partitions. No major or minor issues were found.

• Welfare is well-defined. Every feasible partition is finite, and the evaluator takes finite nonnegative real values. The definition of \(W(\Pi)\) correctly counts block occurrences, including repeated vectors.

• Merge feasibility is verified. Replacing two occurrences by their sum preserves the total vector \(\mu\) and coordinate nonnegativity. Their sum is nonzero because both summands are nonnegative and nonzero. Thus the resulting partition satisfies every feasibility requirement.

• Both promises are applied correctly. The merged occurrence receives at least the combined previous values of its two constituents. Each unmerged occurrence receives at least its previous value. These inequalities concern the appropriate partitions before and after the merge. Their finite sum gives exactly the claimed inequality \(W(\Pi')\geq W(\Pi)\).

The write-up explicitly handles repeated vectors as distinct occurrences and the empty sum when there are exactly two blocks. Neither case introduces an exception.

• The merge sequence establishes global optimality. The proof fixes an arbitrary feasible real partition with a finite number \(k\) of occurrences. Positive total mass excludes \(k=0\). For \(k=1\), feasibility forces the sole block to be \(\mu\). For \(k>1\), every successive merge remains permitted and feasible, and exactly \(k-1\) merges leave the block \(\mu\).

Applying the established welfare inequality along this finite sequence proves \(W(\Pi)\leq W(\{\mu\})\). The quantifier covers every feasible partition individually; no uniform bound on their sizes is needed.

• The real domain is fully covered. The proof invokes promises explicitly stated to hold for real blocks. Consequently, it covers irrational coordinates without requiring continuity, approximation, or evaluation at irrational inputs by an algorithm. Since \(\{\mu\}\) is feasible, the upper bound is attained.

• The output and complexity claims are valid. The output copies the input masses into one block, so its coordinates satisfy the required binary-rational restriction. Under the stated explicit support encoding, copying the support and masses takes \(O(L+\tau)\) time and output length. Neither optimizing nor constructing the output requires evaluating \(V\) or checking the promises. The optional optimal-value computation also has polynomial query length and therefore falls within the evaluator’s stated guarantee.

• The literature comparison is ancillary and accurate. The cited paper’s Theorem 1 states the corresponding grand-coalition optimality result for finite-agent games with weak superadditivity and weak positive externalities. The submitted distributional proof establishes its own conclusion directly rather than assuming that theorem applies to real blocks. [Cited paper](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2008.pdf)

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩