A | B | C | D | E | F
G | H | I | J | K | L | M
N | O | P | Q | R | S | T
U | V | W | X | Y | Z
max planck institut
informatik

Homepage

Angelina Vidali

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 308
Campus E1 4,
66123 Saarbrücken
Germany

Email: angelina at mpi-inf dt mpg dt de
Phone: +49 681 9325 108
Fax: +49 681 9325 199

webpage at the University of Athens: http://users.uoa.gr/~avidali

Teaching: Algorithmic Game Theory (with Vincenzo Bonifaci and Khaled Elbassioni) Lecture time: Tuesday 16:00-18:00, Lecture room: 001, Campus E 1.3

Research Interests

My current research area is Algorithmic Game theory and especially Mechanism Design. My Phd focuses on the scheduling unrelated machines problem, when the machines are selfish players, and have to get payed in order to process the jobs. So in fact the setting is more like the setting of an auction for selling multiple items.

Which are the possible mechanisms we can use for the allocating the tasks?

Other problems I find tempting are adword auctions, cost sharing, secretary problems, voting, computation of equilibria, online algorithms.

I also enjoy computational geometry and algebra.

"Lügen, Versteigerungen und Zeitplanung": Ein kurzer, einfacher Text der erklaert womit ich mich in meiner Disertation beschaeftigt habe. (auf Deutsch)

Publications

Unification of Characterizations of Combinatorial Auction's subdomains, Elias Koutsoupias and Angelina Vidali, submitted [pdf]

Characterizing the mechanisms for the domains of combinatorial auctions and scheduling unrelated machines are two outstanding problems in mechanism design. Since the scheduling domain is essentially the subdomain of combinatorial auctions with additive valuations, we consider whether one can extend a characterization of a subdomain to a domain. This is possible for two players when the only truthful mechanisms for the subdomain are the affine maximizers. Although this is not true for scheduling because besides the ane maximizers there are other truthful mechanisms (the threshold mechanisms), we still show that the truthful mechanisms of practically any domain which is strictly superdomain of scheduling and subdomain of combinatorial auctions are only the ane maximizers.

A complete characterization of group-strategyproof mechanisms of cost-sharing. Emmanouil Pountourakis and Angelina Vidali, ESA '10 (invited to the Algorithmica special issue for ESA) [pdf]

We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides which players are going to be serviced and how much each one of them is going to pay. We determine three conditions: Fence Monotonicity, Stability of the allocation and Validity of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Fence Monotonicity puts restrictions only on the payments of the mechanism and stability only on the allocation. Consequently Fence Monotonicity characterizes group-strategyproof cost-sharing schemes. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has unbounded approximation ratio.

PhD Thesis: Game-theoretic Analysis of Networks, Supervisor: Elias Koutsoupias [pdf]

The Geometry of Truthfulness. Angelina Vidali, WINE '09 [pdf] [SLIDES] [Nisan's blog: Michal Feldman's report from WINE]

We study the geometrical shape of the partitions of the input space created by the allocation rule of a truthful mechanism for multi-unit auctions with multidimensional types and additive quasilinear utilities. We introduce a new method for describing the the allocation graph and the geometry of truthful mechanisms for an arbitrary number of items(/tasks). Applying this method we characterize all possible mechanisms for the case of three items.

Previous work shows that Monotonicity is a necessary and sufficient condition for truthfulness in convex domains. If there is only one item, monotonicity is the most practical description of truthfulness we could hope for, however for the case of more than two items and additive valuations (like in the scheduling domain) we would need a global and more intuitive description, hopefully also practical for proving lower bounds. We replace Monotonicity by a geometrical and global characterization of truthfulness.

Our results apply directly to the scheduling unrelated machines problem. Until now such a characterization was only known for the case of two tasks. It was one of the tools used for proving a lower bound of $1+\sqrt{2}$ for the case of 3 players. This makes our work potentially useful for obtaining improved lower bounds for this very important problem.

Finally we show lower bounds of $1+\sqrt{n}$ and $n$ respectively for two special classes of scheduling mechanisms, defined in terms of their geometry, demonstrating how geometrical considerations can lead to lower bound proofs.

