<html> <title>Balasubramanian Sivan's Home Page - Google Research</title> <body> <table cellpadding="10"> <tbody><tr><td> <img src="./Balu_pic.JPG" alt="photo" width="350" height="270/"><br> </td> <td> <h1>Balasubramanian Sivan</h1> <p>Welcome! I am a research scientist at <a href="https://research.google.com/">Google Research</a> New York. <p> <b><font size = "4.9" >Research Interests</font></b>: Algorithmic Game Theory and Mechanism Design, Online and Approximation Algorithms, Online Learning. </p> <p> <b><font size = "4.9" >Bio</font></b>: I was a postdoctoral researcher in the <a href="http://research.microsoft.com/en-us/groups/theory"> Theory group</a> at Microsoft Research Redmond</a> 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 <a href="http://pages.cs.wisc.edu/~shuchi">Prof. Shuchi Chawla</a>. Prior to that I obtained my undergraduate degree from the Computer Science department at Indian Institute of Technology Madras in July 2008. <!--My undergraduate <a href="papers/2008/btech_thesis.pdf">thesis work</a> was on Algorithms in special Graphs, and my undergraduate advisor was <a href="http://www.cse.iitm.ac.in/~rangan"> Prof. C. PanduRangan</a>.--> </p> <p><b><font size = "4.9" >CV</font></b>: Here's my <a href="BaluSivan_CV.pdf">CV</a>.</p> <p><b><font size = "4.9" >Contact Info:</font></b> 111, 8th Ave, New York, NY 10011<br/> Email: balusivan [at] google [dot] com <br/> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; balu2901 [at] cs [dot] wisc [dot] edu </td> </tr></tbody></table> <p> <b><font size="4.9">PhD Thesis</font></b>: <a href="papers/2013/dissertation.pdf"> Prior Robust Optimization</a> (Was awarded the 2013 ACM SIGecom Doctoral Dissertation Award,<br/>and the University of Wisconsin-Madison CS department's outstanding graduate student researcher award) </p> <p> <b><font size="4.9">Survey</font></b>: Bayesian Algorithmic Mechanism Design, SIGecom exchanges 13(1), 2014 <a href="http://www.sigecom.org/exchanges/volume_13/1/CHAWLA.pdf">(pdf)</a><br /> Shuchi Chawla, Balasubramanian Sivan </p> <p><b><font size="4.9">Program Committees</font></b><br/> 2018: <a href="http://www.sigecom.org/ec18/">EC 2018</a>, <a href="https://www2018.thewebconf.org/">WWW 2018</a>, <a href="http://celweb.vuse.vanderbilt.edu/aamas18/">AAMAS 2018</a>, <a href="https://icml.cc/">ICML 2018</a>, <a href="https://nips.cc/Conferences/2018/">NIPS 2018</a><br/> 2017: <a href="http://www.sigecom.org/ec17/">EC 2017</a>, <a href="http://www.www2017.com.au/">WWW 2017</a>, <a href="http://www.aaai.org/Conferences/AAAI/aaai17.php">AAAI 2017</a>, <a href="http://www.aamas2017.org/">AAMAS 2017</a> <br/> 2016: <a href="http://www.sigecom.org/ec16/">EC 2016</a>, <a href="http://www2016.ca/">WWW 2016</a>, <a href="http://www.aaai.org/Conferences/AAAI/aaai16.php">AAAI 2016</a>, <a href="http://cs.mcgill.ca/~wine2016/">WINE 2016</a> <br/> 2015: <a href="http://www.sigecom.org/ec15/">EC 2015</a> <br/> 2013: <a href="http://www.sigecom.org/ec13/">EC 2013</a>, <a href="http://ijcai13.org/">IJCAI 2013</a> </p> <!--<p><b><font size="4.9">Survey<font></font></b>: Bayesian Algorithmic Mechanism Design, SIGecom exchanges 13(1), 2014 <a href="http://www.sigecom.org/exchanges/volume_13/1/CHAWLA.pdf">(pdf)</a><br /> Shuchi Chawla, Balasubramanian Sivan</p>.--> <h3> Preprints / Working Papers </h3> <ul> <li> <p> <cite> Allocation and Price Guarantees in an Uncertain Internet Advertising Market </cite><a href="https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3088600">(pdf)</a><br/> Maxime C. Cohen, Antoine M. Desir, Nitish Korula, Balasubramanian Sivan </p> <li> <p> <cite> Improved Approximations for Posted Price and Second Price Mechanisms <br/> Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pal, Balasubramanian Sivan </p> </ul> <h3> Publications </h3> <ul> <li> <p> <cite> Truthful Multi-Parameter Auctions with Online Supply: An Impossible Combination, </cite><b> ACM-SIAM SODA 2018 </b><a href="papers/2018/impossibilities_online.pdf">(pdf)</a> <br/> Nikhil R. Devanur, Balasubramanian Sivan, Vasilis Syrgkanis </p> <li> <p> <cite> Robust Repeated Auctions under Heterogeneous Buyer Behavior, </cite><b> ACM EC 2018 </b><a href="https://arxiv.org/abs/1803.00494">(pdf)</a><br/> Shipra Agrawal, Constantinos Daskalakis, Vahab Mirrokni, Balasubramanian Sivan </p> <li> <p> <cite> Testing Incentive Compatibility in Display Ad Auctions, </cite><b> WWW 2018 </b><a href="papers/2018/rpo-detect.pdf">(pdf)</a><br/> Sebastien Lahaie, Andres Munoz Medina, Balasubramanian Sivan, Sergei Vassilvitskii </p> <li> <p> <cite> Stability of Service Under Time-Of-Use Pricing, </cite><b> STOC 2017 </b><a href="papers/2017/cloud_stoc_251.pdf">(pdf)</a><br /> Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James Martin, Balasubramanian Sivan </p> <li> <p> <cite> Tight Lower Bounds for the Multiplicative Weights Algorithm on the Experts Problem, </cite><b> ICALP 2017 </b><a href="papers/2017/experts_project.pdf">(pdf)</a> <br/> Nick Gravin, Yuval Peres, Balasubramanian Sivan </p> <li> <p> <cite> Multi-Score Position Auctions, </cite><b> WSDM 2016 </b><a href="papers/2014/DSA.pdf">(pdf)</a><br /> Denis Charles, Nikhil R. Devanur, Balasubramanian Sivan (previously appeared in Ad Auctions Workshop, 2014) </p> <li> <p> <cite> Towards Optimal Algorithms for Prediction with Expert Advice, </cite><b> ACM-SIAM SODA 2016 </b><a href="http://arxiv.org/abs/1409.3040">(pdf)</a><br /> Nick Gravin, Yuval Peres, Balasubramanian Sivan </p> <li> <p> <cite> Simple Pricing Schemes for Consumers with Evolving Values, </cite><b> ACM-SIAM SODA 2016 </b> <a href="papers/2016/ppp.pdf">(pdf)</a><br /> Shuchi Chawla, Nikhil R. Devanur, Anna Karlin, Balasubramanian Sivan </p> <li> <p> <cite> Perfect Bayesian Equilibria in Repeated Sales, </cite><b> ACM-SIAM SODA 2015 </b><a href="http://arxiv.org/abs/1409.3062">(pdf)</a><br /> Invited to the special issue of <b> Games and Economic Behavior (GEB)</b> dedicated to select AGT papers from STOC/FOCS/SODA 2015<br/> Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan </p> <li> <p> <cite> Price Competition, Fluctuations, and Welfare Guarantees, </cite><b> ACM EC 2015 </b><a href="http://arxiv.org/abs/1411.2036">(pdf)</a><br /> Moshe Babaioff, Renato Paes Leme, Balasubramanian Sivan </p> <li><p> <cite> Bayesian Algorithmic Mechanism Design, </cite> <b> SIGecom exchanges 13(1), 2014 </b> <a href="http://www.sigecom.org/exchanges/volume_13/1/CHAWLA.pdf">(pdf)</a><br /> Shuchi Chawla, Balasubramanian Sivan </p> <li> <p> <cite> Prior-Independent Mechanisms for Scheduling, </cite><b> ACM STOC 2013 </b><a href="http://arxiv.org/pdf/1305.0597v1.pdf">(pdf)</a><br /> Shuchi Chawla, Jason Hartline, David Malec, Balasubramanian Sivan </p> <li> <p> <cite> Cost-Recovering Bayesian Algorithmic Mechanism Design, </cite><b> ACM EC 2013 </b><a href="http://arxiv.org/pdf/1305.0598v1.pdf">(pdf)</a><br /> Hu Fu, Brendan Lucier, Balasubramanian Sivan, Vasilis Syrgkanis </p> <li> <p> <cite> Revenue Maximization with Nonexcludable Goods, </cite><b> WINE 2013 </b><a href="papers/2013/path_externality.pdf">(pdf)</a><br /> Appeared in the special invited issue of <b> ACM Transactions on Economics and Computation (TEAC) </b> from WINE 2013 <br /> MohammadHossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam</p> <li> <p> <cite> Vickrey Auctions for Irregular Distributions, </cite><b> WINE 2013 </b><a href="http://arxiv.org/pdf/1306.4022v2.pdf">(pdf)</a><br /> Balasubramanian Sivan, Vasilis Syrgkanis</p> <li> <p> <cite> Optimal Crowdsourcing Contests, </cite><b> ACM-SIAM SODA 2012 </b><a href="papers/2011/opt_cs.pdf">(pdf)</a> <br /> To appear in the special invited issue of <b> Games and Economic Behavior (GEB)</b> from STOC/FOCS/SODA 2012<br/> Shuchi Chawla, Jason Hartline, Balasubramanian Sivan<br /> (previously appeared in Workshop on Social Computing and User Generated Content, 2011) </p> <li> <p> <cite> Asymptotically Optimal Algorithm for Stochastic Adwords,</cite><b> ACM EC 2012 </b><a href="papers/2012/adwords_optimal.pdf">(pdf)</a><br /> Nikhil Devanur, Balasubramanian Sivan, Yossi Azar</p> <li> <p> <cite> Single-Call Mechanisms, </cite><b> ACM EC 2012 </b><a href="http://arxiv.org/pdf/1011.6134v3.pdf">(pdf)</a> <br /> Appeared in the special invited issue of <b> ACM Transactions on Economics and Computation (TEAC) </b> from EC 2012 <br/> Christopher A. Wilkens, Balasubramanian Sivan</p> <li> <p> <cite> Lower Bounds on Revenue of Approximately Optimal Auctions, </cite><b> WINE 2012 </b><a href="http://arxiv.org/pdf/1210.0275v1.pdf">(pdf)</a><br /> Balasubramanian Sivan, Vasilis Syrgkanis, Omer Tamuz</p> <li> <p> <cite> Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems </cite>, <b> ACM EC 2011 </b> <a href="papers/2011/online_stochastic.pdf">(pdf)</a> <br /> Nikhil Devanur, Kamal Jain, Balasubramanian Sivan, Chris Wilkens </p> <li> <p> <cite> Multi-Parameter Mechanism Design and Sequential Posted Pricing</cite>, <b> ACM STOC 2010 </b> <a href="http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.2435v2.pdf">(pdf)</a><br /> Shuchi Chawla, Jason Hartline, David Malec, Balasubramanian Sivan</p> <li> <p> <cite> The Power of Randomness in Bayesian Optimal Mechanism Design </cite>, <b> ACM EC 2010 </b> <a href="http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.3893v2.pdf">(pdf)</a><br /> Appeared in the special invited issue of <b> Games and Economic Behavior (GEB) </b> from EC 2010 and EC 2011<br/> Shuchi Chawla, David Malec, Balasubramanian Sivan</p> <li> <p> <cite>On Conditional Covering Problem</cite>, <b> Mathematics in Computer Science</b>, Special Issue on "Advances in Combinatorial Algorithms", <a href="http://www.springerlink.com/content/d77684p6133t3g25"> Birkhauser Basel,</a> 2009. <a href="papers/2009/MCS_paper">(pdf)</a> <br /> Balasubramanian Sivan, S. Harini, C. Pandurangan <br /> (previously appeared in the 19th International Workshop on Combinatorial Algorithms (<b>IWOCA</b>), Nagoya, Japan, 2008)</p> <li> <p> <cite>Core and Conditional Core Path of Specified Length in Special Classes of Graphs</cite>, <b> WALCOM 2009</b>, Third Annual Workshop on Algorithms and Computation, Kolkata, India. <a href="papers/2009/WALCOM_paper">(pdf)</a><br /> Balasubramanian Sivan, S. Harini, C.Pandurangan </p> </ul> <!--<h3> Courses </h3> <ul> <li> Fall 2011 <ul> <li> <a href="http://www.math.wisc.edu/~valko/courses/632/632.html"> Introduction to Stochastic Processes </a> </ul> <li> Spring 2011 <ul> <li> <a href="http://www.ssc.wisc.edu/~mrostek/713.htm"> Microeconomic Theory II </a> <li> <a href="http://pages.cs.wisc.edu/~shuchi/courses/880-S11/"> Algorithmic Game Theory </a> </ul> <li> Fall 2010 <ul> <li> <a href="http://www.ssc.wisc.edu/~jkennan/teaching/teaching.htm"> Microeconomic Theory I </a> <li> <a href="http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/"> Quantum Information Processing </a> </ul> <li> Spring 2009 <ul> <li> Stochastic Programming <li> Introduction to Real Analysis </ul> <li> Fall 2009 <ul> <li><a href="http://pages.cs.wisc.edu/~shuchi/courses/787-F09/">Advanced Algorithms </a> <li>Arithmetic Algorithms </ul> <li> Spring 2009 <ul> <li> Mathematical Techniques for the Analysis of Algorithms <li> <a href="http://pages.cs.wisc.edu/~cs764-1/"> Topics in Database Management Systems </a> </ul> <li> Fall 2008 <ul> <li> Complexity Theory <li> <a href="http://pages.cs.wisc.edu/~swift/classes/cs736-fa08/">Advanced Operating Systems</a> </ul> </ul>-->