d4-conf-ijcai-2015-0544 (d4-conf-ijcai-2015-0544)

Given \(N\), a set of complete types \(\Theta\) with rational masses \(\mu_\theta\) satisfying \(N\mu_\theta\in\mathbb{Z}_{\ge 0}\), and a set of houses, let \(x_{\theta,r}\) be the mass of type \(\theta\) reporting ranking \(r\), with \(Nx_{\theta,r}\in\mathbb{Z}_{\ge 0}\) and \(\sum_r x_{\theta,r}=\mu_\theta\). Run PS on the corresponding \(N x_{\theta,r}\) agents. Compute a report-mass matrix \(x\) such that no agent can improve their expected utility by moving their individual mass \(1/N\) from their current report to another ranking.

Given a binary-encoded positive integer \(N\) and \(m\geq 1\) houses, a society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), satisfying \(\sum_\theta\mu_\theta=1\) and \(N\mu_\theta\in\mathbb Z_{>0}\). Here \(\tau\) is the support size, not the number of possible types.
Each complete type specifies a strict ranking of all houses and binary-rational utilities \(u_\theta(h)\in\mathbb Q\) strictly consistent with that ranking; utilities may have either sign and are additive over allocated fractions.
Reports range over all strict complete rankings \(r\). A feasible report-mass matrix satisfies \(x_{\theta,r}\geq0\), \(Nx_{\theta,r}\in\mathbb Z_{\geq0}\), and \(\sum_r x_{\theta,r}=\mu_\theta\), and is represented by its nonzero entries.
Run probabilistic serial on \(Nx_{\theta,r}\) individual agents of each type-report pair. Each house has supply one; agents consume at unit speed until all houses are exhausted, at time \(m/N\), receiving total quantity \(m/N\).
An agent of type \(\theta\) evaluates their individual allocation \(p\) by \(\sum_h u_\theta(h)p(h)\). A unilateral deviation moves exactly \(1/N\) mass from an occupied report to any other ranking and reruns the allocation rule; compare the deviator's own allocations before and after.
Compute a feasible matrix admitting no strictly profitable unilateral deviation. Let \(L\) be the total binary input length; express running times in \(m,\tau,L\), with \(N\) encoded in binary.

Is computing such an equilibrium matrix polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

