Algorithms, Game Theory and Fairness (3 credits)

• Overview

  Recent years have seen a dramatic rise in the use of algorithms for solving problems involving strategic decision makers. Deployed algorithms now assist in a variety of economic interactions: assigning medical residents to schools, allocating students to courses, allocating security resources in airports, allocating computational resources and dividing rent. We will explore foundational topics at the intersection of economics and computation, starting with the foundations of game theory: Nash equilibria, the theory of cooperative games, before proceeding to covering more advanced topics: matching algorithms, allocation of indivisible goods, and mechanism design.

• Learning Objectives

  I hope that by the end of the class students will be able to understand and apply fundamental concepts from:

  1. game theory.
  2. fair division problems with divisible/indivisible goods, both with and without money (e.g. pareto optimality, maximin share, envy-freeness).
  3. mechanism design
  4. algorithmic techniques (e.g. approximation, linear programming, combinatorial and graph algorithms), in order to compute EconCS solution concepts.

  This class tends is more theory oriented - I don't intend on having programming assignments or coding, but rather focus on algorithmic analysis.

• Course Syllabus

  Most of the material we cover appears in the following textbooks, some of them are freely available online.

  • Algorithmic Game Theory (Nisan et al., Eds.)
  • Computational Aspects of Cooperative Game Theory (Chalkiadakis et al., Eds.)
  • Handbook of Computational Social Choice (Brandt et al., Eds.)
  • A Course in Game Theory, by Osborne and Rubinstein (MIT Press)

  The syllabus is subject to change based on class progress and external factors. Homework problem sets will be due in class one week after assigned.

  • Introduction: Nash equilibria and the minimax theorem – 2 lectures.
  • No Regret Learning, the Multiplicative Weights Update Algorithm and Zero-Sum Games – 2 lectures.
  • Existence of Nash Equilibria and Brouwer’s Fixed Point Theorem - 2 lectures
  • Computing Nash Equilibria--- one lecture.
  • Routing Games and the Price of Anarchy – 2 lectures
  • Stable Matching and the Gale-Shapley Algorithm – 2 lectures
  • Fair Allocation of Indivisible Goods – 3 lectures
  • Rent Division – one lecture
  • Mechanism Design with and without money – 4 lectures
  • Cooperative Games – The Core – 2 lectures
  • Cooperative Games – The Shapley Value – 2 lectures
  • The Nash Bargaining Solution – 2 lectures

• Class Policies

  Reading and lectures

  Students must read all assigned material before lecture begins.

  Homework

  You may collaborate and consult outside sources freely when doing homework, but you should tell me who you are collaborating with. Homework will be accepted up to 48 hours after the due time with a 10% penalty if turned in within the first 24 hours and an additional 10% penalty if turned in within the second 24 hours. Later submissions will be automatically given a grade of 0 (if you see you are having problems submitting on time please let me know and we'll try to figure it out).

  Exams

  There will be two evening midterms during the class (usually on weeks 7 and 10). They will be open-book/open-notes. Students may use any printed materials they wish during the exam, but may not use electronic devices except for use as timepieces or legitimate use by disabled students with prior notice. No make-up exams will be given except under extreme circumstances (such as severe illness or death in the immediate family) in which case students must give me notice well before the exam if possible.

  Grade Breakdown

  Coursework	Fraction of Grade
  Homework	50%
  Midterm I	25%
  Midterm II	25%

  Attendance

  I will not be taking attendance; students who cannot attend class are responsible for any material covered during their absence.

• Policy Statements (Accommodation and Academic Honesty)

  Accommodation Statement

  The University of Massachusetts Amherst is committed to providing an equal educational opportunity for all students. If you have a documented physical, psychological, or learning disability on file with Disability Services (DS), you may be eligible for reasonable academic accommodations to help you succeed in this course. If you have a documented disability that requires an accommodation, please notify me within the first two weeks of the semester so that we may make appropriate arrangements

  Academic Honesty Statement

  Since the integrity of the academic enterprise of any institution of higher education requires honesty in scholarship and research, academic honesty is required of all students at the University of Massachusetts Amherst. Academic dishonesty is prohibited in all programs of the University. Academic dishonesty includes but is not limited to: cheating, fabrication, plagiarism, and facilitating dishonesty. Appropriate sanctions may be imposed on any student who has committed an act of academic dishonesty. Instructors should take reasonable steps to address academic misconduct. Any person who has reason to believe that a student has committed academic dishonesty should bring such information to the attention of the appropriate course instructor as soon as possible. Instances of academic dishonesty not related to a specific course should be brought to the attention of the appropriate department Head or Chair. Since students are expected to be familiar with this policy and the commonly accepted standards of academic integrity, ignorance of such standards is not normally sufficient evidence of lack of intent (for more details see here).