No Access

Maximize Liquid Welfare in Combinatorial Auctions with Monotone Valuations

Jiwen Chen

School of Mathematical Science, Ocean University of China, Qingdao 266100, Shandong Province, P. R. China

E-mail Address: cjiwen16@163.com

Search for more papers by this author

Qingqin Nong

School of Mathematical Science, Ocean University of China, Qingdao 266100, Shandong Province, P. R. China

E-mail Address: qqnong@ouc.edu.cn

Corresponding author.

Search for more papers by this author

Yuanyuan Wang

School of Mathematical Science, Ocean University of China, Qingdao 266100, Shandong Province, P. R. China

E-mail Address: wyy8088@stu.ouc.edu.cn

Search for more papers by this author

, and

Wenjing Liu

School of Mathematical Science, Ocean University of China, Qingdao 266100, Shandong Province, P. R. China

E-mail Address: liuwj@ouc.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0217595923400109Cited by:0 (Source: Crossref)

This article is part of the issue:

Special Issue: Machine Learning and Optimization II (Part 1)
Guest Editors: Yong Chen, Dingzhu Du and Chenchen Wu

Abstract

In this paper, we consider how to maximize the liquid welfare in a combinatorial auction where bidders have monotone valuations and are budget constrained. We study the setting that budgets are public information and present a universally truthful, budget feasible and computationally-efficient randomized $O (\sqrt{m n})$ $O (\sqrt{m n})$ -approximate mechanism, where $m$ $m$ is the number of items and $n$ $n$ is the number of bidders, respectively.

Keywords:

References

Assadi, S, T Kesselheim and S Singla (2021). Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proc. 2021 ACM-SIAM Symp. Discrete Algorithms, pp. 653–661. Society for Industrial and Applied Mathematics. Crossref, Google Scholar
Dobzinski, S (2007). Two randomized mechanisms for combinatorial auctions. In Proc. APPROX and RANDOM, pp. 89–103. Berlin: Springer. Crossref, Google Scholar
Dobzinski, S (2016). Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. In Proc. 48th Annual ACM Symp. Theory of Computing, pp. 940–948. New York: Association for Computing Machinery. Crossref, Google Scholar
Dobzinski, S, R Lavi and N Nisan (2012). Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2), 486–503. Crossref, Web of Science, Google Scholar
Dobzinski, S, N Nisan and M Schapira (2005). Truthful randomized mechanisms for combinatorial auctions. In Proc. 38th Annual ACM Symp. Theory of Computing, pp. 644–652. New York: Association for Computing Machinery. Google Scholar
Dobzinski, S, N Nisan and M Schapira (2015). Approximation algorithms for combinatorial auctions with complement-free bidders. in Proc. 37th Annual ACM Symp. Theory of Computing, pp. 610–618. New York: Association for Computing Machinery. Google Scholar
Dobzinski, S and R Paes Leme (2014). Efficiency guarantees in auctions with budgets. In Int. Colloquium on Automata, Languages, and Programming, pp. 392–404. Berlin: Springer. Crossref, Google Scholar
Eden, A, M Feldman and A Vardi (2019). Online random sampling for budgeted settings. Theory of Computing Systems, 63, 1470–1498. Crossref, Web of Science, Google Scholar
Fotakis, D, K Lotidis and C Podimata (2019). A bridge between liquid and social welfare in combinatorial auctions with submodular bidders. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1), 1949–1956. Crossref, Google Scholar
Hoeffding, W (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30. Crossref, Web of Science, Google Scholar
Krysta, P and B Vocking (2012). Online mechanism design (randomized rounding on the fly). In Proc. Int. Colloquium on Automata, Languages, and Programming, pp. 636–647. Berlin: Springer. Crossref, Google Scholar
Lu, P and T Xiao (2015). Improved efficiency guarantees in auctions with budgets. In Proc. 16th ACM Conf. Economics and Computation, pp. 379–413. New York: Association for Computing Machinery. Crossref, Google Scholar
Lu, P and T Xiao (2017). Liquid welfare maximization in auctions with multiple items. In Int. Symp. Algorithmic Game Theory, pp. 41–52. Springer International Publishing. Crossref, Google Scholar