TY - GEN

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

AU - Daskalakis, Constantinos

AU - Weinberg, S. Matthew

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84938255575&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938255575&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973730.130

DO - 10.1137/1.9781611973730.130

M3 - Conference contribution

AN - SCOPUS:84938255575

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1934

EP - 1952

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -