A sufficient condition for truthfulness with single parameter agents

ABSTRACT

We consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when each agent's valuation function for each possible outcome is a one-dimensional function of its type, continuous everywhere and differentiable almost everywhere. For certain types of natural valuation functions, our condition is also necessary. Our condition extends both the Mirrlees-Spence condition [25, 17], applicable only for differentiable real allocations, and Archer and Tardos' single parameter characterization [4], which assumes an agent's valuation is linear in its type.We demonstrate the simplicity of testing our condition by showing that classical criteria for truthfulness in combinatorial problems such as auctions and machine scheduling can be derived from our condition. In addition, we use our condition to derive results for new single parameter problems, which have not been previously analyzed.We also consider combinatorial problems where the true types of agents affect the valuation of each other, such as in machine scheduling with selfish jobs. In such cases there are only degenerate dominant strategy mechanisms. We show that the same condition can be used to design mechanisms which are ex-post truthful, meaning that the outcome where all agents cooperate and report their true type is a Nash equilibrium. We demonstrate the power of this condition by applying it on the problem of machine scheduling with strategic job owners, previously presented in [5]. We give a constant approximation ratio algorithms for the original problem and to the double setting where both jobs and machines are strategic.

REFERENCES

• 1: N. Andelman, Y. Azar, and M. Sorani. Truthful approximation mechanisms for scheduling selfish related machines. In Proc. 22nd Ann. Symp. on Theoretical Aspects of Computer Science (STACS), pages 69--82, 2005.
• 2: N. Andelman and Y. Mansour. Auctions with budget constraints. In Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), pages 26--38, 2004.
• 3: Aaron Francis Archer , Eva Tardos, Mechanisms for discrete optimization with rational agents, 2004
• 4: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 5: Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Pino Persiano, How to route and tax selfish unsplittable traffic, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007942]
• 6: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 7: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 10: H. Gui, R. Müller, and R. V. Vohra. Dominant strategy mechanisms with multidimensional types. working paper.
• 11: Dorit s. Hochbaum , David B. Shmoys, A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach, SIAM Journal on Computing, v.17 n.3, p.539-551, June 1988 [doi>10.1137/0217033]
• 12: Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
• 13: A. Kovács. Fast monotone 3-approximation algorithm for scheduling related machines. In Proc. 13th Ann. European Symp. on Algorithms (ESA), pages 616--627, 2005.
• 14: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 15: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 16: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University press, 1995.
• 17: J. A. Mirrlees. Optimal tax theory: A synthesis. J. of Public Economics, 6:327--358, 1976.
• 18: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 19: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 20: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 21: K. Roberts. The characterization of implementable choice rules. In J. J. Laffont, editor, Aggregation and Revelation of Preferences, pages 321--348. North Holland, 1979.
• 22: J. C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. J. of Mathematical Economics, 16:191--200, 1987.
• 23: Michael Saks , Lan Yu, Weak monotonicity suffices for truthfulness on convex domains, Proceedings of the 6th ACM conference on Electronic commerce, p.286-293, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064040]
• 24: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 25: M. Spence. Competitive and optimal responses to signals: An analysis of efficiency and distribution. J. of Economic Theory, 7:296--332, 1974.
• 26: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. J. of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic mechanism design, algorithms, approximation, game theory