• ## 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

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.

 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