Tight bounds for fractional and randomized truthful scheduling
Auteurs : Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
Résumé scientifique
We resolve one of the longest-standing open problems in algorithmic mechanism design by showing that randomization cannot yield a sublinear approximation for truthful scheduling on unrelated machines, even when truthfulness is required only in expectation. Our main technical result concerns fractional scheduling, where tasks may be split among machines. We prove that every deterministic truthful fractional mechanism on $n$ unrelated machines has worst-case approximation ratio at least $(n+1)/2$, even against the optimal integral makespan. This matches the known upper bound exactly and settles the optimal approximation ratio of truthful fractional scheduling. Since the expected allocations and payments of a truthful-in-expectation mechanism define a truthful fractional mechanism, the same lower bound applies to all truthful-in-expectation mechanisms and, in particular, to all universally truthful mechanisms. On the positive side, we give a universally truthful mechanism with approximation ratio $n/2+o(n)$. Together, these results establish the optimal leading constant $1/2$ for randomized truthful scheduling. Thus, randomization improves on the optimal deterministic approximation ratio by an asymptotic factor of two, and no more.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated MachinesXu-Jin Chen, D. Du, L. Zuluaga · 2013 · Theory of Computing Systems · cité 18 fois · Pas encore résumé
Copula-based Randomized Mechanisms conçoit un mécanisme véridique randomisé pour deux machines non apparentées, tandis que cet article établit des bornes générales pour n machines.
Résumé scientifique
We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within [1.5852,1.58606], offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the known lower bound of 1.506 for the scale-free truthful mechanisms. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other related problems in the future.
-
An Improved Randomized Truthful Mechanism for Scheduling Unrelated MachinesPin-Yan Lu, Chang-Yuan Yu · 2008 · Symposium on Theoretical Aspects of Computer Science · cité 38 fois · Pas encore résumé
An Improved Randomized Truthful Mechanism construit des mécanismes randomisés à meilleur rapport pour deux machines et pour m machines, là où cet article établit des bornes optimales asymptotiques.
Résumé scientifique
We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a $1.75$-approximation randomized truthful mechanism for the case of two machines. We improve this result by a $1.6737$-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m( Mu'alem and Schapira 2007)
-
Universally truthful mechanisms for schedulingA. Anastasiadis, G. Christodoulou, Elias Koutsoupias et al. · 2026 · arXiv.org · preprint, non relu par les pairs · cité 2 fois · Pas encore résumé
Universally truthful mechanisms étudie les bornes d’approximation des mécanismes randomisés universellement véridiques pour l’ordonnancement sur machines non apparentées.
Résumé scientifique
We consider universally truthful randomized mechanisms for the problem of scheduling $m$ jobs on $n$ unrelated machines. We prove a lower bound on the expected approximation ratio of every such mechanism whose probability distribution has discrete support. We show that no universally truthful randomized mechanism in this class can achieve approximation ratio smaller than $n/12 - o(n)$ with respect to the optimal makespan. We match this, up to a constant factor, by a mechanism with approximation ratio $n/2 + o(n)$.
-
Setting Lower Bounds on TruthfulnessAhuva Mu'alem, Michael Schapira · 2007 · ACM-SIAM Symposium on Discrete Algorithms · cité 24 fois · Pas encore résumé
Setting Lower Bounds on Truthfulness établit des bornes d’inapproximabilité pour l’ordonnancement véridique, y compris lorsque la véracité est exigée en espérance.
Résumé scientifique
We present general techniques for proving inapproximability results for several paradigmatic truthful multidimensional mechanism design problems. In particular, we demonstrate the strength of our techniques by exhibiting a lower bound of 2 − 1 m for the scheduling problem with m unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms, regardless of any computational assumptions on the running time of these mechanisms. Moreover, it holds even for the wider class of truthfulness-in-expectation mechanisms. This lower bound nearly matches the known 1.58606 rand…
-
Improved Lower Bounds for Truthful SchedulingShahar Dobzinski, Ariel Shaulker · 2020 · arXiv.org · preprint, non relu par les pairs · cité 15 fois · Pas encore résumé
Improved Lower Bounds établit des bornes inférieures pour l’ordonnancement véridique sur machines non apparentées, tandis que cet article traite notamment des mécanismes randomisés.
Résumé scientifique
The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal "Algorithmic Mechanism Design" paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of $\min(m,n)$, where $n$ is the number of machines and $m$ is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than $2$. Since then, the lower bound was improved to $1 +\sqrt 2 \approx 2.41$ by Christodoulou, Kotsoupias, and Vidali, and then to $1+\phi\approx 2.618$ by Kotsoupias and Vidali. Very recently, the lower bound was improved to $2.755$ by Giannakopoulos,…
-
New Bounds for Truthful Scheduling on Two Unrelated Selfish MachinesO. Kuryatnikova, Juan C. Vera · 2017 · Theory of Computing Systems · cité 4 fois · Pas encore résumé
New Bounds étudie les rapports d’approximation des algorithmes randomisés véridiques pour deux machines non apparentées, un cas particulier de l’ordonnancement étudié ici.
Résumé scientifique
We consider the minimum makespan problem for n tasks and two unrelated parallel selfish machines. Let Rn be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient algorithms known for truthful scheduling on two machines. We propose a new Min − Max formulation for Rn, as well as upper and lower bounds on Rn based on this formulation. For the lower bound, we exploit pointwise approximations of cumulative distribution functions (CDFs). For the upper bound, we construct randomized algorithms using distributions with piecewise rational CDFs. Our method improves upon the existing bounds on Rn for small n. In particular, we obtain almost ti…
-
Optimal Lower Bounds for Anonymous Scheduling MechanismsI. Ashlagi, Shahar Dobzinski, R. Lavi · 2012 · Mathematics of Operations Research · cité 44 fois · Pas encore résumé
Optimal Lower Bounds étudie les bornes inférieures des mécanismes véridiques pour minimiser le makespan sur machines non apparentées.
Résumé scientifique
We consider the problem of designing truthful mechanisms on m unrelated machines, to minimize some optimization goal. Nisan and Ronen [Nisan, N., A. Ronen. 2001. Algorithmic mechanism design. Games Econom. Behav.35 166--196] consider the specific goal of makespan minimization, and show a lower bound of 2, and an upper bound of m. This large gap inspired many attempts that yielded positive results for several special cases, but very partial success for the general case: the lower bound was slightly increased to 2.61 by Christodoulou et al. [Christodoulou, G., E. Koutsoupias, A. Kovacs. 2010. Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms (TALG)6(2) 1--…
-
A characterization of 2-player mechanisms for schedulingG. Christodoulou, E. Koutsoupias, Angelina Vidali · 2008 · Embedded Systems and Applications · cité 33 fois · Pas encore résumé
A characterization caractérise les mécanismes véridiques pour l’ordonnancement sur deux machines non apparentées, sans se concentrer sur leurs garanties d’approximation.
Résumé scientifique
We study the mechanism design problem for 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 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 task-independent mechanism. This characterization is about all truthful mechanisms, including those with unbounded approximation ratio. A direct consequence of this approach i…
Les travaux antérieurs sur lesquels il s’appuie
-
Mechanism design for fractional scheduling on unrelated machinesG. Christodoulou, E. Koutsoupias, Annamária Kovács · 2007 · TALG · cité 61 fois · Pas encore résumé
Mechanism design for fractional scheduling étudie l’ordonnancement fractionnaire véridique sur machines non apparentées, dont cet article établit la meilleure garantie.
-
A Proof of the Nisan-Ronen ConjectureG. Christodoulou, E. Koutsoupias, Annamária Kovács · 2023 · Symposium on the Theory of Computing · cité 24 fois · Pas encore résumé
A Proof of the Nisan-Ronen Conjecture porte sur la meilleure approximation des mécanismes déterministes véridiques pour le makespan sur machines non apparentées.
Résumé scientifique
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.
-
Probability Inequalities for Sums of Bounded Random VariablesN. Fisher, P. Sen · 1994 · cité 7 068 fois · Pas encore résumé
Probability Inequalities fournit des inégalités pour des sommes de variables aléatoires bornées, outil cité dans la preuve de cet article.
-
Truthful Mechanisms for One-Parameter AgentsMoshe Babaioff · 2008 · Encyclopedia of Algorithms · cité 355 fois · Pas encore résumé
Truthful Mechanisms for One-Parameter Agents traite des mécanismes véridiques, cadre général mobilisé dans l’étude de l’ordonnancement véridique.
-
Weak Monotonicity Characterizes Deterministic Dominant-Strategy ImplementationS. Bikhchandani, S. Chatterji, R. Lavi et al. · 2006 · Econometrica · cité 241 fois · Pas encore résumé
Weak Monotonicity caractérise l’implémentation déterministe en stratégies dominantes, propriété fondamentale des mécanismes véridiques étudiés ici.
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 9 novembre 2026.