Introduction; Class overview Examples of games and pure equilibria A global network connection game; congestion games; and the potential function method Price of stability

Nash Equilibria for Bimatrix Games By Dimitris Paparas and Vasilis Gkatzelis Graphical Games By Matthew D'Zmura

Apr 28

Student presentations

Sink Equilibrium and Best-Reply Mechanism By Yundi Zhang Bargaining Solutions for Licensing Negotiations By Sebastian Zimmeck Graphical Games By Barbara Kiskovski and Melanie Kambadur

April 29

Student presentations

A Survey of Two-Player Games in Intrusion Detection By Yi Zhang and Minglei Wang Application of Stackelberg Games in Security By Rui Liu and Yifu Zheng On the Severity of Braess' Paradox By Wei Han A Survey of Incentives for Peer-to-peer Networks By Delia Wang

## Date

## Topic

## Readings

## Exercises

## Notes

Examples of games and pure equilibria

A global network connection game; congestion

games; and the potential function method

Price of stability

Algorithmic Game Theory, By Roughgarden

The Price of Stability for Network Design with Fair Cost Allocation

By Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler and Roughgarden

By Sebastian Zimmeck

of pure equilibria in congestion games; and

the complexity class PLS

Price of anarchy in selfish routing

Convergence to Approximate Nash Equilibria in Congestion Games

By Chien and Sinclair

The Complexity of Pure Nash Equilibria

By Fabrikant, Papadimitriou and Talwar

How Easy is Local Search?

By Johnson, Papadimitriou and Yannakakis

How Bad Is Selfish Routing?

By Roughgarden and Tardos

By Delia Wang

Two-player zero-sum games

Minmax theorem and linear duality

Lecture Notes on Linear Duality

By Trevisan

Game Theory, On-line Prediction and Boosting

By Freund and Schapire

When the Players Are Not Expectation Maximizers

By Fiat and Papadimitriou

Randomized Algorithms: Section 2.2, The Minimax Principle

By Motwani and Raghavan

By Yifu Zheng and Rui Liu

Brouwer's fixed point theorem

via Sperner's lemma

By Nash

The Nash Equilibrium: A Perspective

By Holt and Roth

The Mathematics of Strategy

By Klarreich

Sperner's Lemma and Brouwer's Fixed Point Theorem

By Wright

Atropos: The Sperner Game

By Burke and Teng

IMDB: A Beautiful Mind (2001)

By Barbara Kiskovski

and Melanie Kambadur

Approximation of Nash equilibria with

small supports

By Lipton, Markakis and Mehta

Approximating Nash Equilibria Using Small-Support Strategies

By Feder, Nazerzadeh and Saberi

Probability Inequalities for Sums of Bounded Random Variables

By Hoeffding

Hoeffding's Inequality on Wikipedia

By Yundi Zhang

By Daskalakis, Goldberg and Papadimitriou

Recent Development in Computational Complexity

Characterization of Nash Equilibrium, By Chen and Deng

The Complexity of Computing a Nash Equilibrium

By Daskalakis, Goldberg and Papadimitriou

Settling the Complexity of Computing Two-player Nash Equilibria

By Chen, Deng and Teng

lecture I gave at USC

can be found here

(The construction

there is slightly

more detailed.)

Exchange markets

and existence of market equilibria

By Arrow and Debreu

General Equilibrium and the Theory of Directed Graph

By Maxfield

Nash and Walras Equilibrium via Brouwer

By Geanakoplos

A Complexity View of Markets with Social Influence

By Chen and Teng

for Fisher's model with linear utilities

How to Compute Equilibrium Prices in 1891

By Brainard and Scarf

Consensus of Subjective Probabilities: The Pari-Mutuel Method

By Eisenberg and Gale

Market Equilibrium via a Primal-Dual Algorithm for a Convex Program

By Devanur, Papadimitriou, Saberi and Vazirani

The Computation of Market Equilibria

By Codenotti, Pemmaraju and Varadarajan

By Yi Zhang and Minglei Wang

Arrow's impossibility theorem

The Gibbardâ€“Satterthwaite theorem

Incentive compatibility

VCG mechanisms

Myerson's optimal mechanism

Optimal Auction Design

By Myerson

Lectures on Optimal Mechanism Design

By Hartline

Cross-monotone cost-sharing schemes

and group incentive compatible mechanisms

On Balanced Sets and Cores

By Shapley

Incremental Cost Sharing: Characterization by

Coalition Strategy-Proofness

By Moulin

Strategyproof Sharing of Submodular Costs: Budget Balance

versus Efficiency By Moulin and Shenker

Sharing the Cost of Multicast Transmissions

By Feigenbaum, Papadimitriou and Shenker

By Dimitris Paparas and Vasilis Gkatzelis

Graphical Games

By Matthew D'Zmura

By Yundi Zhang

Bargaining Solutions for Licensing Negotiations

By Sebastian Zimmeck

Graphical Games

By Barbara Kiskovski and Melanie Kambadur

By Yi Zhang and Minglei Wang

Application of Stackelberg Games in Security

By Rui Liu and Yifu Zheng

On the Severity of Braess' Paradox

By Wei Han

A Survey of Incentives for Peer-to-peer Networks

By Delia Wang