Answer: —
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet PV and PW denote consistent subdivisions for a mechanism design problem with an allocation function inducing the initial partition P I V . Let {ˆh(w) | w ∈ˆPW } denote the set of rebates from an optimal solution to the re- stricted problem, which only considers profiles ˆPV . Further, let ˆp denote the set of (n −1)m + 1 extreme points of a polytope p ∈PW . For each polytope, define a linear re- bate function hp(w) = P(n−1)m i=1 ap i wi+bp with coefficients ap ∈R(n−1)m, bp ∈R given by a solution to the system of linear equations {ˆh(w) = P(n−1)m i=1 ap i wi + bp | w ∈ˆp}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite valuation-type set \(\mathcal T\subseteq[0,1]^m\) and rational per-capita item supplies \(q_j\), consider finite markets of size \(N\) whose type counts approximate \(N\mu\) and whose supplies are \(Nq_j\). Determine whether an anonymous Groves rebate functional \(R\), defined as the limit of finite-market rebates on the background type distribution, can attain a specified worst-case limiting ratio of welfare retained after payments to efficient welfare over all \(\mu\in\Delta(\mathcal T)\); if so, compute an optimal \(R\) and its tagged-agent allocation and payment limits, subject to dominant-strategy truthfulness, individual rationality, and weak budget balance.
Input consists of a nonempty finite set \(\mathcal T\subseteq\mathbb Q^m\cap[0,1]^m\), positive rational supplies \(q_j\) with \(\sum_jq_j<1\), and a rational threshold \(\rho\in[0,1]\); assume some type has a positive coordinate. Agents have unit demand, quasilinear utilities, and value zero when unassigned; their type and report domain is \(\mathcal T\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational, summing to one. Here \(\tau\) is the support size, not the number of possible types. Write \(k=|\mathcal T|\) and let \(L\) denote the binary input length; state running times in \(m,k,\tau,L\).
For each \(N\) making every \(Nq_j\) integral, a market has \(N\) agents and \(Nq_j\) copies of item \(j\). Choose uniformly among efficient feasible assignments. Let \(F_N(v)\) be efficient welfare and \(F_N(v_{-i})\) efficient welfare after deleting agent \(i\), retaining the same supplies.
An anonymous Groves mechanism has payments \(t_i(v)=F_N(v_{-i})-\sum_{\ell\ne i}v_\ell(a_\ell)-r_N(v_{-i})\), where \(r_N\) is an arbitrary signed real function of the multiset of other reports. Require dominant-strategy truthfulness, individual rationality, and \(\sum_it_i(v)\ge0\) at every finite profile and every selected assignment.
A family \((r_N)\) induces an admissible limiting functional \(R\) if, for every rational society \(\mu\) and every sequence of profiles with empirical distributions tending to \(\mu\), \(r_N(v_{-i_N})\to R(\mu)\) for every choice of tagged agents \(i_N\). Rebates are per agent and are not divided by \(N\).
Its guarantee is \(G=\inf_{\mu}\inf_{v^{(N)}\to\mu}\liminf_{N\to\infty}(F_N(v^{(N)})-\sum_it_i(v^{(N)}))/F_N(v^{(N)})\), where the inner infimum ranges over empirical-profile sequences and the ratio is defined as one when \(F_N=0\).
For tagged-agent outputs at a rational \(\mu\), use exact replicas with counts \(N\mu_t\), taking \(N\) through common denominator multiples of \(\mu\) and \(q\); tag an existing agent of any positive-mass type. Allocation limits mean assignment-probability limits, and payment limits mean expected-payment limits.
Is deciding whether an admissible limiting functional can achieve \(G\ge\rho\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? What is the complexity of computing an optimal \(R\) and its tagged-agent allocation and payment limits?
For finite markets, suitable geometrically consistent simplicial partitions allow an optimal Groves payment function to be constructed by solving an LP on partition vertices and interpolating; this is a conditional algorithmic result, not a polynomial-time bound in the market input size. [Dufton et al.](https://ojs.aaai.org/index.php/AAAI/article/download/8262/8121)
No verified result settling this precise distributional limiting problem was identified.
I do not settle whether the unrestricted decision problem is in $\mathrm P$. I prove an exact characterization of its optimum, existence of an optimal limiting functional, and the following complexity bounds:
Consequently, $\mathrm{NP}$-hardness under polynomial many-one reductions would imply $\mathrm{NP}=\mathrm{coNP}$. These results leave the polynomial-time question open.
Write
$$
\Delta_i=F_N(v)-F_N(v_{-i}).
$$
Deleting agent $i$ from an efficient assignment, and conversely extending an assignment by leaving $i$ unassigned, gives
$$
0\le \Delta_i\le v_i(a_i).
$$
Thus the payment and truthful utility are
$$
t_i=v_i(a_i)-\Delta_i-r_N(v_{-i}),
\qquad
u_i=\Delta_i+r_N(v_{-i}).
$$
Define total VCG revenue by
$$
B_N(v)=F_N(v)-\sum_i\Delta_i.
$$
Then
$$
0\le B_N(v)\le F_N(v),
\qquad
\sum_i t_i=B_N(v)-\sum_i r_N(v_{-i}).
$$
These identities hold for every selected efficient assignment. In particular, total revenue is independent of that selection.
Any rebate depending only on the other reports preserves dominant-strategy truthfulness: with the other reports fixed, the agent’s utility is true reported-profile welfare minus a term independent of that agent’s report. Truthful reporting selects a maximizer of that welfare.
For nonnegative rebates, individual rationality is immediate. No deficit is equivalent to
$$
\sum_i r_N(v_{-i})\le B_N(v).
$$
For every sequence converging to a rational society $\mu$, admissibility implies
$$
\max_i\left|r_N(v_{-i})-R(\mu)\right|\longrightarrow0.
$$
Otherwise, tags chosen along a violating subsequence would contradict admissibility. Hence
$$
\frac1N\sum_i r_N(v_{-i})\longrightarrow R(\mu).
$$
Every admissible $R$ is also continuous on rational societies. Indeed, suppose rational societies $\mu_n$ converge to a rational $\mu$. Choose increasingly large exact replicas of $\mu_n$, at sizes $N_n$, so that a tagged rebate differs from $R(\mu_n)$ by less than $1/n$. Complete these profiles at the other admissible sizes with profiles converging to $\mu$. Admissibility at $\mu$ then implies $R(\mu_n)\to R(\mu)$.
Index all types by $t\in\mathcal T$. For any nonnegative mass vector $s$, retaining supplies $q$, define
$$
f(s)=
\max\left\{
\sum_{t,j}t_jx_{tj}:
x_{tj}\ge0,\
\sum_jx_{tj}\le s_t,\
\sum_tx_{tj}\le q_j
\right\}.
$$
Its dual is
$$
f(s)=
\min\left\{
s\cdot u+q\cdot p:
u_t,p_j\ge0,\
u_t+p_j\ge t_j
\right\}.
$$
Because $t_j\in[0,1]$, clipping any dual coordinate above one preserves feasibility and cannot increase the objective. We therefore use the fixed rational polytope
$$
D=
\left\{
(u,p)\in[0,1]^{k+m}:u_t+p_j\ge t_j
\right\},
$$
and its optimal face
$$
D^*(s)=
\left\{(u,p)\in D:s\cdot u+q\cdot p=f(s)\right\}.
$$
The assignment matrix is a bipartite network matrix and is totally unimodular. Thus, when $s_t=n_t/N$ and all supplies $Nq_j$ are integral,
$$
F_N(v)=Nf(s),
\qquad
F_N(v_{-i})=Nf(s-e_t/N)
$$
for a type-$t$ agent.
If $(u,p)$ and $(u',p')$ belong to $D^*(s)$, then both
$$
(u\vee u',p\wedge p')
\quad\text{and}\quad
(u\wedge u',p\vee p')
$$
are feasible. For example, if the smaller of $p_j,p'_j$ is $p_j$, then
$$
\max\{u_t,u'_t\}+\min\{p_j,p'_j\}\ge u_t+p_j\ge t_j.
$$
The other feasibility assertion follows symmetrically.
The sum of the two new objective values equals $2f(s)$. Since each feasible objective is at least $f(s)$, both new points are optimal.
Compactness and repeated joins and meets consequently give optimal points
$$
(u^+(s),p^-(s)),
\qquad
(u^-(s),p^+(s)),
$$
where the superscripts denote coordinatewise maximum and minimum over the optimal face. In particular, these coordinatewise extrema are attained simultaneously.
Define
$$
b_-(s)=q\cdot p^-(s)
=f(s)-s\cdot u^+(s),
$$
and
$$
b_+(s)=q\cdot p^+(s)
=f(s)-s\cdot u^-(s).
$$
They satisfy
$$
0\le b_-(s)\le b_+(s)\le f(s).
$$
For a queried society, $f(\mu)$, $b_-(\mu)$ and $b_+(\mu)$ are computable exactly by three rational LPs: the welfare LP, followed by minimization and maximization of $q\cdot p$ on its optimal dual face. Types outside the support can be omitted: their dual utility coordinates impose no additional restriction on prices. These computations therefore take
$$
\operatorname{poly}(m,\tau,L)
$$
bit operations.
The following lemma supplies the missing local constraints.
Lemma. For every real society $\mu$ and every empirical-profile sequence $s_N\to\mu$,
$$
b_-(\mu)
\le
\liminf_N\frac{B_N}{N}
\le
\limsup_N\frac{B_N}{N}
\le
b_+(\mu).
$$
For rational $\mu$, exact replicas eventually have revenue per agent exactly $b_-(\mu)$. There also exists a sequence converging to $\mu$ along which a subsequence has revenue per agent exactly $b_+(\mu)$.
The polytope $D$ has finitely many vertices, and $f$ is the minimum of their affine objective functions. At $\mu$, every nonoptimal vertex has a positive objective gap. Therefore, in a sufficiently small neighborhood of $\mu$, only vertices belonging to $D^*(\mu)$ can be optimal.
For sufficiently large $N$, this observation applies both to $s_N$ and to $s_N-e_t/N$ whenever type $t$ is present.
Choose a vertex optimal at the deleted profile. Using its affine objective at $s_N$ gives
$$
\Delta_t^{(N)}\le u_t^+(\mu).
$$
Choosing instead a vertex optimal at $s_N$ gives
$$
\Delta_t^{(N)}\ge u_t^-(\mu).
$$
Consequently,
$$
f(s_N)-s_N\cdot u^+(\mu)
\le
\frac{B_N}{N}
\le
f(s_N)-s_N\cdot u^-(\mu).
$$
Taking limits proves the bounds.
At a fixed rational $\mu$, for sufficiently small positive $\epsilon$, only vertices optimal at $\mu$ can minimize the objective at $\mu-\epsilon e_t$. Among those vertices, minimization selects the largest $u_t$. Thus
$$
f(\mu-\epsilon e_t)=f(\mu)-\epsilon u_t^+(\mu)
$$
for sufficiently small $\epsilon>0$, when $\mu_t>0$.
Hence, in sufficiently large exact replicas,
$$
\Delta_t^{(N)}=u_t^+(\mu),
\qquad
\frac{B_N}{N}=b_-(\mu).
$$
Fix an optimal primal allocation at $\mu$. Since total supply is less than one, some supported type $z$ has positive unassigned mass. Complementary slackness gives
$$
u_z=0
\qquad\text{for every }(u,p)\in D^*(\mu).
$$
Explicitly, the primal-dual objective difference is a sum of nonnegative terms, one of which is
$$
\left(\mu_z-\sum_jx_{zj}\right)u_z.
$$
Its coefficient is positive, so optimality forces $u_z=0$.
Consider
$$
s_\epsilon=\mu+\epsilon(\mu-e_z).
$$
For sufficiently small $\epsilon>0$, this is a society with the same support. On $D^*(\mu)$, its objective changes by
$$
\epsilon(\mu-e_z)\cdot u=\epsilon\mu\cdot u.
$$
Therefore, for sufficiently small $\epsilon$, its optimal face consists precisely of the minimizers of $\mu\cdot u$ over $D^*(\mu)$.
The lattice minimum $u^-(\mu)$ attains that minimum. Because every supported weight $\mu_t$ is positive, every minimizer has
$$
u_t=u_t^-(\mu)
\qquad(t\in\operatorname{supp}(\mu)).
$$
It follows that
$$
b_-(s_\epsilon)=b_+(\mu).
$$
If $\mu$ is rational, choose rational $\epsilon_n\downarrow0$ and sufficiently large exact replicas of $s_{\epsilon_n}$. Complete these replicas to a profile sequence converging to $\mu$. The chosen subsequence has the claimed revenue.
If $\mu=e_z$, the perturbation is zero. In that case all supported utility coordinates are already zero and $b_-(\mu)=b_+(\mu)$, so exact replicas suffice. This completes the proof.
Let
$$
S=\left\{\mu\in\mathbb R_{\ge0}^k:\sum_t\mu_t=1\right\}.
$$
Theorem. The optimal guarantee exists and equals
$$
G_{\mathrm{opt}}
=
1-
\max_{\substack{\mu\in S\\f(\mu)>0}}
\frac{b_+(\mu)-b_-(\mu)}{f(\mu)}.
$$
The maximum is attained at a rational society. An optimal limiting functional can be chosen nonnegative, continuous on $S$, rational, and piecewise affine.
Equivalently, the threshold answer is yes precisely when
$$
b_+(\mu)-b_-(\mu)\le(1-\rho)f(\mu)
$$
for every rational society $\mu$.
Exact replicas, no deficit, and uniform rebate convergence imply
$$
R(\mu)\le b_-(\mu)
$$
at every rational society.
If $f(\mu)>0$, the upper-endpoint sequence from Section 3 implies
$$
G
\le
1-\frac{b_+(\mu)-R(\mu)}{f(\mu)}
\le
1-\frac{b_+(\mu)-b_-(\mu)}{f(\mu)}.
$$
Indeed, along its selected subsequence,
$$
\frac{F_N-\sum_i t_i}{F_N}
=
1-
\frac{B_N/N-N^{-1}\sum_i r_N(v_{-i})}{F_N/N}
$$
converges to the first expression on the right. A subsequence is sufficient for an upper bound on the relevant $\liminf$.
Enumerate the vertices of $D$. Their affine objectives are
$$
\ell_a(s)=s\cdot u^a+q\cdot p^a.
$$
Intersect $S$ with the hyperplane arrangement
$$
\ell_a(s)=\ell_b(s).
$$
This produces a finite rational polyhedral complex. On the relative interior of each cell $C$:
Denote the latter constants by $b_{-,C}$ and $b_{+,C}$.
If $v$ lies in the closure of $C$, then the cell’s optimal dual face is contained in $D^*(v)$. Hence
$$
b_-(v)\le b_{-,C},
\qquad
b_+(v)\ge b_{+,C}.
$$
Let $V$ be the finite set of vertices of this complex, and set
$$
D_V=
\max_{\substack{v\in V\\f(v)>0}}
\frac{b_+(v)-b_-(v)}{f(v)}.
$$
There is at least one vertex with positive welfare: a pure society supported on a type with a positive coordinate has positive welfare.
For $\mu$ in the relative interior of $C$, express it as
$$
\mu=\sum_{v\in\operatorname{vert}(\overline C)}\alpha_vv,
\qquad
\alpha_v\ge0,\quad\sum_v\alpha_v=1.
$$
Affineness gives
$$
f(\mu)=\sum_v\alpha_vf(v).
$$
Also,
$$
b_+(v)-b_-(v)\ge b_{+,C}-b_{-,C}.
$$
If the latter difference is positive, every such vertex has positive welfare, because an optimal dual point with price vector $p_C^+$ remains optimal at $v$ and
$$
f(v)\ge q\cdot p_C^+=b_{+,C}>0.
$$
It follows that
$$
b_{+,C}-b_{-,C}
\le
\sum_v\alpha_v\bigl(b_+(v)-b_-(v)\bigr)
\le
D_V f(\mu).
$$
When the difference is zero, the same conclusion is immediate.
Thus the maximum in the theorem equals $D_V$ and is attained at a rational vertex.
Put
$$
g=1-D_V.
$$
Take a geometrically consistent rational simplicial refinement of the complex. Such a refinement can be obtained recursively: choose a rational relative interior point in every nonempty face, triangulate its boundary, and cone that triangulation to the chosen point. The shared choices on common faces make the refinement consistent.
At every vertex $v$ of the refinement, prescribe
$$
R(v)=b_-(v),
$$
and interpolate affinely on each simplex. This defines a continuous nonnegative $R$.
Fix a cell $C$ and a simplex contained in its closure. Every vertex $v$ of that simplex satisfies
$$
R(v)\le b_{-,C}
$$
and, by the already proved global bound,
$$
R(v)
\ge b_+(v)-(1-g)f(v)
\ge b_{+,C}-(1-g)f(v).
$$
Affine interpolation therefore gives, throughout $C$,
$$
0\le R(\mu)\le b_-(\mu),
$$
and
$$
R(\mu)\ge b_+(\mu)-(1-g)f(\mu).
$$
More generally, suppose $R:S\to\mathbb R_{\ge0}$ is continuous and satisfies $R(\mu)\le b_-(\mu)$.
For a multiset $w$ of $N-1$ reports, let $\nu_w$ be its normalized empirical distribution, and define
$$
c_N(w)=\min_{t\in\mathcal T}\frac{B_N(w\cup\{t\})}{N},
$$
$$
r_N(w)=\min\{R(\nu_w),c_N(w)\}.
$$
All admissible sizes have $N>1$, since every supply is positive and total supply is less than one.
The rebate is anonymous and nonnegative. For any full profile $v$,
$$
r_N(v_{-i})\le\frac{B_N(v)}N,
$$
so summing proves no deficit. Individual rationality and truthfulness follow from Section 1.
For a convergent profile sequence and any tags, $\nu_{v_{-i}}\to\mu$. Every possible completion $v_{-i}\cup\{t\}$ also converges to $\mu$. Section 3 and finiteness of $\mathcal T$ give
$$
\liminf_N c_N(v_{-i})\ge b_-(\mu)\ge R(\mu).
$$
Continuity now yields
$$
r_N(v_{-i})\longrightarrow R(\mu).
$$
Thus this family induces $R$ in exactly the required sense.
For $f(\mu)>0$, the revenue bounds and rebate convergence give
$$
\liminf_N
\frac{F_N-\sum_i t_i}{F_N}
\ge
1-\frac{b_+(\mu)-R(\mu)}{f(\mu)}
\ge g.
$$
If $f(\mu)=0$, every supported type must be the zero vector: any supported positive coordinate could receive positive mass of its item and produce positive welfare.
Along a sequence converging to this society, eventually the number of nonzero agents is smaller than every item supply. All such agents can simultaneously receive an item attaining their individual maximum value. Therefore,
$$
F_N=\sum_i\max_jv_{ij},
\qquad
\Delta_i=\max_jv_{ij},
\qquad
B_N=0.
$$
Nonnegative rebates and no deficit force every rebate to be zero. The retained-welfare ratio is one, including the specified zero-welfare convention.
The constructed family consequently achieves $g$, completing the theorem.
Let
$$
d=k+m,\qquad h=km+2d.
$$
The boxed dual polytope has at most $h^d$ vertices. These can be enumerated by choosing active constraints and solving the corresponding rational linear systems.
Cramer’s rule bounds each dual vertex’s encoding length by $\operatorname{poly}(m,k,L)$. The arrangement hyperplanes inherit polynomial encoding length. Its vertices likewise have polynomial encoding length, since each is determined by at most $k$ independent rational equations.
An arrangement of $H$ hyperplanes in dimension at most $k-1$ has $H^{O(k)}$ faces. Here
$$
H\le h^{2d}+k.
$$
Enumerating faces and their rational simplicial refinement therefore gives a conservative running-time bound
$$
2^{\operatorname{poly}(m,k)}\operatorname{poly}(L).
$$
At every relevant vertex, the required welfare and price extrema are computed by polynomial-size LPs.
This constructs both $G_{\mathrm{opt}}$ and an explicit optimal piecewise affine $R$. For fixed $m$ and $k$, the algorithm is polynomial in $L$.
If the threshold answer is no, Section 4 supplies a rational arrangement vertex $\mu$ satisfying
$$
b_+(\mu)-b_-(\mu)>(1-\rho)f(\mu).
$$
Its binary encoding length is polynomial in $m,k,L$.
A verifier checks that $\mu$ is a society, solves the welfare LP and the two optimal-face price LPs, and verifies this strict rational inequality. These operations take
$$
\operatorname{poly}(m,k,L)
$$
time. Hence failure of the threshold has polynomial certificates, proving membership in $\mathrm{coNP}$.
Under polynomial many-one reductions, an $\mathrm{NP}$-hard language in $\mathrm{coNP}$ would imply $\mathrm{NP}\subseteq\mathrm{coNP}$, and taking complements would give equality.
The vertex argument also shows that $G_{\mathrm{opt}}$ is rational with polynomial encoding length. With a threshold oracle, binary search followed by rational reconstruction therefore computes it using polynomially many queries of polynomial length. Since a $\mathrm{coNP}$ oracle can be implemented by complementing an $\mathrm{NP}$ oracle answer, this gives
$$
G_{\mathrm{opt}}\in\mathrm{FP}^{\mathrm{NP}}.
$$
This does not establish a polynomial-time algorithm without an oracle, or a compact representation of an optimal functional.
Consider the domain
$$
\mathcal T=\{c_je_j:1\le j\le m\},
\qquad
c_j\in\mathbb Q\cap(0,1].
$$
Thus each type values exactly one item.
Put
$$
H=\sum_jq_jc_j,
\qquad
C=\min_jq_jc_j.
$$
Proposition. For this class,
$$
G_{\mathrm{opt}}=\frac CH,
\qquad
R(\mu)=C
$$
is optimal.
For a finite profile with $n_j$ agents of type $c_je_j$, welfare is
$$
F_N=\sum_jc_j\min\{n_j,Nq_j\}.
$$
Deleting one such agent loses $c_j$ if $n_j\le Nq_j$, and loses zero otherwise. Consequently,
$$
B_N=N\sum_{j:n_j>Nq_j}q_jc_j.
$$
Since
$$
\sum_jn_j=N>N\sum_jq_j,
$$
at least one type is oversupplied relative to its preferred item. Therefore $B_N\ge NC$. Constant rebates $C$ are feasible and give
$$
\frac{F_N-B_N+NC}{F_N}\ge\frac CH.
$$
For the upper bound, choose $a$ with $q_ac_a=C$, and take
$$
\mu_j=q_j\quad(j\ne a),
\qquad
\mu_a=1-\sum_{j\ne a}q_j>q_a.
$$
Here
$$
f(\mu)=H,\qquad b_-(\mu)=C,\qquad b_+(\mu)=H.
$$
The theorem gives $G_{\mathrm{opt}}\le C/H$.
The threshold test and optimal constant functional require $O(m)$ rational arithmetic operations and polynomial bit complexity.
For example, with types $(1,0)$ and $(0,1)$ and supplies $q_1=q_2=1/4$, the optimal guarantee is $1/2$. Thus coordinatewise minimum valuations being zero does not force the multidimensional optimum to be zero.
For allocation counting, I treat identical copies as unlabeled: an assignment records each agent’s item type or unassignment. The guarantee and functional results above do not depend on this convention.
Fix a rational queried society $\mu$, and use only its $\tau$ supported types. Introduce an unassignment column $j=0$. Define the optimal-allocation polytope
$$
P(\mu)=
\left\{
x:
\begin{array}{l}
x_{tj}\ge0,\\
\sum_{j=0}^m x_{tj}=\mu_t,\\
\sum_t x_{tj}\le q_j\quad(j\ge1),\\
\sum_{t,j\ge1}t_jx_{tj}=f(\mu)
\end{array}
\right\}.
$$
Let $x^*(\mu)$ uniquely maximize
$$
\mathcal H(x)=-\sum_{t,j=0}^m x_{tj}\log x_{tj},
\qquad 0\log0=0,
$$
over this polytope. Existence follows from compactness and continuity; uniqueness follows from strict concavity.
Then a tagged type-$t$ agent’s limiting probabilities are
$$
\pi_{tj}=\frac{x^*_{tj}(\mu)}{\mu_t}.
$$
For an integral aggregate allocation with counts $Nx_{tj}$, the number of assignments realizing it is
$$
\prod_t\frac{(N\mu_t)!}{\prod_{j=0}^m(Nx_{tj})!}.
$$
Uniform Stirling bounds give
$$
\log(\text{count})
=
N\left(\mathcal H(x)+\sum_t\mu_t\log\mu_t\right)
+
O\!\left(\tau(m+1)\log(N+1)\right).
$$
There are at most $(N+1)^{\tau(m+1)}$ aggregate arrays.
Optimal feasible lattice arrays approach $x^*$ along every exact-replica sequence. To see this, take a common denominator $D$ of $\mu$ and $q$. The polytope before imposing optimal welfare is a network polytope; its vertices become integral after multiplication by $D$. Its welfare-optimal face introduces no new vertices. Express $x^*$ as a convex combination of its vertices and approximate the coefficients by multiples of $1/n$, summing to one. For $N=nD$, this gives optimal lattice arrays converging to $x^*$.
Outside any fixed neighborhood of $x^*$, uniqueness and compactness give a positive entropy gap. Its exponential counting effect dominates the polynomial number of arrays and the Stirling errors. Aggregate allocations therefore concentrate at $x^*$.
Conditional on an aggregate array, symmetry within type $t$ gives assignment probability $x_{tj}/\mu_t$. Concentration proves the claimed limit.
Section 3 proves that, in sufficiently large exact replicas, a tagged type-$t$ agent’s deletion loss is $u_t^+(\mu)$. Therefore
$$
\overline t_t
=
\sum_{j=1}^m t_j\pi_{tj}
-u_t^+(\mu)
-R(\mu).
$$
The deletion loss is computable exactly by maximizing $u_t$ on the optimal dual face. Computing all supported losses takes one welfare LP and $\tau$ face LPs, in
$$
\operatorname{poly}(m,\tau,L)
$$
time.
Here I supply the quantitative details missing from the earlier argument.
Let
$$
n=\tau(m+1),
\qquad
\mu_{\min}=\min_{t\in\operatorname{supp}(\mu)}\mu_t.
$$
It is enough to consider $0<\varepsilon\le1$.
For $0<\delta\le1/2$, define
$$
\mathcal H_\delta(x)
=
-\sum_{t,j}(x_{tj}+\delta)\log(x_{tj}+\delta).
$$
Integrating the absolute derivative of $z\log z$, separately near zero and away from zero, gives
$$
\sup_{x\in[0,1]^n}
|\mathcal H_\delta(x)-\mathcal H(x)|
\le n\delta\bigl(3+\log(1/\delta)\bigr).
$$
Entropy is strongly concave with constant one on $[0,1]^n$. In the interior this follows from its diagonal Hessian, whose entries are $-1/x_i\le-1$; continuity extends the inequality to the boundary. Since $x^*$ maximizes entropy on a convex set, strong concavity implies
$$
\mathcal H(x^*)-\mathcal H(x)
\ge\frac12\|x-x^*\|_2^2.
$$
For completeness, apply strong concavity to $(1-a)x^*+ax$, use optimality of $x^*$, divide by $a$, and let $a\downarrow0$.
Set
$$
\xi=\frac{\varepsilon^2\mu_{\min}^2}{8}.
$$
Choose a dyadic $\delta\le1/2$ satisfying
$$
n\delta\bigl(3+\log(1/\delta)\bigr)\le\xi.
$$
Its encoding length is
$$
O\!\left(\log n+\log(1/\xi)+\log\log(n/\xi+2)\right).
$$
If $x$ has smoothed objective error at most $\xi$, then
$$
\mathcal H(x^*)-\mathcal H(x)\le3\xi,
$$
so
$$
\|x-x^*\|_2\le\sqrt{6\xi}<\varepsilon\mu_{\min}.
$$
Every tagged probability therefore has additive error less than $\varepsilon$.
The rational description of $P(\mu)$ has polynomial size in $m,\tau,L$.
For each inequality, maximize its slack by an LP. Those with maximum slack zero are equalities throughout the polytope. Together with the displayed equalities, they define its affine hull: averaging points with positive slack for each remaining inequality yields a point strict in all of them, and hence a relative neighborhood within that affine space.
Gaussian elimination gives
$$
x=a+Ay,
$$
where $y$ consists of free original coordinates and $a,A$ have polynomial encoding length. In particular,
$$
\|A\|\le2^{\operatorname{poly}(m,\tau,L)}.
$$
If the reduced dimension is zero, the allocation is already a uniquely determined rational point.
Otherwise, the reduced full-dimensional polytope lies in $[0,1]^{d'}$. An outer radius is
$$
R_0=\max\{1,\sqrt{d'}\}.
$$
To obtain an inner radius, maximize a common positive slack for all remaining inequalities, with that slack bounded above by one. The optimum is positive. A basic optimal solution and Cramer’s rule show that the slack is at least
$$
2^{-\operatorname{poly}(m,\tau,L)}.
$$
Dividing by an upper bound on the constraint-normal norms gives an inner ball of radius
$$
r_0\ge2^{-\operatorname{poly}(m,\tau,L)}.
$$
Both the affine transformation and the logarithms of the radius bounds are thus polynomially controlled.
Use the rational central-cut ellipsoid method in dimension $d'$. The needed fact is: starting with an outer ball, rational cuts through successive centers that preserve a fixed set can be processed with polynomially bounded precision; after $T$ cuts the enclosing volume is reduced by at least $\exp(-T/(5d'))$. Consequently, a preserved ball of radius $r$ rules out more than $O(d'^2\log(R_0/r))$ cuts. This is the rational implementation in Theorem 3.2.1 and its containment and volume lemmas in [Grötschel–Lovász–Schrijver, Chapter 3](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf).
Here is the application, including oracle accuracies. Minimize the convex function
$$
g(y)=-\mathcal H_\delta(a+Ay)
$$
over the reduced polytope. A Lipschitz bound is
$$
K=\max\left\{1,\,
\|A\|\sqrt n\bigl(2+\log(1/\delta)\bigr)\right\}.
$$
Thus $\log K$ has polynomial size.
Suppose the desired objective accuracy is $\eta\le1$. At feasible query points, compute:
These computations are polynomial-time because they involve logarithms of positive rationals at prescribed binary precision.
At an infeasible center, use an exact separating linear inequality. At a feasible center, cut with the approximate gradient, retaining the halfspace
$$
\widetilde{\nabla g}(y)\cdot(z-y)\le0.
$$
Keep the feasible queried point with smallest approximate value.
Let $y^*$ minimize $g$, and let $c$ be an inner-ball center. Put
$$
\theta=\frac{\eta}{32KR_0}.
$$
Convexity of the feasible polytope implies that the ball
$$
B\bigl((1-\theta)y^*+\theta c,\theta r_0\bigr)
$$
is feasible. Lipschitz continuity implies that every point in this ball has objective at most
$$
g(y^*)+3KR_0\theta<g(y^*)+\eta/4.
$$
If every feasible queried center had objective greater than $g(y^*)+\eta/2$, convexity would give, for every point $z$ in that ball,
$$
\nabla g(y)\cdot(z-y)<-\eta/4.
$$
The gradient approximation changes this inner product by at most $\eta/8$, since feasible points are at distance at most $2R_0$. Thus every gradient cut would preserve the ball.
The ellipsoid volume bound makes that impossible after
$$
O\!\left(
d'^2\log\frac{R_0}{\theta r_0}
\right)
$$
cuts. Hence some feasible queried point has objective error at most $\eta/2$. Selecting by approximate values increases this error by at most $\eta/4$.
A zero approximate gradient can be handled immediately: its true norm is at most $\eta/(16R_0)$, so convexity bounds the objective error by $\eta/8$.
All cuts have polynomial encoding length. The radius, Lipschitz, and precision bounds show that the rational implementation takes polynomial bit time. Dimension one uses interval bisection with the same argument.
Applying this with $\eta=\xi$ proves the claimed allocation complexity:
$$
\operatorname{poly}\bigl(m,\tau,L,\log(1/\varepsilon)\bigr).
$$
For expected payments, compute probabilities to accuracy $\varepsilon/(m+1)$ and $R(\mu)$ to the remaining required accuracy. The exact deletion loss introduces no approximation error. The payment complexity is therefore the same polynomial bound plus the cost of evaluating $R(\mu)$.
With the explicit optimal functional from Section 5, evaluation is polynomial in its representation size and the query length. Including construction of that representation gives the exponential upper bound.
Allocation limits need not be rational. Consider
$$
\mathcal T=\{(1,0),(0,1),(1,1)\},
\qquad
q_1=q_2=\frac14,
\qquad
\mu_t=\frac13.
$$
Optimal welfare is $1/2$, forcing both supplies to be allocated entirely on value-one edges.
Symmetry and uniqueness of the entropy maximizer give rows, with columns item one, item two, and unassignment,
$$
\left(\frac14-x,0,\frac1{12}+x\right),
$$
$$
\left(0,\frac14-x,\frac1{12}+x\right),
$$
$$
\left(x,x,\frac13-2x\right).
$$
The entropy derivative is positive near $x=0$ and negative near $x=1/6$, so the maximizer is interior. Differentiation gives
$$
\left(\frac14-x\right)\left(\frac13-2x\right)
=
x\left(\frac1{12}+x\right),
$$
or
$$
12x^2-11x+1=0.
$$
The feasible root is
$$
x=\frac{11-\sqrt{73}}{24}.
$$
A tagged type-$(1,1)$ agent therefore receives each particular item with probability
$$
3x=\frac{11-\sqrt{73}}8,
$$
which is irrational.
The approximation bounds above are consequently more precise than an unspecified claim of “exact polynomial-time output.”
The unrestricted threshold problem has been reduced to the universal optimal-dual-face inequality
$$
q\cdot\bigl(p^+(\mu)-p^-(\mu)\bigr)
\le(1-\rho)f(\mu).
$$
Its failure has a polynomial-size certificate, and an exponential-time algorithm constructs an optimal functional.
What remains unproved is a polynomial-time way to test this inequality over all societies, or a hardness result compatible with the established $\mathrm{coNP}$ upper bound. The complexity of producing or evaluating a compact optimal functional likewise remains open.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial progress, but it does not resolve the unrestricted complexity question in USER_TASK. Its optimal-guarantee characterization and complexity upper bounds are sound in substance. I found no false central step. The remaining issues are an explicitly acknowledged unresolved target and minor clarifications concerning assignment conventions and the rational implementation of the approximation algorithm.
The inequalities
$$
0\le \Delta_i\le v_i(a_i)
$$
are correct. Extending a deleted-profile assignment by leaving the agent unassigned proves the lower bound; deleting that agent from any selected efficient assignment proves the upper bound.
The payment, utility, and revenue identities consequently follow:
$$
t_i=v_i(a_i)-\Delta_i-r_N(v_{-i}),
\qquad
u_i=\Delta_i+r_N(v_{-i}),
$$
$$
B_N=F_N-\sum_i\Delta_i,
\qquad
\sum_i t_i=B_N-\sum_i r_N(v_{-i}).
$$
Summing the deletion-loss upper bounds proves $B_N\ge0$, independently of the selected efficient assignment.
The truthfulness argument is valid: with other reports fixed, truthful reporting selects an assignment maximizing the agent’s true value plus the other agents’ reported values. The remaining terms in that agent’s utility are independent of its report.
Nonnegative rebates are sufficient for individual rationality. Although USER_TASK permits signed rebates, the proof does not mistakenly impose nonnegativity on the necessity argument. It uses nonnegativity only for its constructed mechanism.
The asserted uniform convergence over tagged agents is justified. Failure would provide a subsequence and a choice of tags violating admissibility. Averaged rebate convergence follows immediately.
The diagonal argument for continuity on rational societies also works. Exact-replica sizes can be chosen increasingly large and divisible by the necessary denominators. The selected profiles converge to the limiting rational society, and profiles at the remaining admissible sizes can complete the sequence.
This establishes continuity relative to the rational societies. The later construction independently defines a continuous functional on the entire real simplex, so it does not rely on an unjustified extension of this observation.
The primal and dual LPs are correct. Clipping a dual coordinate above one preserves feasibility because valuations are at most one and all dual coordinates are nonnegative.
The integrality assertion applies: after scaling by $N$, the allocation problem has integer capacities and the bipartite incidence structure required for total unimodularity. Thus both finite welfare identities are valid.
Both lattice operations preserve feasibility. Their objective values sum to twice the optimum, so each is optimal. Compactness and finitely many coordinatewise joins or meets justify simultaneous attainment of the stated coordinate extrema.
Consequently,
$$
b_-(s)=f(s)-s\cdot u^+(s),
\qquad
b_+(s)=f(s)-s\cdot u^-(s)
$$
and their stated bounds are correct.
Omitting unsupported types is legitimate for these price LPs: their utility variables have zero objective coefficients and can always be chosen to satisfy their constraints without restricting prices. The claimed exact computation time
$$
\operatorname{poly}(m,\tau,L)
$$
therefore uses support size appropriately.
The local vertex argument is valid. Finitely many nonoptimal dual vertices have strictly positive objective gaps at the fixed society, so none can become optimal sufficiently nearby.
Evaluating a deleted-profile optimum at the full profile gives the deletion-loss upper bound; evaluating a full-profile optimum at the deleted profile gives the lower bound. Their directions are correct. Summing establishes
$$
b_-(\mu)\le
\liminf_N\frac{B_N}{N}
\le
\limsup_N\frac{B_N}{N}
\le b_+(\mu).
$$
For exact replicas, decreasing a supported coordinate selects the largest utility coordinate among the dual optima. The eventual equality with $b_-(\mu)$ follows.
The upper-endpoint perturbation is also justified:
These facts establish the claimed upper endpoint. Rational perturbations and sufficiently large exact replicas supply the subsequence needed for the guarantee argument.
The necessity argument correctly applies no deficit to exact replicas, obtaining
$$
R(\mu)\le b_-(\mu).
$$
The upper-revenue subsequence then gives the stated upper bound on the guarantee. Using a subsequence is valid because it bounds the relevant $\liminf$ from above.
The subdivision argument also checks out. On each relative cell interior, the optimal dual face is fixed, welfare is affine, and both price-revenue extrema are constant. At a closure point, enlargement of the optimal face has exactly the stated effects on its minimum and maximum price revenues.
The vertex comparison correctly handles zero-welfare vertices. When the cell’s revenue spread is positive, an optimal price vector retained at every closure vertex forces positive welfare there. Thus division by welfare in that case is justified.
The simplicial interpolation satisfies both required bounds:
$$
0\le R(\mu)\le b_-(\mu),
$$
$$
R(\mu)\ge b_+(\mu)-(1-g)f(\mu).
$$
Its construction is continuous and nonnegative.
The finite realization is valid. Every completion used in $c_N$ is a legitimate full profile, and
$$
r_N(v_{-i})\le \frac{B_N(v)}N
$$
proves no deficit after summation. Continuity and the limiting revenue lower bound establish admissibility.
The zero-welfare case is addressed correctly. Such a society supports only the zero type. Eventually, the total number of nonzero agents is smaller than each item capacity, making simultaneous assignment of every such agent to a favorite item feasible. Hence $B_N=0$, and the constructed nonnegative rebates vanish.
Conclusion: the exact optimal-guarantee characterization and existence of an optimal continuous piecewise affine functional stand.
The dual-vertex count, arrangement-size bound, and determinant-based encoding bounds support the exponential construction time
$$
2^{\operatorname{poly}(m,k)}\operatorname{poly}(L).
$$
The $\mathrm{coNP}$ certificate argument is sound. A violating arrangement vertex has polynomial encoding length, and its welfare and revenue extrema can be verified by rational LPs in
$$
\operatorname{poly}(m,k,L)
$$
time.
The consequence concerning polynomial many-one $\mathrm{NP}$-hardness is correct: an $\mathrm{NP}$-hard language in $\mathrm{coNP}$ would imply $\mathrm{NP}=\mathrm{coNP}$.
The numerical optimum has polynomial rational encoding length, and threshold queries together with rational reconstruction justify the stated $\mathrm{FP}^{\mathrm{NP}}$ upper bound. This does not establish polynomial-time computation without an oracle.
Major unresolved target: neither membership in $\mathrm{coNP}$ nor an exponential algorithm answers the requested unrestricted polynomial-time versus hardness question. The output expressly acknowledges this. It also leaves the complexity of a compact optimal functional and general exact tagged outputs unresolved.
Required completion: supply the missing unrestricted complexity classification and specify the exact-output representation for any exact tagged-output complexity claim. This requires additional results, not merely clearer exposition.
The finite welfare and revenue formulas are correct, including the boundary condition $n_j=Nq_j$.
Because total demand exceeds total supply, at least one preferred-item group is strictly oversubscribed. This proves $B_N\ge NC$. Together with $B_N\le F_N\le NH$, it establishes the constant rebate’s stated guarantee.
At the proposed upper-bound society, the values
$$
f(\mu)=H,\qquad b_-(\mu)=C,\qquad b_+(\mu)=H
$$
are correct. The general characterization therefore supplies the matching upper bound.
The proposition and its polynomial bit-complexity claim stand.
Under the explicitly stated unlabeled-copy convention, the counting formula is correct. The Stirling error is uniform, and the number of aggregate arrays is polynomial in $N$ for fixed input dimensions.
The lattice approximation argument is valid: the welfare-optimal polytope is a face of the underlying network polytope, so it introduces no new vertices. Scaling by a common denominator makes those vertices integral. The coefficient approximation works along every exact-replica sequence.
Strict concavity, compactness, and the entropy gap establish concentration at the unique maximizer. Within-type symmetry then gives the tagged probabilities.
The expected-payment formula correctly combines those probabilities, the exact-replica deletion loss, and the limiting rebate.
Minor issue — assignment convention: USER_TASK does not explicitly specify whether copies are labeled. The prover makes a natural, explicit choice, but its tagged allocation and payment formulas depend on that choice. If distinct physical copies are counted separately, the counting weights change.
Minimum clarification: make the final tagged-output conclusions explicitly conditional on the stated unlabeled-copy interpretation. The welfare, guarantee, and functional results do not require this clarification.
The smoothing estimate, strong-concavity inequality, and conversion from objective error to tagged-probability error are correct. In particular,
$$
\sqrt{6\xi}<\varepsilon\mu_{\min}
$$
for the stated choice of $\xi$.
The affine-hull procedure handles forced equalities correctly. The positive common-slack LP and rational encoding bounds justify an exponentially small but adequately controlled inner radius.
The ellipsoid argument correctly preserves the near-optimal ball under the hypothetical absence of sufficiently good queried points. The gradient-error allowance and approximate-value selection bounds are sufficient.
I checked the cited source. The stated volume contraction is supported by its containment and volume lemmas; its fixed-subset variant also accommodates the preserved-ball argument. See [Grötschel–Lovász–Schrijver, Chapter 3](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf).
Minor issue — rational implementation: the displayed outer radius
$$
R_0=\max\{1,\sqrt{d'}\}
$$
need not be rational, while the invoked implementation uses rational input bounds. The write-up also does not explicitly describe normalization of nonzero rational cut vectors.
Minimum clarification: specify rational conservative bounds for the implementation and state the cut normalization used. These are routine implementation details; they do not require new mathematics or alter the claimed polynomial bound.
The payment approximation claim is correctly conditional on evaluating the selected functional.
The example is correct. Welfare optimality forces assignment exclusively on value-one edges and saturation of both supplies. Symmetry gives the displayed parametrization.
The derivative equation expands to
$$
12x^2-11x+1=0,
$$
and the stated root lies in the feasible interval. The resulting tagged probability
$$
\frac{11-\sqrt{73}}8
$$
is irrational.
This demonstrates that exact rational output is insufficient. It does not establish a lower bound for other exact representations, and the prover does not claim otherwise.
The output contains a valid characterization, existence result, complexity upper bounds, an exactly solved subclass, and tagged-limit formulas with polynomial-time additive approximation under its stated convention. These are genuine progress.
The unrestricted complexity question remains open within the output. The appropriate overall status is partial, rather than refuted or proved.
⟨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.