d4-journals-jet-2020-0107 (d4-journals-jet-2020-0107)

Given a fixed finite set of welfare-response types \(T\), rational shares \(\mu_t>0\) summing to \(1\), and finite weak and strict comparisons between profiles \(x,y\in\mathbb{Q}^T\), decide whether there exist \(c\in\mathbb{R}\) and \(a_t\in\mathbb{R}\) such that \(U_\mu(x)=c\sum_{t\in T}\mu_t x_t^2+\sum_{t\in T}\mu_t a_t x_t\) respects every comparison, weakly or strictly as specified.

A society is given by its support: a list \(T\) of \(\tau\geq 3\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; it may vary between instances.
The remaining input consists of finite sets \(R,P\subseteq\mathbb{Q}^T\times\mathbb{Q}^T\) of weak and strict comparisons. Welfare coordinates may have either sign. Write \(m=|R|+|P|\), and let \(L\) be the total binary input length.
A rationalization consists of unrestricted real coefficients \(c\) and \((a_t)_{t\in T}\), defining \(U_\mu(x)=c\sum_{t\in T}\mu_t x_t^2+\sum_{t\in T}\mu_t a_t x_t\).
It must satisfy \(U_\mu(x)\geq U_\mu(y)\) for every \((x,y)\in R\) and \(U_\mu(x)>U_\mu(y)\) for every \((x,y)\in P\). Zero coefficients and empty comparison sets are allowed.

Is deciding whether such a rationalization exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).

