Details for Talk on: 05.12.2016

  • Speaker: Vitor Bosshard
  • Title:  A Fast Algorithm for Computing Bayes-Nash Equilibria in Core-Selecting Combinatorial Auctions
  • Abstract:  

    Combinatorial auctions present a difficult challenge for mechanism design: The VCG mechanism, the gold standard in other domains, is not envy-free and might yield extremely low revenue.

    To overcome these problems, core-selecting auctions have been proposed as an alternative. They are envy-free by definition and have high revenue, but at the cost of losing strategy-proofness. Deriving their Bayes-Nash equilibria is a very hard task both analytically and numerically, and so not much is known about their incentive compatibility and other properties, not even in small settings.

    We present a fast numeric algorithm to approximate Bayes-Nash Equilibria of combinatorial auctions, based on fictitious play. The algorithm makes it feasible to compute the equilibria of games much larger than those studied in the literature so far, without significantly restricting the strategy space of the players.