Syllabus

Class Logistics


Course: CSCE 496/896-013 Special Topics: Computational Game Theory and Its Applications


Days, Times, and Locations: TR (Tuesday and Thursday) 9:30 am - 10:45 am, OLDH 303 (or via Zoom)


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 are 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 is 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 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 Equilibirum 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).

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 0%

  • Exam 2 0%

  • Class Project 15% 40% (see the below description)

  • Class Topic or Paper Presentation 15%

  • Homework Assignment 40% 15%

  • (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:

  1. Propose your project idea (related to some societal problems/issues) 20%

  2. Provide basic computational models for your project idea 20%

  3. Provide (short or long) literature reviews related to your project (i.e., related work section) 20%

  4. Provide your solutions or approaches or implementations to tackle your project 20%

  5. 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 follow:


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]


Self-Care Curricular Adjustments (from Chris Bourke)

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 expected. Students are responsible for knowing all the material discussed in class meetings. Changes to class and lab schedules and assignments will be announced in class or lab.


CSE's Anonymous Contact Form


The CSE Department has an anonymous contact form that you may use to voice your concerns about any problems in the course or department if you do not wish to be identified.


CSE's Email Policy


All students in CSE courses are expected to regularly check their email so they do not miss important announcements.


CSE's Academic Integrity Policy


All homework assignments, quizzes, exams, etc. must be your own work. No direct collaboration with fellow students, past or current, is allowed unless otherwise stated. The Computer Science & Engineering department has an 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.


CSE's Resource Center

There is a Student Resource Center in Avery 12: http://cse.unl.edu/src. (UPDATE for Fall 2020)

The Computer Science Resource Center (SRC) is committed to continuing to provide support for students enrolled in Computer Science and Software engineering courses. For the fall of 2020 the SRC will be operated virtually at https://go.unl.edu/cse-src-zoom

The SRC will be staffed M-F from 9:00 a.m. – 9:00 p.m.

NOTE *There will be no physical presence in Avery 12. All students enrolled in CSCE/SOFT courses will be enrolled in the Virtual SRC via Canvas.

Students will have access to the SRC via Canvas and can access the SRC via this Zoom link above. Students must be logged into Canvas.

SRC front-desk tutors will do their best to help students in the order in which they join the Zoom room.

SRC tutors can help with some content questions, general questions and CSE account questions

SRC tutors will direct students to the appropriate Zoom rooms or breakout rooms for specific courses when those course TAs are available for office hours.


Services for Students with Disabilities


The University strives to make all learning experiences as accessible as possible. If you anticipate or experience barriers based on your disability (including mental health, chronic or temporary medical conditions), please let me know immediately so that we can discuss options privately. To establish reasonable accommodations, I may request that you register with Services for Students with Disabilities (SSD). If you are eligible for services and register with their office, make arrangements with me as soon as possible to discuss your accommodations so they can be implemented in a timely manner. SSD contact information: 232 Canfield Admin. Bldg.; 402-472-3787; acontreras3@unl.edu.


Writing Center


The Writing Center, located in 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 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.


Counseling and Psychological Services

UNL offers a variety of options to students to aid them in dealing 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.