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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153829 |
| _version_ | 1826210239996755968 |
|---|---|
| author | Zhang, Wei |
| author2 | Daskalakis, Constantinos |
| author_facet | Daskalakis, Constantinos Zhang, Wei |
| author_sort | Zhang, Wei |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:46:21Z |
| format | Thesis |
| id | mit-1721.1/153829 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:46:21Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1538292024-03-22T03:20:14Z Online Auctions with Multiple Items Zhang, Wei Daskalakis, Constantinos Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. S.M. 2024-03-21T19:08:41Z 2024-03-21T19:08:41Z 2024-02 2024-02-21T17:10:23.933Z Thesis https://hdl.handle.net/1721.1/153829 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Zhang, Wei Online Auctions with Multiple Items |
| title | Online Auctions with Multiple Items |
| title_full | Online Auctions with Multiple Items |
| title_fullStr | Online Auctions with Multiple Items |
| title_full_unstemmed | Online Auctions with Multiple Items |
| title_short | Online Auctions with Multiple Items |
| title_sort | online auctions with multiple items |
| url | https://hdl.handle.net/1721.1/153829 |
| work_keys_str_mv | AT zhangwei onlineauctionswithmultipleitems |