Algorithmic game theory
Org:
Hu Fu (University of British Columbia) et
Anna R. Karlin (University of Washington, USA)
[
PDF]
 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 BulowKlemperer Result for Gains From Trade in TwoSided Markets [PDF]

We consider a twosided market with unitdemand buyers, singleitem sellers, and identical items. The designer's goal is to maximize the gains from trade (GFT). MyersonSatterthwaite '83 states it's impossible to achieve the optimal GFT using a mechanism that's truthful and budgetbalanced. Instead, we take the approach of BulowKlemperer from revenue maximization, asking: how many additional buyers must we recruit in order to use a simple, priorfree, 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 Nonlinear Agents [PDF]

The optimal singleitem auction for agents with independent but nonidentically distributed values is complex for linear utility agents (Myerson, 1981) and has no closedform characterization for nonlinear 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 nonlinear 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 publicbudget utility, privatebudget utility, and riskaverse utility.
 KEVIN LEYTONBROWN, 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 multiunit 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 behaviorsuch as demand reductioncan 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.