COM 313 Spring 2015
Topics in Algorithmic Game Theory
http://oak.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 sell its ad spaces for its search pages? 

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

·         Which friend on Facebook most effectively influences others? 

·         Why must most voting systems be fundamentally flawed? 

·         When will altruism in a networked system prevail? 

·         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.

Course Info/Policies

 

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

 

Lectures:

 

Tuesdays and Thursdays, 11:50 – 1:05 in New London Hall 204

Professor:

 

Dr. Christine Chung

http://cs.conncoll.edu/cchung

cchung@conncoll.edu
860-439-2074

New London Hall 220

Office hours:  Mondays 10-1 (please sign up for appointment slots)

 

Grading:

Written homework assignments -- there will be homework exercises assigned after each class, collected at the start of the following class

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 citing your sources, depending on how much help you had, you may not earn full credit for the assignment.)

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 at the start of class in hard copy (either typed or hand-written).  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. 

·         Homework turned in after class starts is considered late.  (If you are late to class, your warm-up will be late.)  Late submissions will be accepted until the start of the next class, and will earn a maximum grade of 3. 

 

Course Materials

Required texts (for the first unit of the course only)

·         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: http://www.cs.columbia.edu/coms6998-3/)

·         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 (which applies to all your classes)

*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, 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.  

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.  Our offices are located in Main Street West, The Plex.  Please visit us or call 860-439-5294 for more information or to schedule an appointment.

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.  To make an appointment, call 860-439-2173 or stop by the Writing Center at 214 Blaustein.  If you're a confident, experienced writer we can help you to push your ideas and polish your style; if you're a relatively inexperienced and not-so-confident writer we can also help you, by working on grammar or organization or whatever you need.  Writing Center tutors are trained to help you to discover what you think through writing.  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 workbefore 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

If you have a physical, mental or learning disability, either hidden or visible, which may require classroom, test-taking, or other reasonable modifications, please see me as soon as possible. If you have not already done so, please be sure to register with the Office of Student Accessibility Services. You can do so by going to the Office of Student Accessibility Services, which is located in Crozier Williams, Room 221, or by contacting the Office at campus extensions 5240 or 5428, or by email to barbara.mcllarky@conncoll.edu or lillian.liebenthal@conncoll.edu

Title IX Confidentiality/Mandated Reporter 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 mandated reporters of any incidents of sexual misconduct.  That means that I cannot keep information about sexual misconduct confidential if you share that information with me.  Darcie Folsom, the Director of Sexual Violence Prevention and Advocacy, can advise you confidentially as can Counseling Services and any of the College chaplains.  Darcie can also help you access other resources on campus and in the local community.   You can reach Darcie at x2219 or darcie.folsom@conncoll.edu, and her office is in Cro 222.

The student sexual misconduct policy is in the Student Handbook, 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.

Student Health Services

Student Health Services, located in the Warnshuis Student Health Center behind the library, is available to all full-time, matriculated students. Our purpose is to help students maintain optimal general health through the disciplines of physical and mental health, and health education around lifestyle choices. This is accomplished through a full-time staff and a variety of professional consultants in many disciplines. All professional services are delivered with attention to confidentiality. In the event of a serious illness or injury, parents or guardian will be notified at the discretion of the staff. You can schedule an appointment Monday through Friday by calling 860-439-2275. Information on Care When We Are Closed, Our Services, and Student Health Insurance may be found on Camelweb, in the Student Life Section, under Student Health Services

Student Counseling Services

The mission of the Student Counseling Services is to promote the emotional and psychological growth and well being of the students at Connecticut College. The Student Counseling Services' goal is to enhance each individual's ability to learn, to create and to be fully participating members of the College community by utilizing safe, culturally sensitive and inclusive approaches to mental health treatment.To carry out this mission, Student Counseling Services makes available to students a wide range of outpatient clinical services in a safe, non-judgmental atmosphere including:

·         Evaluation

·         Individual and group counseling

·         Psychopharmacological evaluation and medication management

·         Crisis intervention services

·         Outreach and consultation to the College community

·         Psycho-educational forums

·         Referral to off-campus clinicians for specialized and/or intensive treatment

Connecticut College Student Counseling Services has been accredited by the International Accreditation of Counseling Services (IACS) since 2005. Appointments may be made by phone at (860) 439-4587 or via email at SCS@conncoll.edu.

Course Schedule