On characterizations of truthful mechanisms for combinatorial auctions and scheduling

ABSTRACT

We characterize truthful mechanisms in two multi-parameter domains. The first characterization shows that every mechanism for combinatorial auctions with two subadditive bidders that always allocates all items is an affine maximizer. The second result shows that every truthful machine scheduling mechanism for 2 unrelated machines that yields a finite approximation of the minimum makespan, must be task independent. That is, the mechanism must determine the allocation of each job separately.

The characterizations improve our understanding of these multi-parameter settings and have new implications regarding the approximability of central problems in algorithmic mechanism design.

REFERENCES

• 1: 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
• 2: Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
• 3: George Christodoulou, Elias Koutsoupias, and AnnamáriaKovács. Mechanism design for fractional scheduling on unrelated machines. In ICALP'07.
• 4: George Christodoulou , Elias Koutsoupias , Angelina Vidali, A lower bound for scheduling mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1163-1170, January 07-09, 2007, New Orleans, Louisiana
• 5: Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In APPROX-RANDOM, 2007.
• 6: Shahar Dobzinski , Noam Nisan, Limitations of VCG-based mechanisms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250842]
• 7: Shahar Dobzinski , Noam Nisan, Mechanisms for multi-unit auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250960]
• 8: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 9: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 10: Uriel Feige , Jan Vondrak, Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.667-676, October 21-24, 2006 [doi>10.1109/FOCS.2006.14]
• 11: Andrew Goldberg, Jason Hartline, Anna Karlin, Mike Saks, and AndrewWright. Competitive auctions. Games and Economic Behaviour, 2006.
• 12: Ron Lavi. Computationally efficient approximation mechanisms. In Algorithmic Game Theory, edited by Noam Nisan and Tim Roughgarden and Eva Tardos and Vijay Vazirani.
• 13: 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
• 14: Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
• 15: R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 16: 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]
• 17: 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]
• 18: Kevin Roberts. The characterization of implementable choise rules. In Jean-Jacques Laffont, editor, Aggregation and Revelation of Preferences. Papers presented at the first European Summer Workshop of the Economic Society, pages 321--349. North-Holland, 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Theory

Keywords:
characterizations, combinatorial auctions, incentive compatibility, scheduling