COM 313 Spring 2024
Topics in Algorithmic Game Theory
http://cs.conncoll.edu/cchung/com313

Course Schedule

Course Description

This course will introduce you to the computer science field of algorithmic game theory (AGT).  AGT combines the study of scenarios where competing entities interact strategically (a.k.a. games) with algorithmic/computational thinking.  We will see how game theory is relevant to our lives, from everyday occurrences to important world issues (politics, the environment, etc).  We will then consider the various ways in which computer science and game theory intersect:  we will see how the tools and methods of computer science can be applied to game theory and vice versa.  Some questions that we will discuss from an algorithmic and game theoretic perspective include: 

·         How does Google rank web pages for its search results? 

·         Which friend on Facebook most effectively influences others? 

·         Why must all voting systems be fundamentally flawed? 

·         When will altruism in a networked system prevail? 

·         How does Google sell its ad spaces for its search pages? 

·         When does adding a new highway actually make travel delays worse?

·         How bad are the outcomes of selfish end-user behavior compared with outcomes centrally dictated by an algorithm? 

No prior experience in game theory or algorithms analysis is required, but students are expected to have the mathematical maturity of a student who has taken discrete math (MAT210). 

The official prerequisite for the course is COM212 OR (COM110 and MAT210).

Course Info/Policies

 

All information is subject to change at any time.  Check the course website daily for announcements and updates. 

Meetings:

 

Mondays and Wednesdays, 10:25 – 11:40

Olin 014

