Bayesian Combinatorial Auctions

Christodoulou, George, Kovacs, Annamaria and Schapira, Michael (2016) Bayesian Combinatorial Auctions. JOURNAL OF THE ACM, 63 (2). pp. 1-19.

Text bayesianACMrevised.pdf - Submitted version Download (307kB)

Abstract

<jats:p> We study the following simple Bayesian auction setting: <jats:italic>m</jats:italic> items are sold to <jats:italic>n</jats:italic> selfish bidders in <jats:italic>m</jats:italic> independent second-price auctions. Each bidder has a <jats:italic>private</jats:italic> valuation function that specifies his or her complex preferences over <jats:italic>all</jats:italic> subsets of items. Bidders only have <jats:italic>beliefs</jats:italic> about the valuation functions of the other bidders, in the form of probability distributions. The objective is to allocate the items to the bidders in a way that provides a good approximation to the optimal social welfare value. We show that if bidders have submodular or, more generally, fractionally subadditive (aka XOS) valuation functions, every Bayes-Nash equilibrium of the resulting game provides a 2-approximation to the optimal social welfare. Moreover, we show that in the full-information game, a pure Nash always exists and can be found in time that is polynomial in both <jats:italic>m</jats:italic> and <jats:italic>n</jats:italic> . </jats:p>

Item Type:	Article
Uncontrolled Keywords:	Mechanism design, combinatorial auctions, game theory, simultaneous item-bidding auctions
Depositing User:	Symplectic Admin
Date Deposited:	06 Dec 2016 08:24
Last Modified:	19 Jan 2023 07:24
DOI:	10.1145/2835172
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004766