Answer: polynomial-time solvable
Proposition 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a Min-optimal matching is NP- hard even for AS utility functions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete agent types \(\mathcal T\), rational masses \(\mu_\theta>0\) summing to one, and utilities \(u_\theta(\rho,s_\kappa)=v_\theta(\rho)+w_\theta(s_\kappa)\), choose nonnegative masses \(x_{\theta\kappa\rho}\) to maximize \(\min_{x_{\theta\kappa\rho}>0}u_\theta(\rho,s_\kappa)\), subject to \(\sum_{\kappa,\rho}x_{\theta\kappa\rho}=\mu_\theta\) for every \(\theta\) and \(\sum_\kappa x_{\theta\kappa\rho}=\sum_\lambda x_{\rho\theta\lambda}\) for every \(\theta,\rho\). Here \(x_{\theta\kappa\rho}\) is the mass of type-\(\theta\) agents who receive a service from type \(\kappa\) and supply their service to type \(\rho\); determine the optimum and its complexity in \(|\mathcal T|\) and the input bit length.
A society is given by its support \(\mathcal T\): the list of \(\tau\geq 1\) complete types with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(\theta\) supplies a service labelled \(s_\theta\); there are \(m=\tau\) indexed service labels. Agents of the same type have identical utilities, given by binary-rational tables \(v_\theta(\rho)\) and \(w_\theta(s_\kappa)\), with arbitrary signs and ties allowed. Set \(u_\theta(\rho,s_\kappa)=v_\theta(\rho)+w_\theta(s_\kappa)\).
An allocation consists of real masses \(x_{\theta\kappa\rho}\geq 0\), representing type-\(\theta\) agents receiving service from type \(\kappa\) and supplying service to type \(\rho\), satisfying
\(\sum_{\kappa,\rho\in\mathcal T}x_{\theta\kappa\rho}=\mu_\theta\) for every \(\theta\in\mathcal T\), and \(\sum_{\kappa\in\mathcal T}x_{\theta\kappa\rho}=\sum_{\lambda\in\mathcal T}x_{\rho\theta\lambda}\) for every \(\theta,\rho\in\mathcal T\).
All triples are permitted, including exchanges within a type and retention of one's own service. Individual rationality is not required.
The objective is \(\operatorname{OPT}=\max_x\min\{u_\theta(\rho,s_\kappa):x_{\theta\kappa\rho}>0\}\). Let \(L\) be the total binary input length.
Is computing \(\operatorname{OPT}\) polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finitely many agents, maximizing the minimum realized utility over bijections between agents and their endowed services is NP-hard even with additively separable utilities (Lesca and Todo, 2018).
Computing \(\operatorname{OPT}\) is polynomial-time solvable for the stated model with real, divisible masses. At any fixed utility threshold, feasibility is a rational linear-programming problem. The optimum can be found by searching the finitely many utility values.
Define
\[
c_{\theta\kappa\rho}
=
v_\theta(\rho)+w_\theta(s_\kappa),
\qquad
C=\{c_{\theta\kappa\rho}:\theta,\kappa,\rho\in\mathcal T\}.
\]
Here and below, these are exact rational values. There are at most \(\tau^3\) distinct candidates.
Every feasible allocation satisfies
\[
\sum_{\theta,\kappa,\rho}x_{\theta\kappa\rho}
=
\sum_\theta\mu_\theta
=
1.
\]
Thus its positive support is nonempty, and its minimum realized utility is an element of \(C\).
The feasible set is also nonempty: set \(x_{\theta\theta\theta}=\mu_\theta\) for every \(\theta\), and set all other variables to zero. The mass constraints hold. For a balance constraint indexed by \((\theta,\rho)\), both sides equal \(\mu_\theta\) when \(\theta=\rho\), and both sides equal zero otherwise.
Consequently, the set of achieved objective values is a nonempty subset of the finite set \(C\). It therefore has a maximum, and \(\operatorname{OPT}\in C\). This establishes attainment without requiring continuity of the objective.
Fix a rational threshold \(q\), and define the allowed triples by
\[
A_q=\{(\theta,\kappa,\rho)\in\mathcal T^3:
c_{\theta\kappa\rho}\geq q\}.
\]
Consider the following rational linear feasibility problem. Introduce \(z_{\theta\kappa\rho}\geq0\) only for triples in \(A_q\), and impose:
\[ \sum_{\substack{\kappa,\rho\in\mathcal T\\ (\theta,\kappa,\rho)\in A_q}} z_{\theta\kappa\rho} = \mu_\theta \qquad (\theta\in\mathcal T), \]
\[ \sum_{\substack{\kappa\in\mathcal T\\ (\theta,\kappa,\rho)\in A_q}} z_{\theta\kappa\rho} - \sum_{\substack{\lambda\in\mathcal T\\ (\rho,\theta,\lambda)\in A_q}} z_{\rho\theta\lambda} = 0 \qquad (\theta,\rho\in\mathcal T). \]
Empty sums mean zero.
Claim. This linear program is feasible if and only if an allocation has minimum realized utility at least \(q\).
Proof. Suppose such an allocation \(x\) exists. Every triple with positive mass has utility at least \(q\), so every triple outside \(A_q\) has mass zero. Restricting \(x\) to \(A_q\) gives a feasible solution \(z\).
Conversely, extend a feasible \(z\) by assigning zero to every triple outside \(A_q\). The resulting \(x\) satisfies precisely the allocation constraints. Every positive coordinate belongs to \(A_q\), so every realized utility is at least \(q\). Its positive support is nonempty because its total mass is \(1\). This proves the claim.
In particular, the support condition introduces no strict inequalities into the feasibility problem.
Use the standard polynomial-time theorem for rational linear programming: feasibility of a finite system of rational linear equalities and inequalities can be decided deterministically in time polynomial in its total binary encoding length. Equalities are permitted because each can be replaced by two inequalities.
Its hypotheses hold here:
The algorithm is therefore:
Feasibility is monotone: if \(q_i\) is feasible, every smaller candidate is feasible. Binary search therefore uses at most \(O(\log(K+1))\) feasibility calls. The smallest candidate is feasible because it allows every triple and hence allows the diagonal allocation constructed in Section 1.
For completeness, candidate arithmetic is polynomial in the input length. Adding two binary-encoded rationals produces a rational with encoding length at most a constant multiple of their combined encoding length. Exact comparison uses integer cross-products of polynomial bit length. Thus candidate construction, sorting, threshold classification, and every linear-programming call all take polynomial time in \(\tau,L\).
By Section 1, the optimum is a candidate. By Section 2, a candidate is feasible exactly when an allocation achieves at least that value. Hence the returned candidate equals \(\operatorname{OPT}\). Since \(m=\tau\), this is polynomial time in \(m,\tau,L\).
The distinction is divisibility. For \(n\) equally weighted finite agents, the aggregate coordinates of a bijection necessarily satisfy \(n x_{\theta\kappa\rho}\in\mathbb Z_{\geq0}\). The present formulation allows arbitrary nonnegative real coordinates and imposes no such integrality conditions.
The cited finite-agent hardness therefore does not contradict the polynomial-time algorithm for this model.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated task. Its threshold formulation is exact, its polynomial-time claim includes the required bit-complexity bounds, and no mathematical gaps were found.
The candidate set \(C\) contains every possible realized utility and has at most \(\tau^3\) elements. Ties merely reduce its size; negative utilities cause no difficulty.
Summing the mass constraints gives total allocated mass \(1\), so every feasible allocation has nonempty positive support. Since there are finitely many coordinates, its minimum realized utility exists and belongs to \(C\).
The proposed diagonal allocation is feasible. For each balance constraint indexed by \((\theta,\rho)\), both sides are zero when \(\theta\ne\rho\), and both equal \(\mu_\theta\) when \(\theta=\rho\).
Therefore the set of achieved objective values is a nonempty finite set. Its maximum is achieved by an allocation and belongs to \(C\). This argument correctly establishes attainment without assuming continuity of the support-dependent objective.
Both directions of the stated equivalence are correct.
The second family of equations has exactly the indices required by the task: the incoming term is \(z_{\rho\theta\lambda}\). No balance condition is omitted or replaced by a weaker aggregate condition.
Allowing zero values for coordinates in \(A_q\) is correct: membership in the allowed set does not require a coordinate to be positive. Thus no strict inequality or integrality constraint is needed.
Empty sums are explicitly defined. In particular, an empty allowed set is infeasible because all masses are positive.
The prover states the relevant theorem sufficiently precisely: rational linear feasibility is decidable deterministically in time polynomial in the system’s total binary encoding length.
Its hypotheses are satisfied:
Even an explicit dense encoding has size polynomial in \(\tau\) and \(L\). Consequently, the claimed polynomial bound does not rely on an unstated sparse representation.
The arithmetic bounds are correct. Adding two binary-encoded rationals and comparing rational values by cross-products require only polynomially many bits and polynomial time. Constructing and sorting at most \(\tau^3\) candidates is therefore polynomial.
Threshold feasibility is monotone in the stated direction: lowering the threshold enlarges the allowed set. The smallest candidate permits every triple and is feasible.
Binary search correctly identifies the largest feasible candidate using \(O(\log(K+1))\) feasibility queries, including the case \(K=1\). By attainment and the threshold equivalence, that candidate equals \(\operatorname{OPT}\).
The proof therefore establishes exact computation in polynomial time in \(\tau,L\), and hence in \(m,\tau,L\) under \(m=\tau\).
For \(n\) equally weighted finite agents, each aggregate triple mass is an integer count divided by \(n\), so the stated integrality condition is necessary. The continuous model does not impose that condition.
This observation adequately explains why the supplied finite-agent hardness result does not contradict the algorithm. The prover neither needs nor claims that every integral aggregate allocation is realizable by a bijection.
None is required. The output addresses the intended continuous model, including arbitrary signs, ties, within-type exchanges, and retention.
⟨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.