Advanced Algorithms: Applications of Algorithmic Game Theory

Computer Science 6822
Spring 2009

Instructor: Éva Tardos

Time: Monday and Wednesday 2:30-3:45 

First class: Monday, January 26 (class on Jan 19&21 is cancelled)

Place: 1150 Snee Hall

Office Hours: Fridays 2:30-3:30

• Office:         4130 Upson
• phone:         255-0984  
• email:           eva at cs.cornell.edu
• You can also send me email to make an appointment.

Overview

Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will focus on applications of these ideas in a range of field including mechanism design and keyword auctions used in sponsored search auctions.

Book and Materials

We will use Parts II and IV of the book: Algorithmic Game Theory, and supplement it with additional papers.

Thanks to our progressive-minded publisher you can read the entire book Algorithmic Game Theory (eds. Nisan, Roughgarden, Tardos, Vazirani) online by clicking here (username=agt1user, password=camb2agt).

Another excellent textbook that covers several of the course's topics is Shoham and Leyton-Brown, Multiagent Systems, Cambridge, 2008.

Weekly Schedule and readings:

• Interesting panel discussion on Sponsored Search Research from 2006 http://www.cis.upenn.edu/~mkearns/teaching/SponsoredSearch/panel-SSA-06.pdf
• Jan 19&21 no class
• Jan 26&28&Feb 2: sponsored search pricing and GSP auctions (generalized second price auction):  See  the notes from INFO 2040 of D. Easley and J. Kleinberg (from a preliminary draft of their book).
• Edelman/Ostrovsky/Schwarz, Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords, American Economic Review, 2007. Feb 2&4
• Feb 4&9&11: Truthful auctions, VCG, and applications to keyword auctions and combinatorial auctions. See  Tim Roughgarden's lecture notes.
• Feb 16 Bayesian mechanism design. See  Hartline's lecture notes or Chapter 13
• Feb 18&23: First prize auction and the revenue equivalence theorem
• Feb 25: revenue maximization in auctions for digital goods. See  Hartline's lecture notes or Chapter 13.
• March 2: Sponsored search with Budgets: see Chapter 28: Sponsored Search Auctions, by Sebastian Lahaire, David Pennock, Amin Saberi, and Rakesh Vohra from  the book Algorithmic Game Theory. or see ``Adwords and Generalized Online Matching'', A. Mehta, A. Saberi, U. Vazirani and V. Vazirani, Journal of ACM 54(5), 2007.

Wed. March 5	Georgios Piliouras	Dynamics of Bid Optimization in Online Advertisement Auctions
Mon, March 9	Vasumathi Raman	Cost of Conciseness in Sponsored Search Auctions
Wed. March 11	Maurice Yuk Leung Cheung	Chapter 12:  Computationally Efficient Approximation Mechanisms
March 16&18	SPRING BREAK
Mon March 23	cancelled, see talk at 4:15	by Daron Acemoglu  (MIT, Economics)
Wed March 25	guest lectures	by Joe Halpern
Mon March 31	Igor Gorodezky and Joel Nishimura	Chapter 26: Computational Aspects of Prediction Markets,
Mon Apr 1	Jiawei Qian	Truthful Approximation Schemes for Single-Parameter Agents
Wed Apr 6	Katherine Lai	Chapter 14: Distributed Algorithmic Mechanism Design
Wed Apr 8	Huijia Rachel Lin	Games for exchanging information.
Mon Apr 13	Renato Paes Leme & Stephen Purpura	Optimal Envy-Free Pricing with Metric Substitutability
Wed Apr 15	Matt Paff and Seth Matthew Weinberg	Chapter 10: Mechanism Design without Money
Mon Apr 20	Tal Rusak	Interdomain Routing and Games
Wed Apr 22	Eric Frackleton	Vindictive Bidding in Keyword Auctions,
Mon Apr 27	Di Wang	Chapter 16: Online Mechanisms
Wed Apr 29	Thanh Nguyen	Chapter 25: Incentives and Information Security

Ideas for Papers to be Presented in Class

Selecting papers.

• Please send me email by February 18 with your choice of paper to present, and choice of date. Early dates are great!
• Below is a list of papers that can be selected for presentation in class. You can also make suggestions for other papers, if you have ideas on related papers you would like to present that are not on the list.
• You can either select a paper, or pair up, and select a pair of related papers for two people.
• For presenting your paper, you need to read and understand the paper you are presenting, and understand what is out there in related work. For older paper you may want to use Google scholar or citeseer to look for followup papers, for more recent papers you also need to understand what may have been some related previous papers.
• Once you selected a paper, and understood how much time you need for preparing a presentation, please reserve a time. You can select any Mon or Wed during the semester starting with Monday Feb 23.
• Send me email if you know which paper you want to select, and what date may work for you.
• Selecting early dates would be very appreciated, so we have room for everyone!

Chapters from the book Algorithmic Game Theory (eds. Nisan, Roughgarden, Tardos, Vazirani) online by clicking here (username=agt1user, password=camb2agt).

• (claimed) Chapter 10: Mechanism Design without Money, by James Schummer and Rakesh Vohra,
• Section 11.4-6: Combinatorial Auctions (subsections about Bidding languages for auctions), by Liad Blumrosen and Noam Nisan.

