Article

A lower bound for scheduling mechanisms

Authors:

George Christodoulou,

Elias Koutsoupias,

Angelina VidaliAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1163 - 1170

Published: 07 January 2007 Publication History

Abstract

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 + √2 for 3 or more machines.

References

[1]

Nir Andelman, Yossi Azar, and Motti Sorani. Truthful approximation mechanisms for scheduling selfish related machines. In 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 69--82, 2005.

Digital Library

[2]

Aaron Archer. Mechanisms for Discrete Optimization with Rational Agents. PhD thesis, Cornell University, January 2004.

Digital Library

[3]

Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, and Éva Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 205--214, 2003.

Digital Library

[4]

Aaron Archer and Éva Tardos. Truthful mechanisms for one-parameter agents. In 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages 482--491, 2001.

Digital Library

[5]

Moshe Babaioff, Ron Lavi, and Elan Pavlov. Mechanism design for single-value domains. In Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seven-teenth Innovative Applications of Artificial Intelligence Conference (AAAI), pages 241--247, 2005.

Digital Library

[6]

Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auctions. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pages 72--87, 2003.

Digital Library

[7]

Patrick Briest, Piotr Krysta, and Berthold Vöcking. Approximation techniques for utilitarian mechanism design. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 39--48, 2005.

Digital Library

[8]

Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 610--618, 2005.

Digital Library

[9]

Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 644--652, 2006.

Digital Library

[10]

Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra. Dominant strategy mechanisms with multidimensional types. In Computing and Markets, 2005.

[11]

D. S. Hochbaum. Approximation algorithms for NP-hard problems. PWS Publishing Co. Boston, MA, USA, 1996.

Digital Library

[12]

Roberts Kevin. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, pages 321--348, 1979.

[13]

Annamaria Kovacs. Fast monotone 3-approximation algorithm for scheduling related machines. In Algorithms - ESA 2005: 13th Annual European Symposium, pages 616--627, 2005.

Digital Library

[14]

Ron Lavi, Ahuva Mu'alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In 44th Symposium on Foundations of Computer Science (FOCS), pages 574--583, 2003.

Digital Library

[15]

J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46(1):259--271, 1990.

Digital Library

[16]

Noam Nisan and Amir Ronen. Algorithmic mechanism design (extended abstract). In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), pages 129--140, 1999.

Digital Library

[17]

Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166--196, 2001.

[18]

Michael E. Saks and Lan Yu. Weak monotonicity suffices for truthfulness on convex domains. In Proceedings 6th ACM Conference on Electronic Commerce (EC), pages 286--293, 2005.

Digital Library

Cited By

Kress DMeiswinkel SPesch E(2018)Mechanism design for machine scheduling problemsOR Spectrum10.1007/s00291-018-0512-840:3(583-611)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00291-018-0512-8
Kovács AVidali A(2015)A characterization of n-player strongly monotone scheduling mechanismsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832328(568-574)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832249.2832328
Daskalakis CWeinberg SIndyk P(2015)Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithmsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722259(1934-1952)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722259
Show More Cited By

A lower bound for scheduling mechanisms
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

A Lower Bound for Scheduling Mechanisms

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 on algorithmic mechanism design, where ...
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption

We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines; ...
Coordination mechanisms for selfish scheduling
WINE'05: Proceedings of the First international conference on Internet and Network Economics

In machine scheduling, a set of n jobs must be scheduled on a set of m machines. Each job i incurs a processing time of p_ij on machine j and the goal is to schedule jobs so as to minimize some global objective function, such as the maximum makespan of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
273
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kress DMeiswinkel SPesch E(2018)Mechanism design for machine scheduling problemsOR Spectrum10.1007/s00291-018-0512-840:3(583-611)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00291-018-0512-8
Kovács AVidali A(2015)A characterization of n-player strongly monotone scheduling mechanismsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832328(568-574)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832249.2832328
Daskalakis CWeinberg SIndyk P(2015)Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithmsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722259(1934-1952)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722259
Procaccia ATennenholtz M(2013)Approximate Mechanism Design without MoneyACM Transactions on Economics and Computation10.1145/2542174.25421751:4(1-26)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2542174.2542175
Chawla SHartline JMalec DSivan BBoneh DRoughgarden TFeigenbaum J(2013)Prior-independent mechanisms for schedulingProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488616(51-60)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488616
Penna PVentre C(2012)Collusion-Resistant Mechanisms with Verification Yielding Optimal SolutionsACM Transactions on Computation Theory10.1145/2189778.21897814:2(1-17)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1145/2189778.2189781
Chen NGravin NLu PRandall D(2011)On the approximability of budget feasible mechanismsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133090(685-699)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133090
Dobzinski SNisan NShoham YChen YRoughgarden T(2011)Multi-unit auctionsProceedings of the 12th ACM conference on Electronic commerce10.1145/1993574.1993611(233-242)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.1145/1993574.1993611
Lu PSun XWang YZhu ZParkes DDellarocas CTennenholtz M(2010)Asymptotically optimal strategy-proof mechanisms for two-facility gamesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807393(315-324)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807393
Christodoulou GKoutsoupias EKovács A(2010)Mechanism design for fractional scheduling on unrelated machinesACM Transactions on Algorithms10.1145/1721837.17218546:2(1-18)Online publication date: 6-Apr-2010
https://dl.acm.org/doi/10.1145/1721837.1721854
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents