d4-conf-ecai-2014-0049 (d4-conf-ecai-2014-0049)

Given a terminal proposer with voting weight \(w_0\) and a responder society with rational type masses \(\mu_t\), where \(\sum_t\mu_t=1\), each type \(t\) has voting weight \(w_t\), discount factor \(\delta_t\), and per-capita conflict share \(\alpha_t\). For quota \(q\) and proposer outside payoff \(d_0\), choose offered fractions \(y_t\in[0,1]\) minimizing \(\sum_t\mu_t y_t\delta_t\alpha_t\), subject to \(w_0+\sum_t\mu_t y_t w_t\ge q\) and \(1-\sum_t\mu_t y_t\delta_t\alpha_t\ge d_0\). Compute the accepting fractions and the proposer’s residual share.

A society is given by its support: the list of the \(\tau\ge1\) responder types with positive masses \(\mu_t\), each encoded as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There is a unit-sized divisible pie and a terminal proposer. All input numbers are binary rationals; voting weights satisfy \(w_0,w_t>0\), responder discounts satisfy \(0<\delta_t\le1\), and conflict-share densities satisfy \(\alpha_t\ge0\). Assume \(0<q\le w_0+\sum_t\mu_tw_t\).
Define the proposer's conflict share by \(\alpha_0=1-\sum_t\mu_t\alpha_t\ge0\). Its outside payoff is \(d_0=\delta_0\alpha_0\) for some \(0<\delta_0\le1\), measured in terminal-round units; conflict occurs one round later.
Within each type, arbitrary fractions may receive different offers. A fraction \(y_t\in[0,1]\) receives the per-unit-mass offer \(\delta_t\alpha_t\), and the remainder receives zero. Responders accept at equality with their discounted conflict payoff, so require \(y_t=1\) whenever \(\alpha_t=0\). The proposer votes in favor.
Set \(C(y)=\sum_t\mu_ty_t\delta_t\alpha_t\). Compute a minimizer of \(C(y)\) subject to \(w_0+\sum_t\mu_ty_tw_t\ge q\) and \(1-C(y)\ge d_0\), and its residual share \(1-C(y)\); report infeasibility if necessary. Any minimizer is allowed.

Is this exact terminal-offer computation solvable in polynomial time in \(\tau\) and the total binary input length \(L\), or is it NP-hard? The bargaining-cycle count \(m\) does not enter this terminal-round input.

Discrete: computing a terminal equilibrium offer with nonnegative conflict shares summing to one is NP-hard even under perfect information; the fuller treatment retains this result. [Fatima–Wooldridge, 2014](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2014a.pdf), [Fatima–Wooldridge, 2016](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2016a.pdf).
Continuous: no published result settling this exact support-encoded mass problem was located.

Result

The exact terminal-offer computation is solvable in polynomial time in \(\tau\) and the total binary input length \(L\). A greedy algorithm computes an exact rational minimizer, with at most one type receiving a strictly fractional selection.

Moreover, every input satisfying the stated hypotheses is feasible.

1. The proposer’s outside-payoff constraint is automatic

For any vector \(y\) satisfying \(0\le y_t\le1\),

\(C(y)=\sum_t\mu_ty_t\delta_t\alpha_t \le\sum_t\mu_t\delta_t\alpha_t \le\sum_t\mu_t\alpha_t =1-\alpha_0 \le1-\delta_0\alpha_0 =1-d_0.\)

The first two inequalities use \(\mu_t>0\), \(\alpha_t\ge0\), and \(\delta_t\le1\). The last inequality uses \(\alpha_0\ge0\) and \(\delta_0\le1\).

Thus every such vector satisfies \(1-C(y)\ge d_0\). In particular, selecting \(y_t=1\) for every type satisfies both this constraint and the quorum constraint, because the assumed bound on \(q\) gives

\(w_0+\sum_t\mu_tw_t\ge q.\)

Consequently, infeasibility cannot occur under the stated hypotheses.

2. Reduction to fractional knapsack

Partition the support into

\(Z=\{t:\alpha_t=0\},\qquad P=\{t:\alpha_t>0\}.\)

For every \(t\in Z\), set \(y_t=1\), as required by acceptance at equality. These types contribute no cost and supply voting weight

\(W_Z=\sum_{t\in Z}\mu_tw_t.\)

Define the remaining voting requirement by

\(R=\max\{0,q-w_0-W_Z\}.\)

For each \(t\in P\), define its voting capacity, cost per voting-weight unit, and selected voting weight by

\(b_t=\mu_tw_t>0,\qquad \rho_t=\frac{\delta_t\alpha_t}{w_t}>0,\qquad x_t=b_ty_t.\)

Because \(b_t>0\), this substitution gives a bijection between \(y_t\in[0,1]\) and \(x_t\in[0,b_t]\). Moreover,

\(\mu_ty_t\delta_t\alpha_t=\rho_tx_t.\)

The remaining optimization is therefore exactly

