Speaker: Vitor Bosshard
Title: Combinatorial Auctions as Continuous Bayesian Games
Abstract: Combinatorial auctions (CAs) are mechanisms used to sell multiple goods simultaneously when buyers have complex preferences over bundles of goods. They are often studied in an incomplete information (bayesian) setting: bidder i privately knows her own valuation v_i(S) for each bundle S and has a prior over all other valuations v_j. The solution concept in this setting is that of Bayes-Nash equilibrium (BNE). Unfortunately, proving that a set of strategies are in BNE with respect to each other becomes difficult when both the value space (set of possible valuations) and the action space (set of allowed bids) are continuous.
In this talk, I will present two algorithms which overcome these difficulties and compute ε-BNEs of CAs, where ε is an upper bound (over all possible valuations v_i) of the utility lost by playing the equilibrium instead of a best response to it.