d4-conf-atal-2011-0140 (d4-conf-atal-2011-0140)

Given a population scale \(N\), finite DER types \(T\), rational distribution \(\mu\), positive per-unit outputs \(q_t\), and price \(p>0\), with accurate estimates, compute type payments \(y_t\) that distribute \(pQ\log Q\) and give every submass \(\nu\), where \(0\leq\nu_t\leq N\mu_t\), at least its value \(pQ_\nu\log Q_\nu\). Here \(Q=N\sum_{t\in T}\mu_tq_t\), \(Q_\nu=\sum_{t\in T}\nu_tq_t\), and \(v(0)=0\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) DER types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Inputs also include positive binary rationals \(N,p,q_t\), where \(N\) scales population mass, \(p\) is price, and \(q_t\) is output per unit mass. Production estimates are accurate.
There is one production coordinate, \(m=1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), including the binary encoding of \(N\).
Set \(Q=N\sum_{t\in T}\mu_tq_t\). A coalition is any real submass vector \(\nu\) with \(0\leq\nu_t\leq N\mu_t\); write \(Q_\nu=\sum_{t\in T}\nu_tq_t\) and \(v(\nu)=pQ_\nu\log Q_\nu\), with \(v(0)=0\) and natural logarithms.
A type payment \(y_t\in\mathbb R\) is payment per unit mass, constant within type. Find payments satisfying \(\sum_{t\in T}N\mu_ty_t=pQ\log Q\) and \(\sum_{t\in T}\nu_ty_t\geq v(\nu)\) for every coalition \(\nu\). Signed payments are allowed; all revenue is distributed without fees or deductions.
Exact payments may be represented by finite expressions using binary-rational constants, arithmetic operations, and natural logarithms of positive arguments; computation is measured in the bit model, including expression length.

