CS 6840 : Lecture Schedule (tentative for the future) and
Scribe Notes

Spring 2017

·
Wednesday, Jan 25: introduction and overview, see notes

·
Friday, Jan 27: non-atomic congestion game (routing),
see notes and Section 11 in Roughgarden

·
Monday, Jan 30: Price of anarchy bound in routing games,
see notes and Section 11 in Roughgarden

·
Wednesday, Feb 1: Overprovisioning in routing, see notes and Section 12 in Roughgarden.

problem set 1 available on CMS

·
Friday, Feb 3: existence of equilibria in congestion games, potential
games, and best response, see notes, Section
13 of Roughgarden and Section 18.3 of the AGT book.

·
Monday, Feb 6: price of anarchy in atomic congestion games, see notes, and/or Section 12 of Roughgarden

·
Wednesday, Feb 8: a recipe for price of anarchy bound: smoothness, see
notes, and/or Section 14 of Roughgarden

·
Friday, Feb 10: robustness of PoA in smooth
games, mixed Nash equilibria and coarse correlated equilibria, see notes and/or Section 13 of Roughgarden

·
Monday, Feb 13: Correlated and Coarse Correlated equilibria, and NP
completeness finding the best (coarse correlated) equilibrium, see notes, and Section 13 of Roughgarden

·
Wednesday, Feb 15: Best-Case Analysis and strong Nash equilibria, see notes, and Section 15 of Roughgarden

·
Friday, Feb 17: learning in games: no-regret learning, learning
outcomes and its connection to CCE, see notes
and section 17 of Roughgarden

·
Monday, Feb 20: FEBRUARY BREAK

·
Wednesday, Feb 22: The multiplicative Weight Algorithm, see notes, and section 17 of Roughgarden, problem set
2 available on CMS

·
Friday, Feb 24: no-regret learning and two person 0-sum games, see notes, and section 18.3 of Roughgarden

·
Monday, Feb 27: learning in games with realistic feedback, see notes.

·
Wednesday, March 1: First Price Auction as a Bayesian game: finding
Nash, see notes, or section 2.1-2.3 of the auction survey, or Section 2.3
of Roughgarden

·
Friday, March 3: First Price Auction as a Bayesian game, smoothness
proof for the quality of outcomes, see notes,
and section 2.4 of the auction
survey.

·
Monday, March 6: All pay Auction as a game, smoothness proof for the
quality of outcomes, see notes.

·
Wednesday, March 8: Revenue equivalence: Myerson's lemma, see notes, and section 3.3 of Roughgarden

·
Friday, March 10: Smoothness framework for auctions, and multi-item
auctions, see notes, and sections 3.1 and 3.2
of the auction survey.

·
Monday, March 13: Bayes-Nash equilibria of multi-item auctions, and
the Framework of Smooth Auctions, the price of anarchy, see notes and sections 3.3 and sections 4.2 of the auction survey.

·
Wednesday, March 15: Cornell closed due to snow

·
Friday, March 17: The smoothness framework and Bayes-Nash equilibria
of second prize multi-item auctions, see notes.

·
Monday, March 20: The generalized second price auction (GSP), and Nash
equilibria, and its price of anarchy, see a draft of the notes

·
Wednesday, March 22: limit of price of anarchy results correlation,
and learning outcomes in auction games, see notes

·
Friday, March 24: classes of valuations: submodular, subadditive and fractionally subadditive,
see notes

·
Monday, March 27: more on valuations, see draft of notes

·
Wednesday, March 29: price of anarchy and players with fractionally subadditive valuations, see notes

·
Friday, March 31: discussion of some problem set 2 questions, see notes with discussion of problem (4a’) fixed on
April 8

·
April 1-9: SPRING BREAK

·
Monday, April 10: A multi-item auction with one dimensional bidding
space, see notes. Topic based on the paper Simple
Mechanisms for Agents with Complements.

·
Wednesday, April 12: truthful auctions/mechanism: the Vickrey-Clarke-Groves mechanism, see notes

·
Friday, April 14: empirical price of anarchy: on routing, and
inferring player values in auctions. For the routing example, see notes, and the paper Lili Qiu,
Yang Richard Yang, Yin Zhang, Scott Shenker: On selfish
routing in internet-like environments. SIGCOMM 2003: 151-162

·
Monday, April 17: inferring player values in auctions in Bayesian
environments or assuming players are no-regret learners, see** **notes and** Econometrics
for Learning Agents** by Denis Nekipelov, Vasilis
Syrgkanis, Eva Tardos, EC 2015.

·
Wednesday, April 19: bounding the empirical price of anarchy without
inferring player values, see notes, and **Robust
Data-Driven Efficiency Guarantees in Auctions** by Darrell Hoy,
Denis Nekipelov, Vasilis Syrgkanis

·
Friday, April 21: finishing empirical price of anarchy and (1-1/e)
bound for first price auction, see notes.

·
Monday, April 24: Fair sharing and bidding budgets only, see notes.

·
Wednesday, April 26: inferring distribution of values from
distribution of bids, see notes.

·
Friday, April 28: Guest lecture by Robert Kleinberg on learning to
select the best distribution using Gittins index. See the notes, and the slides from lecture.

·
Monday: May 1^{st}: Guest lecture by Sid Barenjee,
see notes, and Section 10.2 of the Roughgarden
book.

·
Wednesday, May 3^{rd}: estimating prices in maximizing
revenue, see notes. You can read more on
revenue in Section 3 of the Roughgarden book.

·
Friday, May 5^{th}: role of prizes in maximizing social
welfare in auction for a single item, see notes

·
Monday, May 8^{th}: pricing for multiple items with connection
to prices and smooth mechanisms, see notes.