Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms

Constantinos Daskalakis, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, with approximation factors of 2 and min{m-k+1,O(√k)} respectively, matching the approximation ratios of best known polynomial-time algorithms (for max-min fairness, the latter claim is true for certain ratios of the number of goods m to people k). Our mechanisms are obtained by establishing a polynomial-time approximation-sensitive reduction from the problem of designing approximately optimal mechanisms for some arbitrary objective O to that of designing bi-criterion approximation algorithms for the same objective O plus a linear allocation cost term. Our reduction is itself enabled by extending the celebrated "equivalence of separation and optimization" [27, 32] to also accommodate bi-criterion approximations. Moreover, to apply the reduction to the specific problems of makespan and max-min fairness we develop polynomial-time bi-criterion approximation algorithms for makespan minimization with costs and max-min fairness with costs, adapting the algorithms of [45], [10] and [4] to the type of bi-criterion approximation that is required by the reduction.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages1934-1952
Number of pages19
EditionJanuary
ISBN (Electronic)9781611973747
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
CountryUnited States
CitySan Diego
Period1/4/151/6/15

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms'. Together they form a unique fingerprint.

  • Cite this

    Daskalakis, C., & Weinberg, S. M. (2015). Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 (January ed., pp. 1934-1952). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973730.130