Timezone: »
Poster
Online Pricing with Strategic and Patient Buyers
Michal Feldman · Tomer Koren · Roi Livni · Yishay Mansour · Aviv Zohar
We consider a seller with an unlimited supply of a single good, who is faced with a stream of $T$ buyers. Each buyer has a window of time in which she would like to purchase, and would buy at the lowest price in that window, provided that this price is lower than her private value (and otherwise, would not buy at all). In this setting, we give an algorithm that attains $O(T^{2/3})$ regret over any sequence of $T$ buyers with respect to the best fixed price in hindsight, and prove that no algorithm can perform better in the worst case.
Author Information
Michal Feldman (TAU)
Tomer Koren (Technion---Israel Inst. of Technology)
Roi Livni (Huji)
Yishay Mansour (Microsoft)
Aviv Zohar (huji)
More from the Same Authors
-
2022 : Finding Safe Zones of Markov Decision Processes Policies »
Lee Cohen · Yishay Mansour · Michal Moshkovitz -
2021 Workshop: Learning in Presence of Strategic Behavior »
Omer Ben-Porat · Nika Haghtalab · Annie Liang · Yishay Mansour · David Parkes -
2020 Poster: Sample Complexity of Uniform Convergence for Multicalibration »
Eliran Shabat · Lee Cohen · Yishay Mansour -
2020 Poster: Prediction with Corrupted Expert Advice »
Idan Amir · Idan Attias · Tomer Koren · Yishay Mansour · Roi Livni -
2020 Spotlight: Prediction with Corrupted Expert Advice »
Idan Amir · Idan Attias · Tomer Koren · Yishay Mansour · Roi Livni -
2020 Poster: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2020 Poster: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity »
Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia -
2020 Oral: Adversarially Robust Streaming Algorithms via Differential Privacy »
Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2019 : Poster and Coffee Break 2 »
Karol Hausman · Kefan Dong · Ken Goldberg · Lihong Li · Lin Yang · Lingxiao Wang · Lior Shani · Liwei Wang · Loren Amdahl-Culleton · Lucas Cassano · Marc Dymetman · Marc Bellemare · Marcin Tomczak · Margarita Castro · Marius Kloft · Marius-Constantin Dinu · Markus Holzleitner · Martha White · Mengdi Wang · Michael Jordan · Mihailo Jovanovic · Ming Yu · Minshuo Chen · Moonkyung Ryu · Muhammad Zaheer · Naman Agarwal · Nan Jiang · Niao He · Nikolaus Yasui · Nikos Karampatziakis · Nino Vieillard · Ofir Nachum · Olivier Pietquin · Ozan Sener · Pan Xu · Parameswaran Kamalaruban · Paul Mineiro · Paul Rolland · Philip Amortila · Pierre-Luc Bacon · Prakash Panangaden · Qi Cai · Qiang Liu · Quanquan Gu · Raihan Seraj · Richard Sutton · Rick Valenzano · Robert Dadashi · Rodrigo Toro Icarte · Roshan Shariff · Roy Fox · Ruosong Wang · Saeed Ghadimi · Samuel Sokota · Sean Sinclair · Sepp Hochreiter · Sergey Levine · Sergio Valcarcel Macua · Sham Kakade · Shangtong Zhang · Sheila McIlraith · Shie Mannor · Shimon Whiteson · Shuai Li · Shuang Qiu · Wai Lok Li · Siddhartha Banerjee · Sitao Luan · Tamer Basar · Thinh Doan · Tianhe Yu · Tianyi Liu · Tom Zahavy · Toryn Klassen · Tuo Zhao · Vicenç Gómez · Vincent Liu · Volkan Cevher · Wesley Suttle · Xiao-Wen Chang · Xiaohan Wei · Xiaotong Liu · Xingguo Li · Xinyi Chen · Xingyou Song · Yao Liu · YiDing Jiang · Yihao Feng · Yilun Du · Yinlam Chow · Yinyu Ye · Yishay Mansour · · Yonathan Efroni · Yongxin Chen · Yuanhao Wang · Bo Dai · Chen-Yu Wei · Harsh Shrivastava · Hongyang Zhang · Qinqing Zheng · SIDDHARTHA SATPATHI · Xueqing Liu · Andreu Vall -
2019 : Poster Spotlight 1 »
David Brandfonbrener · Joan Bruna · Tom Zahavy · Haim Kaplan · Yishay Mansour · Nikos Karampatziakis · John Langford · Paul Mineiro · Donghwan Lee · Niao He -
2019 Poster: Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function »
Aviv Rosenberg · Yishay Mansour -
2019 Poster: Graph-based Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour -
2019 Spotlight: Graph-based Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour -
2019 Poster: Learning to Screen »
Alon Cohen · Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Shay Moran -
2019 Poster: Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits »
Yogev Bar-On · Yishay Mansour -
2016 : Robust Learning and Inference »
Yishay Mansour -
2016 Poster: The Limits of Learning with Missing Data »
Brian Bullins · Elad Hazan · Tomer Koren -
2015 Poster: Fast Rates for Exp-concave Empirical Risk Minimization »
Tomer Koren · Kfir Y. Levy -
2015 Poster: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2015 Spotlight: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2014 Poster: The Blinded Bandit: Learning with Adaptive Feedback »
Ofer Dekel · Elad Hazan · Tomer Koren -
2014 Poster: On the Computational Efficiency of Training Neural Networks »
Roi Livni · Shai Shalev-Shwartz · Ohad Shamir -
2013 Poster: Distributed Exploration in Multi-Armed Bandits »
Eshcar Hillel · Zohar Karnin · Tomer Koren · Ronny Lempel · Oren Somekh -
2013 Spotlight: Distributed Exploration in Multi-Armed Bandits »
Eshcar Hillel · Zohar Karnin · Tomer Koren · Ronny Lempel · Oren Somekh -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2011 Poster: Beating SGD: Learning SVMs in Sublinear Time »
Elad Hazan · Tomer Koren · Nati Srebro