For explicitly listed finite agents, computing an expected-utility pure Nash equilibrium is NP-hard, and checking a reported profile is coNP-complete. [Source](https://arxiv.org/pdf/1502.04888).
The integrality constraints and individual deviations here retain the finite-agent problem in support encoding; consequently, the discrete hardness already applies to this formulation.

Result and the imported theorem

Computing the requested equilibrium matrix is \(\mathrm{NP}\)-hard. Consequently, an algorithm with running time \(\operatorname{poly}(m,\tau,L)\) would imply \(\mathrm{P}=\mathrm{NP}\).

I interpret “binary-rational” as a rational number represented by binary-encoded numerator and denominator.

We use the finite-agent hardness result supplied in the question: computing an expected-utility pure Nash equilibrium under probabilistic serial is \(\mathrm{NP}\)-hard. This is Theorem 4 of [Aziz et al., *Equilibria Under the Probabilistic Serial Rule*](https://arxiv.org/pdf/1502.04888). The reduction below transfers that search hardness directly; it does not infer computation hardness from verification hardness.

1. Encoding an explicitly listed society

Consider an instance of the finite-agent problem with \(\{1,\ldots,n\}\) as its agent set, \(m\) houses, and explicitly specified strict rankings and rational utilities.

Partition the agents into classes having identical complete types: both their rankings and their utility vectors agree. Let \(\Theta\) be the resulting type set, let \(\tau=|\Theta|\), and let \(c_\theta\) be the number of agents of type \(\theta\).

Construct the support-encoded instance by setting

\[ N=n,\qquad \mu_\theta=\frac{c_\theta}{n}. \]

Thus every listed mass is positive, \(\sum_{\theta\in\Theta}\mu_\theta=1\), and \(N\mu_\theta=c_\theta\in\mathbb Z_{>0}\). Copy each type’s ranking and utilities unchanged.

This is a polynomial-time construction. If the original input length is \(S\), then \(\tau\leq n\), and the new input length satisfies \(L=O(S+n\log n)\). In particular, \(m,\tau,L\) are polynomially bounded in \(S\).

2. Matrices and labeled profiles

For a feasible matrix \(x\), define its integer counts by

\[ k_{\theta,r}=Nx_{\theta,r}. \]

Feasibility says precisely that these are nonnegative integers satisfying

\[ \sum_r k_{\theta,r}=c_\theta. \]

Consequently, \(x\) can be expanded into a labeled report profile: for each type \(\theta\), assign exactly \(k_{\theta,r}\) of its original agents to report \(r\).

Conversely, a labeled report profile determines a feasible matrix by counting the agents in each type-report pair and dividing these counts by \(n\).

On the constructed instances, expansion is polynomial-time. Every nonzero entry accounts for at least one agent, so there are at most \(n\) nonzero entries; the expanded profile contains exactly \(n\) rankings.

3. Allocation and deviation equivalence

Lemma. A feasible matrix is an equilibrium under the task’s deviation rule if and only if any labeled expansion is a pure Nash equilibrium of the finite-agent instance.

Proof. First consider allocation. At any moment, all agents having the same report consume the same most-preferred available house. Hence a group containing \(k_{\theta,r}\) agents contributes consumption rate \(k_{\theta,r}\) to that house.

These rates are exactly those obtained from the labeled expansion. Starting with identical supplies, both descriptions therefore have the same first exhaustion event. After removing the exhausted houses, their consumption rates again agree. Induction over the exhaustion events proves that the entire consumption process agrees. Each individual’s allocation is its consumption time on each house, so individual allocations agree as well.

Now fix an occupied pair \((\theta,r)\). Moving \(1/N\) mass from this pair to another report \(r'\) replaces the counts by

\[ k_{\theta,r}-1,\qquad k_{\theta,r'}+1, \]

with every other count unchanged. In a labeled expansion, this is exactly the report change of one agent of type \(\theta\).

The allocation equivalence just proved applies both before and after that change. The deviating agent has the same utility vector in both descriptions, so its utility difference is identical. In particular, the deviation is strictly profitable in one description exactly when it is strictly profitable in the other.

Every occupied pair contains an individual, and every individual belongs to an occupied pair. Thus all unilateral deviations correspond, proving the lemma. \(\square\)

4. Hardness consequence

Suppose an algorithm always computed the requested matrix in time \(\operatorname{poly}(m,\tau,L)\).

Given an explicitly listed finite-agent instance:

• Construct its support-encoded instance as in Section 1.
• Run the supposed algorithm.
• Expand its output into a labeled report profile.

All three steps take polynomial time in \(S\). By the lemma, the resulting profile is a finite-agent pure Nash equilibrium. This contradicts the supplied search-hardness theorem unless \(\mathrm{P}=\mathrm{NP}\).

Therefore the support-encoded problem is \(\mathrm{NP}\)-hard. The argument accommodates repeated types and arbitrary equilibrium outputs; it does not require all agents to have different types.

5. A running-time bound with binary-encoded population size

For completeness, there is also a finite exhaustive algorithm whose running time can be expressed without expanding the population.

Let \(R=m!\) and \(n_\theta=N\mu_\theta\). Enumerate all integer arrays \((k_{\theta,r})\) with entries between \(0\) and \(n_\theta\), retaining those with the required row sums. There are at most \((N+1)^{\tau R}\) arrays. For every retained array, check all occupied pairs against all \(R\) alternative reports.

Each check can simulate probabilistic serial using group counts. There are at most \(m\) exhaustion stages. Exact arithmetic has polynomial bit complexity: at each stage, consumption rates are integers bounded by \(N\), and a common denominator for residual supplies can be multiplied by at most \(N\). After all stages, its bit length is \(O(m\log N)\). Utility comparisons therefore also use polynomially many bits.

The resulting running-time bound is

\[ (N+1)^{\tau m!}\operatorname{poly}(m,\tau m!,L) \leq 2^{O(L\tau m!)}\operatorname{poly}(m,\tau m!,L). \]

The cited paper’s Theorem 2 guarantees existence of a finite-agent pure equilibrium. Expanding the population conceptually and then applying the lemma verifies existence for this formulation, so exhaustive search finds a matrix.

The classification is search \(\mathrm{NP}\)-hardness; no claim of \(\mathrm{NP}\)-completeness is needed.

⟨structured verdict parsed — rendered above⟩

The hardness reduction is correct. It preserves both individual allocations and unilateral incentives, and it converts every returned equilibrium matrix into a finite-agent equilibrium in polynomial time. The only issue is a minor edge-case imprecision in the supplementary bit-length bound.

• Imported hardness theorem. The cited Theorem 4 states hardness of computing a probabilistic-serial pure Nash equilibrium from agents’ utilities. The paper uses strict complete rankings, additive expected utility, unit consumption speed, and exhaustion at time \(m/n\), matching the finite-agent problem supplied in USER_TASK. Thus the prover imports the appropriate computation theorem, rather than drawing an invalid inference from verification hardness. [Aziz et al., Sections 2 and 5.1](https://arxiv.org/pdf/1502.04888)

The interpretation of “binary-rational” as binary-encoded numerator and denominator is explicitly stated and agrees with the intended rational-input formulation. Allowing utilities of either sign does not restrict the hard instances.

• Construction of the support instance. Partitioning by identical rankings and identical utility vectors is correct. Grouping only by rankings would not suffice, but the prover does not make that mistake.

With \(N=n\) and \(\mu_\theta=c_\theta/n\), positivity, normalization, and population integrality all follow exactly. Rankings and utilities retain their required properties.

Equality testing and grouping of explicitly encoded rational types are polynomial-time operations. Each mass needs \(O(\log(n+1))\) bits. The stated input-size bound is sufficient to establish a polynomial-time construction and polynomial bounds on \(m,\tau,L\) in the original explicit input length.

• Correspondence between matrices and labeled profiles. For the constructed instances, feasibility gives integer counts \(k_{\theta,r}\) whose row sums are \(c_\theta\). These counts can therefore be assigned to the original labeled agents of each type. Conversely, counting a labeled profile gives a feasible matrix.

Every positive count is at least one, and the counts sum to \(n\); hence there are at most \(n\) nonzero entries. Expanding the output into exactly \(n\) complete rankings is polynomial-time on these instances. The argument does not assume that expansion is polynomial-time for arbitrary binary-encoded populations.

• Allocation equivalence. Agents reporting the same ranking choose the same available house at every time. Their combined consumption rate equals their count. Consequently, the grouped and labeled descriptions have identical rates and exhaustion events.

The induction also accommodates simultaneous exhaustions: all houses exhausted at an event are removed together. Individual allocations agree because each agent consumes at unit speed for the same intervals. This part is sound.

• Deviation equivalence. For an occupied pair, subtracting one from its count is feasible. Adding one to the destination report preserves the type’s population. This is precisely one labeled agent changing its report.

The allocation correspondence applies before and after the deviation, and the deviator retains the same utility vector. Strict profitability therefore agrees in both descriptions. Quantifying over all occupied pairs and all alternative complete rankings covers every individual unilateral deviation. The lemma establishes its stated equivalence, including “any labeled expansion.”

• Hardness consequence. Construction, equilibrium computation under the hypothetical algorithm, and expansion are polynomial-time in the explicit input length. Every possible equilibrium output expands to a finite-agent equilibrium. Thus the reduction transfers the supplied search hardness. The claimed implication that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is justified under that supplied theorem.

• Exhaustive algorithm and arithmetic. There are \(R=m!\) reports and \(\tau R\) count coordinates. Bounding each coordinate by \(N\) gives the valid upper bound \((N+1)^{\tau R}\). Filtering by row sums and checking all occupied-pair deviations require only polynomial overhead in \(m,\tau R,L\) per array.

There are at most \(m\) exhaustion stages. The stated denominator-growth argument supports polynomial-size exact arithmetic and exact utility comparisons. Negative utilities cause no difficulty.

Minor issue: The literal bound \(O(m\log N)\) vanishes at the allowed value \(N=1\), although an encoded denominator still has positive bit length. The minimum clarification is to state a bound valid at \(N=1\), or explicitly specify the logarithm convention. This does not affect the algorithm or hardness conclusion.

Since \(N\) is binary-encoded, the final exponential running-time bound in \(L\) is valid. The cited Theorem 2 supplies equilibrium existence for finite populations and arbitrary numbers of houses; conceptual expansion and the correspondence lemma justify termination of exhaustive search here. [Aziz et al., Section 4](https://arxiv.org/pdf/1502.04888)

⟨structured verdict parsed — rendered above⟩