×

Truthful mechanism design via correlated tree rounding. (English) Zbl 1371.91066

Summary: A powerful algorithmic technique for truthful mechanism design is the maximal-in-distributional-range (MIDR) paradigm. Unfortunately, many such algorithms use heavy algorithmic machinery, e.g., the ellipsoid method and (approximate) solution of convex programs. In this paper, we present a correlated rounding technique for designing mechanisms that are truthful in expectation. It is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional optimum solutions with a tree structure. In auctions based on the generalized assignment problem, each bidder has a publicly known knapsack constraint that captures the subsets of items that are of value to him. He has a private valuation for each item and strives to maximize the value of assigned items minus payment. For this domain we design a truthful 2-approximate MIDR mechanism for social welfare maximization. It avoids using the ellipsoid method or convex programming. In contrast to some previous work, our mechanism achieves exact truthfulness. In restricted-related scheduling with selfish machines, each job comes with a public weight, and it must be assigned to a machine from a public job-specific subset. Each machine has a private speed and strives to maximize payments minus workload of jobs assigned to it. Here we design a mechanism for makespan minimization. This is a single-parameter domain, but the approximation status of the optimization problem is similar to unrelated machine scheduling: The best known algorithm obtains a (non-truthful) 2-approximation for unrelated machines, and there is 1.5-hardness. Our mechanism matches this bound with a truthful 2-approximation.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andelman, N.: Online and strategic aspects of network resource management algorithms. Ph.D. thesis, Tel Aviv University (2006) · Zbl 1238.91071
[2] Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. Theory Comput. Syst. 40(4), 423-436 (2007) · Zbl 1121.68017 · doi:10.1007/s00224-006-1316-9
[3] Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: Proceedings of 42nd Symposium Foundations of Computer Science (FOCS), pp. 482-491 (2001) · Zbl 1299.91048
[4] 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
[5] Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-norm approximation algorithms. J. Algorithms 52(2),120-133 (2004) · Zbl 1072.68130
[6] Blumrosen, L.; Nisan, N.; Nisan, N. (ed.); Tardos, É. (ed.); Roughgarden, T. (ed.); Vazirani, V. (ed.), Combinatorial auctions (2007), Cambridge · Zbl 1152.91453
[7] Buchfuhrer, D., Dughmi, S., Fu, H., Kleinberg, R., Mossel, E., Papadimitriou, C., Schapira, M., Singer, Y., Umans, C.: Inapproximability for VCG-based combinatorial auctions. In: Proceedings of 21st Symposium Discrete Algorithms (SODA), pp. 518-536 (2010) · Zbl 1288.91099
[8] Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. SIAM J. Comput. 39(6), 2189-2211 (2010) · Zbl 1263.90037 · doi:10.1137/080735503
[9] Chen, N., Gravin, N., Lu, P.: Truthful generalized assignments via stable matching. Math. Oper. Res. 39(3), 722-736 (2014) · Zbl 1307.91133 · doi:10.1287/moor.2013.0625
[10] Christodoulou, G., Koutsoupias, E., Kovács, A.: Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms 6(2) (2010) · Zbl 1300.90014
[11] 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
[12] 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
[13] Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006) · Zbl 1194.91018
[14] 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
[15] Dobzinski, S., Dughmi, S.: On the power of randomization in algorithmic mechanism design. SIAM J. Comput. 42(6), 2287-2304 (2013) · Zbl 1285.91048 · doi:10.1137/090780146
[16] Dobzinski, S., Fu, H., Kleinberg, R.: Truthfulness via proxies. CoRR arXiv:1011.3232 (2010) · Zbl 1263.90037
[17] Dobzinski, S., Nisan, N.: Limitations of VCG-based mechanisms. Combinatorica 41(4), 379-396 (2011) · Zbl 1299.91048 · doi:10.1007/s00493-011-2528-4
[18] Dobzinski, S., Vondrák, J.: The computational complexity of truthfulness in combinatorial auctions. In: Proceedings of 13th Conference on Electronic Commerce (EC), pp. 405-422 (2012) · Zbl 1318.91090
[19] Dobzinski, S., Vondrák, J.: From query complexity to computational complexity. In: Proceedings of 44th Symposium on Theory of Computing (STOC), pp. 1107-1116 (2012) · Zbl 1286.68225
[20] Dobzinski, S., Vondrák, J.: Impossibility results for truthful combinatorial auctions with submodular valuations. J. ACM 63(1), 5 (2016) · Zbl 1426.68119 · doi:10.1145/2786754
[21] Dughmi, S., Ghosh, A.: Truthful assignment without money. In: Proceedings of 11th Conference on Electronic Commerce (EC), pp. 325-334 (2010) · Zbl 1238.68187
[22] Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanims: toward optimal combinatorial auctions. In: Proceedings of 43rd Symposium on Theory of Computing (STOC), pp. 149-158 (2011) · Zbl 1288.91103
[23] Dughmi, S., Vondrák, J.: Limitations of randomized mechanisms for combinatorial auctions. Games Econom. Behav. 92, 370-400 (2015) · Zbl 1318.91090 · doi:10.1016/j.geb.2014.01.007
[24] Epstein, L., Levin, A., van Stee, R.: A unified approach to truthful scheduling on related machines. Math. Oper. Res. 41(1), 332-351 (2016) · Zbl 1353.68300 · doi:10.1287/moor.2015.0730
[25] Fadaei, S., Bichler, M.: A truthful-in-expectation mechanism for the generalized assignment problem. In: Proceedings of 10th International Conference on Web and Internet Economics (WINE), pp. 247-248 (2014) · Zbl 06384396
[26] Feige, U., Vondrák, J.: Approximation algorithms for allocation problems: improving the factor of 1-1/e. In: Proceedings of 47th Symposium on Foundations of Computer Science (FOCS), pp. 667-676 (2006) · Zbl 1307.91133
[27] Fleischer, L., Goemans, M., Mirrokni, V., Sviridenko, M.: Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3), 416-431 (2011) · Zbl 1238.68187 · doi:10.1287/moor.1110.0499
[28] Hochbaum, D., Shmoys, D.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539-551 (1988) · Zbl 0647.68040 · doi:10.1137/0217033
[29] Khot, S., Lipton, R., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica 52(1), 3-18 (2008) · Zbl 1142.91485 · doi:10.1007/s00453-007-9105-7
[30] Koutsoupias, E., Vidali, A.: A lower bound of \[1+\phi 1\]+ϕ for truthful scheduling mechanisms. Algorithmica 66(1), 211-223 (2013) · Zbl 1262.68044 · doi:10.1007/s00453-012-9634-6
[31] Kovács, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Proceedings of 13th European Symposium Algorithms (ESA), pp. 616-627 (2005) · Zbl 1162.90459
[32] Krysta, P., Vöcking, B.: Online mechanism design (randomized rounding on the fly). In: Proceedings of 39th International Colloquium Automata, Languages and Programming (ICALP), pp. 636-647 (2012) · Zbl 1367.91080
[33] Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. J. ACM 58(6), 25 (2011) · Zbl 1281.91091 · doi:10.1145/2049697.2049699
[34] Lehmann, D., O’Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5) (2002) · Zbl 1326.91011
[35] Lenstra, J., Shmoys, D., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Prog. 46(3), 259-271 (1990) · Zbl 0715.90063 · doi:10.1007/BF01585745
[36] Lu, P.: On 2-player randomized mechanisms for scheduling. In: Proceedings of 5th International Workshop Internet and Network Economics (WINE), pp. 30-41 (2009)
[37] Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Proceedings of 25th Symposium on Theoret. Aspects of Computer Science (STACS), pp. 527-538 (2008) · Zbl 1259.68022
[38] Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Proceedings of 4th International Workshop Internet and Network Economics (WINE), pp. 402-413 (2008) · Zbl 1290.68055
[39] Milgrom, P.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004) · doi:10.1017/CBO9780511813825
[40] Mirrokni, V., Schapira, M., Vondrák, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings of 9th Conference on Electronic Commerce (EC), pp. 70-77 (2008)
[41] Nisan, N.; Ronen, A., No article title, Algorithmic mechanism design. Games Econom. Behav., 35, 166-196 (2001) · Zbl 0996.68251 · doi:10.1006/game.1999.0790
[42] Shmoys, D., Tardos, É.: An approximation algorithm for the generalized assignment problem. Math. Prog. 62(3), 461-474 (1993) · Zbl 0804.90077 · doi:10.1007/BF01585178
[43] Tamir, A.: Least majorized elements and generalized polymatroids. Math. Oper. Res. 20, 583-590 (1995) · Zbl 0839.90097 · doi:10.1287/moor.20.3.583
[44] Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of 40th Symposium on Theory of Computing (STOC), pp. 67-74 (2008) · Zbl 1231.91094
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.