Is computing such a core allocation polynomial-time solvable in \(\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite agents with accurate estimates, production-proportional payments distribute the entire revenue and belong to the core; thus the discrete core is nonempty. [Source](https://pure.hw.ac.uk/ws/files/7446774/ccrjVPPcoop.pdf)
No result settling this exact continuous computational problem was located in the literature search.

Result and exact construction

Computing a core allocation is polynomial-time solvable. For the stipulated \(m=1\), an exact allocation can be output in \(O(\tau L)\) bit operations, with total expression length \(O(\tau L)\).

Define the payment per unit mass of type \(t\) by

\(y_t=pq_t\log Q,\qquad Q=N\sum_{s\in T}\mu_sq_s.\)

Because \(T\) is nonempty and \(N,\mu_s,q_s\) are positive, \(Q>0\), so these expressions are well-defined.

This is the continuous counterpart of the production-proportional allocation in Theorem 1 of the [cited paper](https://pure.hw.ac.uk/ws/files/7446774/ccrjVPPcoop.pdf). The proof below verifies the constraints directly for every real submass coalition.

Proof of core membership

A core allocation must distribute the grand coalition’s entire value and pay every coalition at least its value.

First, the proposed payments satisfy the required efficiency equality:

\(\displaystyle \sum_{t\in T}N\mu_ty_t =p\log Q\sum_{t\in T}N\mu_tq_t =pQ\log Q.\)

Next, fix any coalition \(\nu\) satisfying \(0\leq\nu_t\leq N\mu_t\) for every \(t\in T\). Since each \(q_t>0\), these coordinatewise inequalities imply

\(\displaystyle 0\leq Q_\nu=\sum_{t\in T}\nu_tq_t \leq\sum_{t\in T}N\mu_tq_t=Q.\)

If \(Q_\nu=0\), positivity of the \(q_t\) and nonnegativity of the \(\nu_t\) imply \(\nu_t=0\) for every \(t\). Thus the coalition’s payment and its stipulated value are both zero.

If \(Q_\nu>0\), monotonicity of the natural logarithm gives \(\log Q_\nu\leq\log Q\). Multiplying by the positive number \(pQ_\nu\) yields

\(\displaystyle \sum_{t\in T}\nu_ty_t =pQ_\nu\log Q \geq pQ_\nu\log Q_\nu =v(\nu).\)

This proves every coalition constraint, including those for arbitrary real submasses.

The argument also covers \(Q<1\): the payments are then negative, as permitted by the problem, and the same inequality holds. For \(Q=1\), every proposed payment is zero and every coalition value is nonpositive.

Bit complexity and expression length

The permitted output representation makes numerical evaluation of logarithms unnecessary. Indeed, even the rational arithmetic inside their arguments can remain unevaluated.

Construct the expression

\(\displaystyle E=N\left(\sum_{s\in T}\mu_sq_s\right)\)

using the input’s binary-rational constants, multiplication symbols, addition symbols, and parentheses. Its encoded length is \(O(L+\tau)=O(L)\), since the input explicitly lists \(\tau\) types and consequently \(\tau=O(L)\).

For each \(t\), output the expression \(pq_t\log(E)\), inserting a complete copy of \(E\). Each payment expression has length \(O(L)\), so all \(\tau\) expressions together have length \(O(\tau L)\). These are standalone finite expressions of precisely the allowed form. Every logarithm has the positive argument \(E=Q\).

A direct algorithm scans and copies the input constants to construct each expression. It therefore takes \(O(\tau L)\) bit operations, including writing the output. This bound includes the binary encoding of \(N\); the algorithm never iterates over a population of size \(N\).

Thus, in terms of the requested parameters, the proved bound is \(T(1,\tau,L)=O(\tau L)\) for \(m=1\). No enumeration of coalitions or of possible unsupported types is required.

⟨structured verdict parsed — rendered above⟩

Verdict

The output fully resolves the assigned problem. The proposed allocation satisfies efficiency and every real-submass coalition constraint. Its exact expression representation can be produced within the claimed polynomial bit complexity. No major or minor issues were found.

Step-by-step verification

• Definition and domain. The proposed payment is \(y_t=pq_t\log Q\). The support is nonempty, and every factor contributing to \(Q=N\sum_{s\in T}\mu_sq_s\) is positive. Therefore \(Q>0\), and every payment is a well-defined real number, constant within its type.

• Efficiency. Substitution gives

\[ \sum_{t\in T}N\mu_ty_t =p\log Q\sum_{t\in T}N\mu_tq_t =pQ\log Q. \]
Both equalities follow directly from the proposed payments and the definition of \(Q\). All revenue is distributed.

• Coalition production bound. For an arbitrary admissible real vector \(\nu\), multiplying each inequality \(0\leq\nu_t\leq N\mu_t\) by \(q_t>0\) and summing yields \(0\leq Q_\nu\leq Q\). This applies to every permitted coalition, without an integrality assumption.

• Zero-production case. If \(Q_\nu=0\), the nonnegative summands \(\nu_tq_t\), with \(q_t>0\), force every \(\nu_t=0\). The coalition payment is consequently zero, equal to its stipulated value. No logarithm at zero is evaluated.

• Positive-production case. For \(Q_\nu>0\), both logarithm arguments are positive. Monotonicity gives \(\log Q_\nu\leq\log Q\). Since \(pQ_\nu>0\), multiplication preserves the inequality:

\[ \sum_{t\in T}\nu_ty_t =pQ_\nu\log Q \geq pQ_\nu\log Q_\nu =v(\nu). \]
The coalition was arbitrary, so this proves the full quantified constraint.

• Sign and boundary cases. The proof does not assume positive logarithms. It remains valid when \(Q<1\), where payments are negative and signed payments are explicitly allowed. When \(Q=1\), payments are zero and coalition values are nonpositive. The grand coalition attains equality. These cases are correctly addressed.

• Exact output representation. The expression \(E=N(\sum_{s\in T}\mu_sq_s)\) uses only permitted constants and arithmetic operations. Inserting \(E\) into \(pq_t\log(E)\) produces a permitted exact expression with a positive logarithm argument. The task permits unevaluated finite expressions, so neither rational simplification nor numerical logarithm evaluation is required.

• Expression length and running time. One copy of \(E\) contains input constants of total length at most \(L\), together with \(O(\tau)\) syntax. Because the support is explicitly listed, \(\tau=O(L)\), giving length \(O(L)\). Copying this expression into each of the \(\tau\) payment expressions gives total length \(O(\tau L)\). Sequential scans and copies achieve the same bit-operation bound. The encoding of \(N\) is included in \(L\); no iteration proportional to its numerical value occurs. The stated bound \(T(1,\tau,L)=O(\tau L)\) correctly addresses the stipulated \(m=1\).

• External reference. The description of the finite-agent production-proportional allocation agrees with Theorem 1 of the [cited paper](https://pure.hw.ac.uk/ws/files/7446774/ccrjVPPcoop.pdf). The prover uses this reference as context, not as a theorem establishing the continuous result. Its direct proof independently verifies all required constraints, so there is no unverified theorem application.

Repair feedback

None required. The mathematical proof and expression-output algorithm establish polynomial-time solvability under the exact representation specified in the task.

⟨structured verdict parsed — rendered above⟩