A characterization of 2-player mechanisms for scheduling. George Christodoulou, Elias Koutsoupias and Angelina Vidali, ESA '08 [pdf], [SLIDES]

We study the mechanism design problem of scheduling unrelated machines and we completely characterize the decisive truthful mechanisms for two players when the domain contains both positive and negative values. We show that the class of truthful mechanisms is very limited: A decisive truthful mechanism partitions the tasks into groups so that the tasks in each group are allocated independently of the other groups. Tasks in a group of size at least two are allocated by an affine minimizer and tasks in singleton groups by a threshold mechanism. This characterization is about all truthful mechanisms, including those with unbounded approximation ratio.

A direct consequence of this approach is that the approximation ratio of mechanisms for two players is 2, even for two tasks. In fact, it follows that for two players, VCG is the unique algorithm with optimal approximation 2.

This characterization provides some support that any decisive truthful mechanism (for 3 or more players) partitions the tasks into groups some of which are allocated by affine minimizers, while the rest are allocated by a threshold mechanism (in which a task is allocated to a player when it is below a threshold value which depends only on the values of the other players). We also show here that the class of threshold mechanisms is identical to the class of additive mechanisms.

A $1+\phi$ lower bound for truthful scheduling mechanisms. Elias Koutsoupias and Angelina Vidali, MFCS '07 [pdf], [SLIDES]

We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in the seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound is a step towards the final resolution of this important problem.

A lower bound for scheduling mechanisms. George Christodoulou, Elias Koutsoupias and Angelina Vidali, Algorithmica '09  [pdf]

(a preliminary version appeared in: the ACM-SIAM Symposium on Discrete AlgorithmsSODA '07 [pdf], [ps])

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. 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$. We improve the lower bound to $1 + \sqrt{2}$ for 3 or more machines.

Master's Thesis: “Continued Fractions and average case analysis of the Euclidean Algorithm” Supervisor: Yiannis Moschovakis [pdf] [SLIDES]

(in English, apart from some introductory pages in Greek)  The first part is an introduction to continued fractions, and the second a detailed rewritting of the whole paper: "A.C. Yao & D.E. Knuth, Analysis of the subtractive algorithm for greatest common divisors, Proc. Nat. Acad. Sci., vol. 72 (1979), pp. 4720-4722.

Recent Positions

University of Athens: Researcher for the EU projects: FRONTS, AEOLUS

Scholarships

Alexander von Humbolt Stiftung (Postdoctoral research fellowship) 2010-2012

Max-Planck-Institut für Informatik (Postdoctoral research fellowship) 2009-2010

General Secretariat for Research and Technology (for PhD studies) 2005-2008

Alexandros Onassis foundation (for graduate studies) 2004-2005

Association for Symbolic Logic (ASL) (travel grant), June, 2005

Greek State Scholarships Foundation (ΙΚΥ) (ranked 1st, 2003-2004) and (ranked 1st, 2004-2005 (declined))

Erasmus (European Commission exchange program), summer semester 2003

Greek State Scholarships Foundation (ΙΚΥ) (ranked 5th) 1999-2000

Education

• PhD (2005- 2009) University of Athens, Department of Informatics

• Master's (2003-2005) Inter-university Program in Logic, Algorithms and Computation (MPLA) (with Hons.), ranked 1st

• Bachelor's (1999-2003), University of Athens, Department of Mathematics (with Hons.) ranked at the top 1%

Summer semester 2003: Technical University of Vienna (TUW)

Selected Talks

TU Berlin, Germany (19.05.2010)

Bertinoro Workshop: "Frontiers on Mechnanism Design" (03.2010)

University of Vienna, Austria (18.11.09)

University of Liverpool, Unighted Kingdom (03.11.09)

IDSIA (Istituto Dalle Molle di Studi sull'Intelligenza Artificiale), Lugano Switzerland (27.03.09)

EPFL (Ecole Polytechnique Fédéral de Lausanne), Switzerland (02.02.09)

Private

Hobbies

• literature, movies, drawing, music