Answer: Every deterministic causal allocation policy has an unbounded welfare competitive ratio, already for \(m=3\), \(\tau=1\), \(Q_{\max}=3\), and \(r_{\max}=1\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo allocation mechanism has a bounded competitive ratio.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(\Theta\) with rational arrival masses \(\mu_{\theta,t}\), where each type fixes its timing constraints, rate limit, maximum integral quantity, and valuation \(v_\theta(k)\), does there exist a causal allocation policy and a constant \(p>0\) such that \(p\,SW_{\mathrm{online}}\ge SW_{\mathrm{offline}}\) on every instance? The policy may split each type's mass among schedules, but each individual receives an integral number of units per period and past allocations cannot be revoked. At time \(t\), it observes the actual nondecreasing marginal procurement cost curve \(c_t(q)\); future curves are unknown but subject to the instance's stated forecasts and upper bounds. Procurement of mass \(q\) costs \(\int_0^q c_t(z)\,dz\), and the offline benchmark has the same feasibility constraints and knows all future arrivals and costs.
Time consists of \(m\) discrete periods. A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Masses need not sum to one. Each type \(\theta\) specifies arrival \(a_\theta\), confirmation deadline \(d_\theta\), receiving interval \([\alpha_\theta,\beta_\theta]\), positive integral rate \(r_\theta\le r_{\max}\), positive integral capacity \(Q_\theta\), and an explicitly tabulated nonnegative rational valuation \(v_\theta(k)\), nondecreasing with \(v_\theta(0)=0\). Require \(1\le a_\theta\le d_\theta\le\beta_\theta\le m\) and \(a_\theta\le\alpha_\theta\le\beta_\theta\). Its mass \(\mu_\theta=\mu_{\theta,a_\theta}>0\) arrives together.
An individual schedule \(s\) has integral deliveries \(s_t\), with \(0\le s_t\le r_\theta\), zero outside the receiving interval, and \(\sum_t s_t\le Q_\theta\). The policy may split a type's mass among schedules. Past deliveries are irrevocable, and each individual's final total must be irrevocably fixed by \(d_\theta\); future delivery times may still change. Procurement is unlimited and must be allocated immediately.
Initially the policy knows \(m\), \(r_{\max}\), and nonnegative rational piecewise constant forecast and upper-bound curves \(\widetilde c_t\le\overline c_t\). At period \(t\), it learns that period's arriving types and masses and the actual nonnegative, nondecreasing rational piecewise constant curve \(c_t\le\overline c_t\), before delivering. Forecasts impose no further accuracy or probabilistic promise. Future arrivals and actual curves remain unknown.
If final schedule masses are \(x_{\theta,s}\ge0\), with \(\sum_s x_{\theta,s}=\mu_\theta\), define \(q_t=\sum_{\theta,s}x_{\theta,s}s_t\) and \(SW=\sum_{\theta,s}x_{\theta,s}v_\theta(\sum_t s_t)-\sum_t\int_0^{q_t}c_t(z)\,dz\). The offline optimum knows all arrivals and costs and obeys the same feasibility and commitment constraints. Let \(L\) be the total binary input length; express running times in \(m,\tau,L,Q_{\max},r_{\max}\), where \(Q_{\max}=\max_\theta Q_\theta\).
Does there exist a deterministic causal allocation policy and a universal finite constant \(p>0\) such that \(p\,SW_{\mathrm{online}}\ge SW_{\mathrm{offline}}\) on every admissible instance, or is every such policy without a bounded competitive ratio?
For finite individual agents, no deterministic online allocation mechanism has a bounded welfare competitive ratio under uncertain future procurement costs ([Hayakawa et al., 2018](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p309.pdf)).
Related procurement allocation work analyzes competitive guarantees when the increasing procurement cost function is known in advance ([Ray et al., 2020](https://arxiv.org/abs/2012.12457)); no result settling the exact mass-and-uncertain-cost model above was identified.
Every deterministic causal allocation policy has an unbounded welfare competitive ratio.
This holds already with \(m=3\), \(\tau=1\), \(Q_{\max}=3\), and \(r_{\max}=1\), with arrival at the start of the receiving interval and confirmation deadline at its end. Both instances in the construction have strictly positive offline optimum.
Fix any deterministic causal policy \(A\) and any proposed finite constant \(p>0\). Choose an integer \(N\ge 1\) such that \(2^N>2p\), and set \(\varepsilon=2^{-N}\). Thus \(0<\varepsilon<1\) and \(2p\varepsilon<1\).
There is one supported type, of mass \(1\), with parameters
\(a_\theta=\alpha_\theta=1,\qquad d_\theta=\beta_\theta=3,\qquad r_\theta=1,\qquad Q_\theta=3.\)
Its explicitly tabulated valuation is
\(v_\theta(0)=0,\qquad v_\theta(1)=v_\theta(2)=\varepsilon,\qquad v_\theta(3)=2.\)
This valuation is nonnegative and nondecreasing. All required timing inequalities hold.
The initial forecasts are identically zero. The upper-bound curves are constant in procurement quantity:
\(\overline c_1(z)=0,\qquad \overline c_2(z)=1,\qquad \overline c_3(z)=3\quad\text{for every }z\ge 0.\)
Consider two actual-cost instances:
| Instance | \(c_1(z)\) | \(c_2(z)\) | \(c_3(z)\) |
|---|---:|---:|---:|
| \(I_H\) | \(0\) | \(1\) | \(3\) |
| \(I_L\) | \(0\) | \(1\) | \(0\) |
Every curve is nonnegative, rational, piecewise constant, nondecreasing in quantity, and bounded by its announced upper-bound curve.
The policy receives identical information through its period-two deliveries. Determinism and causality therefore imply that its period-two procurement is the same on both instances. Denote this quantity by \(x\). Because the total mass is \(1\) and each individual can receive at most one unit per period, \(0\le x\le 1\).
Consider any feasible final allocation on either instance. Write \(y=q_3\), and let \(h\) be the mass receiving a final total of three units.
An individual receiving three units must receive one unit in each period: there are exactly three periods, and its rate is one. Consequently,
\(h\le x\qquad\text{and}\qquad h\le y.\)
Every individual outside this mass has valuation at most \(\varepsilon\). Hence aggregate value is at most
\(2h+\varepsilon(1-h)=\varepsilon+(2-\varepsilon)h.\)
These inequalities apply to arbitrary fractional schedule masses.
On \(I_H\), procurement costs are \(x+3y\). Thus
\(SW_H\le\varepsilon+(2-\varepsilon)h-x-3y \le\varepsilon-x-(1+\varepsilon)y \le\varepsilon-x.\)
Here the second inequality uses \(h\le y\) and \(2-\varepsilon>0\).
On \(I_L\), procurement costs are \(x\). Using \(h\le x\) gives
\(SW_L\le\varepsilon+(2-\varepsilon)h-x \le\varepsilon+(1-\varepsilon)x.\)
The preceding bounds also apply to offline allocations.
On \(I_H\), welfare is at most \(\varepsilon\). Giving every individual the schedule \((1,0,0)\) achieves value \(\varepsilon\) at zero procurement cost. Therefore,
\(SW_{\mathrm{offline}}(I_H)=\varepsilon>0.\)
On \(I_L\), since \(x\le 1\) and \(1-\varepsilon>0\), welfare is at most
\(\varepsilon+(1-\varepsilon)x\le 1.\)
Giving every individual the schedule \((1,1,1)\) achieves value \(2\) and procurement cost \(1\). Therefore,
\(SW_{\mathrm{offline}}(I_L)=1.\)
Both schedules satisfy the delivery constraints. The offline policy can fix every individual's final total upon arrival, so the confirmation constraint is also satisfied.
Apply the bounds to the common period-two quantity \(x\) chosen by \(A\).
Thus at least one of the two admissible instances violates the proposed guarantee. The two complete instances are specified in advance; the argument only selects which one witnesses failure for the fixed deterministic policy.
Because \(A\) and \(p>0\) were arbitrary, no deterministic causal allocation policy admits a universal finite welfare competitive ratio.
The construction fixes \(m=3\), \(\tau=1\), \(Q_{\max}=3\), and \(r_{\max}=1\). Under ordinary binary rational encoding, its input length is \(L=\Theta(N)\), and either instance can be written in \(O(L)\) bit operations.
The impossibility holds without any restriction on the policy's running time.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated competitive-ratio question. It establishes impossibility for arbitrary mass splitting, with fixed values of \(m,\tau,Q_{\max},r_{\max}\). No major or minor issues were found.
The proof fixes an arbitrary deterministic causal policy \(A\) and an arbitrary finite \(p>0\), then constructs admissible instances on which the proposed guarantee fails. This is the required quantifier order.
An integer \(N\ge1\) with \(2^N>2p\) exists. Consequently, \(\varepsilon=2^{-N}\) is a positive binary rational, satisfies \(0<\varepsilon<1\), and obeys \(2p\varepsilon<1\). All subsequent uses of these inequalities are valid.
The single type has positive rational mass \(1\), integral rate \(1\), and integral capacity \(3\). Its parameters satisfy all required timing inequalities:
\(a_\theta=\alpha_\theta=1\) and \(d_\theta=\beta_\theta=m=3\).
The valuation table covers every possible total from \(0\) through \(Q_\theta=3\). It is nonnegative and nondecreasing because \(0<\varepsilon<1<2\).
All forecast, upper-bound, and actual curves are nonnegative rational constant functions, hence piecewise constant and nondecreasing in procurement quantity. The forecasts and actual curves satisfy their respective upper bounds. The decrease in actual cost between periods two and three on \(I_L\) is permitted: the task imposes monotonicity in procurement quantity, not across periods.
Both instances have identical initial information, arrivals, and revealed costs through period two. The difference in period-three cost remains unknown when period-two deliveries occur. Therefore, determinism and causality imply identical period-two procurement \(x\).
Immediate allocation and the rate constraint imply \(0\le x\le1\): procurement in that period equals deliveries, and the total supported mass is \(1\), with each individual receiving at most one unit.
The argument does not assume that period-three decisions agree between the instances.
For any feasible allocation, an individual with final total \(3\) must receive one unit in each of the three periods. Thus the mass \(h\) of such individuals satisfies both \(h\le x\) and \(h\le y\), where \(y=q_3\).
Every other individual has final total \(0\), \(1\), or \(2\), and therefore valuation at most \(\varepsilon\). The aggregate-value bound
\(2h+\varepsilon(1-h)=\varepsilon+(2-\varepsilon)h\)
is valid for arbitrary fractional schedule masses.
On \(I_H\), constant marginal costs give total procurement cost \(x+3y\). Since \(2-\varepsilon>0\) and \(h\le y\), the displayed bound correctly reduces to
\(SW_H\le\varepsilon-x-(1+\varepsilon)y\le\varepsilon-x\).
On \(I_L\), total procurement cost is \(x\). Using \(h\le x\) correctly gives
\(SW_L\le\varepsilon+(1-\varepsilon)x\).
The welfare bounds apply to offline allocations as well. On \(I_H\), nonnegativity of \(x\) gives an upper bound of \(\varepsilon\), attained by assigning schedule \((1,0,0)\) to the entire mass.
On \(I_L\), \(x\le1\) and \(1-\varepsilon>0\) give an upper bound of \(1\), attained by assigning schedule \((1,1,1)\) to the entire mass.
Both schedules satisfy the rate, capacity, and receiving-interval constraints. Fixing their final totals upon arrival satisfies the confirmation deadline. Both offline optima are strictly positive.
The cases \(x\ge\varepsilon\) and \(x<\varepsilon\) exhaust all possibilities.
In the first case, online welfare on \(I_H\) is at most zero, so multiplication by any \(p>0\) cannot reach the positive offline optimum.
In the second case, the stated bound on \(I_L\) gives \(SW_A(I_L)<2\varepsilon\), hence \(p\,SW_A(I_L)<1\), strictly below its offline optimum.
Selecting a witness from two predetermined instances is valid for disproving a guarantee required to hold on every instance. No adaptive modification of either instance is needed.
Under ordinary binary rational encoding, the denominator \(2^N\) requires order \(N\) bits; all other data have constant size. Thus \(L=\Theta(N)\), and the claimed \(O(L)\) construction time is justified.
The argument uses no external theorem and imposes no computational restriction on the policy. It proves competitive impossibility, but does not classify the computational complexity of optimization in the continuous model. Accordingly, the requested computational-status field is marked unresolved.
No repair or additional clarification is required.
⟨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.