For finitely many individual welfare coordinates, spherical rationalizability has an exact dual characterization: no probability distribution over observed comparisons assigning positive weight to strict comparisons can simultaneously equalize both the mean welfare vectors and the mean squared norms of their two sides. [Source](https://eml.berkeley.edu/~fechenique/published/orthogonal.pdf)
No result settling this exact mass-weighted decision problem was located in the literature search.

1. Result

The decision problem is in \(\mathrm{P}\), including when the support size \(\tau\) varies. It reduces exactly to rational linear feasibility with \(m\) inequalities and \(\tau+1\) unrestricted variables. The running time is \((m+\tau+L)^{O(1)}\) bit operations, hence \(L^{O(1)}\) under the stated explicit encoding.

If \(P=\varnothing\), zero coefficients immediately rationalize every weak comparison. The argument below handles arbitrary nonempty \(P\).

2. Linear formulation

Define the known weighted quadratic feature
\[ Q_\mu(x)=\sum_{t\in T}\mu_t x_t^2. \]
Set \(b_t=\mu_t a_t\). Because every \(\mu_t>0\), this is an invertible change of unrestricted real variables: \(a_t=b_t/\mu_t\). Thus
\[ U_\mu(x)=cQ_\mu(x)+\sum_{t\in T}b_t x_t. \]

Index the observations by \(j=1,\ldots,m\), retaining both designations if a pair belongs to both \(R\) and \(P\). Write observation \(j\) as \((x^j,y^j)\), and define
\[ d_j=\left(Q_\mu(x^j)-Q_\mu(y^j),\ (x_t^j-y_t^j)_{t\in T}\right)\in\mathbb{Q}^{\tau+1}. \]
For \(z=(c,(b_t)_{t\in T})\), direct substitution gives
\[ U_\mu(x^j)-U_\mu(y^j)=d_j\cdot z. \]
Consequently, rationalizability is precisely feasibility of \(d_j\cdot z\geq0\) for weak observations and \(d_j\cdot z>0\) for strict observations. Negative welfare coordinates cause no difficulty: all entries of \(d_j\) are known rational numbers.

3. Exact removal of strict inequalities

Let \(h_j=0\) for a weak observation and \(h_j=1\) for a strict observation. Consider the ordinary, non-strict linear system
\[ d_j\cdot z\geq h_j,\qquad j=1,\ldots,m. \]

We prove that this system is feasible exactly when the original comparisons are rationalizable.

A solution to this system satisfies every original comparison, since a strict observation has utility difference at least \(1>0\).

Conversely, suppose \(z\) satisfies the original comparisons and \(P\neq\varnothing\). Because there are finitely many strict observations,
\[ \delta=\min_{\substack{j:\text{strict}\\\text{observation}}}d_j\cdot z \]
exists and is strictly positive. Replace \(z\) by \(z/\delta\). Every weak difference remains nonnegative, and every strict difference becomes at least \(1\). The rescaled vector therefore satisfies the non-strict system. When \(P=\varnothing\), the two systems already coincide.

This proves the reduction without requiring any advance bound on the original strict margins.

4. Encoding size and running time

We verify that the reduction is polynomial in the binary input length.

Let \(H\) be the product of all positive denominators appearing in the input, and put \(D=H^3\). Since the input has total length \(L\), the integer \(D\) has \(O(L)\) bits. Moreover:

• Every denominator of \(x_t^j-y_t^j\) divides \(D\).
• Every denominator of \(\mu_t(x_t^j)^2\) and \(\mu_t(y_t^j)^2\) divides \(D\).

Hence multiplying each inequality by \(D>0\) yields an equivalent integer system
\[ Az\geq Dh,\qquad A_{j,\cdot}=Dd_j. \]

Each integer entry has \(O(L)\) bits. To check magnitude as well as denominator size, every input coordinate has absolute value at most \(2^L\), while positivity and normalization of the masses imply
\[ \left|Q_\mu(x^j)-Q_\mu(y^j)\right| \leq\sum_{t\in T}\mu_t\left((x_t^j)^2+(y_t^j)^2\right) \leq2^{2L+1}. \]
Also, \(\left|x_t^j-y_t^j\right|\leq2^{L+1}\). Multiplication by the \(O(L)\)-bit integer \(D\) preserves the \(O(L)\) entry-length bound.

The integer system therefore has total encoding length
\[ B=O\!\left((1+m(\tau+1))L\right). \]
Using elementary integer arithmetic, forming it takes \(O((1+m\tau)L^2)\) bit operations: there are \(O(1+m\tau)\) operations on integers of \(O(L)\) bits.

We now use the standard polynomial-time linear-feasibility theorem: feasibility of a finite rational linear system is decidable in time polynomial in its encoding length. This theorem applies to unrestricted variables and does not require the feasible region to be bounded or full-dimensional; those cases are covered by the exact ellipsoid algorithm. See the [MIT notes on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).

Thus a running-time bound, displaying the dependence on the requested parameters, is
\[ O((1+m\tau)L^2)+\left((1+m(\tau+1))L\right)^{O(1)}. \]
Since the support and comparisons are explicitly listed, \(m,\tau=O(L)\), so this is polynomial in \(L\). No expansion of rational masses into a list of individuals is needed.

5. Exact mass-weighted dual characterization

The same formulation also proves the counterpart of the supplied dual characterization.

For a finite matrix \(M\) and vector \(h\), Farkas’ lemma states that the system \(Mz\geq h\), with unrestricted \(z\), is infeasible exactly when there is \(\lambda\geq0\) such that
\[ M^\mathsf{T}\lambda=0,\qquad h^\mathsf{T}\lambda>0. \]
Apply it with row \(j\) of \(M\) equal to \(d_j\). All hypotheses hold because this is a finite real linear system. Its infeasibility is therefore equivalent to the existence of nonnegative weights satisfying
\[ \sum_{j=1}^m\lambda_j(x_t^j-y_t^j)=0\quad\text{for every }t\in T, \]
\[ \sum_{j=1}^m\lambda_j\left(Q_\mu(x^j)-Q_\mu(y^j)\right)=0, \qquad \sum_{\substack{j:\text{strict}\\\text{observation}}}\lambda_j>0. \]
The last inequality implies \(\sum_j\lambda_j>0\), so the weights can be normalized to sum to \(1\).

Thus rationalization fails exactly when a probability distribution over observed comparisons, giving positive total weight to strict comparisons, equalizes both the mean welfare vectors and the mean weighted quadratic features of the two sides. If a pair has both designations, merging its two weights gives a distribution on \(R\cup P\); conversely, any weight on such a pair can be assigned to its strict designation.

This is the mass-weighted analogue of [Chambers and Echenique, Proposition 5](https://eml.berkeley.edu/~fechenique/published/orthogonal.pdf), derived here directly for the specified input.

The problem is therefore 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 output correctly resolves the stated decision problem: it is in \(\mathrm{P}\), including when \(\tau\) varies. The reduction, treatment of strict inequalities, encoding bounds, and dual characterization are sound. No major or minor mathematical issues were found.

• Scope and change of variables. The prover uses exactly the coefficient domain specified in the task: \(c\) and all \(a_t\) are unrestricted real numbers, and zero coefficients are permitted. Since each \(\mu_t>0\), the substitution \(b_t=\mu_t a_t\) is bijective on the coefficient space. It neither restricts nor enlarges the possible rationalizations. The quadratic feature \(Q_\mu(x)\) depends only on the input, so the resulting constraints are linear in the unknown coefficients.

• Equivalence to linear feasibility. The identity \(U_\mu(x^j)-U_\mu(y^j)=d_j\cdot z\) follows directly from the stated definitions. The feature vectors are rational because masses and coordinates are rational. Recording a comparison twice when it belongs to both \(R\) and \(P\) preserves both requirements and agrees with \(m=|R|+|P|\). Negative welfare coordinates introduce no additional restriction.

• Removal of strict inequalities. Both directions are valid. A solution with strict-designated differences at least \(1\) satisfies the original strict comparisons. Conversely, for any original feasible vector and nonempty \(P\), the minimum strict margin exists and is positive because there are finitely many strict observations. Dividing all coefficients by that positive minimum preserves weak inequalities and makes every strict difference at least \(1\). This relies on homogeneity and unrestricted coefficients, both present here. For \(P=\varnothing\), the systems coincide and the zero vector is feasible.

• Denominator and magnitude bounds. The common-denominator construction is valid. Every input denominator divides \(H\); consequently, each denominator contributed by a mass times a squared coordinate divides \(H^3\). Coordinate differences also have denominators dividing \(H^3\). Sums of these terms retain that common denominator.

The bit length of \(H\), and therefore of \(D=H^3\), is \(O(L)\). The magnitude estimates are correct: input coordinates have absolute value at most \(2^L\), and positive masses summing to \(1\) give the stated bound \(2^{2L+1}\) on quadratic-feature differences. Thus every integer coefficient after multiplication by \(D\) has \(O(L)\) bits.

The resulting encoding bound \(B=O((1+m(\tau+1))L)\) is valid. The construction-time bound \(O((1+m\tau)L^2)\) is also valid using elementary integer arithmetic. The empty-strict-set case can terminate immediately as the prover states; in the remaining case \(m\geq1\), the support-processing work is absorbed by this bound.

• Polynomial-time theorem and requested running time. The invoked theorem is stated sufficiently precisely: rational linear feasibility is decidable in polynomial time in its binary encoding length, including unrestricted variables and feasible regions that are unbounded or have lower dimension. Its hypotheses hold for the constructed integer system. The cited [MIT ellipsoid notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) explicitly discuss arbitrary polyhedra and polynomial-time feasibility with integer data.

Consequently, the displayed total running time is justified. Explicit listing gives \(m,\tau=O(L)\), yielding \(L^{O(1)}\) bit operations. No assumption of fixed support size or expansion into individual agents is used.

• Dual characterization and edge cases. The stated version of Farkas’ lemma has the correct signs for \(Mz\geq h\) with unrestricted \(z\). Its finite-dimensional hypotheses are satisfied. Expanding \(M^\mathsf{T}\lambda=0\) gives exactly the coordinate and weighted-quadratic equalities displayed. Since \(h\) is the strict-designation indicator, \(h^\mathsf{T}\lambda>0\) means positive total strict weight and permits normalization to a probability distribution.

Merging weights for a pair with both designations preserves the equalities and positive strict weight; conversely, assigning such a pair’s weight to its strict designation is valid. This matches the claimed analogue of [Chambers and Echenique, Proposition 5](https://eml.berkeley.edu/~fechenique/published/orthogonal.pdf). Empty comparison sets, strict self-comparisons, and zero feature rows are handled by the formulation without exceptions.

No repair or additional clarification is required. The final qualification concerning \(\mathrm{NP}\)-hardness is correct under polynomial-time many-one reductions.

⟨structured verdict parsed — rendered above⟩