d4-journals-mss-2013-0031 (d4-journals-mss-2013-0031)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, and an explicit rational, differentiable, monotone, convex production function \(V:[0,\mu]\to[0,1]\) with \(V(0)=0\) and \(V(\mu)=1\), compute an exact lottery \(\Pi\) over cutoffs \(q\in(0,1]\). Rank the population mass by \(h_t=\int_0^1 \partial_t V(\lambda\mu)\,d\lambda\); for each cutoff, let the top \(q\) mass decide by simple majority and share the unit payoff equally across selected mass, using the finite-clone limit convention. Require the expected aggregate payoff assigned to each type \(t\) to equal \(\mu_t h_t\).

A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). The parameter \(\tau\) counts supported types, not possible types.
The production function \(V:\prod_{t\in T}[0,\mu_t]\to[0,1]\) is given explicitly as a list of monomials with binary rational coefficients and unary nonnegative integer exponents. It is promised to be monotone, convex, and supermodular, with \(V(0)=0\) and \(V(\mu)=1\). Let \(d\) be its total degree and \(L\) the total input bit length; there are \(m=\tau\) production coordinates.
Define \(h_t=\int_0^1\partial_tV(\lambda\mu)\,d\lambda\). Order types by decreasing \(h_t\), breaking ties by their input order, and place each type's mass consecutively along \([0,1]\). For \(q\in(0,1]\), let \(a_t(q)\) be the mass of type \(t\) lying in the prefix \([0,q]\); a cutoff may split a type.
The selected mass decides by simple majority and receives the entire unit payoff, equally per unit of selected mass; unselected mass receives zero. This is the finite-clone convention: equal infinitesimal clones vote independently, and their aggregate Shapley–Shubik payoff for type \(t\) is \(a_t(q)/q\).
An exact cutoff lottery is a finite list of binary rational cutoffs \(q_j\in(0,1]\) and binary rational probabilities \(p_j>0\), with \(\sum_jp_j=1\), satisfying \(\sum_jp_j a_t(q_j)/q_j=\mu_t h_t\) for every \(t\). The computational problem is to construct such a lottery, or report that none exists.

Is this exact cutoff-lottery construction problem solvable in polynomial time in \(m,\tau,d,L\), or is it \(\mathrm{NP}\)-hard?

For finite normalized convex TU games, a lottery over simple-majority committees consisting of prefixes of the Shapley-value ranking reproduces every player's economic Shapley payoff. This is an existence and construction result, without an input-encoding complexity classification ([Di Giannatale and Passarelli](https://mpra.ub.uni-muenchen.de/43059/7/MPRA_paper_43059.pdf)).
No result settling the exact continuous problem specified above was located in the literature search.

Result

The exact cutoff-lottery construction problem is solvable in polynomial time in \(m,\tau,d,L\). Every input satisfying the promises admits a lottery with at most \(\tau\) cutoffs.

Here, binary rational means a rational number whose numerator and denominator are encoded in binary.

1. Nonnegativity and normalization of the target

For \(0<\lambda<1\), the point \(\lambda\mu\) lies in the interior of the production domain because every \(\mu_t\) is positive. Monotonicity and differentiability imply
\( \partial_t V(\lambda\mu)\geq 0 \):
the forward difference quotient in coordinate \(t\) is nonnegative, and its limit is the partial derivative. Consequently,
\( h_t=\int_0^1\partial_t V(\lambda\mu)\,d\lambda\geq 0 \).

The chain rule and the fundamental theorem of calculus give
\( \displaystyle \sum_{t\in T}\mu_t h_t =\int_0^1\sum_{t\in T}\mu_t\partial_t V(\lambda\mu)\,d\lambda =\int_0^1\frac{d}{d\lambda}V(\lambda\mu)\,d\lambda =V(\mu)-V(0)=1. \)

Thus the target payoffs are nonnegative and sum to one.

Relabel the types in the prescribed order, including its tie-breaking rule, so that
\( h_1\geq h_2\geq\cdots\geq h_\tau\geq0 \).
Define
\( S_k=\sum_{i=1}^k\mu_i \)
for \(1\leq k\leq\tau\), and set \(h_{\tau+1}=0\). Positivity of the masses implies
\( 0<S_1<\cdots<S_\tau=1 \).

