CSC304 (Algorithmic Game Theory and Mechanism Design) Home Page (Fall 2016)

Please send any comments or questions to the instructor:

Announcements:

IMPORTANT: As many of you saw we had an issue with Markus which affected the submission for A3 for many people. Because of this we have moved the deadline for the assignment to this Friday at 3PM (start of tutorial). The submission is the same, submit to the same place to Assignment 3 on Markus. If you have already submitted successfully, then yu do not have to do anything more. And as before:You must submit the file A3.pdf No other file will be accepted.

For the remainder of the term, office hours by appointment. However, you are feee to drop by to see if I am available to meet.

You must use the Markus online system for all submissions.

  • Link to Markus Instructions for using Markus can be found here.

    • log in with your CDF credentials.

    IMPORTANT: You must save all graded work in case there is any inconsistency in what we have recorded and what you have.

    The tentative grading scheme and due dates and other administrative aspects of the course can be found in the course information sheet . The grading scheme is composed of 3 assignments, one term test and a final exam. (Please note that there was a typo on the course info sheet, saying that the term test would be Friday, November 5 but that should have been November 4. We confirmed in the Wednesday, October 26 class that the test will indeed be held Friday, November 4. As we discussed in class, every (sub) problem in any assignment or test will be worth some multiple of 5 points. You will receive 1/5 points for any (sub) problem for which you state "I do not know how to answer this question". You will receive .5/5 if you leave a question blank. If instead you submit irrelevant or erroneous answers you will lose the 1/5 points. That is, you will receive some credit for knowing what you don't know. You can also receive some additional credit for partial work that is clearly "on the right track". You are obliged to submit your own work! I provide a pragmatic clarification for distiguishing between genuine learning together and plagarism. If you have any questions please see the instructor immediately! Any cases of plagarism will be reported to the Faculty.

    IMPORTANT NOTE: I allow one page (double-sided) handwritten notes as an aid in all my tests and exams.

    Lecture slides will be posted here. My slides are just an overview of the lectures and in particular they will usually not contain proofs. I strongly recommend attending lectures as the lecture notes will certainly lack class discussion.
  • Lecture 1 Course administration, introduction; what this course is about.
  • Lecture 2 Games in normal form; basic game theory concepts; pure and mixed Nash equilibrium; the principle of indifference.
  • Lecture 3 More examples of 2 by 2 two plyaer games; the Tragedy of the Commons, i a brief critique of Nash equilibria.
  • Lecture 4 Zero-sum games; the minimax theorem; separating hyperplane theorem.
  • Lecture 5 LP formulation for computing the value of a zero-sum game; LP duality; Konig's bipartite maximum matching theorem; formalisms for games with many players.
  • Lecture 6 Guest lecture by Omer Lev; Games in extnsive form.
  • Lecture 7 Congestion games, potential games, Braess paradox.
    • Lecture 8 is guest lecture by Tyrone Strangway; see paper below.
  • Lecture 9 Start of mechanism desgin; defining combinatorial auctions; Vickrey auctionfor selling one item .
  • Lecture 10 Vickrey auction for selling one item, comparing 1st and 2nd price auctions, the revenue equivalence theorem.
  • Lecture 11 Continuing the discussion of the sale of a single item, the revenue equivalence theorem, the revelation principle, Myersons optimal revenue auction.
  • Lecture 12 Mechanism design, VCG, single parameter mechanism design
  • Lecture 13 Mechanism design, VCG some examples and proof of truthfulness, greedy algorithms for CAs, sponsored search.
  • Lecture 14 Comparing VCG snd GSP for sponsored search; envy-freeness; public projects problem
  • Lecture 15 Finish the revenue comparison of VCG snd GSP for sponsored search; combinatorial public projects problem; more general comments on when we can and can't have truthful mechanisms that have the same social welfare approximation factor as can be obtained when agents are not self interested and will not strategize.
  • Lecture 16 Begin matching markets; constricted sets, the ascending auction.
  • Lecture 17 Finish matching markets; the algorithmic proof of Hall's Matching Theorem
  • Lecture 18 Start mechanism design withou money; stable matching
  • Lecture 19 Finish discussion of stable matching
  • Lecture 20 Start discussion of social choice and voting
  • Lecture 21 Continue discussion of social choice and voting
    • Lecture 22 is guest lecture by Omer Lev on voting
  • Lecture 23 Fair division; the cake cutting problem

    • Assignments will be posted here.
  • Assignment 1 Assignment 1 is now complete.
  • Assignment 1 solutions Here are some solutions for Assignment 1.
  • Assignment 2 Assignment 2 is now complete.
  • Assignment 2 solutions Here are some solutions for Assignment 2.
  • Assignment 3 Assignment 3.
  • Assignment 3 solutions Here are some solutions for Assignment 3.

    • Additional references and papers will be posted here.

  • Link to LP solver Use this link to access an LP solver. Change the example to fit your LP.
  • Nisan-Ronen paper The seminal paper that started AGT.
  • Lehmann-O'Callahan-Shoham paper. One of the seminal AGT papers.
  • hartline-revenue. Jason Hartline lectures concerning Myerson's optimal revenue mechanism. This was mentioned by Tyrone in tutorial on Myerson.
  • Pricing equilibria. The paper that was the basis for Tyrone Strangways lecture.