Do Synthetic Workloads Hide Greedy Resource Exhaustion?

Greedy allocation takes, at every step, whatever looks best right now. Examples are giving the arriving worker the easiest open task, or placing the user on the server with the most free room. In capacity-limited systems this habit can use up the scarce, flexible resources that later, harder requests needed. Theory says this "greedy exhaustion" can be disastrous. Yet many published comparisons of greedy against smarter allocators are run on synthetic workloads: random graphs, Zipf-distributed requests, simulated donor pools, generated energy offers. Those generators tend to smooth away the bursts, clusters and correlated arrivals that set exhaustion off. This note asks whether the measured cost of greediness is a property of the algorithm or largely an artifact of the generator. It also asks how to tell, from a small amount of real data, whether a generator can be trusted for this specific judgment.

The proposal treats synthetic-data evaluation as the method and greedy exhaustion as the quantity being evaluated. The central idea is to judge a workload generator by one test: does it reproduce the gap between greedy and non-greedy allocators that a real trace shows? Statistical likeness to the trace is not the test. We conjecture that this gap is governed by a narrow, greedy-specific summary of the workload, which we call post-depletion demand: how much demand that only a scarce resource can serve arrives after greedy would already have used that resource up. Ordinary fidelity measures miss this summary.

Core Claim

Define the exhaustion gap of a workload $W$ as $G(W) = (V_{\text{ref}}(W) - V_{\text{greedy}}(W)) / V_{\text{ref}}(W)$, where $V_{\text{greedy}}$ is the value greedy achieves and $V_{\text{ref}}$ is the value of a reference allocator. The reference is the offline optimum where it is computable, and otherwise the best available non-greedy online policy. A generator $S$ fitted to a real trace $R$ is decision-faithful if $G(S) \approx G(R)$ and if it ranks candidate allocators in the same order as $R$ does.

We make three claims. First, common generators, including Erdős–Rényi graphs, Zipf request popularity and independent identically distributed arrivals, systematically understate $G$ relative to real traces of the same marginal statistics. Second, a generator's error in $G$ is predicted far better by its error in post-depletion demand than by standard fidelity scores such as likelihood or distance between marginals. Post-depletion demand is computed by replaying greedy on the trace and recording, for each resource type, the mass of compatible-only-with-that-type requests arriving after the type is exhausted. Third, re-calibrating a generator to match post-depletion demand, estimated from a small real sample, restores decision faithfulness. This includes the transfer of tuned anti-exhaustion parameters such as reserve prices and attenuation rates.

The motivating tension is explicit in the file. Worst-case analysis shows greedy is zero-competitive for online capacitated coverage, because it spends capacity on common skills before rare ones arrive (Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations). Average-case analysis on random graphs and grids finds greedy reaching 79% to 100% of optimal welfare, because the trap configurations become vanishingly rare (Average-Case Analysis of Greedy Matching for D2D Resource Sharing). Both results are correct. Neither tells a practitioner which regime a real workload sits in. That depends exactly on the generator assumptions the average-case analysis makes and real data may violate.

Relation to Prior Work

The closest work evaluates greedy against non-greedy allocators on synthetic data but never audits the generator. Weighted Myopia learns blood-type potentials that penalize consuming flexible kidney-exchange pairs (Dynamic Matching via Weighted Myopia with Application to Kidney Exchange). It tunes and tests entirely on the Saidman generator and reports closing about 18% of the gap between myopic matching and perfect foresight. Service placement with slot allocation beats greedy on Zipf ($\kappa = 1.3$) request workloads (Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems). Edge user allocation shows greedy hiring up to 87% of servers versus 32% for goal programming, on a static synthesized user map (QoE-aware user allocation in edge computing systems with dynamic QoS). Each of these papers motivates our question: the size of its headline gap is a function of a generator nobody validated. Our work does not propose a new allocator. It measures how much of these gaps survives contact with real arrival structure.