2. Explicit lottery and proof of correctness

For each \(k\), define the cutoff and its weight by
\( \displaystyle q_k=S_k,\qquad p_k=S_k(h_k-h_{k+1}). \)
Omit every pair whose weight is zero.

The ranking ensures that every retained weight is strictly positive. Furthermore,
\( \displaystyle \sum_{k=1}^{\tau}p_k =\sum_{k=1}^{\tau}\sum_{i=1}^{k}\mu_i(h_k-h_{k+1}) =\sum_{i=1}^{\tau}\mu_i\sum_{k=i}^{\tau}(h_k-h_{k+1}) =\sum_{i=1}^{\tau}\mu_i h_i =1. \)
Here the inner sum telescopes because \(h_{\tau+1}=0\). Hence at least one weight is positive, and the retained pairs form a probability distribution.

At cutoff \(S_k\), precisely the first \(k\) types are selected in full. The specified clone convention therefore gives type \(i\) payoff
\( \displaystyle \frac{a_i(S_k)}{S_k} = \begin{cases} \mu_i/S_k,&i\leq k,\\ 0,&i>k. \end{cases} \)

Its expected payoff under the constructed lottery is
\( \displaystyle \sum_{k=1}^{\tau}p_k\frac{a_i(S_k)}{S_k} =\mu_i\sum_{k=i}^{\tau}\frac{p_k}{S_k} =\mu_i\sum_{k=i}^{\tau}(h_k-h_{k+1}) =\mu_i h_i. \)
Discarding zero weights does not change this equality.

This proves all required payoff equations. Splitting a type is unnecessary.

3. Exact computation of the ranking

Write the explicit polynomial as
\( \displaystyle V(x)=\sum_{\alpha\in A}c_\alpha\prod_{t=1}^{\tau}x_t^{\alpha_t}, \qquad r_\alpha=\sum_{t=1}^{\tau}\alpha_t. \)
For a monomial with \(\alpha_t>0\), its contribution to the integrand is
\( \displaystyle c_\alpha\alpha_t\lambda^{r_\alpha-1} \mu_t^{\alpha_t-1}\prod_{s\ne t}\mu_s^{\alpha_s}. \)
Since \(r_\alpha\geq1\), integration gives the exact rational formula
\( \displaystyle h_t= \sum_{\substack{\alpha\in A\\\alpha_t>0}} \frac{c_\alpha\alpha_t}{r_\alpha} \mu_t^{\alpha_t-1}\prod_{s\ne t}\mu_s^{\alpha_s}. \)
Constant monomials contribute zero. This formula remains valid when some coefficients are negative.

For computation, evaluate each monomial at \(\mu\) once:
\( M_\alpha=\prod_s\mu_s^{\alpha_s} \).
Its contribution to \(h_t\), when \(\alpha_t>0\), is then
\( c_\alpha\alpha_tM_\alpha/(r_\alpha\mu_t) \).
All divisions are legitimate because \(r_\alpha\) and \(\mu_t\) are positive.

After these rational sums are computed, exact rational comparisons determine the required ranking.

4. Polynomial bit complexity

Let \(N\) be the number of listed monomials. Explicit encoding gives \(N=O(L)\). The normalization promises imply \(d\geq1\).

Each numerator and denominator appearing in an input rational has at most \(L\) bits. A monomial evaluation uses powers whose exponents sum to at most \(d\), so its numerator and denominator have \(O(dL)\) bits. Including the coefficient, exponent factor, and divisions above gives a bound
\( B=O((d+1)L+\log(d+1)) \)
on the bit length of each monomial contribution to an \(h_t\).

A sum of at most \(N\) such rationals can be represented using a common denominator equal to the product of their denominators. Its numerator and denominator therefore have
\( O(NB+\log(N+1)) \)
bits. Reduction to lowest terms can only decrease these lengths.

