Abstract
We consider budget feasible mechanisms for procurement auctions with additive valuation functions. For the divisible case, where agents can be allocated fractionally, there exists an optimal mechanism with approximation guarantee e/ (e- 1 ) under the small bidder assumption. We study the divisible case without the small bidder assumption, but assume that the true costs of the agents are bounded by the budget. This setting lends itself to modeling economic situations in which the goods represent time and the agents’ true costs are not necessarily small compared to the budget. Non-trivially, we give a mechanism with an approximation guarantee of 2.62, improving the result of 3 for the indivisible case. Additionally, we give a lower bound on the approximation guarantee of 1.25. We then study the problem in more competitive markets and assume that the agents’ value over cost efficiencies are bounded by some θ≥ 1. For θ≤ 2, we give a mechanism with an approximation guarantee of 2 and a lower bound of 1.18. Finally, we extend these results to settings with different agent types with a linear capped valuation function for each type.
Original language | English |
---|---|
Title of host publication | Algorithmic Game Theory |
Subtitle of host publication | 15th International Symposium, SAGT 2022, Colchester, UK, September 12–15, 2022, Proceedings |
Editors | Panagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris |
Publisher | Springer Science and Business Media Deutschland GmbH |
Pages | 78-93 |
Number of pages | 16 |
ISBN (Electronic) | 9783031157141 |
ISBN (Print) | 9783031157134 |
DOIs | |
Publication status | Published - 2022 |
Event | 15th International Symposium on Algorithmic Game Theory, SAGT 2022 - Colchester, United Kingdom Duration: 12 Sept 2022 → 15 Sept 2022 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13584 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 15th International Symposium on Algorithmic Game Theory, SAGT 2022 |
---|---|
Country/Territory | United Kingdom |
City | Colchester |
Period | 12/09/22 → 15/09/22 |
Bibliographical note
Funding Information:feasible mechanisms for divisible agents when he was a postdoc at CWI. Part of this work was sponsored by the Open Technology Program of the Dutch Research Council (NWO), project number 18938.
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Funding
feasible mechanisms for divisible agents when he was a postdoc at CWI. Part of this work was sponsored by the Open Technology Program of the Dutch Research Council (NWO), project number 18938.
Funders | Funder number |
---|---|
Open Technology Program of the Dutch Research Council | |
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 18938 |
Nederlandse Organisatie voor Wetenschappelijk Onderzoek |
Keywords
- Additive valuations
- Budget feasible mechanism
- Divisible agents
- Knapsack auction
- Mechanism design
- Procurement auction