Implementation with a bounded action space

ABSTRACT

While traditional mechanism design typically assumes isomorphism between the agents' type- and action spaces, in many situations the agents face strict restrictions on their action space due to, e.g., technical, behavioral or regulatory reasons. We devise a general framework for the study of mechanism design in single-parameter environments with restricted action spaces. Our contribution is threefold. First, we characterize sufficient conditions under which the information-theoretically optimal social-choice rule can be implemented in dominant strategies, and prove that any multi-linear social-choice rule is dominant-strategy implementable with no additional cost. Second, we identify necessary conditions for the optimality of action-bounded mechanisms, and fully characterize the optimal mechanisms and strategies in games with two players and two alternatives. Finally, we prove that for any multilinear social-choice rule, the optimal mechanism with k actions incurs an expected loss of O( 1k2 ) compared to the optimal mechanisms with unrestricted action spaces. Our results apply to various economic and computational settings, and we demonstrate their applicability to signaling games, public-good models and routing in networks.

REFERENCES

• 1: S. Athey. Single crossing properties and the existence of pure strategy equilibria in games of incomplete information. Econometrica, 69(4):861--89, 2001.
• 2: M. Babaio and L. Blumrosen. Computationally-feasible auctions for convex bundles. In APPROX 04, pages 27--38, 2004.
• 3: M. Babaio, R. Lavi, and E. Pavlov. Mechanism design for single-value domains. In AAAI'05, pages 241--247, 2005.
• 4: Liad Blumrosen , Noam Nisan, Auctions with Severely Bounded Communication, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.406-415, November 16-19, 2002
• 5: Liad Blumrosen , Noam Nisan, Auctions with Severely Bounded Communication, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.406-415, November 16-19, 2002
• 6: L. Blumrosen, N. Nisan, and I. Segal. Multi-player and multi-round auctions with severely bounded communication. ESA 2003, 2003.
• 7: M. Chwe. The discrete bid first price auction. In Economics Letters, volume 31, pages 303--306, 1989.
• 8: E. David , A. Rogers , J. Schiff , S. Kraus , N. R. Jennings, Optimal design of English auctions with discrete bid levels, Proceedings of the 6th ACM conference on Electronic commerce, p.98-107, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064020]
• 9: R. M. Harstad and M. H. Rothkopf. On the role of discrete bid levels in oral auctions. Europian Journal of Operations Research, pages 572--581, 1994.
• 10: B. E. Hermalin. Lecture notes in economics, 2005.
• 11: Alexander Kress , Craig Boutilier, A Study of Limited-Precision, Incremental Elicitation in Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1344-1345, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.31]
• 12: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 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: P. McAfee. Coarse matching. Econometrica, 70(5):2025--2034, 2002.
• 15: R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 16: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 17: T. Sandholm and A. Gilpin. Sequences of take-it-or-leave-it offers: Near-optimal auctions without full-valuation revelation. In AMEC-V, 2003.
• 18: M. A. Satterthwaite and S. R. Williams. The optimality of a simple market mechanism. Econometrica, 70(5):1841--1863, 2002.
• 19: R. Wilson. Efficient and competitive rationing. Econometrica, 57:1--40, 1989.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

General Terms:
Design, Economics, Theory

Keywords:
communication complexity, implementation, mechanism design, single-crossing condition