d4-conf-atal-2017-0067 (d4-conf-atal-2017-0067)

Given a finite set of complete utility types \(T\) with rational masses \(\mu_t\), a finite set of good types \(G\), rational per-capita supplies \(q_g\), and utility functions \(u_t\), decide whether there are assignment masses \(x_{t,B}\ge 0\) for integral bundles \(B\subseteq G\) such that \(\sum_{B\subseteq G}x_{t,B}=\mu_t\) for each \(t\), \(\sum_{t\in T,\,B\ni g}x_{t,B}=q_g\) for each \(g\), and every bundle receiving positive mass gives the same utility. The population has unit mass, and all goods are allocated.

A society is given by its support: a nonempty list \(T\) of \(\tau\) utility types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\) good types, with binary-rational per-capita supplies \(q_g\in[0,1]\). Each utility function \(u_t:2^G\to\mathbb{Q}_{\ge0}\) is supplied as an explicit table for all bundles; no monotonicity or normalization is assumed. Let \(L\) be the total input bit length.
An individual receives an integral bundle \(B\subseteq G\), possibly empty, containing at most one unit of each good type. A type's mass may be split among different bundles, and all supplies must be allocated.
Perfect equality means that there exist real masses \(x_{t,B}\ge0\) and a single common value \(c\ge0\) such that \(\sum_{B\subseteq G}x_{t,B}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{B\subseteq G:g\in B}x_{t,B}=q_g\) for every \(g\), and \(x_{t,B}>0\Rightarrow u_t(B)=c\). The common value may be zero.

