Skip navigation
Please use this identifier to cite or link to this item:
Title: Selling to No-Regret Buyers
Authors: Zhang, Shirley
Advisors: Weinberg, Matt
Department: Computer Science
Class Year: 2020
Abstract: We consider the problem of optimizing a seller's revenue in an opaque auction where bidders are using a no-regret learning algorithm. In such auctions, we assume a single item and multiple bidders drawing their values from a known distribution D. The seller is able to set the price and allocation probability for each possible bid value independently for each round. We extend results from "Selling to a No-Regret Buyer" by Braverman et. al to the multiple bidder setting by taking a Lagrangian relaxation of the original linear program presented in the paper. We provide three properties of a solution to the Lagrangian relaxation in the single bidder setting and show why one does not hold for the multiple bidder setting. We then present two greedy algorithms for solving the multiple bidder Lagrangian relaxation and show why they do not output an optimal solution. Finally, we present a subset of distributions for which the techniques for solving the single bidder Lagrangian relaxation can be extended to the multiple bidder setting.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Computer Science, 1988-2020

Files in This Item:
File Description SizeFormat 
ZHANG-SHIRLEY-THESIS.pdf223.17 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.