Back to search

National and Kapodistrian University of Athens

Παιγνιοθεωρητική ανάλυση δικτύων

Abstract

dc:description

Algorithmic 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23970

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Vidali, Angelina; Βιδάλη, Αγγελίνα. Παιγνιοθεωρητική ανάλυση δικτύων. National and Kapodistrian University of Athens, 2009. http://hdl.handle.net/10442/hedi/23970