Balasubramanian Sivan Welcome! I am a research scientist at Google Research New York. Research Interests: Algorithmic Game Theory and Mechanism Design, Online and Approximation Algorithms, Online Learning. Bio: I was a postdoctoral researcher in the Theory group at Microsoft Research Redmond between August 2013 and July 2015. I graduated in July 2013 with a PhD from the Computer Science department at University of Wisconsin-Madison. My advisor was Prof. Shuchi Chawla. Prior to that I obtained my undergraduate degree from the Computer Science department at Indian Institute of Technology Madras in July 2008. CV: Here's my CV. Contact Info: 111, 8th Ave, New York, NY 10011 Email: balusivan [at] google [dot] com

PhD Thesis: Prior Robust Optimization (Was awarded the 2013 ACM SIGecom Doctoral Dissertation Award,
and the University of Wisconsin-Madison CS department's outstanding graduate student researcher award)

Survey: Bayesian Algorithmic Mechanism Design, SIGecom exchanges 13(1), 2014 (pdf)
Shuchi Chawla, Balasubramanian Sivan

Program Committees
EC (2013, 2015-23), STOC (2020), SODA (2020), NeurIPS (2018-21), ICML (2018-23), WWW (2016-19, 2021-23), WINE (2016, 2021, 2023), AAAI (2016-17), AAMAS (2018-19), IJCAI (2013)

Preprints / Working Papers

• On Dual-Based PI Controllers for Online Allocation Problems (pdf)
  Santiago R. Balseiro, Haihao Lu, Vahab Mirrokni, Balasubramanian Sivan

Publications

• Robust Budget Pacing with a Single Sample ICML 2023 (ORAL) (pdf)
  Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni, Balasubramanian Sivan, Di Wang

• Description Complexity of Regular Distributions EC 2023 (pdf)
  Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah

• Pseudonorm Approachability and Applications to Regret Minimization ALT 2023 (pdf)
  Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

• Pricing Query Complexity of Revenue Maximization SODA 2023 (pdf)
  Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah

• Optimal Pricing Schemes for an Impatient Buyer SODA 2023 (pdf)
  Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang

• Best of Both Worlds Ad Contracts: Guaranteed Allocation and Price with Programmatic Efficiency, To appear in Management Science (pdf)
  Maxime C. Cohen, Antoine M. Desir, Nitish Korula, Balasubramanian Sivan

• Research Challenges in Internet Ad Markets: Vignettes on Complex Environments, SIGecom exchanges (Survey) 2022 (pdf)
  Kshipra Bhawalkar, Guru Guruganesh, Sebastien Lahaie, Andres Perlroth, Balasubramanian Sivan

• Online Allocation and Display Ads Optimization with Surplus Supply, WINE 2022 (pdf)
  Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari, Balasubramanian Sivan, Yifeng Teng, Creighton Thomas

• Strategizing against Learners in Bayesian Games, COLT 2022 (pdf)
  Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

• Appproximately Efficient Bilateral Trade, STOC 2022 (pdf)
  Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang

• Online Bipartite Matching with Reusable Resources, EC 2022 (pdf)
  Steven Delong, Alireza Farhadi, Rad Niazadeh, Balasubramanian Sivan

• Price Manipulability in First-Price Auctions, WWW 2022 (pdf)
  Johannes Brustle, Paul Dütting, Balasubramanian Sivan

• Learning to Price Against a Moving Target, ICML 2021 (pdf)
  Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah

• Welfare Maximizing Guaranteed Dashboard Mechanisms, EC 2021 (pdf)
  Yuan Deng, Jason D. Hartline, Jieming Mao, Balasubramanian Sivan

• Variable Decomposition for Prophet Inequalities and Optimal Ordering, EC 2021 (pdf)
  Allen Liu, Renato Paes Leme, Martin Pál, Jon Schneider, Balasubramanian Sivan

• Robust Repeated First Price Auctions, EC 2021 (pdf)
  Shipra Agrawal, Eric Balkanski, Vahab Mirrokni, Balasubramanian Sivan

• Jointly Learning Prices and Product Features, IJCAI 2021
  Ehsan Emamjomeh-Zadeh, Renato Paes Leme, Jon Schneider, Balasubramanian Sivan

• Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms, Operations Research (pdf)
  Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pal, Balasubramanian Sivan

• Separation between Second Price Auctions with Personalized Reserves and the Revenue Optimal Auction, Operations Research Letters 48(2): 176-179 (2020) (pdf)
  Will Ma, Balasubramanian Sivan

• Why Do Competitive Markets Converge to First-Price Auctions?, WWW 2020 (pdf)
  Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng

• Strategizing against No-regret Learners, NeurIPS 2019 (ORAL) (pdf)
  Yuan Deng, Jon Schneider, Balasubramanian Sivan

• Prior-Free Dynamic Auctions with Low Regret Buyers, NeurIPS 2019 (pdf)
  Yuan Deng, Jon Schneider, Balasubramanian Sivan

• Truthful Multi-Parameter Auctions with Online Supply: An Impossible Combination, SODA 2018 (pdf)
  Nikhil R. Devanur, Balasubramanian Sivan, Vasilis Syrgkanis

• Robust Repeated Auctions under Heterogeneous Buyer Behavior, EC 2018 (pdf)
  Shipra Agrawal, Constantinos Daskalakis, Vahab Mirrokni, Balasubramanian Sivan

• Testing Incentive Compatibility in Display Ad Auctions, WWW 2018 (pdf)
  Sebastien Lahaie, Andres Munoz Medina, Balasubramanian Sivan, Sergei Vassilvitskii

• Stability of Service Under Time-Of-Use Pricing, STOC 2017 (pdf)
  Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James Martin, Balasubramanian Sivan

• Tight Lower Bounds for the Multiplicative Weights Algorithm on the Experts Problem, ICALP 2017 (pdf)
  Nick Gravin, Yuval Peres, Balasubramanian Sivan

• Multi-Score Position Auctions, WSDM 2016 (pdf)
  Denis Charles, Nikhil R. Devanur, Balasubramanian Sivan (previously appeared in Ad Auctions Workshop, 2014)

• Towards Optimal Algorithms for Prediction with Expert Advice, SODA 2016 (pdf)
  Nick Gravin, Yuval Peres, Balasubramanian Sivan

• Simple Pricing Schemes for Consumers with Evolving Values, SODA 2016 (pdf)
  Accepted to the special issue of Games and Economic Behavior (GEB) dedicated to select AGT papers from STOC/FOCS/SODA 2016
  Shuchi Chawla, Nikhil R. Devanur, Anna Karlin, Balasubramanian Sivan

• Perfect Bayesian Equilibria in Repeated Sales, SODA 2015 (pdf)
  Appeared in the special invited issue of Games and Economic Behavior (GEB) dedicated to select AGT papers from STOC/FOCS/SODA 2015
  Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan

• Price Competition, Fluctuations, and Welfare Guarantees, EC 2015 (pdf)
  Moshe Babaioff, Renato Paes Leme, Balasubramanian Sivan

• Bayesian Algorithmic Mechanism Design, SIGecom exchanges 13(1), 2014 (pdf)
  Shuchi Chawla, Balasubramanian Sivan

• Prior-Independent Mechanisms for Scheduling, STOC 2013 (pdf)
  Shuchi Chawla, Jason Hartline, David Malec, Balasubramanian Sivan

• Cost-Recovering Bayesian Algorithmic Mechanism Design, EC 2013 (pdf)
  Hu Fu, Brendan Lucier, Balasubramanian Sivan, Vasilis Syrgkanis

• Revenue Maximization with Nonexcludable Goods, WINE 2013 (pdf)
  Appeared in the special invited invited issue of ACM Transactions on Economics and Computation (TEAC) from WINE 2013
  MohammadHossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam

• Vickrey Auctions for Irregular Distributions, WINE 2013 (pdf)
  Balasubramanian Sivan, Vasilis Syrgkanis

• Optimal Crowdsourcing Contests, SODA 2012 (pdf)
  Appeared in the special invited issue of Games and Economic Behavior (GEB) dedicated to select AGT papers from from STOC/FOCS/SODA 2012
  Shuchi Chawla, Jason Hartline, Balasubramanian Sivan
  (previously appeared in Workshop on Social Computing and User Generated Content, 2011)

• Asymptotically Optimal Algorithm for Stochastic Adwords, EC 2012 (pdf)
  Nikhil Devanur, Balasubramanian Sivan, Yossi Azar

• Single-Call Mechanisms, EC 2012 (pdf)
  Appeared in the special invited issue of ACM Transactions on Economics and Computation (TEAC) from EC 2012
  Christopher A. Wilkens, Balasubramanian Sivan

• Lower Bounds on Revenue of Approximately Optimal Auctions, WINE 2012 (pdf)
  Balasubramanian Sivan, Vasilis Syrgkanis, Omer Tamuz

• Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems, EC 2011 (pdf)
  Appeared in the Journal of the ACM, Volume 66, Issue 1, Pages 7:1 --7:41, 2019
  Nikhil Devanur, Kamal Jain, Balasubramanian Sivan, Chris Wilkens

• Multi-Parameter Mechanism Design and Sequential Posted Pricing, STOC 2010 (pdf)
  Shuchi Chawla, Jason Hartline, David Malec, Balasubramanian Sivan

• The Power of Randomness in Bayesian Optimal Mechanism Design, EC 2010 (pdf)
  Appeared in the special invited issue of Games and Economic Behavior (GEB) dedicated to select AGT papers from EC 2010 and EC 2011
  Shuchi Chawla, David Malec, Balasubramanian Sivan

• On Conditional Covering Problem, Mathematics in Computer Science, Special Issue on "Advances in Combinatorial Algorithms", Birkhauser Basel, 2009. (pdf)
  Balasubramanian Sivan, S. Harini, C. Pandurangan
  (previously appeared in the 19th International Workshop on Combinatorial Algorithms (IWOCA), Nagoya, Japan, 2008)

• Core and Conditional Core Path of Specified Length in Special Classes of Graphs, WALCOM 2009, Third Annual Workshop on Algorithms and Computation, Kolkata, India. (pdf)
  Balasubramanian Sivan, S. Harini, C.Pandurangan