CanaDAM 2017
Ryerson University, June 12 - 16, 2017

Algorithmic Game Theory
Org: Brendan Lucier (Microsoft Research)

HU FU, University of British Columbia
The power of Bayesian incentive compatible auctions for revenue maximization  [PDF]

Myerson (1981) showed that in single item auctions, Bayesian incentive compatible (BIC) auctions extract no more revenue than dominant strategy incentive compatible (DSIC) ones when bidders' values are drawn independently. When there is correlation in the values, Cr\'emer and McLean (1988) showed that this is no longer true for interim individually rational auctions. It has remained unanswered whether a gap exists when the auction is subject to the stronger requirement of ex post individual rationality. We resolve the question, showing that this gap can be unbounded, and giving conditions under which the gap is bounded.

Oblivious Dynamic Mechanism Design  [PDF]

Dynamic mechanism design is a powerful tool to design auctions that are repeated over time. In this talk I'll survey new algorithmic results in dynamic mechanism design with a focus on the recently introduced concept of obliviousness. A dynamic mechanism is oblivious if the allocation and pricing rule at each period does not depend on the type distributions in future periods. In particular, we will discuss how to design mechanisms that have only distributional information about the present but are competitive against clairvoyant mechanisms, which can see the distributions in the future.

CHAITANYA SWAMY, University of Waterloo
Signaling in Bayesian Zero-Sum and Network-Routing Games  [PDF]

We study the optimization problem faced by a principal in a Bayesian game, who can reveal information about the underlying random state of nature to players so as to obtain a desirable equilibrium. The signaling problem is to determine what information should be revealed to achieve this goal? We obtain various hardness results for signaling. For Bayesian two-player zero-sum games, we exploit the equivalence of optimization and separation to prove that obtaining an FPTAS for maximizing a player's equilibrium utility is NP-hard. For Bayesian network-routing games, we prove a tight 4/3-factor hardness result for minimizing the average equilibrium latency.

ADRIAN VETTA, McGill University
Modern Auction Design: Combinatorial Aspects  [PDF]

I will discuss modern auction design and important practical applications, such as spectrum auctions and carbon pricing mechanisms, with a focus on combinatorial aspects.

MATT WEINBERG, Princeton University
A Duality Based Unified Approach to Bayesian Mechanism Design  [PDF]

We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai et al., simple auctions for additive buyers, and posted-price mechanisms for unit-demand buyers.

We will also provide a brief survey of applications of our framework in the design of approximately optimal mechanisms for many combinatorial bidders, multi-dimensional Bulow-Klemperer results, and budget-constrained buyers.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Ryerson University Office of Naval Research Science and Technology