d4-conf-atal-2013-0118 (d4-conf-atal-2013-0118)

Given an atomless unit-mass population of one complete type and a nonnegative rational piecewise-linear worth function \(W:[0,1]\to\mathbb{Q}_{\ge 0}\) with \(W(0)=0\), a coalition \(A\) has worth \(W(|A|)\). Choose a nonnegative tax schedule \(q\) with \(q(1)=0\) and \(q(x)\le W(x)\), and a nonnegative payoff density \(p\) with \(\int_I p(i)\,di=W(1)\), such that \(\int_A p(i)\,di\ge W(|A|)-q(|A|)\) for every measurable \(A\); compute a stable schedule minimizing \(\int_0^1 q(x)\,dx\).

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts listed types, not possible types. Here there is one complete type of mass \(1\), so \(\tau=1\); realize its atomless population as \(I=[0,1]\) with Lebesgue measure \(\lambda\).
The input worth function \(W:[0,1]\to\mathbb{R}_{\ge0}\) is continuous piecewise linear, specified by rational breakpoints and values, with \(m\) linear pieces and \(W(0)=0\). A measurable coalition \(A\subseteq I\) has worth \(W(\lambda(A))\).
A stable pair consists of a measurable tax schedule \(q:[0,1]\to\mathbb{R}_{\ge0}\), with \(q(1)=0\) and \(q(x)\le W(x)\) for every \(x\), and a nonnegative integrable payoff density \(p:I\to\mathbb{R}_{\ge0}\), satisfying \(\int_I p\,d\lambda=W(1)\) and \(\int_A p\,d\lambda\ge W(\lambda(A))-q(\lambda(A))\) for every measurable \(A\subseteq I\).
Minimize \(\int_0^1q(x)\,dx\) over stable pairs. For the associated decision problem, the input also includes \(B\in\mathbb{Q}_{\ge0}\), and asks whether a stable pair has tax integral at most \(B\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).

Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite anonymous nonnegative TU games specified by a rational worth table indexed by coalition size, an optimal schedule minimizing the sum of taxes over all coalitions is computable in polynomial time. [Source](https://www.ifaamas.org/Proceedings/aamas2013/docs/p523.pdf)
No result settling this exact atomless problem with the tax integral objective was located in the literature search.

Result. The decision problem is in \(\mathrm{P}\) on the stated class, where \(\tau=1\). In fact, writing \(c=W(1)\), an optimal stable pair is
\[ \]
\(p_*(s)=c,\qquad q_*(x)=\max\{W(x)-cx,0\}.\)

Its optimal tax integral is therefore
\[ \]
\(T_*=\int_0^1\max\{W(x)-xW(1),0\}\,dx.\)

The argument below proves optimality directly for the atomless model.

1. Every stable schedule has a pointwise lower bound.

Let \((q,p)\) be any stable pair. By hypothesis, \(p\) is nonnegative and integrable, and \(\int_0^1p(s)\,ds=c\).

Fix \(x\in[0,1]\). Identify \([0,1)\) with the circle, and for each \(t\in[0,1)\) define the measurable coalition
\[ \]
\(A_{t,x}=\{s\in[0,1):(s-t)\bmod 1\in[0,x)\}.\)

Each coalition has measure \(x\). Moreover, for every fixed \(s\in[0,1)\), the set of parameters \(t\) for which \(s\in A_{t,x}\) also has measure \(x\): it is a translated circular interval of length \(x\).

Stability applies to every \(A_{t,x}\), so
\[ \]
\(\int_{A_{t,x}}p(s)\,ds\ge W(x)-q(x).\)

The function \((s,t)\mapsto p(s)\mathbf{1}_{A_{t,x}}(s)\) is jointly measurable and nonnegative. Consequently, Tonelli’s theorem permits exchanging the integrals. Integrating the stability inequality over \(t\) gives
\[ \]
\(\begin{aligned} W(x)-q(x) &\le \int_0^1\int_0^1p(s)\mathbf{1}_{A_{t,x}}(s)\,ds\,dt\\ &=\int_0^1p(s)\left(\int_0^1\mathbf{1}_{A_{t,x}}(s)\,dt\right)\,ds\\ &=x\int_0^1p(s)\,ds=xc. \end{aligned}\)

Together with \(q(x)\ge0\), this proves, for every \(x\in[0,1]\),
\[ \]
\(q(x)\ge\max\{W(x)-cx,0\}=q_*(x).\)

Thus every stable pair has tax integral at least \(T_*\).

2. The lower bound is attained.

Since \(W\) is nonnegative, \(c\ge0\). Hence the constant density \(p_*(s)=c\) is nonnegative and integrable, with total payoff \(c=W(1)\).

The function \(q_*\) is continuous, and therefore measurable. For every \(x\in[0,1]\), nonnegativity of \(W(x)\) and \(cx\) gives
\[ \]
\(0\le q_*(x)\le W(x).\)

Also, \(q_*(1)=\max\{W(1)-c,0\}=0\).

For any measurable coalition \(A\), put \(x=\lambda(A)\). Then
\[ \]
\(\int_Ap_*(s)\,ds=cx \ge \min\{W(x),cx\} =W(x)-q_*(x).\)

Thus \((q_*,p_*)\) is stable. Combined with the pointwise lower bound, this proves that \(T_*\) is the attained minimum.

3. Exact computation from the rational input.

Write the input breakpoints and values as
\[ \]
\(0=x_0<x_1<\cdots<x_m=1,\qquad v_i=W(x_i).\)

Define \(h_i=v_i-cx_i\). On each interval \([x_{i-1},x_i]\), the function \(W(x)-cx\) is affine with endpoint values \(h_{i-1}\) and \(h_i\).

For that interval, let \(d=x_i-x_{i-1}\), \(a=h_{i-1}\), and \(b=h_i\). Its contribution to \(T_*\) is
\[ \]
\(J(d,a,b)= \begin{cases} \dfrac{d(a+b)}2,&a\ge0,\ b\ge0,\\[4pt] 0,&a\le0,\ b\le0,\\[4pt] \dfrac{da^2}{2(a-b)},&a>0,\ b<0,\\[4pt] \dfrac{db^2}{2(b-a)},&a<0,\ b>0. \end{cases}\)

The first two cases integrate an affine nonnegative function or its identically zero positive part. In the third case, the positive part is a triangle with height \(a\) and base \(da/(a-b)\). In the fourth, its height is \(b\) and its base is \(db/(b-a)\). This proves all four formulas; their overlapping all-zero case gives the same value.

Consequently,
\[ \]
\(T_*=\sum_{i=1}^m J(x_i-x_{i-1},h_{i-1},h_i)\)

is rational and can be computed exactly. The decision algorithm returns yes precisely when \(T_*\le B\). Necessity follows from Section 1, and sufficiency follows from the stable pair in Section 2.

4. Running time and scope.

The computation uses \(O(m)\) rational arithmetic operations and comparisons. Each individual interval contribution has numerator and denominator of \(O(L)\) bits: it is obtained by a bounded number of rational operations on input numbers. Accumulating \(m\) contributions using unreduced fractions requires at most \(O(mL)\)-bit intermediate integers. Schoolbook integer arithmetic therefore gives the conservative bit-operation bound \(O(m^3L^2)\), including the final comparison with \(B\).

Thus, on the promised class \(\tau=1\), the running time is polynomial in \(m,\tau,L\). The schedule itself can also be represented exactly with at most \(2m\) linear pieces, because taking the positive part introduces at most one additional breakpoint per original piece.

This settles the specified one-type atomless problem; it makes no claim about societies with several listed types.

⟨structured verdict parsed — rendered above⟩

Overall assessment

The prover resolves the assigned decision problem correctly. The averaging argument gives a pointwise lower bound on every stable tax schedule, the proposed constant payoff density attains that bound, and the resulting integral is computable exactly in polynomial time. No major or minor mathematical issues were found.

Step-by-step verification

1. Pointwise lower bound

Fixing an arbitrary \(x\in[0,1]\) is legitimate: stability is required for every measurable coalition, so it applies to every circular interval \(A_{t,x}\).

The coalition construction and its measure claims are correct. For fixed \(t\), the circular interval has measure \(x\); for fixed \(s\in[0,1)\), the set of parameters \(t\) whose interval contains \(s\) also has measure \(x\).

The endpoint cases are covered:

• When \(x=0\), every constructed coalition is empty.
• When \(x=1\), every constructed coalition is \([0,1)\), which has full measure.
• Omitting the point \(1\) does not affect any integral of the integrable density \(p\).

The stated application of Tonelli’s theorem is justified. The integrand is jointly measurable and nonnegative, and both integrations use Lebesgue measure. Thus the exchanged integral equals \(x\int_I p\,d\lambda=xc\).

Integrating the stability inequality consequently gives \(W(x)-q(x)\le xc\). Combining this with \(q(x)\ge0\) yields the claimed bound
\(q(x)\ge\max\{W(x)-cx,0\}\).

Because \(x\) was arbitrary, this is a pointwise bound for every \(x\), not merely an almost-everywhere statement. Its integration establishes the asserted lower bound on the objective. The objective is finite because \(0\le q\le W\), with \(W\) continuous on a compact interval.

2. Attainment and stability

All requirements on the proposed pair are checked correctly:

• \(c=W(1)\ge0\), so the constant density is nonnegative, integrable, and has the required total payoff.
• The positive part of the continuous function \(W(x)-cx\) is continuous and hence measurable.
• Since \(W(x)\ge0\) and \(cx\ge0\), the tax satisfies \(0\le q_*(x)\le W(x)\).
• At \(x=1\), the tax is zero.

For an arbitrary measurable coalition of measure \(x\), its payoff under the constant density is \(cx\). The identity
\(W(x)-\max\{W(x)-cx,0\}=\min\{W(x),cx\}\)
is correct, and the latter quantity is at most \(cx\). This verifies stability for every measurable coalition.

The construction also covers \(c=0\) and coalitions of measure zero or one. Together with the lower bound, it proves that the minimum is attained and has the stated value.

3. Exact integration

Subtracting \(cx\) preserves affinity on every original linear piece, so the endpoint values \(h_i\) determine each integrand segment correctly.

All four contribution formulas are correct:

• Two nonnegative endpoint values give the trapezoidal integral.
• Two nonpositive endpoint values give zero.
• Opposite strict signs give the stated triangular areas.

The cross-sign denominators are strictly positive under their respective hypotheses. Cases with exactly one zero endpoint are covered by the first or second branch. The only overlap between those branches is \(a=b=0\), where both formulas give zero.

Thus the formulas cover every possible endpoint-sign configuration and produce exact rational contributions. Their sum is precisely the optimum, so comparing it with \(B\) answers the decision problem in both directions.

4. Bit complexity and scope

The arithmetic count is \(O(m)\). Each interval contribution uses only a bounded number of rational operations on input quantities, so its numerator and denominator have \(O(L)\) bits.

The stated \(O(mL)\) bound for unreduced accumulated fractions is valid. Bounding each arithmetic operation conservatively by schoolbook arithmetic on integers of that size gives the claimed \(O(m^3L^2)\) bit-operation bound, including the final rational comparison.

Taking the positive part introduces at most one additional interior breakpoint in each original affine piece, so the stated bound of at most \(2m\) pieces for the optimal schedule is valid.

The conclusion is correctly restricted to the promised class \(\tau=1\). It does not assert a classification for several types, and it does not rely on transferring the cited finite-game result to this model.

Repair feedback

None is required. The supplied argument is rigorous and establishes polynomial-time solvability for the stated input representation and objective.

⟨structured verdict parsed — rendered above⟩