| paper | Multi-Unit Auctions for Allocating Chance-Constrained Resources |
| authors | — |
| venue | AAAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
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\).
An anonymous finite-type population in which \(x_{tq}\) is the mass of type \(t\) assigned bid \(q\); maximize aggregate expected reward subject to capacity and logarithmic survival-risk constraints.
The bid triples encode the paper’s conservative no-agent-exceeds certificate rather than the full aggregate consumption distribution, so this does not continuize the underlying CCMMDP chance constraint.
fatal: False
It covers ACCR’s auctioneer-side winner determination and Proposition 1, but not implicit bid generation, Pareto-frontier computation, VCG pricing, strategic truthfulness, or empirical comparisons.
The strongest honest positive case is a continuous version of ACCR’s winner-determination problem, using the advertising domain as the regime. The paper explicitly studies 1,000 independent agents with identical 15-state MDPs, so this is not an invented high-multiplicity story: one type, or a small number of types if current funnel state is included, represents a very large population of near-identical customers. Mass is the fraction of customers of each type.
There is an important qualification. The supplied paper contains no numbered theorem, lemma, corollary, or proposition establishing membership in P, NP-hardness, W[1]-hardness, or similar. Its only numbered technical result is Proposition 1, proved in this paper. Proposition 1 shows that replacing ACCR’s nonlinear chance constraint (10) by the logarithmic constraint (13) gives an equivalent MILP. It is an algorithmic anchor, but not a formal complexity classification; one must not claim that the paper proves ACCR is polynomial-time, since MILP winner determination can itself be hard.
My lead mirror would be Continuous ACCR Winner Determination.
An instance consists of:
\[
B_{tq}=(k_{tq},b_{tq},\epsilon_{tq}),
\]
with \(k_{tq}\) the allocated resource, \(b_{tq}\) expected reward, and \(\epsilon_{tq}<1\) the probability of exceeding that allocation under the associated policy.
Include a dummy bid \((0,0,0)\), so every unit of mass receives exactly one option. The decision variable \(x_{tq}\ge0\) is the mass of type \(t\) assigned bid \(q\). The problem is
\[ \max \quad N\sum_{t\in T}\sum_{q\in Q_t} b_{tq}x_{tq} \]
subject to
\[ \sum_{q\in Q_t}x_{tq}=\mu_t \qquad(t\in T), \]
\[ N\sum_{t,q} k_{tq}x_{tq}\le L, \]
and the fractional-count extension of ACCR’s survival constraint,
\[ \prod_{t,q}(1-\epsilon_{tq})^{Nx_{tq}}\ge 1-\delta. \]
Equivalently,
\[ N\sum_{t,q}x_{tq}\log(1-\epsilon_{tq}) \ge \log(1-\delta). \]
A solution is the complete mass allocation \(x\), together with its objective value. When \(Nx_{tq}\) are integers, this is exactly the paper’s allocation model after grouping identical agents; allowing real \(x\) is its high-multiplicity relaxation. The final logarithmic formulation is precisely the structure identified by Proposition 1, with the binary individual-choice variables replaced by mass variables.
For an explicit finite bid menu, this is an LP and therefore an expected Class A result. Its size is polynomial in \(|T|+\sum_t|Q_t|\), assuming the logarithmic risk coefficients are represented in the same real-number/oracle convention used by Proposition 1, or are supplied directly as \(r_{tq}=-\log(1-\epsilon_{tq})\). It also has the expected high-multiplicity bridge: a rational mass solution can be rounded to a sufficiently large finite cohort, with controlled additive loss in reward and resource usage.
The mirror is plausible because it preserves the paper’s actual objects: the same resource quantity, expected reward, per-policy exceedance probability, independence-based multiplicative chance accounting, and one-policy-per-agent allocation rule. It does not merely make the outcome fractional; it makes the population anonymous and divisible. The advertising example is particularly strong because the authors already posit identical independent agents and evaluate the method at population sizes of 1,000.
The mirror covers only the ACCR auctioneer’s winner-determination result represented by Proposition 1. It does not cover the generation of Pareto-frontier bids from an implicitly represented MDP, the proposed VCG pricing scheme, strategic truthfulness, or the empirical superiority claims. If the bid menus are implicit, the next problem is a pricing problem over deterministic policies:
\[ \max_{\pi\in\Pi_t} \bigl(b_t(\pi)-\lambda k_t(\pi)-\eta r_t(\pi)\bigr), \]
where \(r_t(\pi)=-\log(1-\epsilon_t(\pi))\). That may be tractable by dynamic programming in some MDP families, but the paper does not establish it.
The weakest point is the chance-constraint scaling. With independent individual failures and fixed global \(\delta\), the product of survival probabilities becomes increasingly restrictive as \(N\) grows; a nondegenerate continuum limit may require \(\epsilon=O(1/N)\), a population-scaled risk parameter, or a model with common environmental shocks. Thus the mirror is strongest as a finite-\(N\), high-multiplicity relaxation of ACCR, rather than as an automatic fixed-\(\delta\) thermodynamic limit.
So the positive case is real but qualified: Proposition 1 supports a clean Class A continuous allocation problem, yet the paper lacks the formal named complexity result normally required by the ChoCo screening gate.
The proponent’s advertising example is the strongest possible rescue. The 1,000 identical customer MDPs really do support a high-multiplicity regime, so objections based on individual identity or implausible grouping would be wrong. But the sole anchor still fails.
Proposition 1 is not a computational-complexity result. It is an algebraic reformulation of the auctioneer’s already integral MINLP: because each named agent selects at most one bid, the product constraint can be logarithmised. It proves neither tractability nor hardness, and the paper gives no complexity theorem for winner determination, bid generation, or pricing. The proposed LP is therefore not a continuous version of a computational result in the paper; it is a new fractional relaxation obtained by replacing the paper’s binary variables.
More seriously, ACCR’s chance constraint has no scale-free population limit. Write \(r_{tq}=-\log(1-\epsilon_{tq})\). The proposed constraint is
\[ N\sum_{t,q}x_{tq}r_{tq}\le -\log(1-\delta). \]
With fixed \(\delta\) and any fixed positive-risk bid \(r_{tq}>0\), its assigned mass is \(O(1/N)\). Thus only \(O(1)\) individuals can receive positive-risk policies; asymptotically, almost all mass must use zero-risk or dummy bids. In the advertising domain, where useful stochastic policies naturally have positive exceedance probability, the chance-constrained part of the model disappears in the continuum. This is a genuine degeneration of the population object, not merely the fact that the resulting LP is easy.
The obvious repairs change ACCR. Making \(\epsilon\) scale as \(1/N\) makes the bid data population-dependent. Scaling \(\delta\) with \(N\) allows the global violation probability to approach one. Replacing the global chance constraint by expected or per-capita risk produces a different optimization problem. Introducing common shocks avoids the product collapse but abandons the paper’s independent-agent assumption.
There is also a fidelity problem. Constraint (10) is a conservative certificate based on the event that no agent exceeds its allocated amount; it is not generally the exact probability that total consumption exceeds \(L\). A faithful grouped model would need the full consumption distributions of policies and their aggregate convolution, not merely \((k,b,\epsilon)\). Retaining the bid triples gives the proponent’s LP, but that LP mirrors the paper’s surrogate certificate rather than its underlying chance-constrained allocation problem.
So the advertising population is legitimately high-multiplicity, and that point should be conceded. Nevertheless, the paper supplies no named complexity result to continuize, while its only plausible relaxation either degenerates under fixed global risk or requires a new scaling and stochastic model. A future study of population-scaled chance constraints could be worthwhile, but it would be a new ChoCo problem—not a worthwhile continuous mirror of this paper.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.