Research Repository

Simple combinatorial auctions with budget constraints

Voudouris, Alexandros A (2020) 'Simple combinatorial auctions with budget constraints.' Theoretical Computer Science, 842. pp. 6-17. ISSN 0304-3975

2007.14274v1.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (195kB) | Preview


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: Elements
Depositing User: Elements
Date Deposited: 13 Aug 2020 11:14
Last Modified: 15 Jan 2022 01:34

Actions (login required)

View Item View Item