Class Logistics
Course: CSCE 496/896-015 Special Topics: Computational Game Theory and Its Applications
Days, Times, and Locations: TR (Tuesday and Thursday) 9:30 am - 10:45 am, BESY 108 (Bessey Hall 108)
Instructor: Hau Chan
Contact: (office) Avery 363, (email) hchan3@unl.edu, (phone) 402-472-5091
Office Hours: By appointments via emails
Course Description:
We Don't Live In A Vacuum! We interact with other agents in our environment to make rational decisions. For example, selecting the quickest or easiest route to go from your apartment to campus, selecting the best amount to bid in an eBay auction, determining whether to fold in a 2-player poker game, or selecting a winning move in a Rock-paper-scissors game. In all of these examples, we must interact with other agents when making decisions. In particular, our best strategy depends on the behavior of other agents in the environment (e.g., the chosen route depends on the number of others using those routes, play rock if my opponent plays scissors). How do we make rational decisions when facing other strategic agents in a given environment? What is the best strategy? Game theory helps us to answer these questions.
Game theory is a mathematical tool that allows us to reason about the strategic interaction of self-interest and rational agents in a given environment. The construct provides a set of frameworks that characterizes the rational outcomes in such an environment of strategic agents. While the area of game theory originated from the economic literature, computer scientists have made significant contributions to this area from the modeling and computational perspectives in the last decades (which led to computational game theory). Moreover, numerous applications of game theory have been deployed in the real world (e.g., allocating policing resources to checkpoints in the LAX airport, allocating patrollers to protect wild animals in Africa, and predicting the voting behavior of the senators in the U.S. for a bill).
In this special topic course on computational game theory, you will be first introduced to fundamental game-theoretic decision-making tools for modeling and understanding the strategic interaction of self-interested and strategic agents. Using these modeling tools, we will discuss their solution concepts and how they can be used to predict the decision-making behavior of agents. Having gained a solid understanding of decision-making tools and solution concepts, we will then discuss the computational aspects of computing these solution concepts. Finally, we will discuss some of the main applications of game theory to security and social science domains.
As such, the course will be divided into three parts: (1) Classical Game Theory and Fundamental, (2) Computational Game Theory, and (3) Computation Game Theory and Its Applications. The topics for each part are covered below (tentatively).
Topics:
Part 1 - (Classical) Game Theory
- Rational Decision Making
- The Single-Person Decision Problem
- Actions, Outcomes, Preferences, and Utility Functions
- Decision Making under Uncertainty
- Risk, Nature, Random Outcomes
- Evaluating Random Outcomes
- Rational Decision Making with Uncertainty
- Static Games of Complete Information
- Basic Model
- Normal-Form Games with Pure Strategies
- Matrix Representation
- Solution Concepts
- Notable Games
- Rationality and Common Knowledge
- Dominance in Pure Strategies
- Iterated Elimination of Strictly Dominated Pure Strategies
- Beliefs, Best Response, and Rationalizability
- Nash Equilibrium
- Nash Equilibrium in Pure Strategies
- Nash Equilibrium and Applications
- Mixed Strategies
- Strategies, Beliefs, and Expected Payoffs
- Mixed-Strategy Nash Equilibrium
- Nash's Existence Theorem
- Other Notable Equilibrium Concept (Correlated Equilibrium and Coarse Correlated Equilibrium)
Part 2 - Modeling and Computation
- Succinct Representations of Games for large numbers of players
- Graphical Games
- Action-Graph Games
- Finding an Equilibrium
- Computing a Nash Equilibrium in a Two-Player Zero-Sum Games
- Computing a Nash Equilibrium in a General-Sum Games
- The Complexity of Computing a Nash Equilibrium
- Heuristic Approaches for Computing Nash Equilibrium
- Learning in Games
- Iterated Best Response
- Fictitious Play
- No-regret Algorithms
- Targeted Learning
- Finding other Solution Concepts (Correlated Equilibrium and Coarse Correlated Equilibrium)
Part 3 - Applications
- Application of Congestion Games
- Resource Allocation (Congestion Games)
- Road Congestion (Network Congestion Games)
- Application of Graphical Games
- Security Domain (e.g., Interdependent Security Games)
- Social Influence Domain (e.g., influence Games)
- Stackelberg Games and Their Applications
- Security against Terrorism
- Wildlife Protection
- Machine-in-the-Loops
(Optional) Advanced Topics: Dynamic Games of Complete Information, Static Games of Incomplete Information, Dynamic Games of Incomplete Information, Price of Anarchy
Course Structures and Learning Goals
The class consists of lectures (by the instructor), textbook and paper readings, (student) presentations, homework, exams, and projects. We don't expect the students to have any background in game theory. Any necessary and required material will be covered in the course. However, it would be desirable if the students have some background in algorithms/probabilities and basic mathematical maturity.
In this course, you will
(1) Understand the key concepts in decision-making under certainty and uncertainty
(2) Understand basic game-theoretic modeling tools and solution concepts
(3) Understand the computational aspects of applying and computing various solution concepts
(4) Understand the potential applications of game theory to real-world domains
(5) Understand some research-level topics in computational game theory (optional)
Course Resources (Books and Reading Assignments)
Readings from (some of) the books and papers are assigned for each class — see the lecture list for details. Please do the readings before the class so that we can make better use of class time to answer your questions about the readings and discuss more advanced topics.
I will be using the following books for the class. All of them (except one) are freely available on the Internet. For the book that is not available online, I will provide the pdf copies of the readings (Please do not distribute or share the pdfs with anyone else outside of the class).
Essentials of Game Theory (EGT). This textbook provides a basic background to game theory from the computer science perspective. Selected materials will be used in this book.
Game Theory: An Introduction (GT-Intro). This is the (first main) textbook of the class. We will use this textbook to cover the first part of the class.
Economics and Computation (EC). This is the (second main) textbook that is not currently available online. I will post the reading materials before each class (through Canvas). Please do not distribute or share the pdfs. We will use this book to cover the second part of the class.
Multiagent Systems Algorithmic, Game-Theoretic, and Logical Foundations (MSA). This textbook provides some advanced game theory materials. We will also use this book to cover the second part of this class.
We will use related papers (see literature list) to cover the last part of the course.
Assignments and Grading
Reading, homework, and presentation assignments would be available from the lecture list. There will be two major exams in this course (no final). The first exam will cover the first part of the course, while the second exam will cover the second part of the course. You will be working on a class project (of your choice) in this class, which will be your final exam grade.
Your grade is determined by:
Participation 30% (in-class and out-of-class off/online activities/discussions)
Exam 1 10%
Exam 2 10%
Evaluation 10%
Class Project 25% (see the below description)
Class Topic or Paper Presentation 10%
Homework Assignment 25%
(Note: schedule periodic meetings with me to discuss your project and presentation)
Your participation and presentation grades include instructor discretion, particularly if the instructor feels your grades do not accurately reflect your true understanding of the materials. If the instructor does not know who you are, this will not reflect well on your participation and presentation grades.
Your presentation grade is based on the paper that is assigned to you. You have the option to schedule a meeting with me (and you should) to discuss the paper beforehand to better prepare for your presentation.
Your class project grade consists of several contiguous parts:
Propose your project idea (related to some societal problems/issues) 20%
Provide basic computational models for your project idea 20%
Provide (short or long) literature reviews related to your project (i.e., related work section) 20%
Provide your solutions or/and approaches or/and implementations to tackle your project 20%
Present your project via an in-class presentation and/or poster (at the end of the semester) 20%
To make sure you are making progress on your project, you will send me a single periodic write-up in pdf throughout the course (see lecture list for due dates). The single write-up pdf should consist of all of the previous results (e.g., if you are submitting your write-up to include 3, then your write-up should also include 1 and 2).
Finally, your final letter grade will be determined as follows:
A+ [100, 97]
A (97, 94]
A- (94, 90]
B+ (90, 87]
B (87, 84]
B- (84, 80]
C+ (80, 75]
C (75, 67]
C- (67, 60]
D+ (60, 57]
D (57, 54]
D- (54, 51]
F (51, 0]
The UNL Faculty Senate passed a resolution on December 1st, 2020 encouraging instructors to make adjustments to courses and curricula in an effort to promote self-care and to relieve stress and promote mental well-being during the pandemic crisis.
As such, the following accommodations and changes have been made to this course:
The midterm exam and final exam have been eliminated
Redistribution of grade weights to more formative assessments
Syllabus Language for Face Coverings in Instructional Spaces (in the absence of a face covering requirement)
The university currently requires face coverings indoors, including at UNL events, until further notice. Should that requirement expire, there will still be some instances where face coverings may be required or requested in classrooms given the current transmission level of COVID-19 in the community.
Pre-approved courses that include substantial work in close physical proximity to one another for extended periods of time.
Instructors may receive approval to require face coverings for a documented instructor or student need after submitting a Request to Require Face Covering Form.
Instructors may request that students join them in wearing face coverings.
The University's Inclement Weather Policy
Beginning Jan. 3, all instructors should include a statement on syllabi to explain the mode of communication they will use (e.g., @huskers.unl.edu email or Canvas) if in-person classes are canceled and the campus follows instructional continuity plans:
If in-person classes are canceled, you will be notified of the instructional continuity plan for this class by email or Canvas.
Students will be expected to be responsible for checking these notifications for instructional continuity assignments or virtual class meetings.
Attendance Policy
Attendance at all officially scheduled class meetings (class and lab sections) is mandatory. Students are responsible for knowing all material discussed in class meetings. Changes to class lectures and assignments will be announced in class and Canvas.
Suggestion Box
The School of Computing (SoC) has an anonymous suggestion box (https://computing.unl.edu/anonymous-department-feedback-form/) that you may use to voice your concerns about any problems in the course or the school if you do not wish to be identified.
Stay Up-to-date
It is SoC Department policy that all students in SoC courses are expected to regularly check their email, so they do not miss important announcements.
SoC's Academic Integrity
All homework assignments, quizzes, exams, etc. must be the student’s own work. No direct collaboration with fellow students, past or current, is allowed unless otherwise stated.
The School of Computing has an Academic Integrity Policy:
https://computing.unl.edu/academic-integrity-policy/
All students enrolled in any computer science course are bound by this policy. You are expected to read, understand, and follow this policy. Violations will be dealt with on a case-by-case basis and may result in a failing assignment or a failing grade for the course itself.
SoC's Resource Center
The SoC Student Resource Center (Avery Hall 13A) is intended to provide UNL Computer Science and Computer Engineering majors who are new to the program with a set of resources that will help them assimilate into college life and encourage them to continue their study of Computer Science and Computer Engineering (https://computing.unl.edu/current-undergraduate/#SRC).
Services for Students with Disabilities
Students with disabilities are encouraged to contact the instructor for a confidential discussion of their individual needs for academic accommodation. This includes students with mental health disabilities like depression and anxiety. It is the policy of the University of Nebraska-Lincoln to provide individualized accommodations to students with documented disabilities that may affect their ability to fully participate in course activities or to meet course requirements. To receive accommodation services, students must be registered with the Services for Students with Disabilities (SSD) office, 232 Canfield Administration, 472-3787.
Writing Center
The Writing Center, located at 102 Andrews Hall and satellite locations from 5-7 pm in Adele Hall , is a free service for all UNL students, faculty, and staff. You can work with an individual writing consultant on any type of writing at any stage in your writing process. For an appointment, call 402-472-8803 or schedule online.
Academic Support Services
You can schedule free appointments for individual academic coaching with First-Year Experience and Transition Program staff through MyPLAN. You can also take advantage of study stops--which provide individual and group study with learning consultants in a variety of disciplines--and free group workshops on topics such as time management, goal setting, test preparation, and reading strategies. See https://success.unl.edu for schedules and more information.
Dealing with Stress and Adversity
UNL offers a variety of options to help students deal with stress and adversity. Counseling and Psychological & Services (CAPS); is a multidisciplinary team of psychologists and counselors that works collaboratively with Nebraska students to help them explore their feelings and thoughts and learn helpful ways to improve their mental, psychological and emotional well-being when issues arise. CAPS can be reached by calling 402-472-7450. Big Red Resilience & Well-Being (BRRWB) provides one-on-one well-being coaching to any student who wants to enhance their well-being. Trained well-being coaches help students create and be grateful for positive experiences, practice resilience and self-compassion, and find support as they need it. BRRWB can be reached by calling 402-472-8770.
Classroom Climate
Because the topics in this course may be emotionally charged or challenging for class members, I hope we can create an environment that is both intellectually productive and supportive for all. I realize there might be days when class members may choose to be silent. Beyond verbal participation, your active and supportive listening is also an important and valuable form of participation. I hope that we will continuously reflect upon our class processes so that we can build an inclusive intellectual community where all feel valued and supported in their learning.
Discussing Controversial Topics
Some of the topics we will discuss over the semester are likely to be sensitive and/or controversial. A variety of opinions, beliefs, and statements may surface during class discussions, some of which may be experienced as “racist,” or “anti-Semitic,” or “homophobic,” or “sexist,” or “fascist,” or “Islamophobic,” etc. You will be encouraged to express your opinions and beliefs, and to do so with respect for the opinions of other students who may hold different beliefs. In the event that controversial claims are made, you will be discouraged from labeling any classmate as “a racist,” or “an anti-Semite,” or “a fascist,” or “a bigot,” etc. Instead, you will be encouraged to respond to opinions with which you disagree by saying, “I disagree with the statement you just made and I experience it [i.e., the statement] as racist (or homophobic, or anti-Semitic, etc.) because...,” and then share your opinion with your classmates and me. All of you are encouraged to express your views and beliefs even when those views may be considered unpopular. If you have any concerns that you will have difficulty with voicing your opinions/beliefs in insensitive language, feel free to consult with me during office hours and I will be happy to assist you.
Video or Audiotaping Class Sessions
Due to the sensitive and controversial nature of some of the topics that will be discussed over the duration of the semester, all classes are closed to the Press/Media. No video or audio taping of class sessions is allowed unless you obtain my permission to do so.
Academic Honesty
Academic honesty is essential to the existence and integrity of an academic institution. The responsibility for maintaining that integrity is shared by all members of the academic community. The University's Student Code of Conduct addresses academic dishonesty. Students who commit acts of academic dishonesty are subject to disciplinary action and are granted due process and the right to appeal any decision.
Diversity & Inclusion
The University of Nebraska-Lincoln does not discriminate on the basis of race, ethnicity, color, national origin, sex (including pregnancy), religion, age, disability, sexual orientation, gender identity, genetic information, veteran status, marital status, and/or political affiliation.
Trespass Policy (Regents’ Policy 6.4.7)
The areas of University academic, research, public service, and administrative buildings of the University used for classrooms, laboratories, faculty and staff offices, and the areas of University student residence buildings used for student living quarters are not open to the general public. Any person not authorized to be or remain in any such building area will be deemed to be trespassing on University property and may be cited and subject to prosecution for criminal trespass in violation of Neb. Rev. Stat., § 28-520 or § 28-521.