Optional Reading
Part I: Behavior, Contributions, and Coordination
Algorithms for Distributed Optimization
Solving Distributed Constraint Optimization Problems Using Cooperative Mediation
Mailler, Roger, and Victor Lesser. "Solving distributed constraint optimization problems using cooperative mediation." Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1. IEEE Computer Society, 2004.
Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems
Mailler, Roger, and Victor Lesser. "Using cooperative mediation to solve distributed constraint satisfaction problems." Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1. IEEE Computer Society, 2004.
A Scalable Method for Multiagent Constraint Optimization
Petcu, Adrian, and Boi Faltings. "A scalable method for multiagent constraint optimization." IJCAI. Vol. 5. 2005.
Voting and Problem Solving in Networks
Experiments in Social Computation
Kearns, Michael. "Experiments in social computation." Communications of the ACM 55.10 (2012): 56-67.
Behavioral Experiments on a Network Formation Game
Kearns, Michael, Stephen Judd, and Yevgeniy Vorobeychik. "Behavioral experiments on a network formation game." Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 2012.
Emergence of Cooperation in Anonymous Social Networks through Social Capital
Immorlica, Nicole, Brendan Lucier, and Brian Rogers. "Emergence of cooperation in anonymous social networks through social capital." Proceedings of the 11th ACM Conference on Electronic Commerce. 2010.
Market-Oriented Programming
The HOMEBOTS System and Field Test: A Multi-Commodity Market for Predictive Power Load Management
Ygge, Fredrik, et al. "The HOMEBOTS system and field test: A multi-commodity market for predictive power load management." Proceedings 4th Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology PAAM-99 (London, UK, 19-21 April 1999). 1999.
A Computational Market Model for Distributed Configuration Design
Wellman, Michael P. A computational market model for distributed configuration design. San Francisco, CA: Morgan Kaufmann, 1998.
Cooperative Approaches
Clearwater, Scott H., Tad Hogg, and Bernardo A. Huberman. "Cooperative problem solving." Computation: The Micro and the Macro View (1992): 33-70.
An Economics Approach to Hard Computational Problems
Huberman, Bernardo A., Rajan M. Lukose, and Tad Hogg. "An economics approach to hard computational problems." Science 275.5296 (1997): 51-54.
Models of Cooperation
Cooperation and assortativity with dynamic partner updating
Wang, Jing, Siddharth Suri, and Duncan J. Watts. "Cooperation and assortativity with dynamic partner updating." Proceedings of the National Academy of Sciences 109.36 (2012): 14363-14368.
Social Influence Bias: A Randomized Experiment
Lev Muchnik, Sinan Aral, and Sean J. Taylor
Science 9 August 2013: 341 (6146), 647-651. [DOI:10.1126/science.1240466]
Behavioral Game Theory
Beyond Equilibrium: Predicting Human Behavior in Normal-Form Games
Wright, James R., and Kevin Leyton-Brown. "Beyond Equilibrium: Predicting Human Behavior in Normal-Form Games." AAAI. 2010.
Security Games
Computing Optimal Randomized Resource Allocation for Massive Security Games
Kiekintveld, Christopher, et al. "Computing optimal randomized resource allocations for massive security games." Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2009.
Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Games
Paruchuri, Praveen, et al. "Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games." Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2. International Foundation for Autonomous Agents and Multiagent Systems, 2008.
Computing the Optimal Strategy to Commit to
Conitzer, Vincent, and Tuomas Sandholm. "Computing the optimal strategy to commit to." Proceedings of the 7th ACM conference on Electronic commerce. ACM, 2006.
Pita, James, et al. "Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport."Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track. International Foundation for Autonomous Agents and Multiagent Systems, 2008.
Game-theoretic Randomization for Security Patrolling with Dynamic Execution Uncertainty
Jiang, Albert Xin, et al. "Game-theoretic randomization for security patrolling with dynamic execution uncertainty." Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 2013.
Game-Theoretic Question Selection for Tests
Li, Yuqian, and Vincent Conitzer. "Game-Theoretic Question Selection for Tests."
Steering User Behavior
Incentives, gamification, and game theory: An economic approach to badge design
Easley, David, and Arpita Ghosh. "Incentives, gamification, and game theory: An economic approach to badge design." Proceedings of the fourteenth ACM conference on Electronic commerce. ACM, 2013.
Evolution of Two-Sided Markets
Kumar, Ravi, Yury Lifshits, and Andrew Tomkins. "Evolution of two-sided markets." Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010.
Designing Incentives for Online Question-and-Answer Forums
Jain, Shaili, Yiling Chen, and David C. Parkes. "Designing incentives for online question-and-answer forums." Games and Economic Behavior (2012).
Implementing Optimal Outcomes in Social Computing: A Game-Theoretic Approach
Ghosh, Arpita, and Patrick Hummel. "Implementing optimal outcomes in social computing: a game-theoretic approach." Proceedings of the 21st international conference on World Wide Web. ACM, 2012.
Anderson, Ashton, et al. "Discovering value from community activity on focused question answering sites: a case study of stack overflow."Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.
A Game-Theoretic Analysis of Rank-Order Mechanisms for User-Generated Content
Ghosh, Arpita, and Patrick Hummel. "A game-theoretic analysis of rank-order mechanisms for user-generated content." Proceedings of the 12th ACM conference on Electronic commerce. ACM, 2011.
Learning and Incentives is User-Generated Content: Multi-Armed Bandits with Endogenous Arms
Ghosh, Arpita, and Patrick Hummel. "Learning and incentives in user-generated content: Multi-armed bandits with endogenous arms." Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM, 2013.
A Game-Theoretic Analysis of the ESP Game
Jain, Shaili, and David C. Parkes. "A game-theoretic analysis of the esp game." ACM Transactions on Economics and Computation 1.1 (2013): 3.
Morgan, John, Dana Sisak, and Felix Vardy. On the merits of meritocracy. No. TI 12-077/1. Tinbergen Institute, 2012.
Evolution of Experts in Question Answering Communities
Pal, Aditya, Shuo Chang, and Joseph A. Konstan. "Evolution of Experts in Question Answering Communities." ICWSM. 2012.
Policy Teaching Through Reward Function Learning
Zhang, Haoqi, David C. Parkes, and Yiling Chen. "Policy teaching through reward function learning." Proceedings of the 10th ACM conference on Electronic commerce. ACM, 2009.
Gamification: Using Game Design Elements in Non-Gaming Contexts
Deterding, Sebastian, et al. "Gamification. using game-design elements in non-gaming contexts." PART 2-----------Proceedings of the 2011 annual conference extended abstracts on Human factors in computing systems. ACM, 2011.
Incentivizing High-quality User-Generated Content
Ghosh, Arpita, and Preston McAfee. "Incentivizing high-quality user-generated content." Proceedings of the 20th international conference on World wide web. ACM, 2011.
Cooperative Game Theory: Shapley Value
On Computational Complexity of Weighted Voting Games
Elkind, Edith, et al. "On the computational complexity of weighted voting games." Annals of Mathematics and Artificial Intelligence 56.2 (2009): 109-131.
On the Complexity of Cooperating Solution Concepts
Deng, Xiaotie, and Christos H. Papadimitriou. "On the complexity of cooperative solution concepts." Mathematics of Operations Research 19.2 (1994): 257-266.
Designing Incentives for Boolean Games
Endriss, Ulle, et al. "Designing incentives for boolean games." The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2011.
A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
Elkind, Edith, et al. "A tractable and expressive class of marginal contribution nets and its applications." Mathematical Logic Quarterly 55.4 (2009): 362-376.
Computational Aspects of Extending the Shapley Value to Coalitional Games with Externalities
Michalak, Tomasz P., et al. "Computational Aspects of Extending the Shapley Value to Coalitional Games with Externalities." ECAI. 2010.
Transferable Utility Planning Games
Brafman, Ronen I., et al. "Transferable Utility Planning Games." AAAI. 2010.
Brafman, Ronen I., et al. "Planning Games." IJCAI. 2009.
Multi-Attribute Coalitional Games
Ieong, Samuel, and Yoav Shoham. "Multi-attribute coalitional games."Proceedings of the 7th ACM Conference on Electronic Commerce. ACM, 2006.
Computational Coalition Formation
Elkind, Edith, Talal Rahwan, and Nicholas R. Jennings. "Computational Coalition Formation." (2013).
Conitzer, Vincent, and Tuomas Sandholm. "Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains." AAAI. Vol. 4. 2004.
Cooperative Game Theory
A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments
Ohta, Naoki, et al. "A compact representation scheme for coalitional games in open anonymous environments." AAAI. Vol. 6. 2006.
The Shapley Value of Phylogenetic Trees
Haake, Claus-Jochen, Akemi Kashiwada, and Francis Edward Su. "The Shapley value of phylogenetic trees." Journal of mathematical biology 56.4 (2008): 479-497.
Axiomatization of the Shapley Value on Minimum Cost Spanning Tree Games
Kar, Anirban. "Axiomatization of the Shapley value on minimum cost spanning tree games." Games and Economic Behavior 38.2 (2002): 265-277.
A Theory of Diversity
Nehring, Klaus, and Clemens Puppe. "A theory of diversity." Econometrica70.3 (2002): 1155-1198.
Assigning Credit - Online Environments
Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing, and Auctions
Vetta, Adrian. "Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions." Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on. IEEE, 2002.
Market Sharing Games Applied to Content Distribution in Ad Hoc Networks
Goemans, Michel X., et al. "Market sharing games applied to content distribution in ad hoc networks." Selected Areas in Communications, IEEE Journal on 24.5 (2006): 1020-1033.
Assigning Credit - Scientific Environments
Mopping Up: Modeling Wikipedia Promotion Decisions
Burke, Moira, and Robert Kraut. "Mopping up: modeling wikipedia promotion decisions." Proceedings of the 2008 ACM conference on Computer supported cooperative work. ACM, 2008.
Egalitarians at the Gate: One-Sided Gatekeeping Practices in Social Media
Keegan, Brian, and Darren Gergle. "Egalitarians at the gate: One-sided gatekeeping practices in social media." Proceedings of the 2010 ACM conference on Computer supported cooperative work. ACM, 2010.
Part II: Aggregation, Selection, and Consensus
Computational Social Choice
Schulze, Markus. "A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method." Social Choice and Welfare 36.2 (2011): 267-303.
A quantitative Gibbard-Satterthwaite theorem without neutrality
Mossel, Elchanan, and Miklós Z. Rácz. "A quantitative Gibbard-Satterthwaite theorem without neutrality." Proceedings of the 44th symposium on Theory of Computing. ACM, 2012.
A Complexity-of-Strategic-Behavior Comparison between Schulze’s Rule and Ranked Pairs
Parkes, David C., and Lirong Xia. "A Complexity-of-Strategic-Behavior Comparison between Schulze's Rule and Ranked Pairs." AAAI. 2012.
Improved Bound for Computing Kemeny Rankings
Conitzer, Vincent, Andrew Davenport, and Jayant Kalagnanam. "Improved bounds for computing Kemeny rankings." AAAI. Vol. 6. 2006.
Young, Peyton. "Optimal voting rules." The Journal of Economic Perspectives9.1 (1995): 51-64.
Arrow’s theorem and the Gibbard-Satterthwaite theorem: a unified approach
Reny, Philip J. "Arrow’s theorem and the Gibbard-Satterthwaite theorem: a unified approach." Economics Letters 70.1 (2001): 99-105.
Axiomatic Ranking and Trust Systems
Trust, Ratings, and Sybil-Proofness
Statistical Rank Aggregation
Young, H. Peyton. "Condorcet's theory of voting." The American Political Science Review (1988): 1231-1244.
Analysis of Irish third-level college application data
Bayesian inference for Plackett-Luce ranking models
Guiver, John, and Edward Snelson. "Bayesian inference for Plackett-Luce ranking models." Proceedings of the 26th Annual International Conference on Machine Learning. ACM, 2009.
Computing Parametric Ranking Models via Rank-Breaking
Soufiani, Hossein Azari, David C. Parkes, and Lirong Xia. "Computing Parametric Ranking Models via Rank-Breaking."
Learning Mallows Model with Pairwise Preferences
Lu, Tyler, and Craig Boutilier. "Learning Mallows models with pairwise preferences." Proceedings of the 28th International Conference on Machine Learning (ICML-11). 2011.
A Maximum Likelihood Approach towards Aggregating Partial Orders
Xia, Lirong, and Vincent Conitzer. "A maximum likelihood approach towards aggregating partial orders." Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume One. AAAI Press, 2011.
Iterative Ranking from Pair-wise Comparisons
Negahban, Sahand, Sewoong Oh, and Devavrat Shah. "Iterative ranking from pair-wise comparisons." arXiv preprint arXiv:1209.1688 (2012).
Whole-History Rating: A Bayesian Rating System for Players of Time-Varying Strength
Coulom, Rémi. "Whole-history rating: A bayesian rating system for players of time-varying strength." Computers and games. Springer Berlin Heidelberg, 2008. 113-124.
MM Algorithms for Generalized Bradley-Terry Models
Hunter, David R. "MM algorithms for generalized Bradley-Terry models."Annals of Statistics (2004): 384-406.
Rank Aggregation Methods for the Web
Dwork, Cynthia, et al. "Rank aggregation methods for the web." Proceedings of the 10th international conference on World Wide Web. ACM, 2001.
Ground Truth Learning from Multiple Experts
Maximum Likelihood Estimation of Observer Error-Rates Using the EM Algorithm
Dawid, Alexander Philip, and Allan M. Skene. "Maximum likelihood estimation of observer error-rates using the EM algorithm." Applied Statistics (1979): 20-28.
Get Another Label? Improving Data Quality and Data Mining Using Multiple, Noisy Labels
Sheng, Victor S., Foster Provost, and Panagiotis G. Ipeirotis. "Get another label? improving data quality and data mining using multiple, noisy labelers."Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008.
Inferring ground truth from subjective labeling of Venus images
Smyth, Padhraic, et al. "Inferring ground truth from subjective labelling of venus images." Advances in neural information processing systems (1995): 1085-1092.
Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise
Whitehill, Jacob, et al. "Whose vote should count more: Optimal integration of labels from labelers of unknown expertise." Advances in neural information processing systems. 2009.
Ranking annotators for crowdsourced labeling tasks
Raykar, Vikas C., and Shipeng Yu. "Ranking annotators for crowdsourced labeling tasks." Advances in Neural Information Processing Systems. 2011.
Peer Evaluation and Peer Review
Bachrach, Yoram, et al. "How To Grade a Test Without Knowing the Answers---A Bayesian Graphical Model for Adaptive Crowdsourcing and Aptitude Testing." arXiv preprint arXiv:1206.6386 (2012).
Peering Inside Peer Review with Bayesian Models
Goldin, Ilya M., and Kevin D. Ashley. "Peering inside peer review with Bayesian models." Artificial Intelligence in Education. Springer Berlin Heidelberg, 2011.
Probabilistic Matrix Factorization
Mnih, Andriy, and Ruslan Salakhutdinov. "Probabilistic matrix factorization."Advances in neural information processing systems. 2007.
Selection Mechanisms
Impartial nominations for a prize
Holzman, Ron, and Hervé Moulin. "Impartial nominations for a prize."Econometrica 81.1 (2013): 173-196.
Matching Markets
The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory
Roth, Alvin E. "The evolution of the labor market for medical interns and residents: a case study in game theory." The Journal of Political Economy(1984): 991-1016.
The Efficient Allocation of Individuals to Positions
Hylland, Aanund, and Richard Zeckhauser. "The efficient allocation of individuals to positions." The Journal of Political Economy (1979): 293-314.
Matching with Incomplete Information
Liu, Quingmin, et al. "Matching with incomplete information." (2012).
Stability in Matching Problems with Weighted Preferences
Pini, Maria Silvia, et al. "Stability in Matching Problems with Weighted Preferences." ICAART (2). 2011.
Stable Matchings, Optimal Assignments, and Linear Programming
Roth, Alvin E., Uriel G. Rothblum, and John H. Vande Vate. "Stable matchings, optimal assignments, and linear programming." Mathematics of Operations Research 18.4 (1993): 803-828.
Two-Sided Matching with Partial Information
Rastegari, Baharak, et al. "Two-sided matching with partial information."Proceedings of the fourteenth ACM conference on Electronic commerce. ACM, 2013.
Stable Matching with Incomplete Lists and Ties
Iwama, Kazuo, et al. "Stable marriage with incomplete lists and ties."Automata, Languages and Programming. Springer Berlin Heidelberg, 1999. 443-452.
College Admissions and the Stability of Marriage
Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15.
Improvements through Interleaving
The K-armed dueling bandit problem
Yue, Yisong, et al. "The< i> K</i>-armed dueling bandits problem." Journal of Computer and System Sciences 78.5 (2012): 1538-1556.
Brandt, Christina, et al. "Dynamic ranked retrieval." Proceedings of the fourth ACM international conference on Web search and data mining. ACM, 2011.
Explore, Exploit, and Dynamic Choice
Analysis of Thompson Sampling for the multi-armed bandit problem
Agrawal, Shipra, and Navin Goyal. "Analysis of thompson sampling for the multi-armed bandit problem." arXiv preprint arXiv:1111.1797 (2011).
Graepel, Thore, et al. "Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.
Strategic Experimentation with Exponential Bandits
Keller, Godfrey, Sven Rady, and Martin Cripps. "Strategic experimentation with exponential bandits." Econometrica 73.1 (2005): 39-68.
Bolton, Patrick, and Christopher Harris. "Strategic experimentation."Econometrica 67.2 (1999): 349-374.
Implementing the “Wisdom of the Crowd”
Kremer, Ilan, Yishay Mansour, and Motty Perry. "Implemeting the” Wisdom of the Crowd”." (2013).
Learning and Incentives in User-Generated Content: Multi-Armed Bandits with Endogenous Arms
Ghosh, Arpita, and Patrick Hummel. "Learning and incentives in user-generated content: Multi-armed bandits with endogenous arms." Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM, 2013.
Mean Field Equilibria of Multiarmed Bandit Games
Gummadi, Ramakrishna, Ramesh Johari, and Jia Yuan Yu. "Mean Field Equilibria of Multiarmed Bandit Games." Available at SSRN 2045842 (2013).
Characterizing Truthful Multi-Armed Bandit Mechanisms
Babaioff, Moshe, Yogeshwer Sharma, and Aleksandrs Slivkins. "Characterizing truthful multi-armed bandit mechanisms." Proceedings of the 10th ACM conference on Electronic commerce. ACM, 2009.
Optimal Coordinated Planning Amongst Self-Interested Agents with Private State
Cavallo, Ruggiero, David C. Parkes, and Satinder Singh. "Optimal coordinated planning amongst self-interested agents with private state." arXiv preprint arXiv:1206.6820 (2012).
Bergemann, Dirk, and Juuso Välimäki. "The dynamic pivot mechanism."Econometrica 78.2 (2010): 771-789.
Improvements through interleaving
Large Scale Validation and Analysis of Interleaved Search Evaluation
Chapelle, Olivier, et al. "Large-scale validation and analysis of interleaved search evaluation." ACM Transactions on Information Systems (TOIS) 30.1 (2012): 6.
Explore, Exploit, and Dynamic Choice
An Empirical Evaluation of Thompson Sampling
Chapelle, Olivier, and Lihong Li. "An empirical evaluation of thompson sampling." Advances in Neural Information Processing Systems. 2011.
An Efficient Simulation-based Approach to Ambulance Fleet Allocation and Dynamic Redeployment
Yue, Yisong, Lavanya Marla, and Ramayya Krishnan. "An Efficient Simulation-Based Approach to Ambulance Fleet Allocation and Dynamic Redeployment."AAAI. 2012.
Below is a list of papers to serve as companion papers to each lecture. These are not required readings but they are intended to serve as a good reference for students who want to dig deeper into these topics.