Learning and Robustness With Applications To Mechanism Design

dc.contributor.advisorDickerson, John Pen_US
dc.contributor.advisorGoldstein, Thomasen_US
dc.contributor.authorCurry, Michael Jeremiahen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2022-09-27T05:39:09Z
dc.date.available2022-09-27T05:39:09Z
dc.date.issued2022en_US
dc.description.abstractThe 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. 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. When an auction mechanism is represented as a neural network mapping bids from outcomes, 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. 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. With PreferenceNet, we extend this approach to notions of fairness that are learned from possibly vague human preferences. 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. Finally, we present a new auction architecture which is a differentiable version of affine maximizer auctions, modified to offer lotteries in order to potentially increase revenue. This architecture is always perfectly strategyproof (avoiding the Lagrangian-based constrained optimization of RegretNet) -- to achieve this goal, however, we need to accept that we cannot in general represent the optimal auction.en_US
dc.identifierhttps://doi.org/10.13016/7ylj-qmhi
dc.identifier.urihttp://hdl.handle.net/1903/29339
dc.language.isoenen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledEconomicsen_US
dc.subject.pquncontrolledadversarial robustnessen_US
dc.subject.pquncontrolledauctionsen_US
dc.subject.pquncontrolleddifferentiable economicsen_US
dc.subject.pquncontrolledmechanism designen_US
dc.titleLearning and Robustness With Applications To Mechanism Designen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Curry_umd_0117E_22790.pdf
Size:
3.8 MB
Format:
Adobe Portable Document Format