We introduce and study strongly truthful mechanisms and their applications. We use strongly truthful mechanisms as a tool for implementation in undominated strategies for several problems,including the design of externality resistant auctions and a variant of multi-dimensional scheduling.

http://arxiv.org/abs/1208.3939

[pdf]

The design of truthful auctions that approximate the optimal expected revenue is a central problem in algorithmic mechanism design. 30 years after Myerson's characterization of Bayesian optimal auctions in single-parameter domains~\cite{M81}, characterizing but also providing efficient mechanisms for multi-parameter domains still remains a very important unsolved problem.

Our work improves upon recent results in this area, introducing new techniques for tackling the problem, while also combining and extending recently introduced tools.

The already extended literature in Combinatorial Auctions, Public Projects and Scheduling demands a more systematic classification of the domains and a clear comparison of the results known. Connecting characterization results for different settings and providing a characterization proof using another characterization result as a black box without having to repeat a tediously similar proof is not only elegant and desirable, but also greatly enhances our intuition and provides a classification of different results and a unified and deeper understanding.

(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."

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.

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.