Publications

Fundamental Limits of Throughput and Availability: Applications to prophet inequalities and transaction fee mechanism design

EC '24: Proceedings of the 25th ACM Conference on Economics and Computation

Publication date: July 8, 2024

Aadityan Ganesh, Jason D. Hartline, Atanu R Sinha, Matthew vonAllmen

This paper studies the fundamental limits of availability and throughput for independent and heterogeneous demands of a limited resource. Availability is the probability that the demands are below the capacity of the resource. Throughput is the expected fraction of the resource that is utilized by the demands. We offer a concentration inequality generator that gives lower bounds on feasible availability and throughput pairs with a given capacity and independent but not necessarily identical distributions of up-to-unit demands. We show that availability and throughput cannot both be poor. These bounds are analogous to tail inequalities on sums of independent random variables, but hold throughout the support of the demand distribution. This analysis gives analytically tractable bounds supporting the unit-demand characterization of Chawla et al. [2023] and generalizes to up-to-unit demands. Our bounds also provide an approach towards improved multi-unit prophet inequalities [Hajiaghayi et al., 2007]. They have applications to transaction fee mechanism design (for blockchains) where high availability limits the probability of profitable user-miner coalitions [Chung and Shi, 2023].

Learn More