{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/153829"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/153829","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Online Auctions with Multiple Items","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zhang, Wei"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Daskalakis, Constantinos"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-02","date_published":"2024-02","updated_at":"2026-07-22T22:22:05Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"rights_urls":["https://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/153829","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Daskalakis, Constantinos"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Zhang, Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2024-03-21T19:08:41Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2024-03-21T19:08:41Z"]},{"key":"dc:date.issued","label":"Date","values":["2024-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Science in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/153829"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Online Auctions with Multiple Items"]}]}],"canonical_facts":{"dc:contributor.advisor":["Daskalakis, Constantinos"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Zhang, Wei"],"dc:date.accessioned":["2024-03-21T19:08:41Z"],"dc:date.available":["2024-03-21T19:08:41Z"],"dc:date.issued":["2024-02"],"dc:description.abstract":["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."],"dc:description.degree":["S.M."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/153829"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"dc:rights.uri":["https://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Online Auctions with Multiple Items"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Science in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:05Z"}