Computational Social Processes

Course overview

This is an introductory course on the theory and application of computational techniques and computational thinking in various problems in ecoonmics.
Instructor: Lirong Xia (xial@cs.rpi.edu). Please call me Lirong.
Time: Tuesday Friday 2:00 pm-3:50 pm
Location: Lally 102
Office hours: Tue 4-5 pm, Lally 306
Piazza: piazza.com/rpi/fall2016/6110
Online Preference Reporting and Aggregation (OPRA): www.opra.tech
- please send me any comments or suggestions or functionalities you want to have
- Github page: https://github.com/PrefPy/opra
Prefpy: https://github.com/PrefPy/prefpy

Schedule

Week	Date	Topic	By	Slides	Further reading
1	8-30	Introduction to the course	Lirong Xia	pdf ppsx
1	9-2	Preferences, utility theory	Lirong Xia	pdf ppsx
2	9-6	Social choice: voting rules	Lirong Xia	pdf ppsx	SLB 9.1-9.4
2	9-9	Social choice: axioms	Lirong Xia	pdf ppsx	SLB 9.1-9.4
3	9-13	Linear and integer programming, computational complexity		pdf ppsx
3	9-16 HW1	Computational social choice		pdf ppsx
4	9-20	Social choice: manipulation	Lirong Xia	pdf ppsx	CACM
4	9-23 HW1 Due	Social choice: statistical approaches	Lirong Xia	pdf ppsx
5	9-27 HW2	Game theory: normal-form games	Lirong Xia	pdf ppsx	SLB 3.2; 3.3-3.3.2; 5.1
5	9-30	Game theory: normal-form games		pdf ppsx
6	10-4 HW2 Due by midnight HW3	Game theory: extensive-form games
6	10-7	Game theory: Bayesian games
7	10-11 no class, Monday schedule HW3 Due by midnight
7	10-14	Review for midterm
8	10-18 In-class Midterm exam	Manipulation in voting
8	10-21 Drop deadline	Condorcet Jury Theorem
9	10-25	Bayesian voting games
9	10-28 Presentation	Auctions	Lirong Xia	pdf	Mechanism Theory
10	11-1	Mechanism design: implementation, revelation principle		pdf
10	11-4	Matching	Lirong Xia	pdf
11	11-8	Fair division	Lirong Xia	pdf	End-10
11	11-11 Presentation
12	11-15	Judgement aggregation and recommender systems	Lirong Xia	pdf	List-12, A nice book chapter
12	11-18 Presentation
13	11-22	Review
13	11-25 No class, Thanksgiving
14	11-29	Hypothesis testing, Project presentation: Yun		pdf
14	12-2	Project presentation: Tristan, Tobe, Steven, Salam, Phil
15	12-6	Project presentation: Nick, marava2, Macfar, Lam, Jun
15	12-9	Project presentation: Jon, Jim, Fay, Chunheng, Barry
16	12-13
16	12-16
17
17

Prerequisites

A qualified student should have taken undergraduate-level courses on
1. Linear algebra
2. Algorithm design (e.g. CSCI-2300 Introduction to Algorithms)
3. Probability or statistics
4. One of the following:
  - Artificial Intelligence (e.g. CSCI-4150 Introduction to Artificial Intelligence)
  - Machine learning (e.g. CSCI-4100/6100 Machine and Computational Learning)
  - Optimization
  - Microeconomics theory
A student with strong backgrounds and skills in mathematics, computational complexity theory, algorithm design, or statistics will be likely to enjoy the course (especially working on your project). If you are unsure about your qualification please contact me.

Grading

grade

Project ideas
- Implement and test voting methods at Prefpy
  - STV
  - ranked pairs
  - Schulze
  - Kemeny
  - Slater
  - Dodgson
  - Other multi-winner election methods
- Implement matching mechanisms at Prefpy
  - Deferred acceptance
  - Top trading cycles

Groups

Barry: recommender systems
Chunheng: rank aggregation
Fay: DA&TTC
Jim: Schulze
Jon Xu: Bitcoin
Jun: MOV
Lam: STV
Macfar: OPRA
marava2: recommender systems
Nick: multi-winner rules
phil: STV
Salam: Ranked pairs
Steven: peer grading
Tobe (tezekwe1). Kemeny
Tristan: mixturue models
Yun: differential privacy

References

There is no textbook. The following survey offers a great introduction to the field.

Felix Brandt, Vincent Conitzer, and Ulle Endriss. Computational Social Choice, 2013.

Also you may find the following books useful, especially the first by Shoham and Leyton-Brown (thus SLB). All of them have free non-printable versions for download.

Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, 2009.
N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, Algorithmic Game Theory, 2007.
M. J. Osborne and A. Rubinstein, A Course in Game Theory, 1994.

Acknowledgements

Similar courses were taught at:

Thanks Felix Brandt, Yiling Chen, Ulle Endriss, Vincent Conitzer, David Parkes, Ariel Procaccial, Sven Seuken, Yi Zhang for offering tremendous helps on developing the course!