Communications of the ACM

skill is a marginal distribution of the posterior joint distribution of a multivariate variable that consists of individual skills and individual performances. This posterior joint distribution consists of several factors that are conveniently represented by a graphical model, a way to represent the information about which factors depend on which variables. The marginal posterior distributions of skills can be computed using standard message-passing methods for inference in graphical models, such as the sum-product algorithm. It is common to approximate a marginal distribution of a skill variable with a distribution from an assumed family of distributions; for example, assuming the family of Gaussian distributions, as done in the TrueSkill rating system. The approximate Bayesian inference amounts to approximating marginal posterior distributions of skills by distributions from the given family of distributions, assuming that marginal prior distributions belong to this family of distributions.

Future Directions

Strategic game models of contests provide plenty of interesting hypotheses about what strategic user behavior may arise in different contest situations. Future work must be devoted to narrowing the gap between theoretical results and empirical validations. The availability of online services whose design is based on contests and the collected data provides us with an opportunity to test the existing theories and guide the development of new contributions to contest theory. Another research direction is to study statistical inference methods for various contest designs, such as in the recent study of A/B testing for auctions. 6

While the skill-rating methods
have been studied extensively over
many years, some interesting ques-
tions still remain open. Most skill-rat-
ing methods represent an individual’s
skill by a scalar parameter. In many
situations, however, it is of interest
to consider an individual’s skill over
multiple dimensions; for example,
an online worker may have differ-
ent types of skills such as analytical
problem solving, strategic business
planning, and software programming
skills. Another interesting direction
is to study statistical inference meth-
ods for statistical models of ranking
outcomes that allow for a larger set of
unknown parameters. For example, in
an online labor platform, a ranking of
job applicants would depend not only
on the idiosyncratic skills of the ap-
plicants, but also on the specific job
requirements, both of which may have
uncertainties. Another direction is to
develop solid theoretical foundations
for individual skill rating based on
observed team performance outputs.
Current statistical inference meth-
ods used in practice assume simple
models of team performance, such as
that a team performance is the sum of
individual performances, which may
not always be valid in practice.

References

1. Archak, N. Money, glory and cheap talk: analysing strategic behavior of contestants in simultaneous crowdsourcing contests on TopCoder.com. In

Proceedings of WWW ‘ 10 (Raleigh, N. C., 2010), 21–30.

2. Baye, M. R., Kovenock, D. and de Vries, C.G. The all-pay auction with complete information. Econ. Theory 8, 2

(1996), 291–305.

3. Bishop, D. T. et al. The war of attrition with random rewards. J. Theoretical Bio 70, 1 (1978), 85–124.

4. Bradley, R. A. and Terry, M.E. Rank analysis of incomplete block designs: I. Method of paired comparisons. Biometrika 20, 3–4 (1952), 334–345.

5. Bulow, J. et al. The generalized war of attrition. Amer.

Econ. Rev. 39, 3–4 (1997), 324–345.

6. Chawla, S., Hartline, J. D. and Nekipelov, D. A/B testing of auctions. In Proceedings of ACM EC ‘ 16 (Maastricht, Neterlands, 2016), 856–868.

7. Chawla, S., Hartline, J.D. and Sivan, B. Optimal crowdsourcing contests. In Proceedings of SODA ‘ 12, (Kyoto, Japan, 2012), 856–868.

8. Clark, D.J. and Riis, C. Competition over more than one prize. Amer. Econ. Rev. 88, 1 (1998), 276–289.

9. Corchon, L. C. The theory of contests: A survey. Rev.

Econ. Design 11 (2007), 69–100.

10. Corchon, L. and Dahm, M. Foundations for contest success functions. Econ. Theory 88, 1 (2010), 81–98.

11. DiPalantino, D. and Vojnovic, M. Crowdsourcing and all-pay auctions. In Proceedings of ACM EC ‘09

(Stanford, CA, 2009), 119–128.

12. Doan, A., Ramakrishnan, R. and Halevy, A. Y.

Crowdsourcing systems on the World-Wide Web.

Commun. ACM 54, 4 (Apr. 2011), 85–96.

13. Elo, A.E. The rating of chessplayers. Ishi Press International, 1978.

14. Franke, J., Kanzow, C., Leininger, W. and Schwartz, A. Lottery versus all-pay auction contests: A revenue dominance theorem. Games and Economic Behavior,

13 (2014), 116–126.

15. Galton, F. The most suitable proportion between the value of first and second prizes. Biometrika 1, 4 (1902),

385–399.