Is deciding whether perfect equality exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite societies, perfect equality with all goods allocated is \(\mathrm{NP}\)-hard even for two agents with additive utilities encoded by singleton values ([2017 result](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p272.pdf)); with an unbounded number of agents it is strongly \(\mathrm{NP}\)-hard even for identical additive utilities ([2022 result](https://link.springer.com/content/pdf/10.1007/s10472-022-09789-z.pdf)).
No result settling this exact continuous problem with the stated encoding was located.

Result. The problem is solvable in polynomial time in \(m,\tau,L\), and indeed in \(L\) alone under the stated explicit-table encoding.

Finite candidate values. For each supported type \(t\), define
\[ V_t=\{u_t(B):B\subseteq G\}, \qquad C=\bigcap_{t\in T}V_t. \]
If perfect equality exists with common value \(c\), then \(c\in C\). To prove this, fix any \(t\in T\). Since
\[ \sum_{B\subseteq G}x_{t,B}=\mu_t>0, \]
at least one bundle \(B\) has \(x_{t,B}>0\). The equality requirement then gives \(u_t(B)=c\), so \(c\in V_t\). This holds for every supported type.

Thus every possible common value occurs in the input tables. In particular, it is rational. Zero is included whenever it belongs to \(C\).

Feasibility for a fixed value. For each \(c\in C\), define
\[ S_t(c)=\{B\subseteq G:u_t(B)=c\}. \]
Consider the following linear feasibility problem, with a real variable \(y_{t,B}\) for each \(t\in T\) and \(B\in S_t(c)\):
\[ y_{t,B}\ge 0, \]
\[ \sum_{B\in S_t(c)}y_{t,B}=\mu_t \qquad(t\in T), \]
\[ \sum_{t\in T}\ \sum_{\substack{B\in S_t(c)\\g\in B}}y_{t,B}=q_g \qquad(g\in G). \]

This system is feasible if and only if perfect equality is possible with common value \(c\).

For the forward implication, extend a feasible solution by setting \(x_{t,B}=0\) whenever \(B\notin S_t(c)\). The displayed equations give the required type masses and allocate every supply exactly. Every positive coordinate corresponds to a bundle with utility \(c\).

Conversely, suppose perfect equality holds with value \(c\). Whenever \(B\notin S_t(c)\), the implication in the definition of perfect equality forces \(x_{t,B}=0\). Restricting \(x\) to the remaining coordinates therefore satisfies the displayed system.

In particular, these constraints preserve the requirement that each individual bundle is integral: the variables split population mass among subsets of \(G\), exactly as permitted in the question.

Algorithm and bit complexity. Compute \(C\), test the displayed system for each \(c\in C\), and accept precisely when at least one test is feasible. The two preceding arguments prove correctness in both directions.

Let \(N=\tau 2^m\), the number of explicitly supplied utility entries. Because each entry requires at least one bit, \(N\le L\). Since \(T\) is nonempty, choosing any \(t_0\in T\) gives
\[ |C|\le |V_{t_0}|\le 2^m\le N. \]
Exact rational comparisons, using cross multiplication of binary integers, compute \(C\) in polynomial time in \(L\).

For each candidate, there are at most \(N\) variables and \(m+\tau\) equality constraints. All matrix coefficients belong to \(\{0,1\}\), and the right-hand sides are the input rationals \(\mu_t,q_g\). Including nonnegativity constraints, the system has encoding length
\[ O\bigl((m+\tau+1)N+L\bigr). \]
This is polynomial in \(L\), since the input also explicitly supplies all masses and supplies.

The polynomial-time rational linear-programming feasibility theorem decides whether such a system has a real solution in time polynomial in its binary encoding length. Equalities can be replaced by pairs of inequalities, so the theorem applies directly, including to feasible sets with empty interior. See [Khachiyan, *A polynomial algorithm in linear programming*](https://www.mathnet.ru/eng/dan42319).

There are at most \(N\le L\) feasibility tests, each of polynomial size. Hence the entire algorithm runs in polynomial time.

Scope of the conclusion. The proof uses both the explicit enumeration of all bundle utilities and the permission to split type masses. It requires neither monotonicity nor normalization, and handles the common value zero. An additive representation by singleton values would not provide the same input-length bound on enumerating bundles; requiring unsplittable agents would not yield the same linear feasibility problem.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument correctly decides the stated continuous problem in polynomial time under the explicit-table encoding. No major or minor mathematical issues were found.

1. Finite candidate values

The necessity of \(c\in C\) is established correctly.

For every supported type \(t\), the finitely many nonnegative coordinates \(x_{t,B}\) sum to the strictly positive mass \(\mu_t\). Consequently, at least one coordinate is positive. The equality condition then gives \(c=u_t(B)\), establishing membership in \(V_t\). Applying this argument to every supported type establishes membership in their intersection.

The positivity assumption on supported masses is used explicitly and correctly. Because every table value is a nonnegative rational, every candidate is automatically rational and satisfies the required restriction \(c\geq 0\). Zero is retained when appropriate.

2. Fixed-value feasibility formulation

For a fixed candidate \(c\), the variables correspond exactly to the allowed bundles \(B\in S_t(c)\).

The type equations enforce the prescribed masses. The good equations enforce allocation of every supply exactly, rather than merely imposing upper bounds. The nonnegativity constraints match the definition of perfect equality.

There is no omitted restriction concerning integral bundles or repeated units: each variable is indexed by a subset of \(G\), which already represents an integral bundle containing at most one unit of each good. Real-valued variables describe population masses, as permitted by the task.

3. Both directions of the equivalence

Both implications are valid.

• Feasibility implies perfect equality: Extending a feasible solution by zero on excluded bundles preserves all required equations. Every positive coordinate has utility \(c\).
• Perfect equality implies feasibility: If \(u_t(B)\neq c\), the defining implication excludes \(x_{t,B}>0\). Together with nonnegativity, this forces \(x_{t,B}=0\). Restricting to allowed bundles therefore preserves all equations.

No stronger interpretation of equality, such as equality of expected utilities, is substituted for the task’s requirement.

4. Correctness of candidate enumeration

Every valid solution has a value in \(C\), and feasibility for any value in \(C\) produces a valid solution. Testing all candidates and accepting exactly when one test succeeds is therefore correct.

If \(C\) is empty, rejection follows from the candidate necessity argument. No additional case is needed.

5. Input-size and construction bounds

The bound \(N=\tau 2^m\leq L\) is valid under the stated explicit-table encoding: all \(N\) utility entries are supplied explicitly and each requires at least one bit.

Since the support is nonempty, selecting \(t_0\in T\) establishes
\(|C|\leq |V_{t_0}|\leq 2^m\leq N\).
Duplicates in utility tables only reduce these cardinalities.

Exact rational comparisons by cross multiplication are polynomial-time operations on the supplied binary integers. Computing the intersection and selecting matching bundles requires only polynomially many such operations.

For each candidate, the variable count is at most \(N\), and the equality count is \(m+\tau\). The stated encoding bound is valid with the usual encoding of nonnegativity as variable bounds. All nonzero matrix entries have constant bit length, and the right-hand-side rationals are already included in the input. Thus every constructed system has polynomial encoding length.

6. Linear-programming theorem

The prover states the needed theorem precisely enough: feasibility of a rational linear system over the reals is decidable in time polynomial in its binary encoding length.

The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time feasibility for arbitrary integer-coefficient linear inequality systems over the reals. The rational formulation invoked here is its standard equivalent form. The prover’s systems satisfy the required finite-dimensional and rational-data hypotheses.

Replacing equalities by pairs of non-strict inequalities preserves feasibility. Lower-dimensional feasible sets, including those with empty interior, are covered; no strict-feasibility hypothesis is needed.

7. Edge cases and scope

The formulation handles zero supplies, unit supplies, empty bundles, zero common utility, and arbitrary nonnegative utility tables without monotonicity or normalization. If \(m=0\), each table contains only the empty bundle, and the same argument remains valid.

The conclusion concerns precisely the explicit-table, divisible-mass problem. The cited finite-society hardness results do not contradict it because their representation or allocation restrictions differ.

Required clarification or repair: None.

⟨structured verdict parsed — rendered above⟩