A Lower Bound of 1 + φ for Truthful
Scheduling Mechanisms 1st Edition by Elias
Koutsoupias, Angelina Vidali ISBN 9783540744566
pdf download
https://ebookball.com/product/a-lower-bound-
of-1aeur-0-aeur-0i-for-truthful-scheduling-mechanisms-1st-
edition-by-elias-koutsoupias-angelina-vidali-
isbn-9783540744566-10762/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Electricity AC DC Motors Controls and Maintenace 10th Edition by
Jeffrey Keljik 1111646759 9781111646752
https://ebookball.com/product/electricity-ac-dc-motors-controls-
and-maintenace-10th-edition-by-jeffrey-
keljik-1111646759-9781111646752-17638/
(Ebook PDF) High Power Converters and AC Drives 2nd edition by Bin Wu,
Mehdi Narimani 1119156068 9781119156062 full chapters
https://ebookball.com/product/ebook-pdf-high-power-converters-
and-ac-drives-2nd-edition-by-bin-wu-mehdi-
narimani-1119156068-9781119156062-full-chapters-14628/
Selfish Load Balancing Under Partial Knowledge 1st Editoin by Elias
Koutsoupias, Panagiota N Panagopoulou, Paul Spirakis ISBN
9783540744566
https://ebookball.com/product/selfish-load-balancing-under-
partial-knowledge-1st-editoin-by-elias-koutsoupias-panagiota-n-
panagopoulou-paul-spirakis-isbn-9783540744566-10764/
A general lower bound for the linear complexity of the product of
shift register sequences 1st Edition by Goettfert Niederreiter ISBN
https://ebookball.com/product/a-general-lower-bound-for-the-
linear-complexity-of-the-product-of-shift-register-sequences-1st-
edition-by-goettfert-niederreiter-isbn-9844/
,Introduction To 80 86 Assembly Language And Computer Architecture 1st
Edition by Detmer ISBN 0763717738 9780763717735
https://ebookball.com/product/introduction-to-80-86-assembly-
language-and-computer-architecture-1st-edition-by-detmer-
isbn-0763717738-9780763717735-12404/
Introduction to 80 86 Assembly Language and Computer Architecture 1st
Edition by Richard C Detmer ISBN 0763746622 9780763746629
https://ebookball.com/product/introduction-to-80-86-assembly-
language-and-computer-architecture-1st-edition-by-richard-c-
detmer-isbn-0763746622-9780763746629-9016/
Machine Learning for Cybersecurity Cookbook Over 80 recipes on how to
implement machine learning algorithms for building security systems
using Python 1st edition by Emmanuel Tsukerman 9781838556341
1838556346
https://ebookball.com/product/machine-learning-for-cybersecurity-
cookbook-over-80-recipes-on-how-to-implement-machine-learning-
algorithms-for-building-security-systems-using-python-1st-
edition-by-emmanuel-tsukerman-9781838556341-1/
Cunningham’s Manual of Practical Anatomy Volume 1 Upper and lower
limbs 16th Edition by Rachel Koshi ISBN 0198749363 9780198749363
https://ebookball.com/product/cunninghamaeurtms-manual-of-
practical-anatomy-volume-1-upper-and-lower-limbs-16th-edition-by-
rachel-koshi-isbn-0198749363-9780198749363-3098/
Paediatric Radiology Rapid Reporting for FRCR Part 2B 1st edition by
Michael Paddock,Amaka Offiah 3030019659 9783030019655
https://ebookball.com/product/paediatric-radiology-rapid-
reporting-for-frcr-part-2b-1st-edition-by-michael-paddock-amaka-
offiah-3030019659-9783030019655-6052/
, A Lower Bound of 1 + φ for Truthful Scheduling
Mechanisms
Elias Koutsoupias and Angelina Vidali
Department of Informatics, University of Athens
{elias,avidali}@di.uoa.gr
Abstract. We give an improved lower bound for the approximation ra-
tio of truthful mechanisms for the unrelated machines scheduling prob-
lem. The mechanism design version of the problem which was proposed
and studied in a seminal paper of Nisan and Ronen is at the core of the
emerging area of Algorithmic Game Theory. The new lower bound 1+φ ≈
2.618 is a step towards the final resolution of this important problem.
1 Introduction
We study the classical scheduling problem on unrelated machines [15,21,16] from
the mechanism-design point of view. There are n machines and m tasks each with
different execution times on each machine. The objective of the mechanism is to
schedule the tasks on the machines to minimize the makespan, i.e. to minimize
the time we have to wait until all tasks are executed. In the mechanism-design
version of the problem, the machines are selfish players that want to minimize the
execution time of the tasks assigned to them. To overcome their “laziness” the
mechanism pays them. With the payments, the objective of each player/machine
is to minimize the time of its own tasks minus the payment. A loose interpreta-
tion of the payments is that they are given to machines as an incentive to tell
the truth. A mechanism is called truthful when telling the truth is a dominant
strategy for each player: for all declarations of the other players, an optimal
strategy of the player is to tell the truth. A classical result in mechanism de-
sign, the Revelation Principle, states that for every mechanism, in which each
player has a dominant strategy, there is a truthful mechanism which achieves the
same objective. The Revelation Principle allows us to concentrate on truthful
mechanisms (at least for the class of centralized mechanisms).
A central question in the area of Algorithmic Mechanism Design is to deter-
mine the best approximation ratio of mechanisms. This question was raised by
Nisan and Ronen in their seminal work [23] and remains wide open today. The
current work improves the lower bound on the approximation to 1 + φ ≈ 2.618,
where φ is the golden ratio.
A lower bound on the approximation ratio can be of either computational or
information-theoretic nature. A lower bound is computational when it is based
on some assumption about the computational resources of the algorithm, most
Supported in part by IST-15964 (AEOLUS) and the Greek GSRT.
L. Kučera and A. Kučera (Eds.): MFCS 2007, LNCS 4708, pp. 454–464, 2007.
c Springer-Verlag Berlin Heidelberg 2007
Scheduling Mechanisms 1st Edition by Elias
Koutsoupias, Angelina Vidali ISBN 9783540744566
pdf download
https://ebookball.com/product/a-lower-bound-
of-1aeur-0-aeur-0i-for-truthful-scheduling-mechanisms-1st-
edition-by-elias-koutsoupias-angelina-vidali-
isbn-9783540744566-10762/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Electricity AC DC Motors Controls and Maintenace 10th Edition by
Jeffrey Keljik 1111646759 9781111646752
https://ebookball.com/product/electricity-ac-dc-motors-controls-
and-maintenace-10th-edition-by-jeffrey-
keljik-1111646759-9781111646752-17638/
(Ebook PDF) High Power Converters and AC Drives 2nd edition by Bin Wu,
Mehdi Narimani 1119156068 9781119156062 full chapters
https://ebookball.com/product/ebook-pdf-high-power-converters-
and-ac-drives-2nd-edition-by-bin-wu-mehdi-
narimani-1119156068-9781119156062-full-chapters-14628/
Selfish Load Balancing Under Partial Knowledge 1st Editoin by Elias
Koutsoupias, Panagiota N Panagopoulou, Paul Spirakis ISBN
9783540744566
https://ebookball.com/product/selfish-load-balancing-under-
partial-knowledge-1st-editoin-by-elias-koutsoupias-panagiota-n-
panagopoulou-paul-spirakis-isbn-9783540744566-10764/
A general lower bound for the linear complexity of the product of
shift register sequences 1st Edition by Goettfert Niederreiter ISBN
https://ebookball.com/product/a-general-lower-bound-for-the-
linear-complexity-of-the-product-of-shift-register-sequences-1st-
edition-by-goettfert-niederreiter-isbn-9844/
,Introduction To 80 86 Assembly Language And Computer Architecture 1st
Edition by Detmer ISBN 0763717738 9780763717735
https://ebookball.com/product/introduction-to-80-86-assembly-
language-and-computer-architecture-1st-edition-by-detmer-
isbn-0763717738-9780763717735-12404/
Introduction to 80 86 Assembly Language and Computer Architecture 1st
Edition by Richard C Detmer ISBN 0763746622 9780763746629
https://ebookball.com/product/introduction-to-80-86-assembly-
language-and-computer-architecture-1st-edition-by-richard-c-
detmer-isbn-0763746622-9780763746629-9016/
Machine Learning for Cybersecurity Cookbook Over 80 recipes on how to
implement machine learning algorithms for building security systems
using Python 1st edition by Emmanuel Tsukerman 9781838556341
1838556346
https://ebookball.com/product/machine-learning-for-cybersecurity-
cookbook-over-80-recipes-on-how-to-implement-machine-learning-
algorithms-for-building-security-systems-using-python-1st-
edition-by-emmanuel-tsukerman-9781838556341-1/
Cunningham’s Manual of Practical Anatomy Volume 1 Upper and lower
limbs 16th Edition by Rachel Koshi ISBN 0198749363 9780198749363
https://ebookball.com/product/cunninghamaeurtms-manual-of-
practical-anatomy-volume-1-upper-and-lower-limbs-16th-edition-by-
rachel-koshi-isbn-0198749363-9780198749363-3098/
Paediatric Radiology Rapid Reporting for FRCR Part 2B 1st edition by
Michael Paddock,Amaka Offiah 3030019659 9783030019655
https://ebookball.com/product/paediatric-radiology-rapid-
reporting-for-frcr-part-2b-1st-edition-by-michael-paddock-amaka-
offiah-3030019659-9783030019655-6052/
, A Lower Bound of 1 + φ for Truthful Scheduling
Mechanisms
Elias Koutsoupias and Angelina Vidali
Department of Informatics, University of Athens
{elias,avidali}@di.uoa.gr
Abstract. We give an improved lower bound for the approximation ra-
tio of truthful mechanisms for the unrelated machines scheduling prob-
lem. The mechanism design version of the problem which was proposed
and studied in a seminal paper of Nisan and Ronen is at the core of the
emerging area of Algorithmic Game Theory. The new lower bound 1+φ ≈
2.618 is a step towards the final resolution of this important problem.
1 Introduction
We study the classical scheduling problem on unrelated machines [15,21,16] from
the mechanism-design point of view. There are n machines and m tasks each with
different execution times on each machine. The objective of the mechanism is to
schedule the tasks on the machines to minimize the makespan, i.e. to minimize
the time we have to wait until all tasks are executed. In the mechanism-design
version of the problem, the machines are selfish players that want to minimize the
execution time of the tasks assigned to them. To overcome their “laziness” the
mechanism pays them. With the payments, the objective of each player/machine
is to minimize the time of its own tasks minus the payment. A loose interpreta-
tion of the payments is that they are given to machines as an incentive to tell
the truth. A mechanism is called truthful when telling the truth is a dominant
strategy for each player: for all declarations of the other players, an optimal
strategy of the player is to tell the truth. A classical result in mechanism de-
sign, the Revelation Principle, states that for every mechanism, in which each
player has a dominant strategy, there is a truthful mechanism which achieves the
same objective. The Revelation Principle allows us to concentrate on truthful
mechanisms (at least for the class of centralized mechanisms).
A central question in the area of Algorithmic Mechanism Design is to deter-
mine the best approximation ratio of mechanisms. This question was raised by
Nisan and Ronen in their seminal work [23] and remains wide open today. The
current work improves the lower bound on the approximation to 1 + φ ≈ 2.618,
where φ is the golden ratio.
A lower bound on the approximation ratio can be of either computational or
information-theoretic nature. A lower bound is computational when it is based
on some assumption about the computational resources of the algorithm, most
Supported in part by IST-15964 (AEOLUS) and the Greek GSRT.
L. Kučera and A. Kučera (Eds.): MFCS 2007, LNCS 4708, pp. 454–464, 2007.
c Springer-Verlag Berlin Heidelberg 2007