\(\min\sum_{t\in P}\rho_tx_t \quad\text{subject to}\quad 0\le x_t\le b_t,\qquad \sum_{t\in P}x_t\ge R.\)

The quorum assumption implies

\(R\le\sum_{t\in P}b_t.\)

Indeed, \(q-w_0-W_Z\le\sum_{t\in P}\mu_tw_t\), and the right-hand side is nonnegative.

3. Exact algorithm and output

If \(R=0\), choose \(y_t=0\) for every \(t\in P\). Together with \(y_t=1\) on \(Z\), this gives minimum cost \(C^*=0\) and proposer residual share \(1\): costs are nonnegative, so no smaller cost is possible.

Suppose now that \(R>0\). Then \(P\) is nonempty. Write its types as \(t_1,\ldots,t_n\), ordered so that

\(\rho_{t_1}\le\cdots\le\rho_{t_n}.\)

Ties may be ordered arbitrarily. Abbreviate \(b_i=b_{t_i}\) and \(\rho_i=\rho_{t_i}\), and define

\(B_0=0,\qquad B_j=\sum_{i=1}^j b_i.\)

Let \(k\) be the smallest index with \(B_k\ge R\). It exists because \(B_n\ge R\). By minimality,

\(0<R-B_{k-1}\le b_k.\)

Choose

\(x_i^*= \begin{cases} b_i,&i<k,\\ R-B_{k-1},&i=k,\\ 0,&i>k. \end{cases}\)

Return \(y_{t_i}^*=x_i^*/b_i\), together with \(y_t^*=1\) for \(t\in Z\).

This vector lies within the required bounds and supplies exactly \(R\) voting weight from \(P\). Hence it meets the quorum, and Section 1 proves that it also meets the proposer’s outside-payoff constraint.

Its cost and proposer residual are

\(C^*=\sum_{i<k}\mu_{t_i}\delta_{t_i}\alpha_{t_i} +\rho_k(R-B_{k-1}),\qquad p_0^*=1-C^*.\)

The offer is represented by these fractions: within type \(t\), a fraction \(y_t^*\) receives per-unit-mass payment \(\delta_t\alpha_t\), and the remainder receives zero. Only type \(t_k\) can have a fraction strictly between zero and one.

4. Proof of optimality

Continue with \(R>0\). Let \(x\) be any feasible vector for the reduced problem, and set \(\lambda=\rho_k>0\). Since \(\sum_i x_i^*=R\),

\(\sum_i\rho_ix_i-\sum_i\rho_ix_i^* =\lambda\left(\sum_i x_i-R\right) +\sum_i(\rho_i-\lambda)(x_i-x_i^*).\)

Every term on the right is nonnegative:

• Feasibility gives \(\sum_i x_i\ge R\), so the first term is nonnegative.
• For \(i<k\), ordering gives \(\rho_i-\lambda\le0\), while \(x_i-x_i^*=x_i-b_i\le0\). Their product is nonnegative.
• For \(i=k\), the coefficient \(\rho_i-\lambda\) is zero.
• For \(i>k\), ordering gives \(\rho_i-\lambda\ge0\), while \(x_i-x_i^*=x_i\ge0\). Their product is nonnegative.

Therefore \(\sum_i\rho_ix_i\ge\sum_i\rho_ix_i^*\). The substitution in Section 2 preserves the objective and feasibility, so \(y^*\) is a minimizer of the original problem.

5. Polynomial bit complexity

Use exact rational arithmetic, representing each rational by an integer numerator and a positive integer denominator, both written in binary.

The algorithm performs \(O(\tau\log(\tau+1))\) rational comparisons for sorting and \(O(\tau)\) additional arithmetic operations. Comparisons are exact: ratios can be compared by cross-multiplying their positive denominators.

These operation counts also give polynomial bit complexity:

• Each individual capacity \(b_t\), ratio \(\rho_t\), and full-selection cost \(\mu_t\delta_t\alpha_t\) is formed using a constant number of products or quotients of input rationals. Its numerator and denominator therefore have \(O(L)\) bits.
• A sum of at most \(\tau\) such rationals can be represented using their product denominator. That denominator has \(O(\tau L)\) bits; the corresponding numerator has \(O(\tau L+\log(\tau+1))\) bits.
• Consequently, \(W_Z\), \(R\), and every prefix sum \(B_j\) have polynomial bit length. The fractional output \((R-B_{k-1})/b_k\), the cost \(C^*\), and the residual \(1-C^*\) require only a constant number of further rational operations and retain polynomial bit length.

Integer arithmetic and comparisons on these representations take polynomial time. Thus the entire algorithm, including writing its exact rational output, runs in time polynomial in \(\tau\) and \(L\). The bargaining-cycle count \(m\) is neither used nor needed.

6. Relation to the discrete hardness result

The cited discrete terminal optimization requires binary coalition choices, as displayed in [Fatima–Wooldridge (2014), Theorem 7](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2014a.pdf) and [Fatima–Wooldridge (2016), Theorem 12](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2016a.pdf).

