Multi-Unit Auctions for Allocating Chance-Constrained Resources (aaai23-26366)

Given finite agent types \(T\) with rational masses \(\mu\), population scale \(N\), capacity \(L\), risk limit \(\delta\), and finite bid menus \(Q_t\) containing bids \((k_{tq},b_{tq},\varepsilon_{tq})\), choose nonnegative masses \(x_{tq}\) summing to \(\mu_t\) for each type, maximizing \(N\) times total expected reward subject to \(N\) times total allocated resource being at most \(L\) and the product of \((1-\varepsilon_{tq})^{N x_{tq}}\) being at least \(1-\delta\).

A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed finite bid menu \(Q_t\). A bid \((k_{tq},b_{tq},\varepsilon_{tq})\) specifies an integer resource allocation \(0\le k_{tq}\le C\), a signed rational expected reward \(b_{tq}\), and a rational probability \(0\le\varepsilon_{tq}<1\) of exceeding that allocation. Include a null bid \((0,0,0)\) in every menu, representing nonselection.
The remaining inputs are a positive integer population scale \(N\), positive integer capacity \(C\), rational risk limit \(0\le\delta<1\), and rational reward threshold \(r\), all encoded in binary. Write \(m=\sum_t|Q_t|\) and let \(L\) be the total input bit length.
An allocation consists of real masses \(x_{tq}\ge0\) with \(\sum_{q\in Q_t}x_{tq}=\mu_t\) for every type. Its reward is \(N\sum_{t,q}b_{tq}x_{tq}\).
Decide whether an allocation exists satisfying \(N\sum_{t,q}k_{tq}x_{tq}\le C\), \(\prod_{t,q}(1-\varepsilon_{tq})^{Nx_{tq}}\ge1-\delta\), and \(N\sum_{t,q}b_{tq}x_{tq}\ge r\). The product is the stipulated risk constraint; all comparisons are exact.

