Abstract
dc:descriptionAlgorithmic mechanism design is an important area between computer science and economics. One of the most fundamental problems in this area is the problem of scheduling unrelated machines to minimize the makespan. The machines behave like selfish players: they have to get paid in order to process the tasks, and would lie about their processing times if they could increase their utility in this way. The problem was proposed and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n. In this thesis, we present some recent improvements of the lower bound to 1 + ?2 for three or more machines and to 1 + φ for many machines. Since the gap between the lower bound of 2.618 and the upper bound of n is huge, we also propose an alternative approach to the problem, which first attempts to characterize all truthful mechanisms and then study their approximation ratio. Towards this goal, we show that the class of truthful mechanisms for two players (regardless of approximation ratio) is very limited: tasks can be partitioned in groups allocated by affine minimizers (a natural generalization of the wellknown VCG mechanism) and groups allocated by threshold mechanisms. Finally we generalize a tool we have used in the proof of the 1 + ?2 lower bound: we give a geometrical characterization of truthfulness for the case of three tasks, which we believe that might be useful for proving improved lower bounds and which provides a more complete understanding of truthfulness.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vidali, Angelina
- Βιδάλη, Αγγελίνα
Subjects
dc:subject × 14- Αλγοριθμική θεωρία παιγνίων
- Σχεδίαση μηχανισμών
- Κάτω φράγμα
- Προσεγγιστικός αλγόριθμος
- Χαρακτηρισμοί
- Algorithmic game theory
- Mechanism design
- Lower bound
- Approximation algorithms
- Characterizations
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23970