• (claimed) Chapter 12:  Computationally Efficient Approximation Mechanisms, by Ron Lavi

• (claimed) Chapter 14: Distributed Algorithmic Mechanism Design, by Joan Feigenbaum, Michael Schapira and Scott Shenker

• (claimed) Chapter 16: Online Mechanisms, by David Parkes

Papers about different aspects of Sponsored Search:

• Auction Design

  • Bayesian: Edelman/Schwarz, Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions, Working paper, 2006.

  • (claimed) Cost of Conciseness in Sponsored Search Auctions, Abrams, Z.; Ghosh, A.; Vee, E, WWW'07

  • Sponsored search with contexts. E. Even-Dar, M. Kearns, and J. Wortman: from WINE 2007

  • Computing Optimal Bundles for Sponsored Search Ghosh, Arpita ; Nazerzadeh, Hamid ; Sundararajan, Mukund, WINE '07 and Mixed Bundling Auctions by P. Jehiel, M. Meyer-ter-Vehn, and B. Moldovanu. 

  • An Online Mechanism for Ad Slot Reservations with Cancellations Florin Constantin, Jon Feldman, S. Muthukrishnan and Martin Pál, from SODA'09

  • (claimed) Zhou/Lukose, Vindictive Bidding in Keyword Auctions, SSA '06.

• Dynamic issues

  • (claimed) Dynamics of Bid Optimization in Online Advertisement Auctions , WWW’07, by Christian Borgs, Jennifer Chayes, Omid Etesami, Nicole Immorlica, Kamal Jain, Mohammad Mahdian

  • Greedy Bidding Strategies for Keyword Auctions (On Bidding strategies and dynamic issues in GSP auctions). Cary/Das/Edelman/Giotis/Heimerl/Mathieu/Schwarz,  from EC'07

• Revenue and Social welfare
  • (claimed) Optimal Envy-Free Pricing with Metric Substitutability Ning Chen, Arpita Ghosh, Sergei Vassilvitskii from EC'08
  • Revenue Analysis of a Family of Ranking Rules for Keyword Auctions  Sebastien Lahaie and David Pennock,
  • "An Analysis of Alternative Slot Auction Designs for Sponsored Search". Lahaie. EC’06,

• Bidder Optimization

  • Budget Optimization in Search-Based Advertising Auctions, Jon Feldman, S. Muthukrishnan; Martin Pal, Cliff Stein

Papers about algorithms for Auctions

• Balcan, Blum, Hartline, Mansour, "Mechanism Design via Machine Learning", FOCS 2005: http://www.ece.northwestern.edu/~hartline/papers/auctions-FOCS-05.pdf

• Analyzing an eqilibrium for a repeated auction: Mechanism Design by Competing Sellers, McAfee, R. P. (1993) . Econometrica, 61, 1281-1312.

• Goldberg, Hartline, Karlin, Saks, and Wright, "Competitive Auctions", 2006. [pdf]

• Baliga and Vohra, "Market Research and Market Design", 2003. [link]

• Hartline and T. Roughgarden, Optimal Mechanism Design and Money Burning, STOC '08.

• (claimed) P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden, Truthful Approximation Schemes for Single-Parameter Agents, full version of FOCS '08 paper.

• Posted prices vs. negotations: an asymptotic analysis
  Liad Blumrosen, Thomas Holenstein https://research.microsoft.com/pubs/75840/postedprice.pdf from EC'08

Other applications of Game theory

• (claimed) Interdomain Routing and Games Hagay Levin, Michael Schapira, Aviv Zohar  http://dimacs.rutgers.edu/Workshops/EconomicTheory/slides/zohar.pdf

• The Myth of the Folk Theorem (about equilibria of repeated games) Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, Christos Papadimitriou, FOCS'08.

• Other chapters from the book Algorithmic Game Theory (eds. Nisan, Roughgarden, Tardos, Vazirani) online by clicking here (username=agt1user, password=camb2agt).

  • Chapter 23, Incentives in Peer-to-Peer systems, Moshe Babaioff, John Chuang, Michal Feldman,

  • (claimed) Chapter 25: Incentives and Information Security, Ross Anderson, Tyler Moore, Shishir Nagarajan, and Andy Ozmen

  • (claimed) Chapter 26: Computational Aspects of Prediction Markets, by David Pennock and Rahul Sami

Pre-requisites

The course pre-requisites is background in algorithms and graphs at the level of CS 482. No prior knowledge of game theory or economics will be assumed: we will start with a quick introduction on the necessary background. Course grade will be based on the presentation, and on class participation

Course work

This is a seminar-style course in which students will read and present papers.

Topics

I will start the course with a few week overview of games, and mechanism design using Chapters 1, 9 and 10 of the Algorithmic Game Theory book. After the initial weeks, students will present sections of the book, or related papers. We will cover some of the Chapters 11-16 on Mechanism Design, and some of the additional topics: 22, 23, 15, 26, 27 and 28, especially expanding on Sponsored Search.

Similar Courses

There are many similar course offered at other schools too: For courses on sponsored search see http://theory.stanford.edu/~tim/f07/f07.html and http://www.cis.upenn.edu/~mkearns/teaching/SponsoredSearch/. Also Game Theory . net offers a wide range of game theory courses.