Topics in Computing for Society

CSE 290T:  Topics in Computing for Society

Game Theory & Applications in Computer Science & Engineering

Announcements:

On Tuesday April 9, the lecture will be delivered via Zoom. This is because the instructor needs to be out of town. You should plan to attend remotely and use the following Zoom link.
https://ucsc.zoom.us/j/92464133769?pwd=d0g4bUJzK2JUNzUvai9iWGRUUHZjZz09

Instructor

John Musacchio
Office: E2-557
johnm@soe.ucsc.edu

Lectures

Tuesdays & Thursdays 11:40 AM - 1:15 PM
McHenry Lib 1350

Description

This course covers the fundamentals of game-theory with a focus on game-theory's connections to computer science and engineering. These connections go in both directions. For example, computer science complexity theory sheds light on whether equilibria concepts from game-theory are plausible predictions of behavior by assessing whether computing an equilibrium is a tractable problem. Game-theory informs computer science about how the incentives of different users and/or stake holders of a computing system can lead to undesirable outcomes (e.g. poor utility across users, congestion, systems with serious security vulnerabilities...)  It also provides a framework for analyzing the performance of various kinds of distributed systems, such as networks like the internet whose congestion is managed by end-to-end rate control. We will also study mechanism design -- how games can be designed to achieve more desirable outcomes. Mechanism design has many applications in computing and engineered systems, such as the creation of markets of advertising on the internet (which has been a multibillion dollar market for over a decade), markets to allocate radio spectrum with complicated interference constraints, and markets for electricity.

The course uses game-theory textbooks, like the classic Game Theory textbook by MIT economist Drew Fudenberg and Nobel Laureate Jean Tirole, as well as key papers for more in-depth study of particular computer science to game-theory connections. We will also make extensive use of a compiled book titled Algorithmic Game Theory that has contributed chapters from many of the leading thought leaders on the connections between game theory and computer science.

Reading Material (Tentative)

Books:

		[AGT ’07] N. Nisan, T. Roughgarden, E ́. Tardos, & V. Vazirani, ed., Algorithmic Game Theory, Cambridge University Press, 2007. 29-51.       Specific contributed chapters: [AGT Papadimitriou] C. Papadimitriou, “The Complexity of Finding Nash Equilibria,” 29-51. [AGT Vazirani] V. Vazirani, “Combinatorial Algorithms for Market Equilibria,” 103-134. [AGT T&W] E ́. Tardos and T Wexler, “Network Formation Games and the Potential Function Method,” 487-516. [AGT Roughgarden] T. Roughgarden, “Routing Games,”  461-486. Acquisition: FREE ONLINE: [link] -Click in this under the book picture: -Then click on "Algorithmic Game Theory": -Then click on "Algorithmic Game Theory": Or buy a hard copy on Amazon: [link] (~$72 new, ~$50 used)
		[F & T '91] D. Fudenberg & J. Tirole, Game Theory, MIT Press, 1991. Acquisition: Buy on Amazon: [link] (~$74 Hardcover or Kindle, ~$40 paper back) UCSC Library Online access: [link] (Only one student at a time)

Other Readings:

[H '17] J. Hespanha, Noncooperative Game Theory: An Introduction for Engineers and Computer Scientists, Princeton University Press, 2017. Acquisition Optional: Amazon: [link]

Lecture Log

Lect#	Date	day	notes	topics	readings
1	April 2	Tu	slides	Strategic Form Games Nash Equilibrium Nash Existence Theorem Brouwer and Kakutani’s Fixed Point Theorem Iterated Strict Dominance	Fudenberg and Tirole Chapter 1
2	April 4	Th	slides notes
3	April 9 Via Zoom [link]	Tu	notes recording	Nash Existence Theorem Zero-Sum Games, Duality
4	April 11	Th	notes	Nash Existence Theorem Zero-Sum Games, Duality	Zero_Sum_Games_Note
5	April 16	Tu	notes	Zero-Sum Games, Duality Detection Games	[DL&M ’17]
6	April 18	Th	notes	Complexity of Finding Nash Equilibria in Finite Games	[AGT Papadimitriou]
7	April 23	Tu	note matlab_script
8	April 25	Th	notes	Games with continuous strategy spaces: Bertrand, Public Goods by Means of Lotteries
9	April 30	Tu	notes	Selfish Routing	[AGT Roughgarden]
10	May 2	Th	slides	Selfish Traffic and Link Pricing with Elastic Traffic, Extensive Form Games
11	May 7	Tu	notes slides	Backward induction in continuous games, Stackelberg Competition, Strategic Commitment, Net Neutrality Model	[MS&W ’08]
12	May 9	Th	notes	Asymmetric Information, Signaling Games, Market for Lemons	[Akerlof '70]
13	May 14	Tu	notes	First and Second Price Auctions, Nonlinear pricing
14	May 16	Th	board notes doc cam notes	Nonlinear Pricing, Revelation Principle, VCG, VCG examples, optimal mechanisms
15	May 21	Tu	notes	Optimal Mechanisms, Arrow Impossibility Theorem [recording]	[Arrow 1950]
16	May 23	Th	notes	Games on Graphs [recording]	S. Goyal, Connections: An Introduction to the Economics of Networks, 2007.
17	May 28	Tu	board notes slides Matlab script	Games on Random Graphs, Botnet Detection Game	B. Soper & J. Musacchio, "Botnet Detection Game", Allerton 2014.
18	May 30	Th

 

 

Lecture Plan (Tentative)

Lect #	Date	Day	notes	Assignments	Topics	Reading
1	April 2	Tu	slides	assignment 1 out	Strategic Form Games Nash Equilibrium Nash Existence Theorem Brouwer and Kakutani’s Fixed Point Theorem Iterated Strict Dominance	Fudenberg and Tirole Chapter 1 and 2.1
2	April 4	Th
3	April 9 Via Zoom [link]	Tu			Zero-Sum Games, connection to LP duality Security Games [Varian ’04] – Blotto Games Detection Games [DL&M ’17]
4	April 11	Th		assignment 1 due
5	April 16	Tu			Complexity of Finding Nash Equilibria in Finite Games [AGT Papadimitriou]
6	April 18	Th
7	April 23	Tu			Nash Equilibria in Games with Continuous Strategy Spaces Cournot and Bertrand Competition Congestion Games [AGT Roughgarden] Efficiency Loss / “Price of Anarchy”
8	April 25	Th
9	April 30	Tu			Markets and Social Choice [F&T ’91, Arrow ’50] Arrow-Debreu Markets Arrow’s Impossibility Theorem [Arrow ’50] Fundamental Theorems of Welfare Economics
10	May 2	Th			MIDTERM
11	May 7	Tu			Extensive Form Games Two Sided Markets [MS&W ’08]
12	May 9	Th
13	May 14	Tu			Bayesian Games Asymmetric Information / Market for Lemons [Akerlof '70] First Price Auction with Private Values
14	May 16	Th
15	May 21	Tu			Mechanism Design [F&T ’91] Revelation Principle Revenue Equivalence Theorem Vickrey Auction [A&M ’10] Optimal Auctions / Myerson Mechanisms
16	May 23	Th
17	May 28	Tu			Sponsored Search Auctions [EO&S ’07] Combinatorial Auctions [Parkes ’10]
18	May 30	Th
19	June 4	Tu			Games on Graphs Network Formation [AGT T&W] Contagion Games
20	June 6	Th
	June 13	Th			FINAL EXAM 8-11 am