Here, arbitrary fractions within every supported type are permitted. This gives precisely the continuous variables used above, for which the greedy optimality proof applies. The discrete hardness result therefore does not obstruct polynomial-time computation for this support-encoded mass problem.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The algorithm computes an exact rational minimizer in polynomial time in \(\tau\) and \(L\), and its argument establishes feasibility for every input satisfying the stated hypotheses. No major or minor mathematical issues were found.

• The outside-payoff constraint is automatic.

Every inequality in Section 1 is valid. The bounds \(0\le y_t\le1\), \(\mu_t>0\), \(\alpha_t\ge0\), and \(0<\delta_t\le1\) imply
\[ C(y)\le\sum_t\mu_t\alpha_t=1-\alpha_0. \]
Since \(\alpha_0\ge0\) and \(\delta_0\le1\), one has \(1-\alpha_0\le1-\delta_0\alpha_0=1-d_0\). Thus the proposer’s constraint holds throughout the box of allowed selections.

The vector with every \(y_t=1\) also satisfies the mandatory selections for zero-conflict types and the quorum bound. Consequently, the feasibility claim is correct, including when \(\alpha_0=0\) or some discounts equal one.

• The reduction preserves the original optimization problem.

The partition into \(Z\) and \(P\) exhausts the support because all conflict-share densities are nonnegative. Setting \(y_t=1\) on \(Z\) is required by the task and contributes precisely the stated voting weight at zero cost.

For each \(t\in P\), both \(b_t\) and \(\rho_t\) are strictly positive. Hence the substitution \(x_t=b_ty_t\) is invertible on the stated intervals. The identity \(\rho_tx_t=\mu_ty_t\delta_t\alpha_t\) correctly preserves costs.

Removing the fixed voting contribution gives the lower bound \(\sum_{t\in P}x_t\ge R\). Taking the maximum with zero is valid because selected voting weights are nonnegative. The outside-payoff constraint can be omitted by Section 1.

The claimed capacity bound \(R\le\sum_{t\in P}b_t\) follows from the input quorum bound. It also covers an empty \(P\), in which case \(R=0\).

• The construction is defined and feasible in all cases.

When \(R=0\), selecting no positive-conflict types gives zero cost, which is optimal by nonnegativity.

When \(R>0\), the capacity bound guarantees that \(P\) is nonempty and that the index \(k\) exists. Strict positivity of capacities and minimality of \(k\) yield
\[ 0<R-B_{k-1}\le b_k. \]
Therefore every constructed coordinate respects its bounds, and their sum is exactly \(R\).

Dividing by \(b_i>0\) produces valid fractions. The construction handles \(R=B_k\) correctly: the boundary type is then fully selected. It also handles \(R=B_n\), arbitrary ties, and a support containing only zero-conflict types. At most one type is strictly fractional.

The stated cost formula follows directly from the selected coordinates, and the residual is correctly computed as \(1-C^*\). The representation specifies the offers requested by the task.

• The optimality proof is complete.

The comparison vector \(x\) is arbitrary among all feasible reduced vectors, including those supplying more than \(R\) voting weight.

The displayed objective-difference identity is algebraically correct because \(\sum_i x_i^*=R\). Every sign assertion is justified:

• The excess-weight term is nonnegative because \(\lambda>0\) and feasibility gives \(\sum_i x_i\ge R\).
• Before the boundary index, both factors in each product are nonpositive.
• At the boundary index, the coefficient vanishes.
• After the boundary index, both factors are nonnegative.

Tied ratios cause zero coefficients and do not affect the argument. Thus the constructed vector has cost no greater than any feasible vector. The established substitution transfers this conclusion to the original problem. No unstated optimality theorem is needed.

• The polynomial bit-complexity claim is justified.

The operation counts correctly include sorting, forming capacities and ratios, accumulating voting weights and costs, and writing the output fractions.

A constant number of products or quotients of input rationals gives numerators and denominators of \(O(L)\) bits. For the sums used here, a product denominator has \(O(\tau L)\) bits; the corresponding numerator bound is also polynomial. Subtractions, comparisons, the boundary fraction, and the final cost and residual therefore retain polynomial bit length.

All divisions have nonzero denominators: input rational denominators are positive, voting weights are positive, and every capacity used in division is positive. Exact integer arithmetic and cross-multiplication on these polynomial-length representations take polynomial time. The output length is polynomial as well.

Neither enumeration of unsupported types nor dependence on \(m\) occurs.

• The comparison with discrete hardness is accurate and ancillary.

The terminal optimization displayed in the proofs of [the 2014 paper’s Theorem 7](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ecai2014a.pdf) and [the 2016 paper’s Theorem 12](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2016a.pdf) uses binary coalition variables. This supports the prover’s stated distinction from the continuously selectable type masses.

The continuous conclusion is established independently by Sections 1–5; it does not rely on applying either discrete hardness theorem to the present input model.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