Two papers supply the method. The approval-election study fits mixture models to real Pabulib elections (Learning Real-Life Approval Elections). It shows that single-component generators produce "average" voters who represent nobody, and that likelihood correlates with distance to real data at Pearson 0.993. We adopt its practice of fitting generator families of increasing richness, and we use likelihood as the fidelity score we expect to fail at predicting decision outcomes. The simulation "Turing test" for knowledge tracing judges a model by whether data simulated from it is distinguishable from real data in a task-relevant topography (Is this Model for Real? Simulating Data to Reveal the Proximity of a Model to Reality). Our decision-faithfulness test is that idea, with the exhaustion gap replacing likelihood topography.

The equivalency and substitutability study for multi-person tracking supplies the vocabulary of exchange rates: about 30 synthetic frames per real frame, and 60–80% of real data replaceable (On the Equivalency, Substitutability, and Flexibility of Synthetic Data). It also shows that behavioral complexity, rather than realism, carries the value, with multi-group scenes raising DanceTrack HOTA from 68.8 to 73.5. We borrow the substitution protocol. Our claim is a decision-level analogue: what matters is the arrival structure that causes exhaustion, not surface fidelity. Two further papers constrain the design. The concept-drift survey warns that stationary synthetic benchmarks miss drift (One or two things we know about concept drift - a survey on monitoring in evolving environments. Part A: detecting concept drift). The randomized-trial evaluation work shows that budget constraints make naive estimates of allocation policies very noisy (Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation). That paper reports up to 7x variance reduction from assignment permutation. Our estimates of $G$ on a few real traces will therefore need careful uncertainty quantification.

Research Program

We need testbeds where a real trace and a fitted synthetic counterpart can both be replayed under several allocators. The file supports five such testbeds.

The first is the Mechanical Turk ellipse dataset of 612 workers who completed all eight task variants (Online Task Assignment in Crowdsourcing Markets). Because every worker's skill on every task is observed, any online assignment policy can be replayed exactly on the real arrival order. Synthetic counterparts are generated by fitting skill distributions and resampling. This is the cleanest testbed and the primary one.

The second is the Device-to-Device setting (Average-Case Analysis of Greedy Matching for D2D Resource Sharing). Here real user coordinates from a university building sit alongside $G(n,p)$ and grid generators. This lets us test directly whether the 79–100% average-case efficiency holds on the empirical layout.

The third is cloud virtual-machine placement, using the reproducible simulator and the real and synthetic CPU traces it serves (Reproducible experiments on dynamic resource allocation in cloud data centers). That paper already found that the demand model matters more than the placement heuristic, which is a prior hint that generator choice can dominate conclusions.

The fourth is the EUA dataset, a real base-station map with user locations mapped from network addresses (QoE-aware user allocation in edge computing systems with dynamic QoS). We contrast its address-derived user positions with uniform and clustered synthetic placements.

The fifth is the Geekplus warehouse data. Its synthesized Syn-A/Syn-B layouts sit alongside the Real-Large industrial trace (Adaptive Task Planning for Large-Scale Robotized Warehouses). We include it only if the data are obtainable from the authors.

For each testbed we build a ladder of generators. The rungs, in order, are: independent marginals; correlated marginals; mixtures in the style of the approval-election work; block bootstrap of the real trace, which keeps contiguous chunks of arrivals in their original order; and finally a calibrated generator. The calibrated generator perturbs arrival order and type mix so that its post-depletion demand matches the value estimated from a small real sample.

For every generator we compute four things. The first is its fidelity score, meaning likelihood and marginal distances. The second is its post-depletion demand error. The third is its error in $G$ for several reference allocators: the dual task assigner, Weighted-Myopia-style potentials, the boosting-and-attenuation policy, and an offline optimum where tractable. The fourth is the real-trace value achieved when an anti-exhaustion policy's parameters are tuned on the synthetic data. The analysis then regresses the error in $G$ across generators and testbeds on the fidelity score and on the post-depletion demand error. Finally, we measure an exchange rate: how many real arrivals are needed to calibrate post-depletion demand well enough to reach decision faithfulness.

