Communications - March 2010

ment slots next to the results for specific searches changes over time, but allocation decisions must be made now.

Conclusion

In this article, I have considered a number of settings in which a decision needs to be made based on the preferences of multiple agents, as well as mechanisms for reaching the decision. People have been using such mechanisms for millennia, and have studied them formally for centuries (although their game-theoretic analysis has taken place mostly in the last 50 years). Still, computer scientists are fundamentally changing these mechanisms and how they are being used.

Increased computing power and better algorithms enable the use of mechanisms, such as the Kemeny voting rule and combinatorial auctions, that were once considered impractical. Also, the Internet provides a great platform for these mechanisms: it makes it easy for spatially distributed users to communicate their preferences to the mechanism, and they will generally be forced to communicate them in a precise way (for example, a bidder will have to enter a number on a Web site rather than vaguely communicating her preferences over the phone), which makes it possible to run the mechanism automatically. I (speculatively) imagine that in the future, more Web-based mechanisms will be oriented around social networking sites such as Facebook and MySpace; the charitable donations work14 is a good example of how such social network structure can be used. Computer scientists are also encountering mechanism design problems in their own work, for example, when shared computing resources need to be allocated to users. Finally, the paradigms of computer science give a different and useful perspective on some classic problems in economics.

This article has summarized a num-
ber of applications where computer sci-
entists have already become involved in
the design of markets and other proto-
cols for making decisions based on the
preferences of multiple agents. I antici-
pate that the number and importance
of such applications will grow steeply
in the years to come. One major reason
for this is that computer scientists and
economists interested in market design
have grown closer together in recent
years, and are now seen working together
more often (this is necessitated by high-
value applications such as sponsored
search auctions). Computer scientists
have caught up on many of the key tech-
niques developed in the microeconom-
ics theory literature. On the other side,
economists are becoming increasingly
familiar with techniques from modern
computer science. This is a very nice ex-
ample where “computational thinking”
is being exported to another discipline
(which is certainly not to say that there
were no prior instances of economists
thinking computationally).

Acknowledgments

This work is supported by NSF award number IIS-0812113, a Research Fellowship from the Alfred P. Sloan Foundation, and a Yahoo! Faculty Research Grant. I thank the reviewers for very detailed and helpful feedback. I also thank Tuomas Sandholm for feedback on the kidney exchange section, and David Pennock for feedback on the prediction markets section. All errors and omissions are my own (though of course I faced constraints on length and number of citations).

References

1. Abraham, D., blum, A., and sandholm, T. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the ACM Conference on Electronic Commerce (san Diego, CA, 2007), 295–304.

2. bartholdi III, J., Tovey, C., and Trick, M. The computational difficulty of manipulating an election. Social Choice and Welfare 6, 3 (1989), 227–241.

3. bartholdi III, J., Tovey, C., and Trick, M. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6 (1989), 157–1659.

4. boutilier, C., brafman, r., Domshlak, C., hoos, h., and Poole, D. CP-nets: A tool for representing and reasoning with conditional ceteris paribus statements. J. Artificial Intelligence Research 21 (2004), 135–191.

5. bouveret, s. and Lang, J. Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (Edinburgh, scotland, 2005), 935–940.

6. Chen, y., Fortnow, L., nikolova, E., and Pennock, D.M. Combinatorial betting. ACM SIGecom Exchanges 7, 1 (2007), 61–64.

7. Clarke, E.h. Multipart pricing of public goods. Public Choice 11 (1971), 17–33.

8. Conitzer, V., Davenport, A., and Kalagnanam, J. Improved bounds for computing Kemeny rankings. In Proceedings of the National Conference on Artificial Intelligence (boston, MA, 2006), 620–626).

9. Conitzer, V. and sandholm, T. Complexity of mechanism design. In Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (Edmonton, Canada, 2002), 103–110.

10. Conitzer, V. and sandholm, T. Expressive negotiation over donations to charities. In Proceedings of the ACM Conference on Electronic Commerce. ACM, ny (2004), 51–60.

11. Conitzer, V., sandholm, T., and Lang, J. When are elections with few candidates hard to manipulate? J. ACM 54, 3 (2007), 1–33.

12. Cramton, P., shoham, y., and steinberg, r. Combinatorial Auctions. MIT Press, Cambridge, MA, 2006.