16. Ghosh, A. and McAfee, R.P. Crowdsourcing with endogenous entry. In Proceedings of WWW ‘ 12 (Lyon, France, 2012), 999–1008.

17. Glazer, A. and Hassin, R. Optimal contests. Economic Inquiry 26, 1 (1988), 133–143.

18. Hajek, B., Oh, S. and Xu, J. Minimax-optimal inference from partial rankings. In Proceedings of NIPS ‘ 14, (Montreal, Quebec, 2014), 1475–1483.

19. Hardin, G. The tragedy of the commons. Science 162,

3859 (1968), 1243–1248.

20. Herbrich, R., Minka, T. and Graepel, T. TrueSkill: A Bayesian skill rating system. In Proceedings of NIPS ‘06, (Vancouver, B. C., 2006), 569–576.

21. Johari, R. and Tsitsiklis, J.N., Efficiency loss in a network resource allocation game. Math. Operations Res 29, 3 (2004), 402–435.

22. Kelly, F. Charging and rate control for elastic traffic.

European Trans. Telecommun. 8, 1 (1997), 33–37.

23. Kitcher, P. The division of cognitive labor. J. Philosophy 87, 1 (1990), 5–22.

24. Kleinberg, J. and Oren, S. Mechanisms for (mis) allocating scientific credit. In Proceedings of S TOC ‘ 11 (San Jose, CA, 2011), 529–538.

25. Konrad, K.A. Strategy in Contest—An Introduction.
WZB-Markets and Politics Working Paper N. SP II
2007-01; 2007 ( http://ssrn.com/abstract=960458).
26. Krueger, A.O. The political economy of the rent-
seeking society. Amer. Econ. Rev. 64, (1974), 291–303.
27. Lazear, E.P. and Rosen, S. Rank-order tournaments
as optimum labor contracts. J. Pol. Econ. 89, 5 (1981),
841–864.

28. Moldovanu, B. and Sela, A. The optimal allocation of prizes in contests. American Econ. Rev. 91, 3 (2001), 542–558.

29. Myerson, R.B. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58–73.

30. Neghaban, S., Oh, S., and Shah, D. Iterative ranking from pair-wise comparisons. In Proceedings of NIPS ‘ 12, (Lake Tahoe, NV, 2012), 2483–2491.

31. Nisan, N., Roughgarden, T., Tardos, E. & Vazirani, V. V., 2007. Algorithmic Game Theory. Cambridge University Press.

32. Nitzan, S., 1994. Modelling rent-seeking contests. Eur. J. Polit. Econ. 10 (1994),, pp. 41-60.

33. Roughgarden, T. Algorithmic game theory. Commun. ACM 53, 7 (2010), 78–86.

34. Roughgarden, T. Intrinsic robustness of the prize of anarchy. Commun. ACM 55, 7 (2012), 116–123.

35. Shaili, J., Yiling, C., Parkes, D.C. Designing incentives for online question and answer forums. In Proceedings of ACM EC ‘09 (Stanford, CA, 2009), 129–138.

36. Shoham, Y. Computer science and game theory. Commun. ACM 51, 8 (2008), 75–79.

37. Stoica, I. et al. A proportional share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th Real-Time Systems Symposium. (Washington, D. C., 1996), 288–299.

38. Tang, J.C. et al. Reflecting on the DARPA Red Balloon Challenge. Commun. 54, 4 (2011), 78–85.

39. Thurstone, L. L. A law of comparative judgment. Psychological Review 34, 2 (1927), 273–286.

40. Tullock, G., Efficient rent seeking. In Theory of the Rent-Seeking Society. A&M University Press (1980), 131–146.

41. Vetta, A., Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (2002), 416–425.

42. Vojnović, M. Contest Theory: Incentive Mechanisms and Ranking Methods. Cambridge University Press, 2016.

43. Vojnović, M. and Yun, S.-Y., Parameter estimation for generalized Thurstone choice models. In Proceedings of ICML ‘ 16 (New York City, NY, 2016).

44. Yang, J., Adamic, L., and Ackerman, M. Crowdsourcing and knowledge sharing: Strategic user behavior on Taskcn. In Proceedings of the ACM EC ‘09 (Chicago, Il, 2008).

45. Zermelo, E. Die Berechnung der Turnier-Ergebnisse al sein Maximumproblem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift 29 (1929), 436–460.

Milan Vojnović ( m.vojnovic@lse.ac.uk) is a professor of data science in the Department of Statistics, London School of Economics, U.K., where he serves as program director of MSc in Data Science.