Algorithmic Game Theory Project

Our class will culminate with a final project (and paper) that allows students to to explore material beyond what was covered in class and to share that material with other students. The project involves students researching and writing a paper on a topic of interest related to the topics of the class, giving a short presentation on the topic, and reading and evaluating other students' papers. Here is the "pipeline":

• By November 5, post on the blog a 2-paragraph outline of the topic you intend to explore, along with at least 2 references that you will be using as a starting point.
• Investigate the topic and write your paper (at least 2400 words, which translates to about 8 pages double-spaced, 12 point font, and then references).
• By December 5, submit your paper as a blog post.
• Prepare a short (20 minute) presentation on the topic. Presentations will occur in class December 6-8.
• By December 12, perform peer review of project reports from other students in the class (more details on this later).

There are a number of possibilities for what your project can be about. Here are some examples:

• Pick a research topic or 1-2 related research papers in algorithmic game theory to synthesize and explain. Formulate additional research questions related to what you have read. These could be theoretical questions or experimental questions. If you have the time and interest, explore some of these questions.

  Some possibilities for how you could find a topic:
  • Pick a chapter from this algorithmic game theory text (username=agt1user, password=camb2agt) and explore its contents. Some very interesting chapters that we probably won't have time to touch on much, if at all, are the chapters on "cryptography and game theory", "mechanism design without money", "incentives and pricing in communications networks", "incentives in peer-to-peer systems", "incentives and information security", "computational aspects of prediction markets", "manipulation-resistant reputation systems", "evolutionary game theory".
  • Pick a few sections that cover material we didn't cover in class from this book on multi-agent systems.
  • Explore papers in the Electronic Commerce conference, the World-Wide-Web conference (especially the monetization track), the Workshop on the Economics of Networks, Systems and Computation or another conference related to this field and find a paper that interests you. Notes: I've given links here only to the most recent of each of these conferences. But it should be easy for you to find earlier versions of the conferences online and many other possible papers/topics. (By the way, when you see a paper title that interests you, it is simply a matter of googling that title to find the actual paper.)
  • Some specific potentially hot topics: pricing of data in the cloud (see e.g. this paper), pricing of digital goods (see e.g. this paper), net neutrality (see e.g. this and this), crowd-sourcing (e.g. this), privacy (see e.g. this), incentives in distributed systems (see e.g. this and this), charity auctions (e.g. this), and ad exchanges.

• Pick a company and some aspect of its business and study it game theoretically. Define the goals and objectives of the company and the incentive structure involved in the service/products involved. Formulate the game and/or mechanism design problem involved. If you define a game, attempt to analyze it and understand its Nash equilibria. If you define a mechanism, make an attempt to analyze the mechanism used by the company and perhaps to propose alternative mechanisms. Explore the successes and failures of the company in terms of this business and any interesting related game-theoretic behavior.

  Here are few examples of companies/businesses/topics you could explore.
  • Twitter and its "trends in advertising"
  • Groupon
  • Quora
  • Swoopo (defunct)
  • Facebook and its social ads
  • Amazon and its advertising
  • Microsoft Cashback Program (defunct)
  • Bing Rewards
  • Google Advertising
  • Crowdsourcing systems such as Mechanical Turk. Here's an overview article about crowdsourcing.

• Study a mechanism that has been put into place by some government. What are the goals and what is the incentive structure for the participants? Is it working or not? Attempt to understand and analyze the mechanism game theoretically and propose alternatives.

  Here are some examples of such mechanisms that you could look into:
  • The mechanism used by San Francisco to price parking spots. For information, see this or this or this.
  • Dynamic pricing on express lanes, such as this example.
  • The recent troubled Medicare auctions. Here is a starting point.
  • Regulation of financial markets.
  • Incentives for teachers. Here is a sample starting point.

• Study game theory and its connections to another field, such as biology, sociology or politics. (There are huge literatures on all these topics -- you'll have to find a good set of starting points yourself.)

• Explore behavioral models for how people really play games and how this corroborates or contradicts the theoretical foundations of game theory. Here is an example paper on the topic.

If there is some other topic that interests you, talk to me about it and I may be able to help you find resources. I am very flexible about your topic.