Conclusions and future work, and References

Table of Links

Abstract and 1. Introduction

2. The Soup Kitchen Problem

   2.1 Model and 2.2 Limits of Throughput and Availability

   2.3 Analysis of Throughput and Availability

3. Multi-Unit Posted-Price Mechanisms

   3.1 Model

   3.2 Results

4. Transaction fee mechanism design

5. Conclusions and future work, and References

A. Proofs for Section 2 (The Soup Kitchen Problem)

B. Proofs for Section 3 (Multi-Unit Posted-Price Mechanisms)

5 Conclusions and future work

For posted-price mechanisms, we are able to significantly improve upon the lower bounds on expected welfare provided by a conventional Chernoff bound. Our bounds on throughput in terms of availability also improve on the analytical tractability of those provided by Chawla, Devanur, and Lykouris (2023) without significantly sacrificing strength, and can be applied to settings with up-to-unit-demand agents.

We are able to show that the unavailability δ can be made much smaller than its usual value in prophet inequalities, with only a minor penalty to expected welfare. As can be seen from Figure 4

and Figure 6, several of our derived lower bounds on throughput τ are nearly flat as a function of δ near the peak of the welfare curve. A nearly flat curve suggests that prices intentionally selected to be higher than their welfare-optimal value can significantly decrease unavailability δ with only a minor impact on throughput τ , and thus only a minor impact on expected welfare. A mechanism designer has good reason to make δ as small as possible, and so may wish to take advantage of this favorable tradeoff.

The bounds we derive can almost certainly be made tighter, and this is an important area for future work. Chawla, Devanur, and Lykouris (2023) are able to demonstrate that Poisson-distributed demand produces the worst ratio of expected welfare achieved by a posted-price mechanism compared to a prophet in a unit-demand setting. In comparison, as can be seen from Figure 4, the throughput τ corresponding to a true Poisson distribution for any given availability α is above the strongest lower bounds on τ available from Theorem 3, via selecting an optimal ReLU function. The tradeoff curve for Poisson distributions would need to be identical to the strongest bound from Theorem 3 for the proof techniques demonstrated in this paper to extend the results of Chawla, Devanur, and Lykouris (2023) that Poisson demand is worst-case from the unit-demand setting to the up-to-unit-demand setting. Future work should seek to close the gap between the two tradeoff curves.

Another area for future work is to refine our availability-throughput bounds to better capture salient features of the demand distribution in Ethereum blocks. The concentration inequalities presented in this paper assume only that individual demands are independent and up-to-unit, and if stronger assumptions can be made on the individual demands’ distributions, stronger concentration inequalities could be developed. For example, in Ethereum it is known that the gas requested by many transactions falls below their maximum possible value. Our analysis used a conservative upper bound on the gas requested by any single transaction of 750, 000. However, a standard transfer between two Ethereum wallets requires 21, 000 units of gas, which is an order of magnitude smaller. Since the variability in the gas requested by each transaction is high, the “effective supply” of κ = 40 that we selected is an underestimate; most blocks typically accommodate over 100 transactions. A more refined analysis that takes into account these empirical facts could demonstrate an improved tradeoff between throughput and availability, by restricting attention to more realistic demand distributions rather than the worst-case demand distributions examined in this paper.

References

Hoeffding, Wassily (1956). “On the distribution of the number of successes in independent trials”. In: The Annals of Mathematical Statistics, pp. 713–721.

Suzuki, Yoshinori (2002). “An empirical analysis of the optimal overbooking policies for US major airlines”. In: Transportation Research Part E: Logistics and Transportation Review 38.2, pp. 135–149.

Goldberg, Andrew V and Jason D Hartline (2003). “Envy-free auctions for digital goods”. In: Proceedings of the 4th ACM conference on Electronic commerce, pp. 29–35.

Bertsimas, Dimitris and Sanne De Boer (2005). “Simulation-based booking limits for airline revenue management”. In: Operations Research 53.1, pp. 90–106.

Hajiaghayi, Mohammad Taghi, Robert Kleinberg, and Tuomas Sandholm (2007). “Automated online mechanism design and prophet inequalities”. In: AAAI. Vol. 7, pp. 58–65.

Lee, Gunho and Randy H Katz (2011). “Heterogeneity-Aware Resource Allocation and Scheduling in the Cloud”. In: 3rd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 11).

Buterin, Vitalik et al. (2014). “A next-generation smart contract and decentralized application platform”. In: white paper 3.37, pp. 2–1.

Boyd, E (2016). The future of pricing: How airline ticket pricing has inspired a revolution. Springer.

Lu, Qiumin et al. (2016). “Fairness-efficiency allocation of CPU-GPU heterogeneous resources”. In: IEEE Transactions on Services Computing 12.3, pp. 474–488.

Jeon, Myeongjae et al. (2018). “Multi-tenant GPU clusters for deep learning workloads: Analysis and implications”. In: Technical report, Microsoft Research.

Roig-Solvas, Biel and Mario Sznaier (2020). “Euclidean Distance Bounds for LMI Analytic Centers using a Novel Bound on the Lambert Function”. In: arXiv preprint arXiv:2004.01115.

Roughgarden, Tim (2020). “Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559”. In: arXiv preprint arXiv:2012.00854.

Ferreira, Matheus VX et al. (2021). “Dynamic posted-price mechanisms for the blockchain transactionfee market”. In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pp. 86–99.

Roughgarden, Tim (2021). “Transaction fee mechanism design”. In: ACM SIGecom Exchanges 19.1, pp. 52–55.

Liu, Yulin et al. (2022). “Empirical analysis of eip-1559: Transaction fees, waiting times, and consensus security”. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2099–2113.

Arnosti, Nick and Will Ma (2023). “Tight guarantees for static threshold policies in the prophet secretary problem”. In: Operations research 71.5, pp. 1777–1788.

Chawla, Shuchi, Nikhil Devanur, and Thodoris Lykouris (2023). “Static pricing for multi-unit prophet inequalities”. In: Operations Research.

Chung, Hao and Elaine Shi (2023). “Foundations of transaction fee mechanism design”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 3856–3899.

Jiang, Jiashuo, Will Ma, and Jiawei Zhang (2023). “Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities”. In: Proceedings of the 24th ACM Conference on Economics and Computation. EC ’23. , London, United Kingdom, Association for Computing Machinery, p. 909. isbn: 9798400701047. doi: 10.1145/3580507.3597734. url: https://doi.org/10.1145/3580507.3597734.

Chung, Hao, Tim Roughgarden, and Elaine Shi (2024). “Collusion-resilience in transaction fee mechanism design”. In: arXiv preprint arXiv:2402.09321.