Online Resource Sharing: Better Robust Guarantees via Randomized Strategies

The strongest positive case is a high-multiplicity mirror of the paper’s robust bidding problem. One qualification is important: the paper contains no named theorem claiming \( \mathrm{P} \), NP-hardness, FPT, or W[1]-hardness. Its named results are quantitative policy-construction and impossibility theorems. Thus this is a computational policy-synthesis mirror, not a complexity-class result already present in the paper.

The natural regime is a large cloud or computing-cluster population. There are \(N\) users, but only finitely many service classes: for example, batch jobs, interactive jobs, research labs, or priority tiers. A type is the complete policy-relevant description
\[ \theta=(a_\theta,F_\theta), \]
where \(F_\theta\) is the user’s value distribution and \(a_\theta\) is its fair-share density. A society is
\[ \mathcal S=(\Theta,\mu,(a_\theta,F_\theta)_{\theta\in\Theta}), \]
where \( \mu_\theta \) is the fraction of users of type \( \theta \), \( |\Theta| \ll N \), and
\[ \sum_{\theta\in\Theta}\mu_\theta a_\theta=1. \]

The \(N\)-agent realization has \(N\mu_\theta\) agents of type \( \theta \), each with fair share \( \alpha_{\theta,N}=a_\theta/N \). Agents of the same type have the same fair share and value law, but independent realized values and different histories. This is exactly the high-multiplicity interpretation: named users are exchangeable whenever the problem uses them in the same way.

The resource remains indivisible: one item is allocated in each round by the same first-price artificial-currency auction. The continuum is in the population description \( \mu \), not in the resource or outcome space. A type-level policy is a randomized kernel mapping an agent’s current value, remaining budget, and private history to a bid. The objective is to maximize the worst-case normalized utility guarantee over type classes, where the denominator is the same ideal utility benchmark used in the paper.

My lead anchor is Theorem 1, proved by the authors, with detailed proof deferred to the full version. It states that Randomized Robust Bidding with \( \bar b=1+\sqrt 2 \) is
\[ \left(2-\sqrt 2-O\!\left(\sqrt{\frac{\log T}{T}}\right)\right) \]
-robust for every value distribution.

The corresponding continuous problem is Continuum Robust Policy Synthesis.

An instance consists of \( \mathcal S \), a rational target \( \beta \), and a finite-support rational representation of every \(F_\theta\). For each \(N\), form the \(N\)-agent realization above. Let \(v^*_{\theta,N}\) be the paper’s ideal utility for a type-\(\theta\) agent with fair share \(a_\theta/N\). The question is whether there is a polynomial-size type-policy compiler \( \Pi \) such that, for every type with \( \mu_\theta>0 \),
\[ \liminf_{\substack{N,T\to\infty\T/N\to\infty}} \inf_{\text{arbitrary behaviour of all other agents}} \frac{\mathbb E[\sum_{t=1}^T V_i[t]W_i[t]]} {T v^*_{\theta,N}} \ge \beta . \]

A solution is the policy compiler together with a proof of the displayed guarantee. The \(T/N\to\infty\) condition is natural: each individual’s fair share is \(O(1/N)\), so the horizon must provide many expected opportunities per user.

Theorem 1 supplies a direct solution for every
\[ \beta<2-\sqrt 2 \]
in the limit. For each type, compute its ideal-utility cutoff, bid only on the corresponding top quantile, and sample the bid uniformly from
\[ [0,1+\sqrt 2] \]
while budget permits. Since Theorem 1 is robust against arbitrary behaviour by the other agents, these type policies can be installed simultaneously across the whole society. This is a genuine Class-A-style result: a continuous population instance receives an explicit, efficiently describable policy and a quantitative certificate.

The natural unresolved optimization problem is to compute the optimal common guarantee
\[ \beta^*(\mathcal S)=\sup_{\Pi}\min_{\theta:\mu_\theta>0}R_\theta^\infty(\Pi;\mathcal S). \]
The paper gives a nontrivial lower bound, but not the exact optimum. That is precisely the sort of computational question the mirror should generate.

Theorem 2, also proved by the authors rather than cited, gives a second anchor. It states that if a Bernoulli-\((\alpha)\) agent uses a fixed bidding distribution \(D\) whenever her value is \(1\), then the strategy cannot be \( \beta \)-robust for \( \beta>3/5 \) as \( \alpha\to0 \).

