skip to main content
10.1145/1250910.1250947acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
Article

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

Published: 11 June 2007 Publication History

Abstract

We consider the problem of makespan minimization on m unrelated machines in the context of algorithmic mechanism design, where the machines are the strategic players. This is a multidimensional scheduling domain, and the only known positive results for makespan minimization in such a domain are O(m)-approximation truthful mechanisms [22, 20]. We study a well-motivated special case of this problem, where the processing time of a job on each machine may either be "low" or "high", and the low and high values are public and job-dependent. This preserves the multidimensionality of the domain, and generalizes the restricted-machines (i.e., {pj,∞}) setting in scheduling. We give a general technique to convert any c-approximation algorithm to a 3c-approximation truthful-in-expectation mechanism. This is one of the few known results that shows how to export approximation algorithms for a multidimensional problem into truthful mechanisms in a black-box fashion. When the low and high values are the same for all jobs, we devise a deterministic 2-approximation truthful mechanism. These are the first truthful mechanisms with non-trivial performance guarantees for a multidimensional scheduling domain.
Our constructions are novel in two respects. First, we do not utilize or rely on explicit price definitions to prove truthfulness; instead we design algorithms that satisfy cycle monotonicity. Cycle monotonicity [23] is a necessary and sufficient condition for truthfulness, is a generalization of value monotonicity for multidimensional domains. However, whereas value monotonicity has been used extensively and successfully to design truthful mechanisms in single-dimensional domains, ours is the first work that leverages cycle monotonicity in the multidimensional setting. Second, our randomized mechanisms are obtained by first constructing a fractional truthful mechanism for a fractional relaxation of the problem, and then converting it into a truthful-in-expectation mechanism. This builds upon a technique of [16], and shows the usefulness of fractional mechanisms in truthful mechanism design.

References

[1]
N. Andelman, Y. Azar, and M. Sorani. Truthful approximation mechanisms for scheduling selfish related machines. In Proc. 22nd STACS, 69--82, 2005.
[2]
A. Archer. Mechanisms for discrete optimization with rational agents. PhD thesis, Cornell University, 2004.
[3]
A. Archer and É. Tardos. Truthful mechanisms for one-parameter agents. In Proc. 42nd FOCS, pages 482--491, 2001.
[4]
V. Auletta, R. De-Prisco, P. Penna, and G. Persiano. Deterministic truthful approximation mechanisms for scheduling related machines. In Proc. 21st STACS, pages 608--619, 2004.
[5]
I. Bezáková and V. Dani. Allocating indivisible goods. In ACM SIGecom Exchanges, 2005.
[6]
S. Bikhchandani, S. Chatterjee, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica, 74:1109--1132, 2006.
[7]
P. Briest, P. Krysta, and B. Vocking. Approximation techniques for utilitarian mechanism design. In Proc. 37th STOC, pages 39--48, 2005.
[8]
G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. In Proc. 18th SODA, pages 1163--1170, 2007.
[9]
E. Clarke. Multipart pricing of public goods. Public Choice, 8:17--33, 1971.
[10]
T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
[11]
H. Gui, R. Muller, and R. V. Vohra. Characterizing dominant strategy mechanisms with multi-dimensional types, 2004. Working paper.
[12]
L. A. Hall. Approximation algorithms for scheduling. In D. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing, MA, 1996.
[13]
A. Kovács. Fast monotone 3-approximation algorithm for scheduling related machines. In Proc. 13th ESA, pages 616--627, 2005.
[14]
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Approximation algorithms for scheduling on multiple machines. In Proc. 46th FOCS, pages 254--263, 2005.
[15]
R. Lavi, A. Mu'alem, and N. Nisan. Towards a characterization of truthful combinatorial auctions. In Proc. 44th FOCS, pages 574--583, 2003.
[16]
R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. In Proc. 46th FOCS, pages 595--604, 2005.
[17]
D. Lehmann, L. O'Callaghan, and Y. Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49:577--602, 2002.
[18]
J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Prog., 46:259--271, 1990.
[19]
R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proc. 5th EC, pages 125--131, 2004.
[20]
A. Mu'alem and M. Schapira. Setting lower bounds on truthfulness. In Proc. 18th SODA, 1143--1152, 2007.
[21]
R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
[22]
N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Econ. Behavior, 35:166--196, 2001.
[23]
J. C. Rochet. A necessary and sufficient condition for rationalizability in a quasilinear context. Journal of Mathematical Economics, 16:191--200, 1987.
[24]
M. Saks and L. Yu. Weak monotonicity suffices for truthfulness on convex domains. In Proc. 6th EC, pages 286--293, 2005.
[25]
D. B. Shmoys and É. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62:461--474, 1993.
[26]
W. Vickrey. Counterspeculations, auctions, and competitive sealed tenders. J. Finance, 16:8--37, 1961.

Cited By

View all

Index Terms

  1. Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      EC '07: Proceedings of the 8th ACM conference on Electronic commerce
      June 2007
      384 pages
      ISBN:9781595936530
      DOI:10.1145/1250910
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 11 June 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. approximation algorithms
      2. mechanism design
      3. scheduling

      Qualifiers

      • Article

      Conference

      EC07
      Sponsor:
      EC07: ACM Conference on Electronic Commerce
      June 11 - 15, 2007
      California, San Diego, USA

      Acceptance Rates

      Overall Acceptance Rate 664 of 2,389 submissions, 28%

      Upcoming Conference

      EC '25
      The 25th ACM Conference on Economics and Computation
      July 7 - 11, 2025
      Stanford , CA , USA

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)13
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2020)Mechanism DesignComplex Social and Behavioral Systems10.1007/978-1-0716-0368-0_327(317-333)Online publication date: 21-Aug-2020
      • (2018)Mechanism design for machine scheduling problemsOR Spectrum10.1007/s00291-018-0512-840:3(583-611)Online publication date: 1-Jul-2018
      • (2018)A Truthful Mechanism for Interval SchedulingAlgorithmic Game Theory10.1007/978-3-319-99660-8_10(100-112)Online publication date: 27-Aug-2018
      • (2016)Algorithmic Mechanism DesignEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_9(37-48)Online publication date: 22-Apr-2016
      • (2015)Truthful Online Scheduling with CommitmentsProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764535(715-732)Online publication date: 15-Jun-2015
      • (2015)Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing ClustersACM Transactions on Parallel Computing10.1145/27423432:1(1-29)Online publication date: 13-Apr-2015
      • (2013)Approximate Mechanism Design without MoneyACM Transactions on Economics and Computation10.1145/2542174.25421751:4(1-26)Online publication date: 1-Dec-2013
      • (2013)Built-in generation of multicycle functional broadside tests with observation pointsACM Transactions on Design Automation of Electronic Systems10.1145/253439619:1(1-17)Online publication date: 20-Dec-2013
      • (2013)Optimal common-centroid-based unit capacitor placements for yield enhancement of switched-capacitor circuitsACM Transactions on Design Automation of Electronic Systems10.1145/253439419:1(1-13)Online publication date: 20-Dec-2013
      • (2013)Low-energy volatile STT-RAM cache design using cache-coherence-enabled adaptive refreshACM Transactions on Design Automation of Electronic Systems10.1145/253439319:1(1-23)Online publication date: 20-Dec-2013
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media