What is this course about?

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 advanced algorithms: Find beauty in the depths of several algorithmic paradigms.

Example: Game theory tells us why these players are trying hard to lose the game in the Olympics.

Course Description:

Advanced algorithms course with a focus on game theory. Topics include non-cooperative games, linear programming, network flow, computational complexity, 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), which is a pillar of liberal arts education
  • Interest in the mathematical foundation of CS
  • Strong programming background
  • Some experience with probability theory and matrix algebra

Learning Goals

Even after 5 years:

  • Know: Foundational concepts of game theory, computational complexity, and advanced algorithmic topics like network flow.
  • Be able to do: Read scientific papers, design game-theoretic models and devise solutions, apply advanced algorithmic techniques to various problem areas.
  • Find value in: Abstraction in terms of deep theoretical knowledge and translating this knowledge to a wide range of real-world scenarios.


What does it look like on a day-to-day basis?
  • 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.

What are the central themes?

This course is structured into the following units:

Unit 1: Foundational Topics (~4 weeks)

We will get a very brief introduction to game theory, including formal/mathematical definitions and solution concepts. We will then take a cursory glance at linear programming (LP) without going into the depth of duality theorem. The ability of solving certain classes of games using LP naturally leads us to computational complexity of solving general games.

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 (~4 weeks)

We will learn about the computational complexity of problems, especially game-theoretic problems. We will then learn a new algorithmic framework known as network flow, which has numerous applications, including studying the strategic interactions between buyers and sellers in a market. In fact, one of the major application areas of game theory is markets. We will also learn about games on networks, known as graphical games. Computer scientists, both from the AI and theory communities, have been giving a great deal of attention to graphical games due to their succinct representation size (which makes these games computationally attractive) and their real-world applications. Graphical games will naturally lead us to several selected topics on real-world games on networks.

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 (~4 weeks)

In this unit, we will first look at influence games, a type of game that models real-world behavioral choices made by networked agents (e.g., senators in the U.S. Congress) whose choices are interdependent. Please see an illustration below. Within computer science, one area of intense research right now is mechanism design, which is often termed as reverse game theory because it aims to design a game with certain objectives. We will take a brief look at mechanism design. Within the umbrella of mechanism design, a hot topic within the AI and theory communities is computational social choice. We will 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 will 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 will 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 will also talk about other topics based on students' interests.

Instructor

Professor: Mohammad T. Irfan
Email: mirfan@bowdoin.edu
Office Hrs:
TBA
Office room: Mills 209
LA: None

Time & Place

Lectures: MW 2:50-4:15
Room: Mills 210

Course Details

Textbooks:

[EGT] Essentials of Game Theory (3 Chapters)
Amazon link
See Canvas

[AGT] Algorithmic Game Theory (3 Chapters)
Amazon link
Non-printable pdf file
Also available on Canvas

[CSC] Computational Social Choice (4 Chapters)
Amazon link
Instructions to download as pdf
Also available on Canvas

Other book chapters and papers will be linked through this website.


Programming Language:

For programming assignments, the language of our choice is Python 3. You are free to use any IDE, but Visual Studio Code is recommended.

Grading:

Prof. Irfan has designed an evaluation scheme specifically for this course with the following goals:

  1. Incentivizing learning and engagement (which itself is a game theory problem)
  2. Weighing student growth more than test scores
  3. Embracing hard topics (including latest scientific papers) without fears of losing grade

Goal 1 will be achieved by an in-class exam as well as viva voce, which means "with the living voice" in Latin and is usually translated as an oral exam. However, in this course, viva voce will mean face-to-face conversation with Prof. Irfan. You will get points on viva voce by demonstrating that you have an adequate understanding of the course materials.

Goals 2 and 3 will be achieved by ungraded assignments. You will get detailed feedback on the assignments. The ungraded assignments will be connected with viva voce through the feedback, as described in the bullet points below. Goal 3 will also be achieved through a final project.

