Jason Hartline, Associate Professor

jason-costa-ricaProf. Hartline’s research introduces design and analysis methodologies from computer science to understand and improve outcomes of economic systems. Optimal behavior and outcomes in complex environments are complex and, therefore, should not be expected; instead, the theory of approximation can show that simple and natural behaviors are approximately optimal in complex environments. This approach is applied to auction theory and mechanism design in his graduate textbook Mechanism Design and Approximation which is under preparation.

Prof. Hartline received his Ph.D. in 2003 from the University of Washington under the supervision of Anna Karlin. He was a postdoctoral fellow at Carnegie Mellon University under the supervision of Avrim Blum; and subsequently a researcher at Microsoft Research in Silicon Valley. He joined Northwestern University in 2008 where he is an associate professor of computer science. He was on sabbatical at Harvard University in the Economics Department during the 2014 calendar year and visiting Microsoft Research, New England for the Spring of 2015.

Curriculum Vitae: [pdf]

Publications. (in reverse-chronological order)

  • Bayesian Budget Feasibility with Posted Pricing, with Eric Balkanski [arxiv]
  • Non-revelation Mechanism Design, with Samuel Taggart, Working paper, 2016. [arxiv]
  • A/B Testing of Auctions, with Shuchi Chawla and Denis Nekipelov, EC 2016. [arxiv]
  • Optimal auctions vs. anonymous pricing, with Saeed Alaei, Rad Niazadeh, Manolis Pountourakis, and Yang Yuan, FOCS 2015. [arxiv]
  • Non-optimal Mechanism Design, with Brendan Lucier, American Economic Review 2015. [link]
  • Bayesian Incentive Compatibility via Matching, with Bobby Kleinberg and Azarakhsh Malekian, Games and Economic Behavior 2015. [link]
  • Optimal Crowdsourcing Contests, with Shuchi Chawla and Balu Sivan, Games and Economic Behavior 2015. [link]
  • Multi-dimensional Virtual Values and Second-degree Price Discrimination, with Nima Haghpanah. Working paper, 2014-2016. [arxiv]
  • Mechanism Design for Data Science, with Shuchi Chawla and Denis Nekipelov. EC 2014. [arxiv]
  • Price of Anarchy for Revenue, with Darrell Hoy and Samuel Taggart. EC 2014. [arxiv]
  • Optimal Auctions for Correlated Buyers with Sampling, with Hu Fu, Nima Haghpanah, and Robert Kleinberg. EC 2014. [arxiv]
  • The Simple Economics of Approximately Optimal Auctions, with Saeed Alaei, Hu Fu, Nima Haghpanah. FOCS 2013. [pdf] [arXiv]
  • Bayesian Mechanism Design (a survey), Foundations and Trends in Theoretical Computer Science 2013. [pdf] [link]
  • Auction with Unique Equilibria, with Shuchi Chawla, EC 2013. [pdf]
  • Prior-independent Auctions for Risk-averse Agents, with Hu Fu and Darrell Hoy. EC 2013. [pdf] [arXiv]
  • Prior-free Auctions for Budgeted Agents, with Nikhil Devanur and Bach Ha. EC 2013. [pdf] [arXiv]
  • Prior-independent Mechanisms for Scheduling, with Shuchi Chawla, David Malec, and Balu Sivan, STOC 2013. [pdf] [arXiv]
  • Badminton and the Science of Rulemaking, with Robert Kleinberg. Huffington Post, 2012. [link]
  • The Biased Sampling Profit Extraction Auction, with Bach Ha. Working paper, 2012. [arXiv]
  • Approximation in Mechanism Design, AER: Papers and Proceedings 2012[pdf]
  • Bayesian Optimal Auctions via Multi- to Single-agent Reduction, with Saeed Alaei, Hu Fu, Nima Haghpanah, and Azarakhsh Malekian, EC 2012 [abstract] [arXiv]
  • Optimal Crowdsourcing Contests, with Shuchi Chawla and Balu Sivan. SODA 2012. [arXiv] [video1] [video2]
  • Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction with Bach Ha. SODA 2012 and TEAC 2012. [pdf]
  • Prior-independent Multi-Parameter Mechanism Design, with Nikhil Devanur, Anna Karlin, and Thach Nguyen. WINE 2011. [pdf]
  • Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction, with Bach Ha. SODA 2012. [arXiv]
  • Truth, Envy, and Profit, with Qiqi Yan. EC 2011. [pdf]
  • Derandomization of Auctions, with Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Nicole Immorlica, and Madhu Sudan, GEB 2011. [link]
  • Bayesian Incentive Compatibility and Matchings, with Robert Kleinberg and Azarakhsh Malekian. SODA 2011. [pdf]
  • Multi-parameter Mechanism Design and Sequential Posted Pricing, with Shuchi Chawla, David Malec, and Balasubramanian Sivan. STOC 2010.[pdf]
  • Bayesian Algorithmic Mechanism Design, with Brendan Lucier. STOC 2010. [pdf]
  • Simple versus Optimal Mechanisms, with Tim Roughgarden. EC 2009.[pdf]
  • Limited and Online Supply and the Bayesian Foundations of Prior-free Mechanism Design, with Nikhil Devanur. EC 2009. [pdf]
  • Selling Ad Campaigns: Online Algorithms with Cancellations, with Moshe Babaioff and Robert Kleinberg. EC 2009. [pdf]
  • Reducing Mechanism Design to Algorithm Design via Machine Learning, with Nina Balcan, Avrim Blum, and Yishay Mansour. JCSS, December 2008. [link] (Preprints: [ps] [pdf])
  • Position Auctions and Non-uniform Conversion Rates, with Liad Blumrosen and Shuzhen Nong. Workshop on Ad Auctions 2008 (no proceedings). [ps][pdf]
  • Optimal Mechanism Design and Money Burning, with Tim Roughgarden. STOC 2008. [ps] [pdf] (Full version recommended [link])
  • Optimal Marketing Strategies over Social Networks, with Vahab Mirrokni and Mukund Sundararajan. WWW 2008. [pdf]
  • Auctions for Structured Procurement, with Matthew Cary, Abraham Flaxman, and Anna Karlin. SODA 2008. [ps] [pdf]
  • Book Chapter: Profit Maximization in Mechanism Design, with Anna Karlin. In Algorithmic Game Theory, Editors: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vizarani, October 2007. [web site] (Based loosely onTopics in Algorithmic Game Theory course notes [pdf] [ps])
  • Algorithmic Pricing via Virtual Valuations, with Shuchi Chawla and Robert Kleinberg. EC 2007. [ps] [pdf] (Full version recommended [arXiv])
  • Bayesian Optimal No-deficit Mechanism Design, with Shuchi Chawla, R. Ravi, and Uday Rajan. WINE 2006. [ps] [pdf]
  • Transcript of panel discussion: Models for Sponsored Search: What are the right questions? Speakers: Kamal Jain, David Pennock, Michael Schwarz, and Rakesh Vohra. EC 2006. [ps] [pdf]
  • Competitive Auctions, with Andrew Goldberg, Anna Karlin, Mike Saks, and Andrew Wright, Games and Economic Behavior, 2006. [ps] [pdf]
  • Knapsack Auctions, with Gagan Aggarwal, SODA 2006 [ps] [pdf]
  • On the competitive ratio of the random sampling auction, with Uriel Feige, Abraham Flaxman, and Robert Kleinberg, WINE 2005 [ps] [pdf]
  • Mechanism Design via Machine Learning, with Maria-Florina Balcan, Avrim Blum, and Yishay Mansour, FOCS 2005 [pdf] (Full version recommended[ps] [pdf])
  • Near-Optimal Pricing in Near-Linear Time, with Vladlen Koltun, WADS 2005[ps] [pdf]
  • From Optimal Limited to Unlimited Supply Auctions, with Robert McGrew, EC 2005. [ps] [pdf]
  • Derandomization of Auctions, with Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Nicole Immorlica, and Madhu Sudan, STOC 2005. [ps] [pdf]
  • Near-Optimal Online Auctions, with Avrim Blum, SODA 2005. [ps] [pdf]
  • On Profit-Maximizing Envy-Free Pricing, with Venkat Guruswami, Anna Karlin, David Kempe, Claire Kenyon, and Frank McSherry, SODA 2005. [ps][pdf]
  • Collusion-Resistant Mechanisms for Single Parameter Agents, with Andrew Goldberg, SODA 2005. [ps] [pdf] (Full Version: MSR-TR-2004-40)
  • A Lower Bound on the Competitive Ratio of Truthful Auctions, with Andrew Goldberg, Anna Karlin, and Mike Saks, STACS 2004. [ps] [pdf]
  • Optimization in the Private Value Model: Competitive Analysis Applied to Auction Design, Ph.D. Thesis, Aug. 2003. [ps] [pdf]
  • Envy-Free Auctions for Digital Goods, with Andrew Goldberg, EC 2003.[ps] [pdf]
  • Competitiveness via Consensus, with Andrew Goldberg, SODA 2003. [ps][pdf]
  • Characterizing History Independent Data Structures, with Edwin Hong, Alexander Mohr, William Pentney, and Emily Rocke, ISAAC 2002. (© Springer-Verlag) [ps] [pdf]
    (Full version appears in special issue of Algorithmica [ps] [pdf])
  • Truthful and Competitive Double Auctions, with Kaustubh Deshmukh, Andrew Goldberg, and Anna Karlin, ESA 2002. (© Springer-Verlag) [ps][pdf] (Full version [ps] [pdf])
  • Competitive Generalized Auctions, with Amos Fiat, Andrew Goldberg, and Anna Karlin, STOC 2002. [ps] [pdf]
  • Competitive Auctions for Multiple Digital Goods, with Andrew Goldberg, ESA 2001. (© Springer-Verlag) [ps] [pdf]
  • An Experimental Study of Data Migration Algorithms, with Eric Anderson, Joe Hall, Michael Hobbes, Anna Karlin, Jared Saia, Ram Swaminathan, and John Wilkes. Workshop on Algorithm Engineering, WAE 2001. [ps][pdf]
  • Competitive Auctions and Digital Goods, with Andrew Goldberg and Andrew Wright, SODA 2001. [ps] [pdf]
    (Full Version, see Competitive Auctions, above)
  • On Algorithms for Efficient Data Migration, with Joe Hall, Anna Karlin, Jared Saia, and John Wilkes, SODA 2001. [ps] [pdf]