Document Open Access Logo

Optimal Deterministic Clock Auctions and Beyond

Authors Giorgos Christodoulou, Vasilis Gkatzelis, Daniel Schoepflin

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.49.pdf
  • Filesize: 0.77 MB
  • 23 pages

Document Identifiers

Author Details

Giorgos Christodoulou
  • University of Liverpool, UK
Vasilis Gkatzelis
  • Drexel University, Philadelphia, PA, USA
Daniel Schoepflin
  • Drexel University, Philadelphia, PA, USA

Funding

  • Gkatzelis, Vasilis: Supported by NSF grants CCF-2008280 and CCF-1755955.
  • Schoepflin, Daniel: Supported by NSF grants CCF-2008280 and CCF-1755955.

Acknowledgements

The authors are grateful to Ron Lavi for his significant contributions on this project. We believe that he should be listed as one of the co-authors of this paper, but we agreed to respect his modesty and his wish to receive no credit for these contributions. We would also like to thank Jason Hartline for his helpful observations that initiated this work.

Cite AsGet BibTex

Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin. Optimal Deterministic Clock Auctions and Beyond. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 49:1-49:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.49

Abstract

We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational pricing and auctions
Keywords
  • Auctions
  • Obvious Strategyproofness
  • Mechanism Design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mohammad Akbarpour and Shengwu Li. Credible auctions: A trilemma. Econometrica, 88(2):425-467, 2020. Google Scholar
  2. Saeed Alaei, Azarakhsh Malekian, and Aravind Srinivasan. On random sampling auctions for digital goods. In Proceedings of the 10th ACM conference on Electronic commerce, pages 187-196, 2009. Google Scholar
  3. Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. On budget-feasible mechanism design for symmetric submodular objectives. In International Conference on Web and Internet Economics, pages 1-15. Springer, 2017. Google Scholar
  4. Georgios Amanatidis, Pieter Kleer, and Guido Schäfer. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 901-919, 2019. Google Scholar
  5. Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 653-661. SIAM, 2021. Google Scholar
  6. Sepehr Assadi and Sahil Singla. Improved truthful mechanisms for combinatorial auctions with submodular bidders. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 233-248. IEEE, 2019. Google Scholar
  7. Moshe Babaioff and Liad Blumrosen. Computationally-feasible truthful auctions for convex bundles. Games and Economic Behavior (GEB), 63:588-620, July 2008. Google Scholar
  8. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 434-443, 2007. Google Scholar
  9. Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 21-30. IEEE, 2014. Google Scholar
  10. Moshe Babaioff, Ron Lavi, and Elan Pavlov. Single-value combinatorial auctions and algorithmic implementation in undominated strategies. Journal of the ACM (JACM), 56(1):4, 2009. Google Scholar
  11. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. Learning on a budget: posted price mechanisms for online procurement. In Proceedings of the 13th ACM conference on electronic commerce, pages 128-145, 2012. Google Scholar
  12. Maria-Florina Balcan, Avrim Blum, Jason D Hartline, and Yishay Mansour. Reducing mechanism design to algorithm design via machine learning. Journal of Computer and System Sciences, 74(8):1245-1270, 2008. Google Scholar
  13. Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Tan Xizhi. Deterministic budget-feasible clock auctions. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), (to appear). Google Scholar
  14. Xiaohui Bei, Ning Chen, Nick Gravin, and Pinyan Lu. Worst-case mechanism design via bayesian analysis. SIAM Journal on Computing, 46(4):1428-1448, 2017. Google Scholar
  15. Martin Bichler, Zhen Hao, Richard Littmann, and Stefan Waldherr. Strategyproof auction mechanisms for network procurement. OR Spectrum, 42(4):965-994, 2020. Google Scholar
  16. Liad Blumrosen and Osnat Zohar. Multilateral deferred-acceptance mechanisms. In International Conference on Web and Internet Economics, pages 173-186. Springer, 2015. Google Scholar
  17. Felix Brandt and Tuomas Sandholm. Unconditional privacy in social choice. In Ron van der Meyden, editor, Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), Singapore, June 10-12, 2005, pages 207-218. National University of Singapore, 2005. Google Scholar
  18. Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311-320, 2010. Google Scholar
  19. George Christodoulou, Khaled M. Elbassioni, and Mahmoud Fouz. Truthful mechanisms for exhibitions. In Amin Saberi, editor, Internet and Network Economics - 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings, volume 6484 of Lecture Notes in Computer Science, pages 170-181. Springer, 2010. Google Scholar
  20. Edward H Clarke. Multipart pricing of public goods. Public choice, 11(1):17-33, 1971. Google Scholar
  21. Bart De Keijzer, Maria Kyropoulou, and Carmine Ventre. Obviously strategyproof single-minded combinatorial auctions. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, page 71, 2020. Google Scholar
  22. Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 89-103. Springer, 2007. Google Scholar
  23. Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. Journal of Computer and System Sciences, 78(1):15-25, 2012. Google Scholar
  24. Paul Dütting, Vasilis Gkatzelis, and Tim Roughgarden. The performance of deferred-acceptance auctions. Math. Oper. Res., 42(4):897-914, 2017. Google Scholar
  25. Paul Dütting, Inbal Talgam-Cohen, and Tim Roughgarden. Modularity and greed in double auctions. Games and Economic Behavior, 105:59-83, 2017. Google Scholar
  26. Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna R Karlin. Combinatorial auctions with interdependent valuations: Sos to the rescue. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 19-20, 2019. Google Scholar
  27. Ludwig Ensthaler and Thomas Giebe. A dynamic auction for multi-object procurement under a hard budget constraint. Research Policy, 43(1):179-189, 2014. Google Scholar
  28. Thomas Erlebach and Frits C. R. Spieksma. Simple algorithms for a weighted interval selection problem. In D. T. Lee and Shang-Hua Teng, editors, Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings, volume 1969 of Lecture Notes in Computer Science, pages 228-240. Springer, 2000. Google Scholar
  29. Uriel Feige, Abraham Flaxman, Jason D Hartline, and Robert Kleinberg. On the competitive ratio of the random sampling auction. In International Workshop on Internet and Network Economics, pages 878-886. Springer, 2005. Google Scholar
  30. Diodato Ferraioli, Paolo Penna, and Carmine Ventre. Two-way greedy: Algorithms for imperfect rationality. The 17th Conference on Web and Internet Economics (WINE 2021), (to appear). Google Scholar
  31. Vasilis Gkatzelis, Evangelos Markakis, and Tim Roughgarden. Deferred-acceptance auctions for multiple levels of service. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 21-38, 2017. Google Scholar
  32. Vasilis Gkatzelis, Rishi Patel, Emmanouil Pountourakis, and Daniel Schoepflin. Prior-free clock auctions for bidders with interdependent values. In Ioannis Caragiannis and Kristoffer Arnsfelt Hansen, editors, Algorithmic Game Theory, pages 64-78, Cham, 2021. Springer International Publishing. Google Scholar
  33. Andrew V Goldberg, Jason D Hartline, Anna R Karlin, Michael Saks, and Andrew Wright. Competitive auctions. Games and Economic Behavior, 55(2):242-269, 2006. Google Scholar
  34. Theodore Groves et al. Incentives in teams. Econometrica, 41(4):617-631, 1973. Google Scholar
  35. Jason D Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225-234. ACM, 2009. Google Scholar
  36. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pages 409-426. Springer, 1994. Google Scholar
  37. Felix Jarman and Vincent Meisner. Ex-post optimal knapsack procurement. Journal of Economic Theory, 171:35-63, 2017. Google Scholar
  38. John H Kagel, Ronald M Harstad, and Dan Levin. Information impact and allocation rules in auctions with affiliated private values: A laboratory study. Econometrica: Journal of the Econometric Society, pages 1275-1304, 1987. Google Scholar
  39. Anthony Kim. Welfare maximization with deferred acceptance auctions in reallocation problems. In Algorithms-ESA 2015, pages 804-815. Springer, 2015. Google Scholar
  40. Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, and Qiang Zhang. Budget feasible mechanisms on matroids. In International Conference on Integer Programming and Combinatorial Optimization, pages 368-379. Springer, 2017. Google Scholar
  41. Shengwu Li. Obviously strategy-proof mechanisms. American Economic Review, 2017. Google Scholar
  42. Simon Loertscher and Leslie M Marx. Asymptotically optimal prior-free clock auctions. Journal of Economic Theory, page 105030, 2020. Google Scholar
  43. Paul Milgrom and Ilya Segal. Deferred-acceptance auctions and radio spectrum reallocation. In Moshe Babaioff, Vincent Conitzer, and David A. Easley, editors, ACM Conference on Economics and Computation, EC '14, Stanford , CA, USA, June 8-12, 2014, pages 185-186. ACM, 2014. Google Scholar
  44. Paul Milgrom and Ilya Segal. Clock auctions and radio spectrum reallocation. Journal of Political Economy, 2019. Google Scholar
  45. Aviad Rubinstein. Beyond matroids: secretary problem and prophet inequality with general constraints. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 324-332. ACM, 2016. Google Scholar
  46. Aviad Rubinstein. On the computational complexity of optimal simple mechanisms. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 21-28. ACM, 2016. Google Scholar
  47. William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact