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.
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.
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
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
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),
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),
28. Moldovanu, B. and Sela, A. The optimal allocation of
prizes in contests. American Econ. Rev. 91, 3 (2001),
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
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),
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),
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
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
Zeitschrift 29 (1929), 436–460.
Milan Vojnović ( firstname.lastname@example.org) 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.
©2017 ACM 0001-0782/17/05 $15.00.
Watch the author discuss
his work in this exclusive