The prefix masses \(S_k\) have
\( O(\tau L+\log(\tau+1)) \)
bits. Consequently, the differences \(h_k-h_{k+1}\) and probabilities \(S_k(h_k-h_{k+1})\) also have polynomial bit length.

Evaluating all monomials and accumulating all derivatives takes polynomially many rational arithmetic operations: repeated multiplication uses at most \(d\) multiplications per monomial, followed by at most \(\tau\) contributions. Sorting, computing prefix sums, and forming the probabilities likewise require polynomially many operations. Integer arithmetic and rational comparison on the bounded-length integers take polynomial time.

The output contains at most \(\tau=m\) rational pairs and has polynomial total length. Thus this is an exact polynomial-time construction.

Convexity and supermodularity are unnecessary for this construction: monotonicity supplies nonnegativity, normalization supplies the total payoff, and the prescribed ranking supplies nonnegative lottery weights.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The construction satisfies every required payoff equation, and its exact rational computation and output size are polynomially bounded.

• Nonnegativity of the target is justified. Since every supported mass is positive, \(\lambda\mu\) is interior for \(0<\lambda<1\). Coordinatewise monotonicity makes the forward difference quotients nonnegative. Polynomial differentiability then gives \(\partial_tV(\lambda\mu)\geq0\). Integrating yields \(h_t\geq0\). Endpoint values cause no problem because polynomial derivatives are continuous.

• Normalization is correct. The polynomial restriction \(\lambda\mapsto V(\lambda\mu)\) is continuously differentiable. The chain rule, finite interchange of sum and integral, and fundamental theorem of calculus therefore apply exactly as written:

\[ \sum_t\mu_th_t=V(\mu)-V(0)=1. \]
Thus the target is a probability allocation.

• The ordering and cutoffs satisfy the domain requirements. Relabeling follows the prescribed decreasing order and input-order tie breaking. Positive masses ensure \(0<S_1<\cdots<S_\tau=1\), so every proposed cutoff lies in the required interval.

• The lottery weights form a probability distribution. The ordering gives \(h_k-h_{k+1}\geq0\), including the final difference because \(h_{\tau+1}=0\). The displayed finite-sum rearrangement and telescoping calculation are correct:

\[ \sum_{k=1}^{\tau}S_k(h_k-h_{k+1}) =\sum_{i=1}^{\tau}\mu_i h_i=1. \]
Consequently, omitting zero weights leaves a nonempty list of strictly positive probabilities summing to one. Ties and zero target values are covered by this argument.

• Every payoff equation is verified. At cutoff \(S_k\), type \(i\) contributes its full mass precisely when \(i\leq k\). The payoff formula follows directly from the clone convention specified in the task. Substituting the proposed probabilities gives

\[ \sum_{k=1}^{\tau}p_k\frac{a_i(S_k)}{S_k} =\mu_i\sum_{k=i}^{\tau}(h_k-h_{k+1}) =\mu_i h_i. \]
All divisions are valid because \(S_k>0\). Removing zero weights preserves the equality. The case \(\tau=1\) is also covered.

• The exact derivative computation is correct. Differentiating a monomial with \(\alpha_t>0\) produces the stated factor \(\lambda^{r_\alpha-1}\). Its integral is \(1/r_\alpha\), since \(r_\alpha\geq1\). Constant monomials contribute zero. Linearity makes the formula valid for signed coefficients, and the alternative expression using \(M_\alpha/\mu_t\) is legitimate because \(\mu_t>0\). Thus every \(h_t\) is rational and can be compared exactly.

• The polynomial-time claim is supported. Monomial products and derivative contributions have polynomial bit length. The product-denominator bound for summing rational contributions is valid even with signed numerators. Prefix sums, differences, and probability products likewise retain polynomial bit length. The number of arithmetic operations, sorting comparisons, and output pairs is polynomial in the stated parameters. Unary exponent encoding also bounds the listed exponents by the input length, so cancellation among listed monomials does not undermine the complexity conclusion.

No external existence theorem is needed: the write-up directly establishes the required construction. Its observation that convexity and supermodularity are unnecessary is supported by the proof. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