Online Auctions with Multiple Items

Motivated by a recent switch of online ad exchanges from second-price auctions to firstprice auctions, this thesis studies computational problems related to how an advertiser can select bids to maximize her cumulative reward when participating in a sequence of single-item f irst-price auctions, or a sequence of several first-price auctions that take place in parallel. In particular, we study the problem of regret minimization in this setting, extending prior work for second-price auctions. We show that sub-linear regret cannot be achieved when the values are continuous and there are two or more single-item auctions that take place per round. On the other hand, we show that if the values are discretized the regret can be made to grow sublinearly, and this can be attained computationally efficiently using a best-response oracle. Finally, when there is a single first-price auction per round, we can attain tight regret bounds in two settings where additional information is available, in the form of hints, about the opponent bids.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Zhang, Wei

Advisor dc:contributor.advisor

• Daskalakis, Constantinos

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/153829

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/153829