Jason Hartline

Prof. Hartline is on sabbatical at Harvard Economics and Computer Science Departments for the 2014 calendar year (January 2014-December 2014).

Prof. 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 is currently on sabbatical at Harvard University.

Curriculum Vitae: [pdf]

Publications. (in reverse-chronological order)

  • Reverse Mechanism Design, with Nima Haghpanah. Working paper, 2014. [arxiv]

  • Mechanism Design for Data Science, with Shuchi Chawla and Denis Nekipelov. EC 2014. [arxiv] [video]

  • 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] [video (Saeed)]

  • 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] [video]

  • 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] [video (Bobby)]

  • 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] [video (Brendan)]

  • 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] [audio] (Full version recommended [link])

  • Optimal Marketing Strategies over Social Networks, with Vahab Mirrokni and Mukund Sundararajan. WWW 2008. [pdf] [video (Mukund)]

  • 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 on Topics 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]


Kleinberg and Tardos, Algorithm Design, 2005.

EECS 336: Introduction to Algorithms (Fall 2013)

Required Text: Kleinberg and Tardos, Algorithm Design, 2005.
Discussion/Announcements/Homeworks/etc: on Piazza.

Lectures: Tuesday and Thursday 3:30-4:50 in Tech M345.
Instructor: Jason D. Hartline.
Office Hours: Tuesday, 1:00-2:50, or by appt.; Ford 3-329.

Teaching Assistant: Sam Taggart
Lab Sections: Monday, various times.
Office Hours: Wednesday, 10:30-12:00; Tech B252.

Overview. Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study optimization. This course provides an introduction to algorithm design through a survey of the common algorithm design paradigms of greedy optimization, divide and conquer, dynamic programming, network flows, reductions, and randomized algorithms. Important themes that will be developed in the course include the algorithmic abstraction-design-analysis process and computational tractability (e.g., NP-completeness).

Prerequisites. EECS 212 (Mathematical Foundations of Computer Science) and EECS 214 (Data Structures and Data Management) which cover abstract data types such as stacks, queues, and binary search trees; and discrete mathematics such as recurrence relations, sets, and graphs.

Grading. 50% Homework, 15% Midterm, 25% Final, 10% Participation.

Homework Policy. Homeworks may be done in pairs by students in the same section. Both students must contribute to the solution of all problems. One copy of the assignment should be turned in with the names of both students on it. Both students will receive the same grade. You may consult your text book and course notes when answering homework questions; you must not consult the Internet. Homeworks are assigned in class and due at the beginning of class on Thursday the week after (or as noted). Late homework will be accepted until Monday (at the beginning of your section) and will be marked down by 25% of the grade received.

Tentative Schedule:

Week 1: beginning Sept. 23

  • Course overview: computing Fibonacci numbers. (Chapter 1)
  • Review of runtime analysis, graphs, and basic graph algorithms. (Chapters 2 and 3)

Week 2: beginning Sept. 30

  • Greedy algorithms: interval scheduling. (Chapter 4)
  • Greedy algorithms: minimum spanning trees, matroids. (Chapter 4, Matroid Notes)

Week 3: beginning Oct. 7

  • Greedy algorithms: shortest paths, MSTs. (Chapter 4)
  • Divide and conquer: merge sort, recurrence relations, public key cryptography, repeated squaring (Chapter 5)

Week 4: beginning Oct. 14

  • Divide and conquer: integer multiply, convolution, fast Fourier transform (Chapter 5)
  • Dynamic programming: memoization, weighted interval scheduling, integer knapsack (Chapter 6)

Week 5: beginning Oct. 21

  • Dynamic programming: all pairs shortest paths (Chapter 6)
  • Reductions, Network flow, Bipartite Matching (Chapter 7)

Week 6: beginning Oct. 28

  • Network flow. (Chapter 7)

Week 7: beginning Nov. 4

  • NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8)
  • NP and intractability: NP, circuit sat (Chapter 8)

Week 8: beginning Nov. 11

  • NP and intractability: circuit sat, 3-sat (Chapter 8)
  • NP and intractability: independent set, vertex cover, hamiltonian cycle, TSP.

Week 9: beginning Nov. 18

  • Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11)
  • Approximation algorithms: pseudo polynomial time, PTAS, knapsack (Chapter 11)

Week 10+: beginning Nov. 25

  • Online algorithms: ski-renter, secretary.
  • TBA.
  • FINAL (cumulative).


more news