ALGORITHMIC GAME THEORY

Comp761/Math761 - Fall Term, 2008.

General Information.

  • Course Instructor
  • Teaching Assistant
  • Lectures
  • Topics
  • Prerequisites
  • Textbook
  • Assignments

    Instructor.

  • Prof. Adrian Vetta
  • Telephone: 398-3822
  • Office: Room 1118, Burnside Building
  • Office hours: Wednesday, 2.30-4pm.
  • Email: vetta at math.mcgill.ca
    • Top
    Top

    Lectures.

  • Time: Tuesday and Thursday, 2.30pm-4pm.
  • Location: Room 1234, Burnside Bldg.
    • Top

    Topics.

    We consider the area of algorithmic game theory. We are interested in combining ideas
    from economics (such as rationality and mechanism design) with concepts from theoretical computer
    science (such as complexity and algorithm design) and applying them to "real-world" problems. Our approach
    will be entirely mathematical. Theoretical concepts will, however, be complemented by examples drawn mainly
    from computer science, e.g. network and traffic routing, online auctions, bandwidth allocation,
    webpage advertising etc.

  • Specific topics for study include: Equilibria: e.g. Nash equilibria; Correlated equilibria; Sink equilibria.
  • Auctions: e.g. Combinatorial Auctions; Online Auctions.
  • Mechanism Design e.g. Pricing Mechanisms; Cost Sharing.
  • Coalition Games.
  • Complexity: Algorithms and Hardness results.

    A list of the lectures as well as additional course notes be found here.
    Top

    Co-requisites.

    This course is primarily aimed at graduate students in mathematics, computer science
    or economics. No formal experience with this topic will be needed, but a strong mathematical
    background is necessary.
    Top

    Textbooks.

    The course textbook is
  • Algorithmic Game Theory by Nisan, Roughgarden, Tardos and Vazirani.

    Top

    Assignments.

    Course grades will be based upon assignments (30%) and a project (70%).

    Assignments are posted here.

    Here is a list of possible projects.
    Top