National Technical University of Athens (NTUA)
Mechanism design, social choice and equilibrium computation in restricted domains
Abstract
dc:descriptionAbstract: The work in this thesis primarily revolves around efficient algorithmic frameworks for settings where information is not readily available. Specifically, we look at limitations of provided information from three main angles: (1) Information is difficult to quantify. In this line of work we focused on distortion in voting (JAIR ’22, AAAI ’22), which is the notion that quantifies the impact of being able to use only limited information on the social welfare of the outcome (i.e. in terms of approximation). Here 1 we study both the effects of various forms of limited information on metric distortion and also the distortion of a very popular mechanism, STV, in relation to the dimensionality of the underlying metric space. (2) Information is private to strategic agents and needs to be revealed to the algorithm through properly designed incentives. This area is commonly referred to as mechanism design and my related work focuses on fighting strong impossibility results by restricting our analysis in “natural” sub-classes of the general instance space (WINE ’21). In this setting we have studied the approximability of the facility location problem by truthful mechanisms, whose allocation is aligned with the agent incentives. (3) Communication is expensive. Combining this restriction along with the strategic environment described previously, we show that known mechanisms have implementations with asymptotically optimal communication complexity (SAGT ’20). In most of our works, our objective is to maximize the social welfare. Furthermore, some work has been focused on a classical aspect of algorithmic game theory, that of equilibrium computation, where we study the complexity of computing a Pure Nash Equilibrium in linear weighted congestion games and also show an efficient algorithm for computing approximate equilibria in a natural subclass of Max-Cut games (ICALP ’20).
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Patsilinakos, Panagiotis
- Πατσιλινάκος, Παναγιώτης
Subjects
dc:subject × 26- Αλγοριθμική θεωρία παιγνίων
- Αλγοριθμική κοινωνική επιλογή
- Προσεγγιστικοί αλγόριθμοι
- Υπολογιστική πολυπλοκότητα
- Σχεδιασμός μηχανισμών
- Σχεδιασμός αλγορίθμων
- Μετρική παραμόρφωση
- Υπολογισμός ισορροπιών
- Πολυπλοκότητα επικοινωνίας
- Ανάλυση πέραν της χειρότερης περίπτωσης
- Algorithmic game theory
- Algorithmic social choice
- Mechanism design
- Approximation algorithms
- Computational complexity
- Communication complexity
- Equilibrium computations
- Metric distortion
- Beyond worst case analysis
- Algorithm design
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Computer science, Hardware and Architecture
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/54559