The matching continuous problem is Fixed-Type Bid-Distribution Optimization. Take a society sequence with \(N\) equal-share agents, so \( \alpha=1/N\), and let the focal type have Bernoulli values with mean \(1/N\). The focal agent must choose one distribution \(D\) on a fixed bounded bid interval and use independent bids from \(D\) whenever her value is \(1\). The question is to compute
\[ \beta_{\mathrm{fix}}^* = \sup_D\; \liminf_{\substack{N,T\to\infty\T/N\to\infty}} \inf_{\text{other-agent strategies}} \frac{\mathbb E[\sum_t U_i[t]]}{\alpha T}, \]
and to output an optimal or approximately optimal \(D\), together with an adversarial certificate.

Theorem 2 gives
\[ \beta_{\mathrm{fix}}^*\le \frac35 \]
in the high-multiplicity limit. Theorem 1 gives the lower bound
\[ \beta_{\mathrm{fix}}^*\ge 2-\sqrt2 \]
through the uniform distribution. The paper’s Lemma 2 supplies the key continuous constraint:
\[ F(x^-)\le \frac{1-\beta}{1-\alpha x}. \]
Thus the problem becomes an optimization over probability measures or CDFs, with a small number of linear moment and pointwise constraints. I would expect the stationary fixed-distribution version to be Class A: a measure LP or equivalent convex program should characterize the optimum, plausibly closing the gap between \(2-\sqrt2\) and \(3/5\).

Theorem 3 is a third, independent anchor. It is proved by the authors and gives an explicit stationary adversarial policy. It states that there exists a stationary bidding policy under which an agent with fair share \( \alpha \) and Bernoulli-\((\alpha)\) values receives at most
\[ 1-\frac1e+\frac{\alpha}{e} +O\!\left(\sqrt{\frac{\log T}{T}}\right) \]
of ideal utility. The earlier \(1-1/e\) impossibility was cited from Fikioris, Banerjee, and Tardos; Theorem 3 is the paper’s constructive version.

The associated problem is Stationary Adversary Synthesis. Given a focal type with fair share \( \alpha \), determine
\[ \inf_{\nu:\,\int b\,d\nu(b)\le 1-\alpha} \; \sup_{\pi} \limsup_{T\to\infty} \frac{\mathbb E_{\nu,\pi}[\sum_t U_i[t]]}{\alpha T}, \]
where \( \nu \) is a stationary distribution from which the aggregate opposing bidder samples its bid, and \( \pi \) ranges over all history-dependent focal policies obeying the budget constraint. A solution is a stationary bid distribution \( \nu \) and a proof that every focal policy is bounded by the claimed ratio.

Theorem 3 provides the explicit candidate
\[ G_\alpha(b)= \begin{cases} 0, & b<0,\[2mm] \dfrac{1-\alpha}{e-(e-2)b}+\alpha, & 0\le b\le \dfrac{e-1}{e-2},\[3mm] 1, & b>\dfrac{e-1}{e-2}. \end{cases} \]
In the high-multiplicity limit \( \alpha\to0 \), this yields the \(1-1/e\) upper bound. This again looks like Class A on the stationary side: the adversary’s problem is an infinite-dimensional linear optimization problem over bid distributions with a budget moment constraint, and the theorem already exhibits a closed-form feasible certificate. Whether the full history-dependent minimax problem has an equally simple exact solution is a worthwhile further question.

These mirrors cover only the paper’s robust strategy results: Theorems 1–3 and, as supporting structure, Lemma 1’s reduction from arbitrary value distributions to Bernoulli values. They do not attempt to mirror the empirical comparison in Section 5, the equilibrium interpretation, or the broader mechanism-design literature.

The plausibility case is unusually good because the paper already identifies value distributions, fair shares, budgets, and bidding policies as the complete relevant description of an agent. A large population of users sharing a small number of entitlement and workload classes is therefore not an artificial simplification. The paper’s cloud-computing motivation supplies a credible setting, and high multiplicity turns its list of named agents into the type distribution \( \mu \). The randomized bids remain an action variable inherited from the original problem; they are not being used to pretend that outcome-space continuity is the contribution.

The weakest point is that robustness against arbitrary other agents causes much of the population composition to disappear from the focal-agent analysis: all other agents can be collapsed into one adversary. Consequently, Theorem 1 may look like a theorem that already applies unchanged, with \( \mu \) added only as bookkeeping. The literal continuum of bidders would also be ill-defined because maxima of infinitely many bids are problematic; the mirror must therefore be understood through finite high-multiplicity approximants with \(T/N\to\infty\), not as an unqualified uncountable-agent auction.

That weakness is real, but it does not eliminate the mirror. The continuous problem still asks for a compact type-indexed policy library, finite-\(N\) approximation guarantees, and exact optimization over bid-distribution or occupation-measure variables. The paper’s own results provide unusually strong anchors: an explicit positive policy at \(2-\sqrt2\), a fixed-policy barrier at \(3/5\), and a constructive adversarial barrier at \(1-1/e\).