Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents

Sophie Klumper*, Guido Schäfer

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

25 Downloads (Pure)

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 languageEnglish
Title of host publicationAlgorithmic Game Theory
Subtitle of host publication15th International Symposium, SAGT 2022, Colchester, UK, September 12–15, 2022, Proceedings
EditorsPanagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris
PublisherSpringer Science and Business Media Deutschland GmbH
Pages78-93
Number of pages16
ISBN (Electronic)9783031157141
ISBN (Print)9783031157134
DOIs
Publication statusPublished - 2022
Event15th International Symposium on Algorithmic Game Theory, SAGT 2022 - Colchester, United Kingdom
Duration: 12 Sept 202215 Sept 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13584 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Symposium on Algorithmic Game Theory, SAGT 2022
Country/TerritoryUnited Kingdom
CityColchester
Period12/09/2215/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.

Keywords

  • Additive valuations
  • Budget feasible mechanism
  • Divisible agents
  • Knapsack auction
  • Mechanism design
  • Procurement auction

Fingerprint

Dive into the research topics of 'Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents'. Together they form a unique fingerprint.

Cite this