CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Algorithmic game theory
Org: Hu Fu (University of British Columbia) et Anna R. Karlin (University of Washington, USA)

NIKHIL DEVANUR, Microsoft Research
Online Stochastic Optimization and game theory: beyond convexity  [PDF]

Online Stochastic Optimization (OSO) is a class of problems that capture decision making under uncertainty. The algorithm has to make real time decisions as it sees new input without knowing future arrival. Some mild stochastic assumptions about the input such as random arrival order can give near optimal algorithms for a broad class of problems.

We have known how to solve OSO with convex constraints and objectives for a few years now. I will show how game theoretic considerations lead to formulations that are beyond convexity, and present a few solutions.

KIRA GOLDNER, University of Washington
A Bulow-Klemperer Result for Gains From Trade in Two-Sided Markets  [PDF]

We consider a two-sided market with unit-demand buyers, single-item sellers, and identical items. The designer's goal is to maximize the gains from trade (GFT). Myerson-Satterthwaite '83 states it's impossible to achieve the optimal GFT using a mechanism that's truthful and budget-balanced. Instead, we take the approach of Bulow-Klemperer from revenue maximization, asking: how many additional buyers must we recruit in order to use a simple, prior-free, deterministic mechanism to approximate the optimal GFT? We give results for our candidate mechanism, Buyer Trade Reduction, depending on the initial market size and agent distributions.

Joint work with Moshe Babaioff and Yannai Gonczarowski.

JASON HARTLINE, Northwestern University
Anonymous Pricing for Non-linear Agents  [PDF]

The optimal single-item auction for agents with independent but non-identically distributed values is complex for linear utility agents (Myerson, 1981) and has no closed-form characterization for non-linear agents (Alaei et al., 2012). For linear utility agents satisfying a natural regularity property, Alaei et al.\ (2018) showed that posting an anonymous price is an $e$-approximation. We give a parameterized regularity property for non-linear agents and show that the approximation bound of anonymous pricing for regular agents approximately extends to agents that satisfy this approximate regularity property. We apply this approximation framework to agents with public-budget utility, private-budget utility, and risk-averse utility.

KEVIN LEYTON-BROWN, University of British Columbia
Formalizing the Boundary Between Strategic and Nonstrategic Reasoning  [PDF]

It is common to distinguish between strategic behavior and other forms of intentional but "nonstrategic" behavior; cf. many prominent models in behavioral game theory. The literature gives no clear guidance on how computationally bounded nonstrategic agents must be, instead singling out specific decision rules and asserting them to be nonstrategic. We propose a formal characterization of nonstrategic behavior, showing that: (1) it captures all "nonstrategic" decision rules of which we are aware; (2) it captures no strategic behavior, in a precise sense. Several computationally easy special cases of Nash equilibrium also satisfy our criterion.

Joint work with James Wright.

BRENDAN LUCIER, Microsoft Research
Efficiency and Inefficiency in Emission License Auctions  [PDF]

Emission license auctions aim to control the negative externalities of pollution by distributing identical permits to firms, up to a cap. We can view this as a multi-unit auction with a convex and increasing social cost of production. The goal is to allocate an efficient number of licenses, distributed to the firms that would make the best use of them. Unfortunately, strategic bidding behavior---such as demand reduction---can dramatically affect welfare outcomes, especially in the presence of social costs. In this talk we will explore simple augmentations to the standard auction format that can help limit the impact of strategic manipulation.