Is this exact reward-threshold decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For discrete agents selecting at most one bid each, the multiplicative risk constraint admits an equivalent MILP formulation with logarithmic coefficients; this establishes no polynomial-time complexity bound. [Gautier et al. (2023)](https://www.robots.ox.ac.uk/~nickh/papers/gautier23aaai.pdf)
No result settling this exact continuous decision problem was located in the literature search.

Partial result: polynomial-time many-one equivalence with product-of-powers comparison

I do not settle the unrestricted classification as polynomial-time solvable or $\mathrm{NP}$-hard. I prove a stronger characterization than the Turing equivalence in the notes.

Let $\mathcal A$ denote the allocation decision problem, and let $\mathrm{PoE}_{\ge}$ denote binary-encoded product-of-powers comparison. Then
$$ \mathcal A\equiv_m^p\mathrm{PoE}_{\ge}, $$
where $\equiv_m^p$ means polynomial-time many-one reducibility in both directions. Consequently,
$$ \mathcal A\in\mathrm P \quad\Longleftrightarrow\quad \mathrm{PoE}_{\ge}\in\mathrm P, $$
and
$$ \mathcal A\text{ is }\mathrm{NP}\text{-hard} \quad\Longleftrightarrow\quad \mathrm{PoE}_{\ge}\text{ is }\mathrm{NP}\text{-hard}. $$

The new ingredient is an unconditional polynomial-time algorithm that finds an exact rational allocation minimizing risk among allocations satisfying capacity and reward. It requires only logarithmic comparisons involving a fixed number of arguments. Comparing the resulting minimum risk with the prescribed limit is the single unrestricted product-of-powers comparison that remains.

All proofs below include ties, zero multipliers, and empty products.

1. The arithmetic comparison problem

An instance of $\mathrm{PoE}_{\ge}$ consists of positive integers $a_i,u_i,c_j,v_j$, encoded in binary. The question is whether
$$ \prod_{i=1}^{s}a_i^{u_i} \ge \prod_{j=1}^{h}c_j^{v_j}. $$
Either factor list may be empty; an empty product equals $1$. Factors with base $1$ may be omitted. Any zero exponents arising in reductions are also omitted.

We use the following unconditional theorem:

Fixed-factor comparison theorem. For every fixed constant $K$, product-of-powers comparison with at most $K$ factors in total is decidable in polynomial time in its binary encoding length.

This is Proposition 3.7(2) of [Etessami–Stewart–Yannakakis, *A note on the complexity of comparing succinctly represented integers*](https://www.pure.ed.ac.uk/ws/files/17370828/Etessami_Stewart_ET_AL_2014_A_note_on_the_complexity_of_comparing_succinctly_represented_integers_with_an_application_to_maximum_probability_parsing.pdf).

Here is the precise consequence needed below. Consider
$$ \Lambda=\sum_{\ell=1}^{J}\gamma_\ell\log\rho_\ell, $$
where $\gamma_\ell$ are rational and $\rho_\ell>0$ are rational, all binary encoded. Write $\rho_\ell=U_\ell/V_\ell$ with positive integers $U_\ell,V_\ell$. Choose a positive common denominator $M$ of the coefficients and put $e_\ell=M\gamma_\ell\in\mathbb Z$. Then
$$ M\Lambda = \sum_{\ell=1}^{J}e_\ell\log U_\ell - \sum_{\ell=1}^{J}e_\ell\log V_\ell. $$
Moving negative coefficients to the opposite side converts $\Lambda\ge0$ into a product-of-powers comparison with at most $2J$ factors.

The transformation preserves equality, since multiplication by $M>0$ and exponentiation are order preserving. Its encoding length is polynomial: a product of the coefficient denominators has bit length at most their total bit length, and the resulting integer exponents have polynomial bit length.

Therefore, when $J$ is bounded by a fixed constant, the exact sign of $\Lambda$ is computable in polynomial time. Two weak comparisons distinguish positive, zero, and negative values. Empty sides are handled by the convention above.

2. Product-of-powers comparison reduces to allocation

Proposition 1.
$$ \mathrm{PoE}_{\ge}\le_m^p\mathcal A, $$
even with $N=C=1$, zero resource consumption, dyadic masses, and two bids per type.

Proof. Write
$$ A=\prod_i a_i^{u_i}, \qquad B=\prod_j c_j^{v_j}, \qquad E=\sum_i u_i+\sum_j v_j. $$

If $E=0$, both lists are empty and the comparison is true. Output the fixed feasible allocation instance with one type of mass $1$, only its null bid, $N=C=1$, and $r=\delta=0$.

Now suppose $E>0$. Choose powers of two $S,D$ such that
$$ E\le S<2E, \qquad D\ge2, \qquad D>\max\bigl(\{a_i\}_i\cup\{c_j\}_j\bigr). $$

For every left-hand factor, create a type of mass $u_i/S$ with bids
$$ (0,0,0), \qquad (0,1,1-a_i/D). $$
For every right-hand factor, create a type of mass $v_j/S$ with bids
$$ (0,0,0), \qquad (0,1,1-1/(Dc_j)). $$
If $S>E$, add a type of mass $(S-E)/S$ with bids
$$ (0,0,0), \qquad (0,1,1-1/D). $$

Set
$$ N=C=1, \qquad r=1, \qquad \delta=1-\frac1D. $$

Every included mass is positive and dyadic, and their sum is $1$. Every nonnull bid has an admissible exceedance probability: its success probability lies strictly between $0$ and $1$. All allocations satisfy capacity because every bid has resource consumption zero.

The reward equals $1$ minus the total mass assigned to null bids. Thus meeting $r=1$ forces every type’s entire mass onto its nonnull bid. The risk product of this unique reward-feasible allocation is
$$ \prod_i(a_i/D)^{u_i/S} \prod_j(1/(Dc_j))^{v_j/S} (1/D)^{(S-E)/S} = \frac1D\left(\frac AB\right)^{1/S}, $$
where the padding factor is omitted if $S=E$.

Hence the risk condition holds precisely when
$$ \frac1D\left(\frac AB\right)^{1/S}\ge\frac1D, $$
equivalently $A\ge B$.

The binary lengths of $S,D$, all masses, and all bid probabilities are polynomial in the source input length. No expanded product is computed. $\square$

3. The rational feasible polytope and its risk objective

For an allocation instance, define
$$ y_{tq}=Nx_{tq}, \qquad w_t=N\mu_t, \qquad a_{tq}=-\log(1-\varepsilon_{tq}), \qquad d=-\log(1-\delta). $$
All logarithms are finite because their arguments are positive. Also $a_{tq}\ge0$ and $d\ge0$.

The substitution between $x$ and $y$ is bijective because $N>0$. Define the rational polytope
$$ P= \left\{ y\ge0: \sum_qy_{tq}=w_t\ \text{for every }t,\ \sum_{t,q}k_{tq}y_{tq}\le C,\ \sum_{t,q}b_{tq}y_{tq}\ge r \right\}. $$
Its rational coefficients have polynomial encoding length. The polynomial-time theorem for rational linear programming therefore decides whether $P$ is empty.

If $P$ is nonempty, its type equalities imply
$$ 0\le y_{tq}\le w_t. $$
Thus $P$ is compact, and
$$ z^*=\min_{y\in P}\sum_{t,q}a_{tq}y_{tq} $$
exists and is finite.

Taking logarithms of the stipulated product gives
$$ \prod_{t,q}(1-\varepsilon_{tq})^{y_{tq}}\ge1-\delta \quad\Longleftrightarrow\quad \sum_{t,q}a_{tq}y_{tq}\le d. $$
Consequently, the original instance is feasible exactly when $P$ is nonempty and $z^*\le d$.

The objective coefficients are generally irrational. Ordinary rational linear programming alone does not justify computing $z^*$.

4. An attained dual optimum among polynomially many candidates

For $\lambda,\nu\ge0$, put
$$ f_{tq}(\lambda,\nu) = a_{tq}+\lambda k_{tq}-\nu b_{tq}, $$
and
$$ g(\lambda,\nu) = -C\lambda+r\nu+ \sum_t w_t\min_q f_{tq}(\lambda,\nu). $$

Lemma 2. If $P$ is nonempty, then $g$ attains its maximum on the nonnegative quadrant, and that maximum equals $z^*$.

Proof. The linear-programming dual is
$$ \max \left\{ -C\lambda+r\nu+\sum_t w_t\alpha_t: \lambda,\nu\ge0,\ \alpha_t\le a_{tq}+\lambda k_{tq}-\nu b_{tq} \text{ for every }t,q \right\}. $$
The signs follow from the Lagrangian terms
$$ \lambda\left(\sum_{t,q}k_{tq}y_{tq}-C\right) + \nu\left(r-\sum_{t,q}b_{tq}y_{tq}\right). $$

The primal is feasible and has a finite optimum. The dual is feasible: take $\lambda=\nu=0$ and $\alpha_t=0$, using $a_{tq}\ge0$. Finite-dimensional linear-programming strong duality, which applies to real coefficients, gives an attained dual optimum equal to $z^*$.

Since $w_t>0$, maximizing over $\alpha_t$ for fixed $\lambda,\nu$ sets
$$ \alpha_t=\min_q f_{tq}(\lambda,\nu). $$
This yields the stated conclusion. $\square$

For each same-type pair of bids with different vectors $(k,b)$, form the indifference line
$$ (k_{tq}-k_{tq'})\lambda - (b_{tq}-b_{tq'})\nu = a_{tq'}-a_{tq}. $$
Include both coordinate axes. There are $O(m^2)$ lines.

Pairs with identical $(k,b)$ are omitted because their difference is constant. Let $V$ consist of all intersections of two lines with independent normals that lie in the nonnegative quadrant. The axes ensure $(0,0)\in V$, and
$$ |V|=O(m^4). $$

Lemma 3. Some point of $V$ maximizes $g$.

Proof. Let $p^*$ be an attained maximizer. For each type, choose a minimizing bid $q_t$ at $p^*$. Define
$$ H= \left\{ (\lambda,\nu)\ge0: f_{tq_t}(\lambda,\nu)\le f_{tq}(\lambda,\nu) \text{ for every }t,q \right\}. $$
This closed polyhedron contains $p^*$. On $H$, the function $g$ agrees with the affine function
$$ F(\lambda,\nu) = -C\lambda+r\nu+\sum_t w_t f_{tq_t}(\lambda,\nu). $$
Because $g\le z^*$ throughout the quadrant,
$$ H^*=\{p\in H:F(p)=z^*\} $$
is a nonempty face of $H$.

This face contains an extreme point. Indeed, minimize $\lambda+\nu$ on $H^*$. The minimum is attained because restricting to a sublevel set through any chosen point gives a nonempty compact set. Among its minimizers, choose $v$ minimizing $\lambda$.

If $v$ were a nontrivial convex combination of two points of $H^*$, minimality would force both points to have the same coordinate sum and then the same $\lambda$. They would also have the same $\nu$, so both would equal $v$. Thus $v$ is extreme in $H^*$. Since $H^*$ is a face, $v$ is extreme in $H$.

The active constraint normals of $H$ at $v$ span the plane. Otherwise, a nonzero direction perpendicular to all active normals would permit sufficiently small perturbations in both directions: active constraints would remain equalities, and every inactive constraint would remain satisfied by its positive slack. This would contradict extremality.

Therefore two independent active boundaries meet at $v$. Each is an axis or one of the included indifference lines. Hence $v\in V$ and $g(v)=z^*$. $\square$

5. Exact minimization without unrestricted product comparisons

Theorem 4. There is an unconditional algorithm, polynomial in $m,\tau,L$, that either detects $P=\varnothing$ or outputs a rational minimizer of
$$ \sum_{t,q}a_{tq}y_{tq} $$
over $P$. Its output has polynomial encoding length.

Proof. First test rational feasibility of $P$. Suppose it is nonempty.

Computing the candidates and their minimizing bids

Each indifference line has rational normal coefficients and a right-hand side that is a difference of two bid-risk logarithms. Solving two independent line equations therefore expresses both candidate coordinates as rational linear combinations of at most four bid-risk logarithms. Intersections involving axes use no more.

The rational coefficients have polynomial bit length: solving a rational system of order two uses a fixed number of rational operations, and its determinant and inverse have polynomial encoding length.

Candidate membership in the nonnegative quadrant can therefore be tested using the fixed-factor comparison theorem.

At any retained candidate $v=(\lambda,\nu)$, compute, for every type,
$$ M_t(v)= \left\{ q: f_{tq}(v)=\min_{q'}f_{tq'}(v) \right\}. $$
A comparison of two bids has the form
$$ f_{tq}(v)-f_{tq'}(v) = a_{tq}-a_{tq'} + (k_{tq}-k_{tq'})\lambda - (b_{tq}-b_{tq'})\nu. $$
It involves at most six bid-risk logarithms: the four from the candidate coordinates and the two from the compared bids. After splitting rational arguments into numerators and denominators, there are at most twelve integer bases.

Thus all minimizing sets, including exact ties, and the signs of $\lambda,\nu$ are computable in polynomial time using the unconditional fixed-factor theorem.

Testing optimality using a rational system

For each candidate $v$, form the following rational feasibility system $Q(v)$:

• Require $y\in P$.
• Require $y_{tq}=0$ whenever $q\notin M_t(v)$.
• If $\lambda>0$, require $\sum_{t,q}k_{tq}y_{tq}=C$.
• If $\nu>0$, require $\sum_{t,q}b_{tq}y_{tq}=r$.

Every coefficient in this system is rational. The logarithmic comparisons determine only which equations to include.

We show that every feasible point of $Q(v)$ minimizes risk. Put
$$ \alpha_t=\min_q f_{tq}(v), \qquad K(y)=\sum_{t,q}k_{tq}y_{tq}, \qquad B(y)=\sum_{t,q}b_{tq}y_{tq}. $$
For every $y\in P$,
$$ \sum_{t,q}a_{tq}y_{tq}-g(v) = \sum_{t,q}y_{tq}\bigl(f_{tq}(v)-\alpha_t\bigr) + \lambda\bigl(C-K(y)\bigr) + \nu\bigl(B(y)-r\bigr). $$
This identity follows by expanding $f_{tq}$ and using $\sum_qy_{tq}=w_t$.

Every summand on the right is nonnegative. For $y\in Q(v)$, the first sum vanishes because positive coordinates occur only at minimizing bids. Each of the last two terms vanishes either because its multiplier is zero or because its imposed equality holds. Hence
$$ \sum_{t,q}a_{tq}y_{tq}=g(v). $$
Lemma 2 gives $g(v)\le z^*$, whereas feasibility gives $\sum a_{tq}y_{tq}\ge z^*$. Both must equal $z^*$.

At least one $Q(v)$ is nonempty. By Lemma 3, choose $v\in V$ with $g(v)=z^*$, and let $y^*$ be any primal minimizer. The displayed identity has zero left-hand side and nonnegative summands. Thus every summand vanishes. In particular, $y^*$ is supported on $M_t(v)$ and satisfies every global equality whose multiplier is positive. Therefore $y^*\in Q(v)$.

The algorithm enumerates the $O(m^4)$ candidates, constructs their minimizing sets, and tests the corresponding rational systems. It stops at the first feasible one and outputs a rational feasible point. Rational linear programming supplies such a point in polynomial time with polynomial encoding length. All preceding comparisons have a constant number of logarithmic arguments. $\square$

This is the crucial strengthening: the algorithm never compares the global values $g(v)$ with one another or with the risk limit.

6. A sparse optimal allocation

The optimizer can additionally be chosen with at most $\tau+2$ positive coordinates.

Proposition 5. If $P$ is nonempty, an exact risk minimizer can be computed in polynomial time that is a vertex of $P$. Every vertex of $P$ has at most $\tau+2$ positive coordinates. Consequently, at most two types split their mass among several bids.

Proof. For any feasible $Q(v)$, its extra constraints set nonnegative coordinates to zero or make original global inequalities tight. Each such restriction defines a face of $P$; their nonempty intersection $Q(v)$ is therefore a face of $P$.

A vertex of $Q(v)$ can be computed by sequential rational linear programs minimizing coordinates. Each minimization restricts to a nonempty compact face; after all coordinates have been fixed, the remaining set is a singleton and hence a vertex. All these faces have vertices among the original rational polytope’s vertices, whose coordinates have polynomial bit length by determinant bounds. Thus this procedure is polynomial-time.

A vertex of a face is a vertex of $P$, and Theorem 4 shows that every point of $Q(v)$ minimizes risk.

Now let $y$ be a vertex of $P$, with $h$ positive coordinates. Restrict to those coordinates. There are $\tau$ type equalities and at most two active global inequalities. If $h>\tau+2$, their coefficient matrix has a nonzero null vector. Extend that vector by zero on the other coordinates.

Sufficiently small perturbations of $y$ in either direction preserve positivity on its support, all type equalities, and every active global constraint. They preserve inactive constraints because those have positive slack. This contradicts that $y$ is a vertex. Hence
$$ h\le\tau+2. $$

Every type has at least one positive coordinate because $w_t>0$. Each type using several bids contributes at least one coordinate beyond this baseline of $\tau$. Therefore at most two types split their mass. $\square$

7. Allocation reduces to one product-of-powers comparison

Proposition 6.
$$ \mathcal A\le_m^p\mathrm{PoE}_{\ge}. $$

Proof. If rational feasibility testing finds $P=\varnothing$, output the fixed false comparison $1\ge2$.

Otherwise, use Theorem 4 to compute a rational minimizer $y^*$. Write
$$ 1-\varepsilon_{tq}=\frac{U_{tq}}{V_{tq}}, \qquad 1-\delta=\frac{H}{J}, $$
with positive integers in numerator and denominator.

Choose a positive common denominator $M$ of all coordinates of $y^*$ and set
$$ e_{tq}=My^*_{tq}\in\mathbb Z_{\ge0}. $$
The original allocation instance is feasible exactly when
$$ \prod_{t,q}(1-\varepsilon_{tq})^{y^*_{tq}}\ge1-\delta, $$
because $y^*$ minimizes the negative logarithm of that product over $P$.

Raising both sides to the positive integer $M$ and cross-multiplying positive denominators gives the equivalent comparison
$$ J^M\prod_{t,q}U_{tq}^{e_{tq}} \ge H^M\prod_{t,q}V_{tq}^{e_{tq}}. $$
This is one $\mathrm{PoE}_{\ge}$ instance. Omit zero exponents and unit bases, interpreting any empty side as $1$.

The rational optimizer has polynomial encoding length. Choosing $M$ as the product of its coordinate denominators therefore gives $M$ and every $e_{tq}$ polynomial bit length. The entire comparison is constructed in polynomial time. $\square$

Propositions 1 and 6 establish the asserted many-one equivalence. Composing these reductions also proves the equivalence of $\mathrm{NP}$-hardness under polynomial-time many-one reductions.

8. Consequences and remaining open question

Two unconditional polynomial-time special cases follow.

Fixed support size. By Proposition 5, the final risk comparison uses at most $\tau+2$ bid-risk arguments and one threshold argument. For fixed $\tau$, this is a fixed number of rational logarithm arguments. The fixed-factor comparison theorem therefore decides the final comparison in polynomial time.

Fixed number of distinct exceedance probabilities. If the menus contain at most a fixed number of distinct exceedance probabilities, collect the optimizer’s exponents for equal success probabilities. The final comparison again has a fixed number of rational arguments, including the threshold, so the same theorem applies.

For unrestricted inputs, the proved result isolates the difficulty precisely: an exact minimum-risk allocation is computable in polynomial time, but its comparison with the prescribed threshold is equivalent to unrestricted binary-encoded product-of-powers comparison.

I have not supplied an unconditional polynomial-time algorithm or an $\mathrm{NP}$-hardness proof for that arithmetic problem. Thus the requested unrestricted classification remains unresolved in this answer.

⟨structured verdict parsed — rendered above⟩

Verification report

Assessment: correct and rigorous partial progress. The write-up establishes the claimed polynomial-time many-one equivalence and the two stated polynomial-time special cases. I found no false step or substantive gap in those arguments. It does not resolve the unrestricted classification requested in USER_TASK, and it explicitly acknowledges that limitation.

1. Arithmetic comparison theorem

The fixed-factor comparison theorem is correctly stated and attributed. Proposition 3.7(2) establishes unconditional polynomial-time inequality testing when the numbers of factors on both sides are fixed constants, with integer bases and exponents encoded in binary. See [Etessami–Stewart–Yannakakis, Proposition 3.7(2)](https://www.pure.ed.ac.uk/ws/files/17370828/Etessami_Stewart_ET_AL_2014_A_note_on_the_complexity_of_comparing_succinctly_represented_integers_with_an_application_to_maximum_probability_parsing.pdf).

The conversion of a rational logarithmic form is valid:

• All logarithm arguments are positive.
• Multiplying by a positive common denominator preserves the sign.
• Splitting each rational argument into numerator and denominator introduces at most two integer-base terms.
• Moving terms according to the signs of their integer coefficients produces the stated comparison.
• The common denominator and resulting exponents have polynomial binary encoding length, even though their numerical values may be large.
• Two weak comparisons suffice to distinguish all three possible signs.

Unit bases and zero coefficients can be omitted without changing the comparison. Empty products cause no arithmetic difficulty.

Finding: The theorem applies exactly as needed. No issue.

2. Reduction from product-of-powers comparison to allocation

Proposition 1 correctly constructs a legal allocation instance.

For nonempty factor lists, $E$ is positive. Powers of two satisfying the specified conditions on $S$ and $D$ exist and have polynomial encoding length. All constructed masses are positive and dyadic; the padding type is included only when its mass is positive.

Every bid satisfies the input restrictions:

• Resource consumption is zero, hence lies in the permitted range.
• Rewards are rational.
• The success probabilities $a_i/D$, $1/(Dc_j)$, and $1/D$ lie strictly between zero and one.
• Every menu contains the null bid.
• The capacity, population scale, and risk limit are admissible.

Because total mass is one and every nonnull bid has reward one, the reward threshold forces all mass onto nonnull bids. There is therefore exactly one reward-feasible allocation.

The critical product calculation is correct:

$$ D^{-E/S}D^{-(S-E)/S} \left(\frac AB\right)^{1/S} = \frac1D\left(\frac AB\right)^{1/S}. $$

The padding exponent is zero when padding is absent. Since $S$ and $D$ are positive, comparison with $1/D$ is equivalent to $A\ge B$.

When $E=0$, positivity of all listed exponents implies that both lists are empty. The fixed feasible instance correctly represents the true comparison.

No expanded product is needed, and the construction has polynomial output size.

Finding: The reduction is correct, including empty lists and padding. No issue.

3. Rational polytope and logarithmic risk objective

The substitution $y_{tq}=Nx_{tq}$ is bijective because $N>0$. It correctly transforms type masses, capacity, and reward.

The polytope $P$ uses only rational coefficients of polynomial encoding length. Polynomial-time rational linear-programming feasibility testing therefore applies.

For nonempty $P$, each coordinate satisfies

$$ 0\le y_{tq}\le w_t. $$

Together with closedness, this establishes compactness. Consequently, the real linear risk objective attains its minimum.

All success probabilities and the threshold success probability are positive, including when an exceedance probability or the risk limit is zero. Taking logarithms is therefore valid, and the direction of the risk inequality is correctly reversed when multiplying by negative one.

The write-up correctly distinguishes rational feasibility testing from optimization with generally irrational objective coefficients.

Finding: The formulation and feasibility equivalence are correct. Signed rewards introduce no omitted restriction. No issue.

4. Dual attainment and candidate sufficiency

Lemma 2

The Lagrangian signs and displayed dual constraints are correct.

The primal is feasible and bounded whenever this lemma is invoked. The dual is feasible at zero multipliers and zero type variables because all risk coefficients are nonnegative. Finite-dimensional linear-programming strong duality applies to real coefficients and provides attainment under these hypotheses.

Since every $w_t$ is positive, maximizing over each type variable gives precisely the corresponding minimum bid value.

Finding: Dual attainment and equality with $z^*$ are justified. No issue.

Lemma 3

The chosen minimizing bids define a nonempty closed polyhedron $H$. On this polyhedron, the function $g$ equals the specified affine function $F$.

Because $g$ is everywhere bounded above by $z^*$, the nonempty set where $F=z^*$ is a face of $H$.

The extreme-point argument is valid:

• Nonnegativity of both coordinates makes a coordinate-sum sublevel set bounded.
• Closedness makes the relevant nonempty sublevel set compact.
• Minimizing the coordinate sum and then the first coordinate yields the stated extreme point.
• Extremality passes from the face to $H$.
• If active normals failed to span the plane, sufficiently small perturbations in both directions would preserve every constraint, contradicting extremality.

Thus two independent active boundaries determine the point. They are coordinate axes or included indifference lines.

Omitting pairs with identical resource and reward vectors is harmless: their difference is constant, so they introduce no nonzero boundary normal. Ties, coincident lines, lower-dimensional regions, and unbounded regions do not invalidate the argument.

There are polynomially many line pairs, with at most $O(m^4)$ candidate intersections.

Finding: A candidate attaining the dual optimum is rigorously established. No issue.

5. Polynomial-time computation of a rational risk minimizer

Theorem 4 is the central algorithmic claim. Its argument checks out.

Candidate representation and comparisons

Solving two independent line equations uses rational coefficients and at most four bid-risk logarithms. Independence is determined by rational normals; no comparison of irrational determinants is required.

The rational coefficients obtained from these fixed-size systems have polynomial bit length. Testing coordinate signs therefore uses only a fixed number of logarithmic arguments.

A bid comparison adds at most two further bid-risk logarithms. The resulting bound of six rational logarithmic arguments, or twelve integer bases after splitting arguments, is correct.

The algorithm consequently determines minimizing bids and multiplier signs exactly, including equality cases, in polynomial time.

Rational optimality tests

The system $Q(v)$ is rational. The candidate values themselves need not be inserted as irrational coefficients: only minimizing sets and multiplier signs determine which rational restrictions are included.

The displayed identity is algebraically correct:

$$ \sum_{t,q}a_{tq}y_{tq}-g(v) = \sum_{t,q}y_{tq}\bigl(f_{tq}(v)-\alpha_t\bigr) + \lambda\bigl(C-K(y)\bigr) + \nu\bigl(B(y)-r\bigr). $$

For feasible $y$, every term on the right is nonnegative. For $y\in Q(v)$, each term vanishes under precisely the restrictions stated in the proof. Such a point therefore achieves the dual value and is optimal.

Conversely, at an optimal candidate, any primal minimizer makes the nonnegative right-hand side sum to zero. This forces the support and tightness conditions required by $Q(v)$. Hence at least one tested system is feasible.

There are polynomially many candidates and comparisons, and every rational feasibility system has polynomial encoding length. Rational linear programming supplies a rational feasible point of polynomial encoding length.

Finding: The algorithm computes an exact rational optimizer without an unrestricted product comparison. No issue.

6. Sparse optimal allocation

Each additional restriction defining $Q(v)$ makes an original valid inequality tight: either a nonnegativity inequality or a global inequality. Their nonempty intersection is therefore a face of $P$.

Sequential coordinate minimization on this compact rational face produces a singleton face, hence a vertex. The bit-length argument is valid because the intermediate sets remain faces whose vertices are vertices of the original rational polytope.

For the support bound, if a vertex had more than $\tau+2$ positive coordinates, the type equalities and active global constraints would leave a nonzero null direction on that support. Small perturbations in both directions preserve nonnegativity and all constraints, contradicting extremality.

Positive type masses ensure at least one positive coordinate per type. The support bound therefore implies that at most two types split their mass.

Finding: Both the constructive vertex claim and the support bound are correct. No issue.

7. Reduction from allocation to one product comparison

If $P$ is empty, the fixed false comparison correctly represents infeasibility.

Otherwise, using the computed optimizer is valid because minimizing the negative logarithm maximizes the risk product over $P$. Thus testing that optimizer against the risk limit decides allocation feasibility.

The common-denominator transformation is correct. Raising both sides to the positive integer $M$ and cross-multiplying gives

$$ J^M\prod_{t,q}U_{tq}^{e_{tq}} \ge H^M\prod_{t,q}V_{tq}^{e_{tq}}. $$

Every base is positive, every retained exponent is positive, and omitted zero exponents or unit bases preserve the comparison. The optimizer’s polynomial encoding length ensures polynomial encoding length for the common denominator and all exponents.

Finding: The polynomial-time many-one reduction is correct. Together with Proposition 1, it establishes the asserted equivalence and its stated membership and hardness consequences.

8. Special cases and unresolved target

The fixed-support special case follows from the bound of $\tau+2$ positive optimizer coordinates. Adding the threshold yields a fixed number of rational logarithmic arguments when $\tau$ is fixed.

The fixed-number-of-distinct-probabilities special case also follows: collecting rational exponents preserves polynomial encoding length and leaves a fixed number of arguments.

Neither special case covers unrestricted input. The many-one equivalence transfers a classification between the two problems; it does not itself supply one.

Major scope issue: The unrestricted question in USER_TASK remains unanswered. This is an explicitly acknowledged limitation, not an error in the proved characterization.

Minimum additional work required: Establish one of the requested unrestricted complexity classifications and invoke the proved reductions. No clarification or repair of the existing proof is needed to verify its partial results.

⟨structured verdict parsed — rendered above⟩