Characterizing false-name-proof allocation rules in combinatorial auctions

ABSTRACT

A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategy-proof allocation rules. In particular, a condition called weak-monotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity.

In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. False-name-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-name-proof, do not satisfy sub-additivity; they are not false-name-proof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.

REFERENCES

• 1: M. Babaioff and L. Blumrosen. Computationally feasible auctions for convex bundles. Games and Economic Behavior, 63(2):588--620, 2008.
• 2: M. Babaioff, R. Lavi, and E. Pavlov. Mechanism design for single-value domains. In AAAI, pages 241--247, 2005.
• 3: S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica, 74(4):1109--1132, 2006.
• 4: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 5: 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
• 6: Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
• 7: E. Maskin and T. Sjostrom. Implementation theory. In Handbook of Social Choice and Welfare, volume 1, chapter 5, pages 237--288. Elsevier, 2002.
• 8: Tokuro Matsuo , Takayuki Ito , Robert W. Day , Toramatsu Shintani, A robust combinatorial auction mechanism against shill bidders, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160846]
• 9: H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. Economic Theory, 18(3):511--533, 2001.
• 10: Ahuva Mu'alem , Michael Schapira, Mechanism design over discrete domains, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386797]
• 11: E. Muller and M. A. Satterthwaite. Strategy-proofness: the existence of dominant-strategy mechanisms. In Social Goals and Social Organization, chapter 5, pages 131--171. Cambridge University Press, 1985.
• 12: R. B. Myerson. Optimal auction design. Mathematics of Operation Research, 6(1):58--73, 1981.
• 13: D. C. Parkes and Q. Duong. An ironing-based approach to adaptive online mechanism design in single-valued domains. In AAAI, pages 94--101, 2007.
• 14: B. Rastegari, A. Condon, and K. Leyton-Brown. Revenue monotonicity in combinatorial auctions. In AAAI, pages 122--127, 2007.
• 15: J.-C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16(2):191--200, 1987.
• 16: 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]
• 17: M. Yokoo. Characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In IJCAI, pages 733--742, 2003.
• 18: Makoto Yokoo , Toshihiro Matsutani , Atsushi Iwasaki, False-name-proof combinatorial auction protocol: Groves Mechanism with SubModular Approximation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160840]
• 19: Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids., Artificial Intelligence, v.130 n.2, p.167-181, 08/01/2001 [doi>10.1016/S0004-3702(01)00077-7]
• 20: M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in Internet auctions. Games and Economic Behavior, 46(1):174--188, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Economics, Theory

Keywords:
combinatorial auctions, false-name-proof, mechanism design