Baselines

The naive reference point is to report $G$ on the default generator each source paper used: Erdős–Rényi for the Device-to-Device setting, Zipf for placement, independent identically distributed worker arrivals for crowdsourcing. This is what the field currently does. Our first claim is falsified if this default already lands within the confidence interval of real $G$ on most testbeds.

The strongest competing predictor of decision faithfulness is likelihood-based generator fitting, as in Learning Real-Life Approval Elections. That work reports a Pearson correlation of 0.993 between a model's log-likelihood and its distance from real data. It is the strongest competitor because it is principled, cheap, and already validated as a realism proxy. We give it the same real data, the same generator families and the same fitting budget as our calibration. It is beaten if post-depletion demand error explains substantially more variance in the error of $G$, as judged by held-out testbed cross-validation, and if likelihood-ranked generators misorder allocators on at least one testbed where the calibrated generator does not.

The strongest real-data baseline is block bootstrap of the real trace, which keeps local temporal correlation without any model. For the allocators themselves, the strongest reported results are the edge-allocation server usage of 32% versus 87% for greedy and the warehouse planner's 37.1% makespan reduction. For crowdsourcing, the file reports no numerical value: no reported result found on Lacuna for the dual task assigner's improvement over greedy on the ellipse data, so we will re-measure it.

The ablation that isolates the key ingredient keeps the calibrated generator's marginals and type mix but shuffles arrival order. If this ablation recovers $G$ just as well, the claim about timing relative to depletion is wrong and the effect is purely compositional.

Why not just…?

Why not just evaluate on real traces and skip generators? Real traces exist in our testbeds, which is precisely what makes this study possible. Practitioners, however, usually have one trace or none. They also need synthetic data to explore regimes and to tune anti-exhaustion parameters, as Weighted Myopia does with 1,500 generated graphs. A single real trace gives one noisy estimate of $G$, and Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation shows such estimates are high-variance under budgets. The question is which generators can stand in for the real trace, not whether to use real data.

Why not just use a better general-purpose fidelity score? This is the real threat. If likelihood, or a richer two-sample test, predicts the error in $G$ as well as post-depletion demand does, the greedy-specific summary is unnecessary. The regression in our program settles it directly, and we commit to reporting the result whichever way it falls. Our prior that fidelity scores will lose rests on a concrete mechanism. Exhaustion depends on the order of arrivals relative to depletion, and a generator can match marginals and pairwise correlations while reordering exactly the rare late requests that matter.

Why not just bootstrap the real trace? Block bootstrap is a strong, model-free generator, and on long stationary traces it may be decision-faithful by construction. It cannot extrapolate to new pool sizes, to new capacity levels, or to the drifted regimes that the concept-drift survey warns about. It also needs a long real trace. We include it as a baseline and measure its exchange rate. If it matches calibrated generators at equal real-data budgets, we will recommend it and narrow our claim to the extrapolation setting.

Why not just stress-test with adversarial arrival orders? Worst-case orderings show that greedy can fail. Combined with the 79–100% average-case results, they show the answer depends on the workload, which is the gap we target. Adversarial testing overstates $G$ just as benign generators understate it, so it cannot rank allocators for a particular deployment.

Decisive Checks

The study stands or falls on four results. The first is whether default generators understate real $G$ on the Mechanical Turk replay and the Device-to-Device layout by more than bootstrap confidence intervals. The second is whether post-depletion demand error out-predicts likelihood error for the error in $G$ under leave-one-testbed-out evaluation. The third is whether dual-task-assigner reserve prices, or attenuation thresholds, tuned on the calibrated generator recover more real-trace value than the same parameters tuned on the likelihood-best generator. The fourth is whether the order-shuffling ablation destroys that advantage. The last check is the exchange rate: how many real arrivals are needed to calibrate post-depletion demand to within the noise of $G$. A positive outcome would give the allocation literature an inexpensive audit of any synthetic benchmark before trusting its greedy-versus-smart headline.