Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Bayesian Combinatorial Auctions
verfasst von : George Christodoulou, Annamária Kovács, Michael Schapira
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the following Bayesian setting:
m
items are sold to
n
selfish bidders in
m
independent second-price auctions. Each bidder has a
private
valuation function that expresses complex preferences over
all
subsets of items. Bidders only have
beliefs
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 valuation functions, then every Bayesian 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
m
and
n
.