Overall, the majority of evaluation will be ungraded, as detailed below.

  • 20% points for exam: There will be an in-class midterm exam. You may bring a 1-page, single-sided, handwritten or typed cheat sheet to the exam.

  • 20% points for formative assessment: The formative assignments (FAs) will be ungraded, but you will receive feedback on them. You will get the points for FAs after you understand the feedback and in some cases (to be specified by Prof. Irfan), after you resubmit corrections.

  • Ungraded summative assessment: The summative assignments (SAs) will be signficiantly harder than the FAs. The SAs will constitute of problem solving and programming assignments. These assignments will be ungraded, but you will receive detailed feedback. The SAs will be connected to viva voce as described next.

  • 40% points for viva voce: After you receive the feedback for each SA, you will meet with Prof. Irfan during office hours (or by appointment) for a few minutes and talk to him about the SA. You should come prepared with any necessary corrections to the SA and having reviewed the relevant topics. You will get points based on your understanding of the materials. In addition to SA-related viva voce, you will be asked for viva voce on materials for which there is no SA (e.g., topics in Unit 3). While viva voce will normally be one-on-one, we will occasionally do viva voce in groups.

  • 15% points for final project: The final project can be theoretical (addressing a theoretical question that's not already answered in a paper) or practical (implementing a solution -- perhaps from a paper -- for a problem of your interest). You will submit a project report.

  • 5% points for good citizenship: Attendance, adherence to the screen policy, and active participation in class, including note taking. Taking handwritten notes is highly recommended for its many benefits.

  • Points to letter grade conversion: 94% A, 90% A-, 85% B+, 80% B, 75% B-, 70% C+, 65% C, 60% C-, 55% D, below 55% F


Late Policy:

Extensions will be given if there is any health or other emergency situation. Otherwise, late submissions will be accepted up until 24 hours after the deadline with a penalty. Each hour after the deadline would cost 4% (for SAs, this cost will be charged to viva voce).

Course Schedule
Week Unit Topics Reference Links and Notes
Week 1
(9/3)
 Unit 1: Foundation 1. Course intro: Why study game theory?
2. Example: Braess's paradox 		[Easley-Kleinberg] Ch 8, Sec 8.1 and 8.2 1. Slides (Course Intro)
2. 2012 Olympics badminton scandal
3. Why were they trying to lose?
Week 2
(9/8, 9/10)		 Unit 1: Foundation Intro to game theory: solution concepts and examples
 [Easley-Kleinberg] Ch 6 1. Slides (Intro to game theory)
2. Why the movie A Beautiful Mind got Nash equilibrium wrong!
Week 3
(9/15, 9/17)		 Unit 1: Foundation Intro to game theory: mixed-strategy NE
 [Easley-Kleinberg] Ch 6
 Slides (continued)
Week 4
(9/22, 9/24)		 Unit 1: Foundation 1. Intro to game theory: formal definitions with examples
2. Discrete math 		1. [EGT] Ch 1-2
2. Set Theory Sections A and C.1 		1. Slides (continued)
2. Nash's Paper
3. Prof. Irfan's explanation
Week 5
(9/29, 10/1)
 Unit 1: Foundation 1. Solution concepts incl. correlated equilibrium
2. Connection to linear programming 		1. [EK] Ch 6
2. [AGT] Ch 1 		Slides (continued)
Week 6
(10/6, 10/8)		 Unit 2: Adv. Topics
Computational complexity of games 1. AGT [Ch 1, 2]
2. Algorithm Design Ch 8 [Canvas]
3. Gottlob et al. paper 		Slides (Complexity)
Fall Break        
Week 7
(10/15)		 Unit 2: Adv. Topics
Market equilibria: Intro

[AGT] Ch 5

 Slides (Market Equilibria)
Week 8
(10/20, 10/22)		 Unit 2: Adv. Topics
Market equilibria (continued)
Nonlinear optimization
KKT conditions 		[AGT] Ch 5
KKT conditions 		Slides (continued)
Week 9
(10/27, 10/29)
 Unit 2: Adv. Topics
Network flow Algorithm Design Ch 7 [Canvas] 1. Slides (Network Flow)
2. Ford-Fulkerson Demo
Week 10
(11/3, 11/5)		 Unit 2: Adv. Topics
Graphical games [AGT] Ch 7 Slides (Graphical Games)
Week 11
(11/10, 11/12)
 Unit 3: Selected Topics
Influence games Influence games paper
Sections 1—3 (up to pg. 86), Sections 4.5, 5 (no proof), 6 		Slides (Influence Games)
Week 12
(11/17, 11/19)
 Unit 3: Selected Topics
Congestion games
 Papers posted on canvas Slides (Congestion Games)
Thanksgiving Break        
Week 13
(12/1, 12/3)
 Unit 3: Selected Topics
Mechanism design Slides (mechanism design)
Week 14
(12/8, 12/10)
 Unit 3: Selected Topics
Coputational social choice Slides (computational social choice)
Projects Unit 3: Selected Topics
See Canvas for details


Collaboration Policy

With some exceptions, summative assignments (SAs) will normally be done individually. In contrast, formative assignments (FAs) will be group work, but you must write your own submission individually.

Students are expected to follow Bowdoin's Academic Honor Code.

Following is the collaboration policy for individual assignments. You are encouraged to discuss ideas and techniques broadly with your classmates, but not specifics of assigned problems. Discussions should be limited to questions that can be asked and answered without using any written medium (e.g., pencil and paper, board, or email). This means that at no time should a student read anything written by another student. Violation of this policy is grounds for me to initiate an action that would be filed with the Dean's office and would come before the Conduct Review Board. If you have any questions about this policy, PLEASE do not hesitate to contact me. This will be a zero-tolerance policy.

If in the future you provide your work to other students, this will also constitute a violation of Bowdoin's honor code.

Github Policy

Making assignment solutions publicly available through Github or other media will constitute a violation of the honor code for this course.

AI Policy

We will follow the DCS AI policy in this course.

What counts as Generative AI?

Generative AI refers to all the AI systems that can create new content like text, code, images, audio, and other types of media. This includes but is not limited to:

  • Large language models (ChatGPT, Claude, Gemini, etc.), apps and agents derived from them, and aggregator interfaces (Amplify, LibreChat, etc.)
  • Code generation tools (GitHub Copilot, Google Colab, Cursor, etc.)
  • Image generators (DALL-E, Midjourney, etc.)
  • AI-powered writing assistants and autocomplete features
  • NotebookLM, Quizlet AI features, and other AI-enhanced study tools

Always acknowledge what generative AI tools were used to help you complete assignments.

How can generative AI help you to learn in this course?

  • Converting slides and notes to study guides and podcasts (e.g., NotebookLM)
  • Creating practice materials like flashcards and mock quizzes or exams (e.g., Quizlet)
  • Proposing a study plan
  • Providing alternative explanations or examples
  • Suggesting refinements to grammar and corrections to spelling
  • A guide to debugging code

How can generative AI impair your learning in this course?

  • For coding projects, AI often misses design layers, making results hard to debug
  • Reduces critical thinking and problem-solving abilities
  • Can limit creativity
  • Creates a sense of false confidence
  • Creates dependency
  • Reduces retention
  • Limits research skills
  • Denies you the possibility of self-expression in a constructive environment

Other costs of using AI

  • Environmental impact – large energy use
  • Labor exploitation – poorly paid workers for moderation and labeling
  • Digital colonialism – reinforces inequalities and Western perspectives
  • Digital divide – widens gaps in tech access
  • Aggregation – concentrated power in few companies
  • Privacy – inputs may be stored despite disclaimers

Why do we give you assignments?

"We don’t assign essays because the world needs more student essays." - Emily Bender

Assignments are designed to help you develop essential skills and ways of thinking that will serve you throughout your education and beyond. Each assignment is an opportunity to practice critical thinking, develop your unique voice, learn from struggle, engage with material, demonstrate learning, and prepare for future challenges.

Academic Integrity Expectations

  • Be transparent about AI use
  • When in doubt, acknowledge it
  • Submit your prompts with assignments
  • Understand that overreliance hinders learning
  • Violations will be treated as academic dishonesty

When is generative AI not allowed?

  • To generate code. AI code lacks structure and context and is often too complicated to debug (Prof. Irfan can give you many examples). You must write the initial draft of code yourself.
  • To generate text; e.g., to flesh out an outline, leading to an initial draft that you intend to revise
  • To brainstorm – your background is richer than AI’s
  • To solve problems – designed to strengthen critical thinking
  • As a search engine for facts – verify independently
  • To analyze data or interpret results without your own reasoning
  • To generate ideas for creative projects or research questions
  • To complete exams or quizzes unless permitted
  • To translate assignments or materials without permission

When can generative AI be used?

  • Polishing text by checking for grammar, spelling, and styling suggestions
  • Outlining, i.e., preparing an initial structure with AI to be expanded with your own perspective (note that the opposite is not allowed)
  • Debugging your code, including generating test cases
  • Getting help on a software tool (e.g., how do I do X?)
  • Finding resources to support research
  • Testing discussion questions for class
  • Checking your work and getting preliminary feedback

Screen Policy

We will follow the DCS screen policy.

No screen use is permitted in class unless explicitly stated by the instructor or in cases of learning accommodations. This includes phones, tablets, and computers. Most courses will display a symbol during presentations that indicates when screen use is allowed. When screens are not permitted, all devices should be put away and out of sight.

If you have a documented accommodation that allows the use of a laptop or tablet for note-taking, please make sure to submit the appropriate materials to the professor.

If Winter comes, can Spring be far behind? -- Percy Bysshe Shelley