×

zbMATH — the first resource for mathematics

The VCG mechanism for Bayesian scheduling. (English) Zbl 1410.90087
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9470, 343-356 (2015).
Summary: We study the problem of scheduling \(m\) tasks to \(n\) selfish, unrelated machines in order to minimize the makespan, where the execution times are independent random variables, identical across machines. We show that the VCG mechanism, which myopically allocates each task to its best machine, achieves an approximation ratio of \(O\left( \frac{\ln n}{\ln \ln n}\right) \). This improves significantly on the previously best known bound of \(O\left( \frac{m}{n}\right) \) for prior-independent mechanisms, given by S. Chawla et al. [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM). 51–60 (2013; Zbl 1293.90030)] under the additional assumption of monotone hazard rate (MHR) distributions. Although we demonstrate that this is in general tight, if we do maintain the MHR assumption, then we get improved, (small) constant bounds for \(m\geq n\ln n\) i.i.d. tasks, while we also identify a sufficient condition on the distribution that yields a constant approximation ratio regardless of the number of tasks.
For the entire collection see [Zbl 1326.68026].

MSC:
90B35 Deterministic scheduling theory in operations research
62C10 Bayesian problems; characterization of Bayes procedures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: FOCS, pp. 482–491 (2001) · doi:10.1109/SFCS.2001.959924
[2] Ashlagi, I., Dobzinski, S., Lavi, R.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37(2), 244–258 (2012) · Zbl 1238.91071 · doi:10.1287/moor.1110.0534
[3] Aven, T.: Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables. J. Appl. Probab. 22(3), 723–728 (1985) · Zbl 0576.60016 · doi:10.1017/S002190020002948X
[4] Barlow, R.E., Marshall, A.W., Proschan, F.: Properties of probability distributions with monotone hazard rate. Ann. Math. Stat. 34(2), 375–389 (1963) · Zbl 0249.60006 · doi:10.1214/aoms/1177704147
[5] Berenbrink, P., Friedetzky, T., Hu, Z., Martin, R.: On weighted balls-into-bins games. Theor. Comput. Sci. 409(3), 511–520 (2008) · Zbl 1155.68085 · doi:10.1016/j.tcs.2008.09.023
[6] Chawla, S., Immorlica, N., Lucier, B.: On the limits of black-box reductions in mechanism design. In: STOC, pp. 435–448 (2012) · Zbl 1286.90122 · doi:10.1145/2213977.2214019
[7] Chawla, S., Hartline, J.D., Malec, D., Sivan, B.: Prior-independent mechanisms for scheduling. In: STOC, pp. 51–60 (2013) · Zbl 1293.90030 · doi:10.1145/2488608.2488616
[8] Christodoulou, G., Kovács, A.: A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput. 42(4), 1572–1595 (2013) · Zbl 1290.68055 · doi:10.1137/120866038
[9] Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. Algorithmica 55(4), 729–740 (2009) · Zbl 1183.68105 · doi:10.1007/s00453-008-9165-3
[10] Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17–33 (1971) · doi:10.1007/BF01726210
[11] Daskalakis, C., Weinberg, S.M.: Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In: SODA, pp. 1934–1952 (2015) · Zbl 1372.90044
[12] Devanur, N., Hartline, J., Karlin, A., Nguyen, T.: Prior-independent multi-parameter mechanism design. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 122–133. Springer, Heidelberg (2011) · Zbl 05985905 · doi:10.1007/978-3-642-25510-6_11
[13] Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T.: Truthful approximation schemes for single-parameter agents. SIAM J. Comput. 40(3), 915–933 (2011) · Zbl 1234.68460 · doi:10.1137/080744992
[14] Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games Econ. Behav. 91, 318–333 (2015) · Zbl 1318.91088 · doi:10.1016/j.geb.2014.03.011
[15] Dughmi, S., Roughgarden, T., Sundararajan, M.: Revenue submodularity. Theory Comput. 8(1), 95–119 (2012) · Zbl 1246.91054 · doi:10.4086/toc.2012.v008a005
[16] Giannakopoulos, Y., Kyropoulou, M.: The VCG mechanism for bayesian scheduling. CoRR, abs/1509.07455 (2015). http://arxiv.org/abs/1509.07455 · Zbl 1410.90087
[17] Groves, T.: Incentives in teams. Econometrica 41(4), 617–631 (1973) · Zbl 0311.90002 · doi:10.2307/1914085
[18] Hall, L.A.: Approximation algorithms for scheduling. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 1–45. PWS, Boston (1997)
[19] Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: EC, pp. 225–234 (2009) · doi:10.1145/1566374.1566407
[20] Koutsoupias, E., Vidali, A.: A lower bound of \[ 1+\varphi \]
for truthful scheduling mechanisms. Algorithmica 66(1), 211–223 (2013) · Zbl 1262.68044 · doi:10.1007/s00453-012-9634-6
[21] Lavi, R., Swamy, C.: Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games Econ. Behav. 67(1), 99–124 (2009) · Zbl 1168.90454 · doi:10.1016/j.geb.2008.08.001
[22] Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990) · Zbl 0715.90063 · doi:10.1007/BF01585745
[23] Lu, P.: On 2-player randomized mechanisms for scheduling. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 30–41. Springer, Heidelberg (2009) · Zbl 05644096 · doi:10.1007/978-3-642-10841-9_5
[24] Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: STACS, pp. 527–538 (2008) · Zbl 1259.68022
[25] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) · Zbl 0849.68039 · doi:10.1017/CBO9780511814075
[26] Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35(1/2), 166–196 (2001) · Zbl 0996.68251 · doi:10.1006/game.1999.0790
[27] Nisan, N., Ronen, A.: Computationally feasible VCG mechanisms. J. Artif. Int. Res. 29(1), 19–47 (2007) · Zbl 1165.91387
[28] Raab, M., Steger, A.: ”Balls into Bins” – a simple and tight analysis. In: Luby, M., Rolim, J.D.P., Serna, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 159–170. Springer, Heidelberg (1998) · Zbl 0928.60001 · doi:10.1007/3-540-49543-6_13
[29] Roughgarden, T., Talgam-Cohen, I., Yan, Q.: Supply-limiting mechanisms. In: EC, pp. 844–861 (2012) · doi:10.1145/2229012.2229077
[30] Sivan, B.: Prior Robust Optimization. Ph.D. thesis, University of Wisconsin-Madison (2013)
[31] Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1), 8–37 (1961) · doi:10.1111/j.1540-6261.1961.tb02789.x
[32] Yu, C.: Truthful mechanisms for two-range-values variant of unrelated scheduling. Theor. Comput. Sci. 410(21–23), 2196–2206 (2009) · Zbl 1191.68877 · doi:10.1016/j.tcs.2009.02.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.