Optimal Lower Bounds for Anonymous Scheduling Mechanisms

References

• Aggarwal G., Fiat A., Goldberg A. V., Hartline J. D., Immorlica N., Sudan M. Derandomization of auctions. Proc. 37th ACM Sympos. Theory of Comput. (STOC) (2005) (ACM Press, New York) Crossref, Google Scholar
• Archer A., Tardos E. Truthful mechanisms for one-parameter agents. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (FOCS) (2001) (IEEE Computer Society, Washington, DC) 482–491Crossref, Google Scholar
• Bikhchandani S., Chatterji S., Lavi R., Mu'alem A., Nisan N., Sen A. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica (2006) 74(4):1109–1132Crossref, Google Scholar
• Christodoulou G., Kovacs A. A deterministic truthful PTAS for scheduling related machines. Proc. 21st ACM-SIAM Sympos. Discrete Algorithms (SODA) (2010) (SIAM, Philadelphia) Crossref, Google Scholar
• Christodoulou G., Koutsoupias E., Kovács A. Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms (TALG) (2010) 6(2):1–18Crossref, Google Scholar
• Christodoulou G., Koutsoupias E., Vidali A. A characterization of 2-player mechanisms for scheduling. Proc. 16th Eur. Sympos. Algorithms (ESA) (2008) (Springer LNCS, Berlin) Crossref, Google Scholar
• Christodoulou G., Koutsoupias E., Vidali A. A lower bound for scheduling mechanisms. Algorithmica (2009) 55(4):729–740Crossref, Google Scholar
• Dhangwatnotai P., Dobzinski S., Dughmi S., Roughgarden T. Truthful approximation schemes for single-parameter agents. Proc. IEEE 49th IEEE Sympos. Foundations Comput. Sci. (FOCS) (2008) (IEEE Computer Society, Washington, DC) Crossref, Google Scholar
• Dobzinski S., Sundararajan M. On characterizations of truthful mechanisms for combinatorial auctions and scheduling. Proc. 9th ACM Conf. Electronic Commerce (ACM-EC) (2008) (ACM Press, New York) Crossref, Google Scholar
• Eastman W. L., Even S., Isaacs I. M. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11(2):268–279Link, Google Scholar
• Koutsoupias E., Vidali A. A lower bound of 1+phi for truthful scheduling mechanisms. Proc. 32nd Internat. Sympos. Math. Foundations Comput. Sci. (MFCS) (2007) (Springer LNCS, Berlin) Crossref, Google Scholar
• Lavi R., Swamy C. Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games and Economic Behavior (2009) 67(1):99–124Crossref, Google Scholar
• Mu'alem A., Schapira M. Setting lower bounds on truthfulness: Extended abstract. Proc. 18th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2007) (SIAM, Philadephia) Google Scholar
• Nisan N., Ronen A. Algorithmic mechanism design. Games Econom. Behav. (2001) 35(1–2):166–196Crossref, Google Scholar
• Roberts K., Laffont J.-J. The characterization of implementable choice rules. Aggregation Revelation Preferences (1979) (North Holland, Amsterdam) 321–348Google Scholar
• Yu C. Truthful mechanisms for two-range-values variant of unrelated scheduling. Theoretical Comput. Sci. (2009) 410(21–23):2196–2206Crossref, Google Scholar