Integer Programming and Computational Social Choice - NTIN113

• Title: Integer Programming and Computational Social Choice
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2023
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: English
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: Mgr. Martin Koutecký, Ph.D.

Annotation

Last update: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)

Integer Programming is an optimization tool rich both in theory and applications. Computational Social Choice is a field of growing relevance which considers the computational aspects of elections, fair divison, opinion dynamics, etc. In this course, we will describe algorithms for important IP and IP-related problems, and show their applications to problems from computational social choice.

Literature

Last update: Mgr. Martin Koutecký, Ph.D. (29.01.2024)

Friedrich Eisenbrand: Integer Programming and Algorithmic Geometry of Numbers - A tutorial. 50 Years of Integer Programming 2010: 505-559

Martin Koutecký, Asaf Levin, Shmuel Onn: A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. ICALP 2018: 85:1-85:14

Dusan Knop, Martin Koutecký, Matthias Mnich: A Unifying Framework for Manipulation Problems. AAMAS 2018: 256-264

Martin Koutecký, Nimrod Talmon: Multi-Party Campaigning. AAAI 2021: 5506-5513

Syllabus

Last update: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)

• Lenstra's algorithm (fixed-dimension IP)

• Graver basis definitions, properties, bounds, generic iterative augmentation algorithm

• n-fold and 2-stage stochastic IPs, treedepth generalization

• elections, voting rules, bribery problems

• opinion diffusion

• campaigning and Cooper's algorithm for Presburger Arithmetic