Truthful mechanism design for multidimensional scheduling via cycle monotonicity

Ahuja, 1993 Andelman, 2007, Truthful approximation mechanisms for scheduling selfish related machines, Theory Computing Systems, 40, 423, 10.1007/s00224-006-1316-9 Archer, A., 2004. Mechanisms for discrete optimization with rational agents. PhD thesis. Cornell University Archer, A., Tardos, É., 2001. Truthful mechanisms for one-parameter agents. In: Proc. 42nd FOCS, pp. 482–491 Auletta, V., De-Prisco, R., Penna, P., Persiano, G., 2004. Deterministic truthful approximation mechanisms for scheduling related machines. In: Proc. 21st STACS, pp. 608–619 Bezáková, 2005, Allocating indivisible goods, ACM SIGecom Exchanges, 5, 11, 10.1145/1120680.1120683 Bikhchandani, 2006, Weak monotonicity characterizes deterministic dominant-strategy implementation, Econometrica, 74, 1109, 10.1111/j.1468-0262.2006.00695.x Briest, P., Krysta, P., Vöcking, B., 2005. Approximation techniques for utilitarian mechanism design. In: Proc. 37th STOC, pp. 39–48 Christodoulou, G., Koutsoupias, E., Kovács, A., 2007a. Mechanism design for fractional scheduling on unrelated machines. In: Proc. 34th ICALP, pp. 40–52 Christodoulou, G., Koutsoupias, E., Vidali, A., 2007b. A lower bound for scheduling mechanisms. In: Proc. 18th SODA, pp. 1163–1170 Clarke, 1971, Multipart pricing of public goods, Public Choice, 8, 17, 10.1007/BF01726210 Ford, 1956, Maximal flow through a network, Can. J. Mathematics, 8, 399, 10.4153/CJM-1956-045-5 Goldberg, 1990, Solving minimum-cost flow problems by successive approximation, Mathematics Operations Res., 15, 430, 10.1287/moor.15.3.430 Groves, 1973, Incentives in teams, Econometrica, 41, 617, 10.2307/1914085 Gui, H., Muller, R., Vohra, R., 2004. Characterizing dominant strategy mechanisms with multi-dimensional types. Working paper Hall, 1996, Approximation algorithms for scheduling Kleinberg, 2006 Koutsoupias, E., Vidali, A., 2007. A 1+ϕ lower bound for truthful scheduling. In: Proc. 32nd MFCS, pp. 454–464 Kovács, A., 2005. Fast monotone 3-approximation algorithm for scheduling related machines. In: Proc. 13th ESA, pp. 616–627 Kumar, V., Marathe, M., Parthasarathy, S., Srinivasan, A., 2005. Approximation algorithms for scheduling on multiple machines. In: Proc. 46th FOCS, pp. 254–263 Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595–604 Lavi, R., Mu'alem, A., Nisan, N., 2003. Towards a characterization of truthful combinatorial auctions. In: Proc. 44th FOCS, pp. 574–583 Lehmann, 2002, Truth revelation in approximately efficient combinatorial auctions, J. ACM, 49, 577, 10.1145/585265.585266 Lenstra, 1990, Approximation algorithms for scheduling unrelated parallel machines, Math. Programming, 46, 259, 10.1007/BF01585745 Lipton, R., Markakis, E., Mossel, E., Saberi, A., 2004. On approximately fair allocations of indivisible goods. In: Proc. 5th EC, pp. 125–131 McAfee, 1988, Multidimensional incentive compatibility and mechanism design, J. Econ. Theory, 46, 335, 10.1016/0022-0531(88)90135-4 Mu'alem, A., Schapira, M., 2007. Setting lower bounds on truthfulness. In: Proc. 18th SODA, pp. 1143–1152 Myerson, 1981, Optimal auction design, Mathematics Operations Res., 6, 58, 10.1287/moor.6.1.58 Nisan, 2001, Algorithmic mechanism design, Games Econ. Behav., 35, 166, 10.1006/game.1999.0790 Rochet, 1987, A necessary and sufficient condition for rationalizability in a quasilinear context, J. Math. Econ., 16, 191, 10.1016/0304-4068(87)90007-3 Rockafellar, 1972 Saks, M., Yu, L., 2005. Weak monotonicity suffices for truthfulness on convex domains. In: Proc. 6th EC, pp. 286–293 Schrijver, 1998 Shmoys, 1993, An approximation algorithm for the generalized assignment problem, Math. Programming, 62, 461, 10.1007/BF01585178 Vickrey, 1961, Counterspeculations, auctions, and competitive sealed tenders, J. Finance, 16, 8, 10.2307/2977633