PhD Proposal: Learning and Robustness With Applications to Mechanism Design

Talk
Michael Curry
Time: 
05.11.2021 15:30 to 17:30
Location: 

Remote

The design of economic mechanisms, especially auctions, is an increasingly important part of the modern economy. A particularly important property for a mechanism is strategyproofness- the mechanism must be robust to strategic manipulations so that the participants in the mechanism have no incentive to lie. By avoiding the need to model complex strategic interactions between agents, strategyproofness greatly simplifies the mechanism design problem. Yet in the important case when the mechanism designer's goal is to maximize their own revenue, the design of optimal strategyproof mechanisms has proved immensely difficult, with very little progress after decades of research.Recently, to escape this impasse, a number of works have parameterized auction mechanisms as deep neural networks and used gradient descent to successfully learn approximately optimal and approximately strategyproof mechanisms. We present several improvements on these techniques.Existing neural networks for auctions learn to maximize revenue subject to strategyproofness. Yet in many auctions, fairness is also an important concern -- in particular, fairness with respect to the items in the auction, which may represent, for instance, ad impressions for different protected demographic groups. With our new architecture, ProportionNet, we impose fairness constraints in addition to the strategyproofness constraints, and find approximately fair, approximately optimal mechanisms which outperform baselines.Existing network architectures can represent additive and unit-demand auctions but are unable to imposing more complex exactly-k constraints on the allocations made to the bidders. By using the Sinkhorn algorithm to add differentiable matching constraints, we produce a network which can represent valid allocations in such settings. We learn auctions with good revenue properties, and where optimal mechanisms are known we are able to reproduce them.When an auction mechanism is represented as a neural network mapping bids from outcomes, the property of strategyproofness can be thought of as a type of adversarial robustness. Making this connection explicit, we design a modified architecture for learning auctions which is amenable to integer-programming-based certification techniques from the adversarial robustness literature. Existing baselines are empirically strategyproof, but with no way to be certain how strong that guarantee really is. By contrast, we are able to provide perfectly tight bounds on the degree to which strategyproofness is violated at any given point.Ongoing work includes attempts to add distributional robustness to the mechanism design problem, to incorporate learned human preferences, to make explainable and globally certifiable auctions, and perhaps to extend the theory of mechanism design in order to prove some of the learned mechanisms optimal.Examining Committee:

Chair: Dr. John Dickerson Dept rep: Dr. Aravind Srinivasan Members: Dr. Tom Goldstein