Answer: Polynomial-time solvable: \(\mathrm{P}\).
Proposition 4.2 — class: other
Given two finite-support societies μ and ν on \(D × \{1,\ldots,H\}\), with rational incomes and binary-rational masses, decide whether ν is at least as good as μ for every \(U \in U_{22}\): equivalently, whether all three inequalities in Proposition 4.2 hold for every income threshold and ability prefix.
Inputs are two finite-support probability societies \(\mu,\nu\) on \(D\times\{1,\ldots,H\}\), where \(D=[a,b]\), \(a<b\) are rational, and \(H\ge2\) is a binary-encoded integer. Incomes may have either sign; higher ability labels mean greater ability, with consecutive labels equally spaced.
Each society is given by its support: the list of types \((x,h)\) with positive mass, each mass a binary rational; its masses sum to \(1\). Write \(\tau_\rho=|\operatorname{supp}\rho|\) and \(\tau=\tau_\mu+\tau_\nu\): these are support sizes, not numbers of possible types. Let \(m\) count distinct supported incomes and \(L\) be the total input bit length, including endpoints and ability labels; state running times in \(m,\tau,L\) and any dependence on \(H\).
For \(\rho\in\{\mu,\nu\}\), define \(F_\rho(y,h)=\rho(\{(x,k):x\le y,\ k\le h\})\) and \(W_U(\rho)=\sum_{(x,h)\in\operatorname{supp}\rho}\rho(x,h)U(x,h)\).
Define \(\Delta_h V(y,h)=V(y,h+1)-V(y,h)\). The class \(\mathcal U_{22}\) consists of real-valued utilities twice continuously differentiable in income satisfying \(\Delta_h U\ge0,\ U_y\ge0,\ \Delta_h U_y\le0,\ U_{yy}\le0,\ \Delta_h U_{yy}\ge0,\ \Delta_h^2 U\le0,\ \Delta_h^2 U_y\ge0,\ \Delta_h^2 U_{yy}\le0\), everywhere on \(D\) and wherever the ability differences are defined.
Decide whether \(W_U(\nu)\ge W_U(\mu)\) for every \(U\in\mathcal U_{22}\); equivalently, whether the following three weak inequalities hold:
\(\sum_{r=1}^{h}F_\nu(b,r)\le\sum_{r=1}^{h}F_\mu(b,r)\) for every \(1\le h\le H\);
\(\int_a^y F_\nu(t,H)\,dt\le\int_a^y F_\mu(t,H)\,dt\) for every \(y\in D\);
\(\sum_{r=1}^{h}\int_a^y F_\nu(t,r)\,dt\le\sum_{r=1}^{h}\int_a^y F_\mu(t,r)\,dt\) for every \(y\in D\) and \(1\le h\le H\).
Is this dominance decision problem in \(\mathrm P\), with polynomial running time in the binary input length \(L\), or is it \(\mathrm{NP}\)-hard?
For finite agent lists with equal individual weights, utilitarian unanimity over \(\mathcal U_{22}\) is equivalent to these three inequalities; this is a characterization, without a stated bit-complexity classification. [Verified characterization](https://cahiersdugretha.u-bordeaux.fr/2011/2011-23.pdf).
No explicit complexity classification for this exact rational-mass input model was located in the literature search.
The dominance decision problem is in \(\mathrm{P}\). An exact algorithm uses
\(O(m\tau+\tau\log(\tau+1))\) arithmetic operations and has bit running time
\(O((m\tau+\tau\log(\tau+1))L^2)\) using elementary integer arithmetic. There is no multiplicative dependence on \(H\); its binary encoding is accounted for in \(L\).
I use the intended rational input model: supported incomes, as well as masses and endpoints, are encoded as binary rationals. Without a specified encoding of supported incomes, a bit-complexity question would need further specification.
Keep the two support lists as separate records, and enumerate their combined \(\tau\) records by \((x_i,k_i,s_i)\), where \(s_i\) is the positive mass for a record from \(\nu\) and the negative mass for a record from \(\mu\). Thus \(\sum_i s_i=0\). Identical types in the two societies need not be merged.
Write \(u_+=\max\{u,0\}\). Define three real-valued functions:
\( \displaystyle A(z)=\sum_{i=1}^{\tau}s_i(z-k_i+1)_+, \qquad 0\le z\le H, \)
\( \displaystyle B(y)=\sum_{i=1}^{\tau}s_i(y-x_i)_+, \qquad a\le y\le b, \)
\( \displaystyle C(y,z)=\sum_{i=1}^{\tau}s_i(y-x_i)_+(z-k_i+1)_+, \qquad (y,z)\in[a,b]\times[0,H]. \)
For an integer \(h\in\{1,\ldots,H\}\), a record of ability \(k_i\) contributes to \(F_\nu(b,r)-F_\mu(b,r)\) precisely when \(r\ge k_i\). Consequently,
\( \displaystyle \sum_{r=1}^{h}\bigl(F_\nu(b,r)-F_\mu(b,r)\bigr) =\sum_i s_i(h-k_i+1)_+=A(h). \)
Because \(x_i\in[a,b]\), direct integration gives
\( \displaystyle \int_a^y \mathbf{1}_{\{x_i\le t\}}\,dt=(y-x_i)_+. \)
The value of the indicator at its jump does not affect this integral. Therefore,
\( \displaystyle \int_a^y\bigl(F_\nu(t,H)-F_\mu(t,H)\bigr)\,dt=B(y), \)
and, interchanging finite sums,
\( \displaystyle \sum_{r=1}^{h}\int_a^y\bigl(F_\nu(t,r)-F_\mu(t,r)\bigr)\,dt=C(y,h). \)
Thus the three conditions in the question are exactly:
These identities use no assumption that incomes are nonnegative.
Let
\( \displaystyle Y=\{a,b\}\cup\{x_i:1\le i\le\tau\}, \qquad Z=\{0,H\}\cup\{k_i-1:1\le i\le\tau\}, \)
with duplicates removed. Then \(|Y|\le m+2\) and \(|Z|\le\tau+2\).
Lemma. The three dominance conditions hold if and only if
\( \displaystyle A(z)\le0\quad(z\in Z),\qquad B(v)\le0\quad(v\in Y),\qquad C(v,z)\le0\quad((v,z)\in Y\times Z). \)
Proof. Each function \(z\mapsto(z-k_i+1)_+\) is continuous and affine between consecutive elements of \(Z\). Hence \(A\) is affine on every such interval. If \(z_0<z_1\) are consecutive elements and \(z=(1-\lambda)z_0+\lambda z_1\), with \(0\le\lambda\le1\), then
\( \displaystyle A(z)=(1-\lambda)A(z_0)+\lambda A(z_1). \)
Nonpositive endpoint values therefore imply \(A(z)\le0\) throughout the interval, including all integer labels it contains.
Similarly, each income hinge \(y\mapsto(y-x_i)_+\) is continuous and affine between consecutive elements of \(Y\). Endpoint checks therefore establish \(B(y)\le0\) throughout \([a,b]\).
For \(C\), first fix \(v\in Y\). As a function of \(z\), \(C(v,z)\) is affine between consecutive elements of \(Z\). The grid checks imply \(C(v,z)\le0\) for every \(z\in[0,H]\).
Now fix any such \(z\). Between consecutive income points \(v_0<v_1\), write \(y=(1-\theta)v_0+\theta v_1\). Affineness in income gives
\( \displaystyle C(y,z)=(1-\theta)C(v_0,z)+\theta C(v_1,z)\le0. \)
This proves sufficiency.
Conversely, every element of \(Z\setminus\{0\}\) is an integer in \(\{1,\ldots,H\}\), and every element of \(Y\) lies in \([a,b]\). Thus the original conditions imply all grid checks except those at \(z=0\). Those additional checks hold automatically because \(k_i\ge1\) implies \(A(0)=C(v,0)=0\). This proves necessity. \(\square\)
The ability breakpoints are the actual values \(k_i-1\). Their numerical gaps are retained; no iteration over all \(H\) labels is needed.
Sort the records once by ability and construct sorted, deduplicated lists \(Y\) and \(Z\). This takes \(O(\tau\log(\tau+1))\) comparisons.
For each \(v\in Y\), compute
\( \displaystyle c_i(v)=s_i(v-x_i)_+\qquad(1\le i\le\tau). \)
Then \(B(v)=\sum_i c_i(v)\), so its test requires \(O(\tau)\) operations.
To evaluate all \(C(v,z)\) for this fixed \(v\), scan \(Z\) in increasing order while scanning the ability-sorted records. Maintain
\( \displaystyle P=\sum_{k_i\le z}c_i(v),\qquad R=\sum_{k_i\le z}k_i c_i(v). \)
At an integer \(z\), records with \(k_i>z\) have zero ability hinge. Thus
\( \displaystyle C(v,z)=(z+1)P-R. \)
Each record enters the maintained sums once. Evaluating every \(z\in Z\) therefore takes \(O(\tau+|Z|)=O(\tau)\) operations.
The same scan, using coefficients \(s_i\) instead of \(c_i(v)\), evaluates all \(A(z)\) in \(O(\tau)\) operations.
The algorithm rejects upon finding a positive checked value and otherwise accepts. By the lemma, it decides exactly the three inequalities. Its arithmetic-operation count is
\( \displaystyle O\bigl(m\tau+\tau\log(\tau+1)\bigr). \)
Assume the usual explicit binary numerator-denominator encoding of rationals. Let \(M\) be the product of all mass denominators, and let \(X\) be the product of all denominators of supported incomes and endpoints. Both are positive integers of bit length \(O(L)\): the bit length of a product is bounded by the sum of the factor bit lengths.
Define integers
\( \displaystyle p_i=Ms_i,\qquad \xi_i=Xx_i,\qquad \eta_v=Xv. \)
They all have bit length \(O(L)\). The signs of the grid values can be determined from the following integer expressions:
\( \displaystyle MA(z)=\sum_i p_i(z-k_i+1)_+, \)
\( \displaystyle MXB(v)=\sum_i p_i(\eta_v-\xi_i)_+, \)
\( \displaystyle MXC(v,z)=\sum_i p_i(\eta_v-\xi_i)_+(z-k_i+1)_+. \)
The scaling factors are positive, so these expressions preserve signs exactly.
Implement the scans from the preceding section with the integer coefficients
\(p_i(\eta_v-\xi_i)_+\). Every intermediate integer has \(O(L)\) bits:
Building the common denominators and scaled coordinates takes \(O(\tau)\) elementary integer operations. Sorting rational incomes can use exact cross multiplication.
With elementary multiplication and division, each operation on these integers costs at most \(O(L^2)\) bit operations. Consequently the total bit running time is
\( \displaystyle O\bigl((m\tau+\tau\log(\tau+1))L^2\bigr). \)
Because \(m\le\tau=O(L)\), this is polynomial in \(L\); in particular, \(O(L^4)\) is a valid coarse bound. The algorithm manipulates \(H\) and ability labels as binary integers and never performs \(H\) iterations.
The supplied equal-weight characterization is [Proposition 4.2 of Moyes’s paper](https://cahiersdugretha.u-bordeaux.fr/2011/2011-23.pdf). Its passage to rational probability masses is exact.
Indeed, choose a positive integer \(N\) divisible by every mass denominator in both societies. Replace each supported type of mass \(q\) by \(Nq\) agents of that type. Both resulting lists contain exactly \(N\) agents, and their empirical distribution functions and average utilitarian welfare coincide with those of the original societies. If needed, enlarge \(N\) by an integer factor so that \(N\ge H\).
Applying the stated characterization to these lists gives the equivalence for rational masses. This is a mathematical reduction only: the algorithm above never constructs the potentially enormous agent lists.
Therefore the original utilitarian-unanimity decision problem is polynomial-time solvable. Under polynomial-time many-one reductions, it could also be \(\mathrm{NP}\)-hard only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended rational-input problem correctly. The hinge identities, finite-grid reduction, scanning algorithm, and bit-complexity bound all withstand verification. No major or minor proof defects were found.
The task does not explicitly specify the encoding of supported incomes. The prover explicitly assumes binary rational incomes, which is the natural interpretation of the intended rational-input model. The complexity conclusion is valid under this stated interpretation; it does not purport to cover arbitrary real-number encodings.
The algorithm uses the combined support size \(\tau\), rather than the number of possible types. It also preserves the numerical ability labels, as required by equally spaced consecutive abilities.
Taking positive coefficients for records from \(\nu\) and negative coefficients for records from \(\mu\) gives the correct difference of the two societies. Keeping identical types as separate records is harmless because every subsequent expression is linear in their coefficients.
For an integer \(h\), the number of integers \(r\) satisfying \(1\le r\le h\) and \(r\ge k_i\) is exactly \((h-k_i+1)_+\). Consequently, the identity defining \(A(h)\) has the correct sign, index range, and offset.
The integration identity is correct for every \(x_i,y\in[a,b]\), including \(x_i=a\), \(x_i=b\), and \(y=x_i\). An indicator’s value at a single endpoint does not affect its integral. Thus the identities for \(B(y)\) and \(C(y,h)\) follow by finite summation.
These calculations impose no nonnegativity restriction on incomes.
Every ability breakpoint \(k_i-1\) belongs to \([0,H]\), and every income breakpoint belongs to \([a,b]\). Including both endpoints ensures that the intervals between consecutive grid points cover the full domains.
Each ability hinge is continuous and affine between consecutive elements of \(Z\). The displayed interpolation formula for \(A\) is therefore valid, even though the coefficients may have either sign. Nonpositive endpoint values imply nonpositivity throughout each interval.
The corresponding argument for \(B\) is valid.
For \(C\), the two successive interpolation arguments are sufficient: first they establish nonpositivity for every ability coordinate at each income-grid point, then for every income coordinate at each fixed ability coordinate. No unsupported claim about joint convexity is used.
Necessity also holds. Every nonzero element of \(Z\) is an admissible integer ability label. The additional coordinate \(z=0\) introduces no constraint because all its ability hinges vanish.
Hence the grid tests are exactly equivalent to the original three families of inequalities.
At an integer grid coordinate \(z\), a record with \(k_i>z\) has zero ability hinge, including the boundary case \(k_i=z+1\). For all remaining records, that hinge equals \(z+1-k_i\). The formula
\[
C(v,z)=(z+1)P-R
\]
is therefore correct with the stated maintained sums.
Each record enters those sums once during a scan. This remains true when consecutive grid coordinates have very large numerical gaps. Sorting and scanning do not require visiting the intervening labels.
Computing all coefficients and testing \(B\) costs \(O(\tau)\) operations per income-grid point; evaluating all corresponding \(C\)-values costs another \(O(\tau)\). The separate scan for \(A\) costs \(O(\tau)\).
Since \(m\ge1\), the bound \(|Y|\le m+2\) yields the claimed total
\[
O\bigl(m\tau+\tau\log(\tau+1)\bigr).
\]
Sorting the income and ability lists fits within the stated sorting bound.
The common-denominator construction is valid for arbitrary positive binary rational denominators; they need not be powers of two. The product denominators \(M\) and \(X\) each have \(O(L)\) bits because their factor encodings are included in \(L\).
The scaled masses and coordinates are integers of \(O(L)\) bits. Positive scaling commutes with taking the positive part, so all three displayed scaled expressions preserve the tested signs exactly.
The scan uses products of a constant number of such integers, followed by sums of at most \(\tau\) terms. This gives \(O(L+\log\tau)=O(L)\) bits for every intermediate value. Negative incomes and cancellation do not invalidate this bound.
Constructing the scaling factors and scaled coordinates requires \(O(\tau)\) integer operations, including exact divisions. Rational comparisons by cross multiplication also use operands and products of \(O(L)\) bits.
Elementary integer arithmetic therefore supports the stated bound
\[
O\bigl((m\tau+\tau\log(\tau+1))L^2\bigr).
\]
Since \(m\le\tau=O(L)\), the coarse bound \(O(L^4)\) is valid. Dependence on \(H\) occurs through its bit length and arithmetic on labels, without a multiplicative \(H\) factor.
The cited [Proposition 4.2](https://cahiersdugretha.u-bordeaux.fr/2011/2011-23.pdf) states the supplied three-condition characterization. Its framework permits incomes in a real interval and assumes \(2\le H\le n\).
The replication argument correctly produces two populations of the same size \(N\): each mass \(q\) produces the integer number \(Nq\) of agents, and normalization preserves both distribution functions and average welfare. Enlarging \(N\) ensures the population-size hypothesis. This replication is used only to justify equivalence, not as an algorithmic construction.
Thus the polynomial algorithm applies to the original utility-unanimity decision problem. The concluding qualification about possible NP-hardness is also correct under polynomial-time many-one reductions.
No additional mathematical clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.