[Zoom link for just in case we ever need a remote class meeting:
https://conncoll-edu.zoom.us/j/4470209231]

Professor:

 

Dr. Christine Chung

http://cs.conncoll.edu/cchung

cchung@conncoll.edu
860-439-2074

New London Hall 220

Office hours:  please sign-up for a slot or email me for an appointment

 

TAs:

TBD

Grading:

Written homework assignments -- there will be homework exercises assigned after each class, due before the start of the following class, graded purely on completeness of effort

55%

Participation -- this includes in-class and on-line (moodle) participation

10%

Midterm Project

15%

Final Project

20%

                               

Culture of cooperation. 

In this class you are expected to work cooperatively.  You are encouraged to discuss ideas and ask each other for help.  Indeed, giving and asking for constructive input to/from fellow students is a part of the important learning experience we will be striving for.  However, copying solutions from one another is not allowed.  Likewise it is forbidden to copy solutions from anyone/anywhere.  Copying (without citing your sources) is considered an honor code breach.*  When you receive help/input on an assignment, you must always cite your sources.  As long as you cite your sources, you will not be in violation of the honor code. (Note that when using external sources extensively, you may not earn full credit for the assignment.) Please also note the policy on AI use for this course at the bottom of this page. 

Homework Exercises. 

Homework exercises will be due almost every class.  They are written assignments that will allow you to reflect on what you’ve learned the previous class, or prepare you for what we will be learning in the next class.  They must be turned in by the deadline before the start of each class via moodle (either typed or hand-written, submitted as a pdf or image file).  They will be graded on completeness and effort rather than correctness.  The lowest homework grade will be dropped.

·         A “complete” homework exercise is one that demonstrates a complete effort.  This means you must show more than just an answer to the problem or question; you must in fact show your thought process in arriving at an answer.  It also means that if you don’t arrive at a satisfactory solution, but describe your thought process during your (sufficiently lengthy) attempts at finding one, and this thought process demonstrates that you have completed the reading assignment, you will have demonstrated a complete effort.  Inversely, if your write-up reveals that you did not complete the reading assignment, you will not earn full credit for the exercise.  Solutions alone with no explanation are also worth minimal credit.  Complete homework exercises will earn a 5 out of 5. 

·         The HW submission link will close 15 minutes before each class meeting and I will re-open it again for late submissions after class.  Late HW submissions will be accepted until the start of the next class, and will earn a maximum grade of 3 out of 5 per exercise. 

 

Course Materials

Required texts (for the first unit of the course only, on reserve in the library)

·         Games of Strategy, third edition, by Avinash Dixit, Susan Skeath, and David H Reiley, Jr.

Texts closely related to the main content of the course (on reserve in the library)

·         Algorithmic Game Theory, edited by Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani
(This text can be found free, online, linked from here: https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf)

·         Networks, Crowds, and Markets, by David Easley and Jon Kleinberg

·         Networked Life, by Mung Chiang

Recommended/optional texts (also on reserve in the library)

·         An Introduction to Game Theory, by Martin Osborne

·         Rock, Paper, Scissors: Game Theory in Everyday Life, by Len Fisher
(This is an informal, fun, and very readable introduction to game theory.)

·         Game Theory and Strategy, by Philip Straffin

·         Playing for Real:  a Text on Game Theory, by Ken Binmore

Other important info

 

*The Connecticut College Honor Code

Academic integrity is of the utmost importance in maintaining the high standards of scholarship in our community. Academic dishonesty is considered to be a serious offense against the community and represents a significant breach of trust between the professor, the classmates, and the student. There are many forms of academic dishonesty including plagiarism, falsifying data, misrepresenting class attendance, submitting the same work in two courses without prior approval, unauthorized discussion or distribution of exams or assignments, and offering or receiving unauthorized aid on exams or graded assignments.  Students violating the Honor Code may be referred to the college's Honor Council for resolution. 

Credit Hour Definition

A semester course is normally equivalent to four credit hours.  Connecticut College complies with federal regulations defining the credit hour.  For each credit hour awarded, a course will provide an average of at least one hour of classroom or direct faculty instruction (class meetings, labs, review sessions, field trips, office hours, film screenings, tutorials, training, rehearsals, etc.) and at least two hours of out-of-class work (homework, preparatory work, practice, rehearsals, etc.) per week. 

Title IX Statement

As a faculty member, I am deeply invested in the well-being of each student I teach. I am here to assist you with your work in this course. If you come to me with other non-course-related concerns, I will do my best to help. It is important for you to know that all faculty members are trained and required to report any incidents of gender-based discrimination, including discrimination based on gender identity, gender expression, and sexual orientation. This means that I cannot keep information confidential about sexual harassment, sexual assault, dating violence, stalking, or other forms of gender-based discrimination, and that I will report that information to the Title IX office, if it is shared with me.  However, the Title IX office typically only acts on formal complaints, and in response to notice from me will reach out to you to offer support and resources, and offer you the opportunity to file a formal Title IX complaint, which is up to you.  The Director of Sexual Violence Prevention and Advocacy and the SVPA Confidential Advocates can advise you confidentially as can Counseling Services and any of the College chaplains.  SVPA can also help you access other resources on campus and in the local community.  You can reach the Confidential Advocates at SVPA@conncoll.edu, make an appointment with the Confidential Advocates at http://bit.ly/ConnCollSVPA or contact the SVPA Confidential Advocate ON Call 24/7 at 860-460-9194.  The student sexual harassment, dating violence, stalking, and non-discrimination policies are in the Sexual Harassment and Nondiscrimination Policy, which can be found on CamelWeb, in the “Documents/Policies” section, under the Student Life section. There you will find the policies, definitions, procedures, and resources. If you need to report an incident or have any questions about the policy, you can contact 860-439-2624 or titleix@conncoll.edu.

Academic Resource Center

The Academic Resource Center (ARC) offers services to support your academic work such as study skills workshops, time management, coaching and tutoring. Its offices are located on the second floor of Shain Library. Students can make appointments by clicking on this link: https://forms.gle/BQecmVdK8Bg1sv5P7.

The ARC is open to the community Monday – Friday, 8:30 – 5:00 (evenings are by appointment only).

Students may continue to use the ARC as a quiet study space, though social distancing and masks are required at ALL times.

If faculty or students have any questions or concerns, they should contact Noel Garrett (ngarrett@conncoll.edu) or Patricia Dallas (pdallas@conncoll.edu).

 

Writing Center

The Roth Writing Center provides one-to-one peer tutoring (free of charge) to help student writers of all abilities during all stages of the writing process.  You can make an appointment here using Google Calendar.  If you're a confident, experienced writer our tutors can help you to push your ideas and polish your style; if you're a relatively inexperienced and not-so-confident writer they can help you to work on grammar or organization or whatever you need.  Working with a tutor gives you the opportunity to share your work-in-progress with an actual reader, so that you can get useful feedback on that work before you have to turn it in for a final grade. For further information, visit the Writing Center web page at http://write.conncoll.edu/ 

 

Office of Student Accessibility Services

Connecticut College complies with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act. If you have a documented disability and have been approved for academic accommodations, please have your Faculty Notification Letter emailed to me through the Student Accessibility online management system (AIM) and schedule a meeting during my office hours as early as possible in the semester so that we can discuss the logistics of your accommodations. If you are not approved for accommodations, but have a disability requiring academic accommodations, or have questions about applying for accommodations, please contact Student Accessibility Services at 860-439-5428 or sas@conncoll.edu.

 

Classroom Recording

With the exception of those granted accommodations through the Office of Student Accessibility Services, students are prohibited from audio, video, or photographic recording during class periods or out-of-class meetings with the instructor without explicit permission from the instructor. Recordings approved in this manner may not be shared in any form without permission of the instructor. Violations of this policy shall be considered an Honor Code violation.

 

Office Hours

Office hours provide students with additional opportunities to review or ask questions about the class discussions and assignments. Connecticut College faculty encourage students to go to office hours so they might learn about your interests, both inside and outside the classroom. In addition to talking about class material and assignments, you may find you share common interests, such as music, books, hobbies, and movies. If a professor knows your interest, they may inform you about campus programs and activities or other opportunities like fellowships and scholarships. Most importantly, a professor who knows their students writes better letters of recommendation. Successful students at Connecticut College make time to go to their professors’ office hours. All Connecticut College faculty are required to have office hours on their syllabus and posted on their office door.  If you cannot make your professor’s scheduled office hours, contact your professor to set up an appointment.  

 

Respecting Personal Pronouns and Identity

Everyone deserves to be referred to and addressed in accordance with their personal identity. As a faculty member, I am committed to ensuring my classroom affirms people of all gender expressions and gender identities. In this course, we will only use the name and pronouns of each individual's choosing. The repeated usage of incorrect names and/or pronouns are against Connecticut College policy and may constitute a T9 policy violation as well as a violation of state and federal law. In the classroom, be assured that you will always be referred to by the name and pronouns you choose. If you go by a different name than your legal name, Connecticut College has a process to change your preferred name on most campus systems. If you want to learn more about this process go to conncoll.edu/equity-inclusion/preferred-name-faq/ or email GSP@conncoll.edu. Students, faculty and staff are now able to choose and share their pronouns within the college community by using the Preferred Name/Pronouns link on the navigation menu in CamelWeb and the CC Mobile App.  Your gender pronouns will appear in the internal directory located in CamelWeb and the CC Mobile App. If none are selected, or if “Not Applicable” is selected, no pronouns will display. Enrolled students’ gender pronouns will also display in Moodle for instructors via the class participants page.  Pronouns are one way to affirm someone’s gender identity, but they are not necessarily indicative of a person’s gender identity. Commonly, they/them is a gender-inclusive pronoun used by a variety of identities. Remember to ask for pronouns, listen, and then respect the gender identities of those around you by using the proper terminology. If you have any further questions or you want to learn more about gender & sexuality, please do not hesitate to contact the Director of Gender & Sexuality Programs at gsp@conncoll.edu.

*AI Policy

Please note that the student handbook now includes policy on AI as it pertains to academic integrity.  Here is the relevant passage:

Plagiarism occurs when work does not reflect the student’s personal and original words, word-groupings, or ideas. Authorized use of artificial intelligence (AI) tools such as ChatGPT needs to be acknowledged unless otherwise specified.   Plagiarism is a violation of the Honor Code, regardless of intent.  Ignorance or negligence is not considered an excuse for plagiarism.  Plagiarism consists of:  
a.      handing in a paper, assignment, or project that is not one’s own work;
b.      using the language of another writer or tool (such as AI or language translator) without proper documentation (e.g. footnotes, quotation marks, parenthetical documentation, bibliography);
c.      using the ideas, arguments, or organization of another writer or tool (such as AI or language translator) without proper acknowledgment.

Generally speaking, the output of large language models (LLMs) like ChatGPT and others does not meet the standards that we tend to hold for student writing. However, you may find some of their functions useful in your writing process–to help you brainstorm, for example.

In this class, you are allowed to use large language models as a tool to assist you, but you may not use them to generate answers. AI assistance means that you might use a language model to help you explore potential counterexamples to your solutions, or engage in a targeted revision. Targeted revision might mean asking the model to help you revise a solution that you feel you just can’t get right. AI generated work means that you use the program to generate large blocks of text or use the model as a substitute for creating your own ideas. Here is a good rule of thumb: You may use LLMs to enhance your learning; you may not use them as an opportunity to cheat yourself of the opportunity to learn.

If you use a LLM, you are required to cite your use of it in a footnote in a manner similar to the way a scientist might describe an instrument they have used in an experiment. If you use a language model and do not cite it, it will be considered academic dishonesty and an honor code violation. When submitting a write-up where you used/consulted a LLM, you should create a footnote with the following information:

·       The AI tool/program used to assist you (e.g., GPT-3)

·       The date and/or dates that you used the program to assist you

·       A general description of how AI influenced the submission, including the actual prompting language if possible. 

Here is an example footnote: “The following three paragraphs of the text have been influenced by my work with the GPT-3 Davinci model, used on 1/16/22.  Originally, I drafted and revised this write-up in response to feedback from a classmate/TA. However, even after revision, I had difficulty with the organization of the following three paragraphs. The flow did not seem correct to me. I fed these paragraphs into the LLM and prompted it with the following language: ‘These paragraphs have organization issues. Please revise them to make them more coherent.’”

Course Schedule