Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated Machines

详细信息    查看全文

• 作者：Xujin Chen ; Donglei Du ; Luis F. Zuluaga
• 关键词：Algorithmic mechanism design ; Random mechanism ; Copula ; Truthful scheduling
• 刊名：Theory of Computing Systems
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：57
• 期：3
• 页码：753-781
• 全文大小：602 KB
• 参考文献：1.Ashlagi, I., Dobzinski, S., Lavi, R.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37 (2), 244–258 (2012)MATH MathSciNet CrossRef
  2.Bertsekas, D.P.: Nonlinear Programming, 2nd. Athena Scientific (1999)
  3.Christodoulou, G., Koutsoupias, E., Vidali, A.: A characterization of 2-player mechanisms for scheduling. In: Proceedings of the 16th annual European symposium on Algorithms, ESA’08, pp 297–307. Springer-Verlag, Berlin, Heidelberg (2008)
  4.Clayton, D.G.: A model for association in bivariate life tables and its application in epidemiological studies of familial tendency in chronic disease incidence. Biometrika 65 (1), 141–151 (1978)MATH MathSciNet CrossRef
  5.Dobzinski, S., Sundararajan, M.: On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: Proceedings of the 9th ACM conference on Electronic commerce, EC’08, pp 38–47. ACM, New York, NY, USA (2008)
  6.Koutsoupias, E., Vidali, A.: A lower bound of 1+ϕ for truthful scheduling mechanisms. In: Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science, MFCS’07, pp 454–464. Springer-Verlag, Berlin, Heidelberg (2007)
  7.Lavi, R., Mu’Alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS’03, pp. 574–583 (2003)
  8.Lu, P.: On 2-player randomized mechanisms for scheduling. In: Proceedings of the 5th International Workshop on Internet and Network Economics, WINE’09, pp. 30–41. Springer-Verlag, Berlin, Heidelberg (2009). doi:10.​1007/​978-3-642-10841-9_​5 CrossRef
  9.Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Albers, S., Weil, P. (eds.) Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS’08, pp. 527–538. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008)
  10.Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Proceedings of the 4th International Workshop on Internet and Network Economics, WINE’08, pp. 402–413. Springer-Verlag, Berlin, Heidelberg (2008)
  11.McNeil, A.J., Neṡlehová, J.: Multivariate archimedean copulas, d-monotone functions and l 1-norm symmetric distributions. Ann. Stat. 37 (5), 3059–3097 (2009)MATH CrossRef
  12.Mu’alem, A., Schapira, M.: Setting lower bounds on truthfulness: extended abstract. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA’07, pp 1143–1152. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)
  13.Nelsen, R.B.: An introduction to copulas. Springer (1999)
  14.Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166–196 (2001)MATH MathSciNet CrossRef
  15.Patton, A.J.: A review of copula models for economic time series. J. Multivariate Anal. 110, 4–18 (2012)MATH MathSciNet CrossRef
  16.Saks, M., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proceedings of the 6th ACM conference on Electronic commerce, pp. 286–293. ACM (2005)
  17.Ugray, Z., Lasdon, L., Plummer, J.C., Glover, F., Kelly, J., Martí, R.: Scatter search and local nlp solvers: A multistart framework for global optimization. INFORMS J. Comput. 19 (3), 328–340 (2007)MATH MathSciNet CrossRef
  
• 作者单位：Xujin Chen (1)
  Donglei Du (2)
  Luis F. Zuluaga (3)
  
  1. Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China
  2. Faculty of Business Administration, University of New Brunswick, Fredericton, E3B 9Y2, NB, Canada
  3. Department of Industrial and Systems Engineering, Lehigh University, 18015, Bethlehem, PA, USA
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490

文摘

We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within [1.5852,1.58606], offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the known lower bound of 1.506 for the scale-free truthful mechanisms. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other related problems in the future.