Voudouris, Alexandros A (2020) Simple combinatorial auctions with budget constraints. Theoretical Computer Science, 842. pp. 6-17. DOI https://doi.org/10.1016/j.tcs.2020.07.019
Voudouris, Alexandros A (2020) Simple combinatorial auctions with budget constraints. Theoretical Computer Science, 842. pp. 6-17. DOI https://doi.org/10.1016/j.tcs.2020.07.019
Voudouris, Alexandros A (2020) Simple combinatorial auctions with budget constraints. Theoretical Computer Science, 842. pp. 6-17. DOI https://doi.org/10.1016/j.tcs.2020.07.019
Abstract
We study the efficiency of simple combinatorial auctions for the allocation of a set of items to a set of agents, with private subadditive valuation functions and budget constraints. The class we consider includes all auctions that allocate each item independently to the agent that submits the highest bid for it, and requests a payment that depends on the bids of all agents only for this item. Two well-known examples of this class are the simultaneous first and second price auctions. We focus on the pure equilibria of the induced strategic games, and using the liquid welfare as our efficiency benchmark, we show an upper bound of 2 on the price of anarchy for any auction in this class, as well as a tight corresponding lower bound on the price of stability for all auctions whose payment rules are convex combinations of the bids. This implies a tight bound of 2 on the price of stability of the well-known simultaneous first and second price auctions, which are members of the class. Additionally, we show lower bounds for the whole class, for more complex auctions (like VCG), and for settings where the budgets are assumed to be common knowledge rather than private information.
Item Type: | Article |
---|---|
Additional Information: | Accepted to Theoretical Computer Science |
Uncontrolled Keywords: | Combinatorial auctions; Budget constraints; Liquid price of anarchy |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 13 Aug 2020 11:14 |
Last Modified: | 30 Oct 2024 16:19 |
URI: | http://repository.essex.ac.uk/id/eprint/28352 |
Available files
Filename: 2007.14274v1.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0