Strategic thinking and reasoning: A modern way of making sense of the complex world

Studying interdependent systems: Agents/components impact each other through their choices

Diving into the depth of algorithms: A compelling story of the equivalence among several algorithmic paradigms

Course Description:

Advanced algorithms course with a focus on game theory. Topics include non-cooperative and cooperative games, linear programming, network flow, computational complexity, explainable AI (XAI), graphical games, and computational social choice. Game theory, also known as the mathematical theory of strategic interactions, rose to prominence due to its applicability to a variety of strategic scenarios ranging from markets and auctions to kidney exchanges to social influence. These scenarios often involve complex interactions in large-scale systems, giving rise to many computational questions, including: how algorithms for certain games are devised; how local interactions lead to global outcomes; how individual choices, such as selfishness, impact outcomes. Most questions will be addressed theoretically, some by programming. (Fulfills the Algorithms and Theory and 3000-level course requirements for majoring in CS.)

Prerequisites:

• CSCI 2200: Algorithms
• Intrest in learning outside of the class (e.g., in office hours)— a pillar of liberal arts education
• Ability to attend morning (10am) classes
• Interest in the mathematical foundation of CS
• Strong programming background
• Some experience with probability theory and matrix algebra
• Review of set theory: Sections A and C.1 from this website.
• Review intro to probability: Sections 5 to 11 of this tutorial
• Review intro to matrix algebra: Sections 1 to 4 of this tutorial

Even after 5 years:

• Know: concepts of game theory, computational complexity, duality theorem.
• Able to do: design and implement linear programming solutions, design game-theoretic models.
• Find value in: abstraction in terms of deep theoretical knowledge and translation of knowledge to a wide range of real-world scenarios.

• This is a lecture-based course with in-class activities designed for student engagement and learning.
• There will be regular assignments, both formative and summative.
• There is no final exam. Students will do a final project or make a final presentation.

This course is structured into the following units:

Unit 1: Foundational Topics (6 weeks)

We'll get a very brief introduction to game theory. We'll then look at game theory from a computational perspective, where the focus will be on linear programming (LP). LP will also help us transition from the basics of grame theory to several important topics in advanced algorithms.

John Nash proved the existence of an equilibrium point in any finite game.	Christos Papadimitriou and colleagues proved the hardness of computing a Nash equilibrium, even though it always exists.

Unit 2: Advanced Topics (~5 weeks)

We'll learn about the computational hardness of a problem, especially for game-theoretic problems. We'll also learn a new algorithmic framework known as network flow, which has numerous applications, including studying the strategic interaction between buyers and sellers in a market. We'll also dive into a different branch of game theory known as cooperative or coalitional game theory and will investigate its connection with explainable AI (XAI), a rapidly growing field in AI.

Application of game theory to markets: A microfinance meeting is in progress in Kerala, India (Source). Microfinance programs are recognized as one of the most effective poverty alleviation tools.

Unit 3: Selected Topics on Computational Game Theory (~3 weeks)

Computer scientists, both from the AI and theory communities, have been giving a great deal of attention to how the new advances in game theory can be applied to real-world scenarios. One example is games on networks or "graphical games" (see an illustration below). For computer scientists, the main attraction of these games is their succinct representation size. We'll examine various computational problems on games on networks. Another topic of intense research right now is computational social choice. Within computational social choice, we will in particular look into how game theory can be used in a broad array of real-world problems that fall under the the category of "fair allocation."

Irfan and Ortiz (2014) captured the network of influence among the US senators using a game-theoretic approach. Above is a partial picture of the network. Black arcs represent positive influence, red negative influence. Darker shades of nodes (i.e., bubbles) represent higher threshold (or stubbornness).

In Unit 3, we'll also take a step back and look at the "quality guarantee" of Nash equilibria. For example, do Nash equilibria maximize social welfare? If not, how far off are they? We'll see that for special types of games, such as selfish routing, Nash equilibria are not that far off from the most desirable outcomes. This is, in fact, a surprising result. We'll also talk about other topics based on students' interests.