192.118 Algorithmic Social Choice
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021S, VU, 4.0h, 6.0EC
TUWEL

Properties

  • Semester hours: 4.0
  • Credits: 6.0
  • Type: VU Lecture and Exercise
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to...

  • explain and identify basic concepts, structures, and problems from collective decision making,
  • describe and design efficient algorithms, and analyze properties (e.g., computational complexity, existence or stability of solutions, characterizations) of problems arising in the context of collective decision making and related fields.

 

Subject of course

The course addresses problems at the intersection of economics, social choice theory, and computer science. The focus is on processes of algorithmic decision making, such as voting rules or fair division. We discuss fundamental concepts from collective decision making and related topics and investigate algorithmic and computational aspects.

Specific topics include:

  • aggregating preferences (rank aggregation) and voting,
  • preference domain restrictions,
  • matchings under preferences,
  • algorithmic mechanism design,
  • cake cutting protocols,
  • fair allocation of resources, and
  • judgment aggregation.

Teaching methods

The course will consist of lectures and exercises. The students will receive an exercise sheet 1-2 weeks before each exercise and are expected to submit their solutions in advance and also to be able to present the solutions on the whiteboard. Exercise sheets will be available for download.

The first lecture takes place on March 5th, 10:15-11:15, via Zoom.

 Please register and go to the Tuwel forum to see the zoom link.

Mode of examination

Immanent

Additional information

ECTS Breakdown

36 h: Lectures
68 h: Solving and presenting the solutions of the 4 exercise sheets
22 h: Preparation and follow-up
23.5 h: Exam preparation
0.5 h: Exam
----------

Sum: 150 h
ECTS: 6

 

Literature

  • F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, ed.:Handbook of Computational Social Choice. Cambridge University Press, 2015.
  • U. Endriss, ed: Trends in Computational Social Choice. AI Access, 2017
  • D. Gusfield and R. Irving: The Stable Marriage Problem--Structure and Algorithms. MIT Press, 1989
  • D. Manlove: Algorithmics of Matchihng under Preferences, World Scientific Press, 2013
  • J. Rothe, ed.: Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer, 2015
  • Y. Shoham, K. Leyton-Brown: Multiagent Systems. Cambridge University Press, 2009

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri10:15 - 11:3005.03.2021 zoom (LIVE)Introductory session
Wed14:00 - 16:0010.03.2021 - 30.06.2021 zoom (LIVE)Lecture/exercises
Fri10:15 - 11:4512.03.2021 - 02.07.2021 zoom (LIVE)Lecture/exercises
Algorithmic Social Choice - Single appointments
DayDateTimeLocationDescription
Fri05.03.202110:15 - 11:30 zoomIntroductory session
Wed10.03.202114:00 - 16:00 zoomLecture/exercises
Fri12.03.202110:15 - 11:45 zoomLecture/exercises
Wed17.03.202114:00 - 16:00 zoomLecture/exercises
Fri19.03.202110:15 - 11:45 zoomLecture/exercises
Wed24.03.202114:00 - 16:00 zoomLecture/exercises
Fri26.03.202110:15 - 11:45 zoomLecture/exercises
Wed31.03.202114:00 - 16:00 zoomLecture/exercises
Fri02.04.202110:15 - 11:45 zoomLecture/exercises
Wed07.04.202114:00 - 16:00 zoomLecture/exercises
Fri09.04.202110:15 - 11:45 zoomLecture/exercises
Wed14.04.202114:00 - 16:00 zoomLecture/exercises
Fri16.04.202110:15 - 11:45 zoomLecture/exercises
Wed21.04.202114:00 - 16:00 zoomLecture/exercises
Fri23.04.202110:15 - 11:45 zoomLecture/exercises
Wed28.04.202114:00 - 16:00 zoomLecture/exercises
Fri30.04.202110:15 - 11:45 zoomLecture/exercises
Wed05.05.202114:00 - 16:00 zoomLecture/exercises
Fri07.05.202110:15 - 11:45 zoomLecture/exercises
Wed12.05.202114:00 - 16:00 zoomLecture/exercises

Examination modalities

Exercise + oral exam

Course registration

Begin End Deregistration end
18.02.2021 00:00 08.03.2021 23:55

Curricula

Literature

No lecture notes are available.

Previous knowledge

Basic knowledge of algorithmic design. Good to have heard:

  1. Algorithmen und Datenstrukturen,
  2. Algorithmics,
  3. Komplexitätstheorie, etc.

Language

English