Simple combinatorial auctions with budget constraints

DOI10.1016/J.TCS.2020.07.019zbMATH Open1459.91067arXiv2007.14274OpenAlexW3044780425MaRDI QIDQ2006772FDOQ2006772

Publication date: 12 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2007.14274

zbMATH Keywords

combinatorial auctions budget constraints liquid price of anarchy

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

Cited In (2)

This page was built for publication: Simple combinatorial auctions with budget constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006772)