Mathematical foundations for social computing

Abstract

Social computing benefits from mathematical foundations, but research has barely scratched the surface.

References

1. Abernethy, J., Chen, Y. and Vaughan, J.W. Efficient market making via convex optimization, and a connection to online learning. ACM Trans. Economics and Computation 1, 2 (2013), Article 12.
2. Abernethy, J., Frongillo, R., Li, X. and Vaughan, J.W. A general volume-parameterized market-making framework. In Proceedings of the 15^th ACM Conference on Economics and Computation, 2014.
3. Barowy, D., Curtsinger, C., Berger, E.D. and McGregor, A. Automan: A platform for integrating human-based and digital computation. In Proceedings of the Object-Oriented Programming, Systems, Languages, and Applications, 2012.
4. Brandt, F., Conitzer, V., Endriss, U., Lang, J. and Procaccia, J.D., Eds. Handbook of Computational Social Choice. Cambridge University Press. Forthcoming.
5. Chen, Y., Fortnow, L., Lambert, N., Pennock, D. and Wortman, J. Complexity of combinatorial market makers. In Proceedings of the 9^th ACM Conference on Electronic Commerce, 2008.
6. Coleman, J. Introduction to Mathematical Sociology. Free Press of Glencoe, 1964.
7. Dasgupta, A. and Ghosh, A. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22^nd International World Wide Web Conference, 2013.
8. de Clippel, G., Moulin, H. and Tideman, N. Impartial division of a dollar. J. Economic Theory 139, 1 (2008), 176--191.
9. Dudik, M., Lahaie, S. and Pennock, D.M. A tractable combinatorial market maker using constraint generation. In Proceedings of the 13^th ACM Conference on Electronic Commerce, 2012.
10. Dudik, M., Lahaie, S. and Pennock, D.M and Rothschild, D. A combinatorial prediction market for the U.S. elections. In Proceedings of the 14^th ACM Conference on Electronic Commerce, 2013.
11. Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science 9, 34 (2014), 211--407.
12. Easley, D. and Ghosh, A. Incentives, gamification, and game theory: An economic approach to badge design. In Proceedings of the 14^th ACM Conference on Electronic Commerce, 2013.
13. Easley, D. and Ghosh, A. Behavioral mechanism design: Optimal crowdsourcing contracts and prospect theory. In Proceedings of the 16^th ACM Conference on Economics and Computation, 2015.
14. Ghosh, A. Game theory and incentives in human computation. Handbook of Human Computation. P. Michelucci, ed. Springer, 2014.
15. Ghosh, A. and Hummel, P. A game-theoretic analysis of rank-order mechanisms for user-generated content. In Proceedings of the 12^th ACM Conference on Electronic Commerce, 2011.
16. Ghosh, A. and Kleinberg, R. Behavioral mechanism design: Optimal contests for simple agents. In Proceedings of the 15^th ACM Conference on Economics and Computation, 2014.
17. Ghosh, A. and McAfee, P. Incentivizing high-quality user generated content. In Proceedings of the 22^th International World Wide Web Conference, 2011.
18. Ghosh, A. and McAfee, P. Crowdsourcing with endogenous entry. In Proceedings of the 21^st International World Wide Web Conference, 2012.
19. Giles, J. Computational social science: Making the links. Nature 488, 7412 (2012).
20. Gneiting, T. and Raftery, A.E. Strictly proper scoring rules, prediction, and estimation. J. American Statistical Association 102, 477 (2007), 359--378.
21. Goel, A., Krishnaswamy, A., Sakshuwong, S. and Aitamurto, T. Knapsack voting. Collective Intelligence, 2015.
22. Goldman, J. and Procaccia, A.D. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13, 2 (2014), 41--46.
23. Hanson, R. Combinatorial information market design. Information Systems Frontiers 1 (2003), 105--119.
24. Ho, C.-J. and Vaughan, J.W. Online task assignment in crowdsourcing markets. In Proceedings of the 26^th AAAI Conference on Artificial Intelligence, 2012.
25. Ho, C.-J., Jabbari, S. and Vaughan, J.W. Adaptive task assignment for crowdsourced classification. In Proceedings of the 26^th International Conference on Machine Learning, 2013.
26. Ho, C.-J., Slivkins, A., Suri, S. and Vaughan, J.W. Incentivizing high quality crowdwork. In Proceedings of the 24^th International World Wide Web Conference, 2015.
27. Immorlica, N., Stoddard, G. and Syrgkanis, V. Social status and badge design. In Proceedings of the 24^th International World Wide Web Conference, 2015.
28. Jain, S. and Parkes, D.C. A game-theoretic analysis of the ESP Game. ACM Trans. Economics and Computation 1, 1 (2013), 3:1--3:35.
29. Jain, S., Chen, Y. and Parkes, D.C. Designing incentives for online question-and-answer forums. Games and Economic Behavior 86 (2014), 458--474.
30. Karger, D., Oh, S. and Shah, D. Iterative learning for reliable crowdsourcing systems. Advances in Neural Information Processing Systems, 2011.
31. Kearns, M. Experiments in social computation. Commun. ACM 55, 10 (Oct. 2012).
32. Kurokawa, D., Procaccia, A.D. and Shah, N. Leximin allocations in the real world. In Proceedings of the 16^th ACM Conference on Economics and Computation, 2015.
33. Lambert, N.S., Langford, J., Vaughan, J.W., Chen, Y., Reeves, D., Shoham, Y. and Pennock, D.M. An axiomatic characterization of wagering mechanisms. J. Economic Theory 156 (2015), 389--416.
34. Lazer, D. et al. Computational social science. Science 323, 5915 (2009), 721--723.
35. Mason, W. and Watts, D. Financial incentives and the "performance of crowds." In Proceedings of the First Human Computation Workshop, 2009.
36. Procaccia, A.D. Cake cutting: Not just child's play. Commun. ACM 56, 7 (July 2013), 78--87.
37. Slivkins, A. and Vaughan, J.W. Online decision making in crowdsourcing markets: Theoretical challenges. ACM SIGecom Exchanges 12, 2 (2013).
38. Ungar, L., Mellors, B., Satopää, V., Baron, J., Tetlock, P., Ramos, J. and Swift, S. The good judgment project: A large-scale test of different methods of combining expert predictions. AAAI Technical Report FS-12-06, 2012.
39. Waggoner, B. and Chen, Y. Output agreement mechanisms and common knowledge. In Proceedings of the 2^nd AAAI Conference on Human Computation and Crowdsourcing, 2014.
40. Yin, M., Chen, Y. and Sun, Y.-A. The effects of performance-contingent financial incentives in online labor markets. In Proceedings of the 27^th AAAI Conference on Artificial Intelligence, 2013.

Index Terms

• Mathematics of computing

• Theory of computation

  • Logic

    • Constructive mathematics

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Social networks