Online learning in repeated auctions
© 2016 J. Weed, V. Perchet & P. Rigollet. Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137801 |
| _version_ | 1811076847586246656 |
|---|---|
| author | Rigolette, Philippe Weed, Jonathan |
| author_facet | Rigolette, Philippe Weed, Jonathan |
| author_sort | Rigolette, Philippe |
| collection | MIT |
| description | © 2016 J. Weed, V. Perchet & P. Rigollet. Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical. Comparing our performance against that of the best fixed bid in hindsight, we show that sublinear regret is also achievable in this case. For both the stochastic and adversarial models, we prove matching minimax lower bounds showing our strategies to be optimal up to lower-order terms. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type. |
| first_indexed | 2024-09-23T10:28:53Z |
| format | Article |
| id | mit-1721.1/137801 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:28:53Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1378012021-11-09T03:30:07Z Online learning in repeated auctions Rigolette, Philippe Weed, Jonathan © 2016 J. Weed, V. Perchet & P. Rigollet. Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical. Comparing our performance against that of the best fixed bid in hindsight, we show that sublinear regret is also achievable in this case. For both the stochastic and adversarial models, we prove matching minimax lower bounds showing our strategies to be optimal up to lower-order terms. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type. 2021-11-08T19:41:47Z 2021-11-08T19:41:47Z 2019-11-19T17:08:43Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137801 Rigolette, Philippe and Weed, Jonathan. "Online learning in repeated auctions." en http://proceedings.mlr.press/v49/weed16.pdf Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf arXiv |
| spellingShingle | Rigolette, Philippe Weed, Jonathan Online learning in repeated auctions |
| title | Online learning in repeated auctions |
| title_full | Online learning in repeated auctions |
| title_fullStr | Online learning in repeated auctions |
| title_full_unstemmed | Online learning in repeated auctions |
| title_short | Online learning in repeated auctions |
| title_sort | online learning in repeated auctions |
| url | https://hdl.handle.net/1721.1/137801 |
| work_keys_str_mv | AT rigolettephilippe onlinelearninginrepeatedauctions AT weedjonathan onlinelearninginrepeatedauctions |