13. Feigenbaum, J., schapira, M., and shenker, s. Distributed algorithmic mechanism design. Algorithmic Game Theory. n. nisan, T. roughgarden, E. Tardos, and V. Vazirani, Eds. Cambridge university Press, 2007.

14. Ghosh, A. and Mahdian, M. Charity auctions on social networks. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2008), 1019–1028.

15. A. Gibbard. Manipulation of voting schemes: A general result. Econometrica 41 (1973), 587–602.

16. Groves, T. Incentives in teams. Econometrica 41 (1973), 617–631.

17. Guo, M. and Conitzer, V. Worst-case optimal redistribution of VCG payments in multi-unit auctions. Games and Economic Behavior, 2009. To appear.

18. hemaspaandra, E. and hemaspaandra, L.A. Dichotomy for voting systems. J. Comput. Syst. Sci. 73, 1 (2007), 73–83.

19. Lahaie, s., Pennock, D.M., saberi, A., and Vohra, r.V. sponsored search auctions. Algorithmic Game Theory. n. nisan, T. roughgarden, E. Tardos, and V. Vazirani, Eds. Cambridge university Press, 2007.

20. Lang, J. Vote and aggregation in combinatorial domains with structured preferences. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (hyderabad, India, 2007), 1366–1371.

21. Lehmann, D., o’Callaghan, L.I., and shoham, y. Truth revelation in rapid, approximately efficient combinatorial auctions. J. ACM 49, 5 (2002), 577–602.

22. Lipton, r., Markakis, E., Mossel, E., and saberi, A. on approximately fair allocations of indivisible goods. In Proceedings of the ACM Conference on Electronic Commerce. ACM, ny, (2004), 125–131.

23. Müller, r. Tractable cases of the winner determination problem. Combinatorial Auctions. P. Cramton, y. shoham, and r. steinberg, Eds. MIT Press, Cambridge, MA, 2006, 319–336.

24. nisan, n and ronen, A. Algorithmic mechanism design. Games and Economic Behavior 35 (2001), 166–196.

25. Parkes, D. Iterative combinatorial auctions. Combinatorial Auctions. P. Cramton, y. shoham, and r. steinberg, Eds. MIT Press, 2006, 41–77.

26. Parkes, D. online mechanisms. Algorithmic Game Theory. n. nisan, T. roughgarden, E. Tardos, and V. Vazirani, Eds. Cambridge university Press, 2007.

27. roth, A.E., sonmez, T., and unver, M.u. Kidney exchange. Quarterly J. Economics, 119, (2004), 457–488.

28. rothkopf, M., Pekec, A., and harstad, r. Computationally manageable combinatorial auctions. Management Science 44, 8 (1998), 1131–1147.

29. sandholm, T. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135 (Jan. 2002), 1–54.

30. sandholm, T. optimal winner determination algorithms. Combinatorial Auctions. P. Cramton, y. shoham, and r. steinberg, Eds. MI T Press, 2006, 337–368.

31. sandholm, T. Expressive commerce and its application to sourcing: how we conducted $35 billion of generalized combinatorial auctions. AI Magazine 28, 3 (2007), 45–58.

32. sandholm, T. and boutilier, C. Preference elicitation in combinatorial auctions. Combinatorial Auctions. P. Cramton, y. shoham, and r. steinberg, Eds. MI T Press, 2006, 233–263.

33. satterthwaite, M. strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Economic Theory 10 (1975), 187–217.

34. shoham, y. Computer science and game theory. Commun. ACM 51, 8 (Aug. 2008), 74–79.

35. Varian, h.r. Designing the perfect auction. Commun. ACM 51, 8 (Aug. 2008) 9–11.

36. Vickrey, W. Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16 (1961), 8–37.

37. Wolfers, J. and Zitzewitz, E. Prediction markets. J. Economic Perspectives 18, 2 (2004), 107–126.

38. Xia, L., Conitzer, V., and Lang, J. Voting on multiattribute domains with cyclic preferential dependencies. In Proceedings of the National Conference on Artificial Intelligence (Chicago, IL, 2008), 202–207.

39. yokoo, M., sakurai, y., and Matsubara, s. The effect of false-name bids in combinatorial auctions: new fraud in Internet auctions. Games and Economic Behavior 46, 1 (2004), 174–188.