Computational Social Choice: Some Current and New Directions

Aziz, Haris

Computational Social Choice: Some Current and New Directions

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 4054-4056.

Abstract

Computational social choice is an exciting interdisciplinary field at the intersection of computer science and social choice theory. In this article, I discuss some current and new directions in the field. This is an accompanying paper of my IJCAI 2016 Early Career Spotlight invited talk.

[Alon et al., 2011] N. Alon, F. Fischer, A. D. Procaccia, and M. Tennenholtz. Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th TARK Conference, pages 101-110, 2011.
[Amanatidis et al., 2015] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. In Proceedings of the 35th ICALP Conference, pages 39-51, 2015.
[Aziz and Mackenzie, 2016a] H. Aziz and S. Mackenzie. A dis- crete and bounded envy-free cake cutting protocol for any number of agents. 2016.
[Aziz and Mackenzie, 2016b] H. Aziz and S. Mackenzie. A dis- crete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th STOC. ACM Press, 2016.
[Aziz and Savani, 2016] H. Aziz and R. Savani. Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Pro- caccia, editors, Handbook of Computational Social Choice, chapter 15. Cambridge University Press, 2016.
[Aziz and Stursberg, 2014] H. Aziz and P. Stursberg. A gener- alization of probabilistic serial to randomized social choice. In Proceedings of the 28th AAAI Conference, pages 559-565. AAAI Press, 2014.
[Aziz and Ye, 2014] H. Aziz and C. Ye. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In Proceedings of the 10th WINE, pages 1-14, 2014.
[Aziz et al., 2013] H. Aziz, F. Brandt, and M. Brill. On the trade- off between economic efficiency and strategyproofness in ran- domized social choice. In Proceedings of the 12th AAMAS Conference, pages 455-462. IFAAMAS, 2013.
[Aziz et al., 2015a] H. Aziz, Simina Brânzei, S. Frederiksen, and A. Filos-Ratsikas. The adjusted winner procedure: Characteri- zations and equilibria. In Proceedings of the 24th IJCAI, pages 454-460, 2015. IJCAI
[Aziz et al., 2015b] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. In Proceedings of the 29th AAAI Conference, pages 784-790, 2015.
[Aziz et al., 2015c] H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh. Computational as- pects of multi-winner approval voting. In Proceedings of the 14th AAMAS Conference, pages 107-115. IFAAMAS, 2015.
[Aziz et al., 2015d] H. Aziz, S. Gaspers, S. Mackenzie, N. Mat- tei, N. Narodytska, and T. Walsh. Manipulating the probabilis- tic serial rule. In Proceedings of the 14th AAMAS Conference, pages 1451-1459, 2015.
[Aziz et al., 2016a] H. Aziz, S. Bouveret, J. Lang, and S. Mackenzie. Complexity of manipulating sequential allocation. 2016.
[Aziz et al., 2016b] H. Aziz, P. Goldberg, and T. Walsh. Equi- libria in sequential allocation. 2016.
[Aziz et al., 2016c] H. Aziz, J. Lang, and J. Monnot. Computing Pareto Optimal Committees. In Proceedings of the 25th IJCAI, 2016. IJCAI
[Aziz et al., 2016d] H. Aziz, O. Lev, N. Mattei, J. S. Rosenchein, and T. Walsh. Strategyproof peer selection: Mechanisms, anal- yses, and experiments. In Proceedings of the 30th AAAI Con- ference, 2016.
[Aziz et al., 2016e] H. Aziz, G. Rauchecker, G. Schryen, and Toby Walsh. Approximation algorithms for max-min share allocations of indivisible chores and goods. 2016.
[Aziz et al., 2016f] H. Aziz, I. Schlotter, and T. Walsh. Control of fair division. In Proceedings of the 25th IJCAI, 2016.
[Aziz, 2013] H. Aziz. Maximal Recursive Rule: A New Social Decision Scheme. In Proceedings of the 23nd IJCAI, pages 34-40. AAAI Press, 2013. IJCAI
[Bouveret and Lang, 2011] S. Bouveret and J. Lang. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd IJCAI, pages 73-78. AAAI Press, 2011. IJCAI
[Bouveret et al., 2016] S. Bouveret, Y. Chevaleyre, and N. Maudet. Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12. Cambridge University Press, 2016.
[Brams and Taylor, 1996] S. J. Brams and A. D. Taylor. Fair Di- vision: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.
[Brandl et al., 2015] F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Technical report, http://arxiv.org/abs/1503.00694, 2015. Link
[Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
[Branzei and Miltersen, 2013] S. Branzei and P. B. Miltersen. Equilibrium analysis in cake cutting. In Proceedings of the 12th AAMAS Conference, pages 327-334. IFAAMAS, 2013.
[Branzei et al., 2014] S. Branzei, Y. Chen, X. Deng, A. Filos- Ratsikas, S. K. S. Frederiksen, and J. Zhang. The fisher mar- ket game: Equilibrium and welfare. In Proceedings of the 28th AAAI Conference, pages 587-593. AAAI Press, 2014.
[Brânzei et al., 2016] S. Brânzei, I. Caragiannis, D. Kurokawa, and A. D. Procaccia. An algorithmic framework for strategic fair division. In Proceedings of the 30th AAAI Conference. AAAI Press, 2016.
[Chen et al., 2013] Y. Chen, J. K. Lai, D. C. Parkes, and A. D. Procaccia. Truth, justice, and cake cutting. Games and Eco- nomic Behavior, 77(1):284-297, 2013.
[Chevaleyre et al., 2007] Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A short introduction to computational social choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOF- SEM), volume 4362 of LNCS, pages 51-69. Springer, 2007.
[Christodoulou et al., 2015] G. Christodoulou, A. Filos- Ratsikas, S. K. S. Frederiksen, P. W. Goldberg, J. Zhang, and J. Zhang. Welfare ratios in one-sided matching mechanisms. Technical report, arXiv.org, 2015.
[Conitzer, 2010] V. Conitzer. Making decisions based on the preferences of multiple agents. Communications of the ACM, 53(3):84-94, 2010.
[de Clippel et al., 2008] G. de Clippel, H. Moulin, and N. Tide- man. Impartial division of a dollar. Journal of Economic The- ory, 139:176-191, 2008.
[Edmonds and Pruhs, 2006] J. Edmonds and K. Pruhs. Cake cut- ting really is not a piece of cake. In Proceedings of the 17th SODA, pages 271-278, 2006.
[Elkind et al., 2014] E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of multiwinner voting rules. In Proceed- ings of the 13th AAMAS Conference, pages 53-60. IFAAMAS, 2014.
[Hazon et al., 2012] N. Hazon, Y. Aumann, S. Kraus, and M. Wooldridge. On the evaluation of election outcomes un- der uncertainty. Artificial Intelligence, 189:1-18, 2012.
[Holzman and Moulin, 2013] R. Holzman and H. Moulin. Im- partial nominations for a prize. Econometrica, 81(1):173-196, 2013.
[Kalinowski et al., 2013] T. Kalinowski, N. Narodytska, T. Walsh, and L. Xia. Strategic behavior when allocating indivisible goods sequentially. In Proceedings of the 27th AAAI Conference, pages 452-458. AAAI Press, 2013.
[Kilgour, 2010] D. M. Kilgour. Approval balloting for multi- winner elections. In Handbook on Approval Voting, chapter 6. Springer, 2010.
[Kurokawa et al., 2015] D. Kurokawa, O. Lev, J. Morgenstern, and A. D. Procaccia. Impartial peer review. In Proceedings of the 23rd IJCAI, pages 582-588. AAAI Press, 2015.
[Lang and Xia, 2016] J. Lang and L. Xia. Voting in combinato- rial domains. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational So- cial Choice, chapter 9. Cambridge University Press, 2016.
[Lindner and Rothe, 2015] C. Lindner and J. Rothe. Cake- cutting: Fair division of divisible goods. In J. Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Divi- sion, chapter 7. Springer-Verlag, 2015.
[Manlove, 2013] D. Manlove. Algorithmics of Matching Under Preferences. World Scientific Publishing Company, 2013.
[Nguyen et al., 2015] N-T. Nguyen, D. Baumeister, and J. Rothe. Strategy-proofness of scoring allocation correspon- dences for indivisible goods. In Proceedings of the 23rd IJCAI, pages 1127-1133. AAAI Press, 2015. IJCAI
[Peterson and Su, 1998] E. Peterson and F. E. Su. Exact proce- dures for envy-free chore division. 1998.
[Procaccia and Wang, 2014] A. D. Procaccia and J. Wang. Fair enough: Guaranteeing approximate maximin shares. In Pro- ceedings of the 15th ACM Conference on E-Commerce, pages 675-692. ACM Press, 2014.
[Procaccia, 2009] A. D. Procaccia. Thou shalt covet thy neigh- bor's cake. In Proceedings of the 21st IJCAI, pages 239-244. AAAI Press, 2009. IJCAI
[Procaccia, 2010] A. Procaccia. Can approximation circumvent Gibbard-Satterthwaite? In Proceedings of the 24th AAAI Con- ference, pages 836-841. AAAI Press, 2010.
[Procaccia, 2016] A. D. Procaccia. Cake cutting algorithms. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procac- cia, editors, Handbook of Computational Social Choice, chap- ter 13. Cambridge University Press, 2016.
[Robertson and Webb, 1998] J. M. Robertson and W. A. Webb. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters, 1998.
[Roth and Sotomayor, 1990] A. E. Roth and M. A. O. So- tomayor. Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press, 1990.
[Rothe, 2015] J. Rothe, editor. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational So- cial Choice, and Fair Division. Springer, 2015.
[Skowron et al., 2016] P. Skowron, P. Faliszewski, and A. Slinko. Axiomatic characterization of committee scoring rules. Technical Report 1604.01529, arXiv.org, 2016.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

Computational Social Choice (COMSOC) is a multidisciplinary research field that combines ideas, models, tools, and techniques from both traditional social choice theory as well as computer science. On one side is classical social choice theory that involves a formal and axiomatic approach towards the problem of achieving socially optimal, fair, or stable outcomes by aggregating agents' preferences in a suitable manner. Representative social choice settings include voting and allocation problems. Since many multi-agent settings within computer science such as ranking systems, crowdsourcing, cloud computing, and two-sided matching markets involve similar concerns, social choice theory has provided a groundswell of ideas to model strategic scenarios in mult-agent settings and formalize fairness and welfare. On the other hand, there are many important problems in social choice that require computational consideration to build scalable systems. Computer science with its toolkit of optimization techniques, tradeoff analysis, and algorithm design is ideal to tackle such problems.

The symbiosis between computer science and social choice theory is well-documented [Conitzer, 2010; Chevaleyre et al., 2007]. AI researchers have been at the forefront of many such developments. As computational social choice matures as a field, flagship handbooks [Brandt et al., 2016] and textbooks [Rothe, 2015] have recently been published. The purpose of this short paper is to mention some current and new trends with COMSOC. The list is very much a personalized perspective on a rich and active field. This is an accompanying paper of my IJCAI 2016 Early Career Spotlight invited talk. The directions I will mention are some I have been working on with colleagues in recent years.

The most well-studied settings in COMSOC include deterministic voting rules selecting a single winning candidate, or mechanisms to divide a set of goods between agents. Recent research tries to go beyond some of these settings. For instance, there has been further progress on randomized voting rules rather than deterministic, on voting rules that select a committee rather than a single winner, and on mechanisms that allocate chores rather than goods. Other approaches include dropping the assumption that agents will act sincerely in settings such as resource allocation and considering computational aspects of strategic behaviour. Finally, reasoning about uncertain preferences in multi-agent settings is another promising direction.

2.1 Randomized Voting

A major focus within computational social choice has been on computational and axiomatic aspects of deterministic voting rules. In many of the papers, if multiple candidates are short-listed as winners, then a lexicographic tie-breaking rule is assumed to return a unique candidate. In the past few years, there has been refreshed focus on randomized voting rules that return a probability distribution over alternative instead of single deterministic alternative [Aziz et al., 2013; Procaccia, 2010]. Randomized voting rules can also be viewed as deterministic fractional voting rules in which the probability of a candidate is its fractional share. Randomization may be a mechanism to escape from various impossibility results [Brandl et al., 2015; Procaccia, 2010].

When the outcomes may be probabilistic, the design space of interesting voting rules becomes much richer. Similarly, standard properties and goals such as participation incentive, strategyproofness, and Pareto optimality need to be generalized to the randomized settings. Often, the properties can be generalized to randomized settings in a number of interesting ways. There has been a flurry of new work in randomized voting on questions such as which axioms can be simultaneously satisfied or are incompatible, as well as the computational complexity of computing outcomes. A case in point is work on the maximal lottery rule that can be viewed as the right way to return a 'randomized Condorcet winner' [Aziz et al., 2013; Brandl et al., 2015]. Other interesting new randomized voting rules that have been recently proposed [Aziz, 2013;

Aziz and Stursberg, 2014] that are fairer or less manipulable than deterministic voting rules.

2.2 Multi-winner Voting

There has also been a surge in new research in multi-winner voting or what is also referred to as committee voting. In the single-winner voting, agents can compactly express preferences over all possible outcomes since the set of outcomes coincides with the set of candidates. In multi-winner voting, the number of possible outcomes can be exponential in the number of candidates. Hence, new computational issues arise with respect to succinct and expressive representation of agent preferences as well as computing optimal multiwinner outcomes. Multi-winner voting can be seen more generally within the umbrella of voting in combinatorial domains [Lang and Xia, 2016].

Compared to single-winner voting, axiomatic aspects of multi-winner voting are also relatively less explored [Elkind et al., 2014]. For example, recently we have been examining a very simple setting in which each agent approves a subset of candidates and based on these approvals, a specified number of candidates are selected [Aziz et al., 2015c]. For this particular setting, we proposed a reasonable property called strong justified representation that captures a fairness goal about which agents should have how many approved candidates in the winning set. We showed that the axiomatic property characterizes an interesting voting rule called proportional approval voting (PAV) (see e.g., [Kilgour, 2010; Aziz et al., 2015b]). The field has a number of under-explored areas and there is potential to generalize rules and characterizations for single-winner settings to those multi-winner voting (see e.g., [Skowron et al., 2016]) as well as to formalize the right axioms for specific multi-winner voting application domains and devise efficient algorithms for rules that satisfy those axioms (see e.g., [Aziz et al., 2016c]).

2.3 Strategyproof Peer Selection

Peer Selection refers to the setting in which the set of voters (agents) and candidates coincide and a subset of agents are to be selected based on peer evaluations. Although standard voting rules can directly be applied to obtain a suitable outcome, such rules may give incentive to agents to misreport their valuations so as to have a better chance of being selected themselves. A challenge in this domain is to construct rules that are strategyproof and also perform well in identifying the 'best' agents. Although the problem is a fundamental one, it has been formally studied only in recent years [Alon et al., 2011; Holzman and Moulin, 2013]. Developments within AI include an interesting randomized rule called Credible Subset that is strategyproof and performs well if each agent reviews a few other agents [Kurokawa et al., 2015]. We proposed a new rule called Dollar Partition [Aziz et al., 2016d] that combines a natural agent partitioning approach with the 'sharing a Dollar' mechanism of de Clippel et al. [2008]. Strategyproof peer selection is still an under-developed area and there is scope for further axiomatic, algorithmic, experimental, and analytical work.

2.4 Computational Aspects of Cake Cutting

Cake-cutting setting is a versatile mathematical model for allocation of a heterogeneous divisible good among multiple agents. Its main application is fair scheduling, resource allocation, and conflict resolution [Brams and Taylor, 1996; Robertson and Webb, 1998]. In the past few years, many of the new developments in algorithmic aspects of cake cutting have been due to AI researchers. For a recent survey on the topic, see [Procaccia, 2016] or [Lindner and Rothe, 2015].

A major goal in the field is finding protocols that use minimal number of queries to compute a fair allocation. It has been open for years whether there exists an envy-free protocol for more than three agents that uses bounded number of queries. Recently, we showed that there exists a bounded envy-free protocol for the case of four agents [Aziz and Mackenzie, 2016b] and even for any number of agents [Aziz and Mackenzie, 2016a]. It will be interesting to see if some of the new techniques used in the protocols can be applied for other fairness concepts. Now that we have shown there exists a bounded envy-free protocol, it also opens the door for finding optimal bounds. The lower bound query complexity of envy-free cake cutting is far from well-understood with only a few results [Edmonds and Pruhs, 2006; Procaccia, 2009].

2.5 Algorithms for Chore Allocation

Fair and efficient allocation of indivisible items has become one of the most active areas in COMSOC. In most of the literature, it is assumed that the items are goods for which the agents have positive utility [Bouveret et al., 2016]. Some of the algorithms that are designed to work for allocation of goods may work for allocation of chores as well especially when preferences are ordinal. However, in general there are no reductions from allocation to chores to goods or vice versa. Compared to goods, the literature on fair allocation of chores is relatively under-developed. A case in point is that there has been exciting progress on approximation of max-min share fair allocations for goods [Procaccia and Wang, 2014; Amanatidis et al., 2015]. It will be interesting to see whether similar approximation bounds can be achieved for allocation of chores [Aziz et al., 2016e]. Just like the allocation of indivisible items, cake cutting in the case where agents have negative utilities is less explored as well [Peterson and Su, 1998]. Finally, allocating combinations of goods and chores is an even more general problem.

2.6 Strategic Aspects in Fair Allocation

Computation complexity of manipulating voting rules is one of the most widely studied problem in COMSOC. There has been progress on looking at similar issues for well-known allocation rules. Relevant questions include the complexity of computing a best response; Nash equilibrium, or Stackelberg strategy as well conditions under which the rules are strategyproof. These questions have recently been studied for prominent allocation rules such as Fischer market allocation [Branzei et al., 2014], sequential allocation [Aziz et al., 2016a; 2016b; Bouveret and Lang, 2011; Kalinowski et al., 2013], probabilistic serial [Aziz et al., 2015d], adjusted winner [Aziz et al., 2015a], scoring-based welfare maximizing rules [Nguyen et al., 2015], as well as cake cutting protocols [Aziz and Ye, 2014; Branzei and Miltersen, 2013; Chen et al., 2013; Brˆanzei et al., 2016]. Other related directions include quantifying the quality of equilibria under prominent allocation rules [Christodoulou et al., 2015], understanding the tradeoffs between different fairness and strategic properties as well as devising rules with better strategic properties. Apart from strategic aspects in fair allocation, another promising direction is to minimally modify allocation settings (such as by adding or deleting items) so as allow for fair allocations [Aziz et al., 2016f].

2.7 Matching and Coalition Formation with Uncertain Preferences

Matching markets constitute a versatile formal model for matching agents to other agents as well as agents to resources. Much of the work on algorithmic and strategic aspects of matching markets assume that the preferences of the agents are deterministic [Manlove, 2013; Roth and Sotomayor, 1990]. Dealing with uncertainty is a central concern in AI and uncertainty could arise because of limited communication or information. Therefore, it will be interesting to explore resource allocation and matching with uncertain preferences. Similar work has already been done in voting (see e.g., [Hazon et al., 2012]). The uncertainty in the preferences can be captured and represented in a number of natural ways. In these settings with uncertainty, it will be interesting to identify outcomes that are most likely to be efficient, stable or fair. Uncertain preferences are also relatively less explored in other coalition and team formation models such as hedonic games [Aziz and Savani, 2016].

3 Conclusions

Computational social choice is an exciting field with a number of fundamental problems than cut across various disciplines. In this paper, I have highlighted some developments and trends in the field. For the interested reader, I would recommend recents books by Brandt et al. [2016] and Rothe [2015] that provide a useful window into the field.

Acknowledgments

Data61 is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. The author thanks Enrico Gerding, J´erˆome Lang, and Toby Walsh for comments. The author thanks his colleagues and coauthors for collaboration and discussions on various research projects.

Haris Aziz. 2016. Computational Social Choice: Some Current and New Directions. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 4054–4056. https://ijcai.org/proceedings/2016/599

@inproceedings{ijcai2016p599,
  title     = {Computational Social Choice: Some Current and New Directions},
  author    = {Aziz, Haris},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {4054--4056},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/599},
}

TY  - CPAPER
TI  - Computational Social Choice: Some Current and New Directions
AU  - Aziz, Haris
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 4054
EP  - 4056
UR  - https://ijcai.org/proceedings/2016/599
ER  -

[1] [Alon et al., 2011] N. Alon, F. Fischer, A. D. Procaccia, and M. Tennenholtz. Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th TARK Conference, pages 101-110, 2011.

[2] [Amanatidis et al., 2015] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. In Proceedings of the 35th ICALP Conference, pages 39-51, 2015.

[3] [Aziz and Mackenzie, 2016a] H. Aziz and S. Mackenzie. A dis- crete and bounded envy-free cake cutting protocol for any number of agents. 2016.

[4] [Aziz and Mackenzie, 2016b] H. Aziz and S. Mackenzie. A dis- crete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th STOC. ACM Press, 2016.

[5] [Aziz and Savani, 2016] H. Aziz and R. Savani. Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Pro- caccia, editors, Handbook of Computational Social Choice, chapter 15. Cambridge University Press, 2016.

[6] [Aziz and Stursberg, 2014] H. Aziz and P. Stursberg. A gener- alization of probabilistic serial to randomized social choice. In Proceedings of the 28th AAAI Conference, pages 559-565. AAAI Press, 2014.

[7] [Aziz and Ye, 2014] H. Aziz and C. Ye. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In Proceedings of the 10th WINE, pages 1-14, 2014.

[8] [Aziz et al., 2013] H. Aziz, F. Brandt, and M. Brill. On the trade- off between economic efficiency and strategyproofness in ran- domized social choice. In Proceedings of the 12th AAMAS Conference, pages 455-462. IFAAMAS, 2013.

[9] [Aziz et al., 2015a] H. Aziz, Simina Brânzei, S. Frederiksen, and A. Filos-Ratsikas. The adjusted winner procedure: Characteri- zations and equilibria. In Proceedings of the 24th IJCAI, pages 454-460, 2015. IJCAI

[10] [Aziz et al., 2015b] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. In Proceedings of the 29th AAAI Conference, pages 784-790, 2015.

[11] [Aziz et al., 2015c] H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh. Computational as- pects of multi-winner approval voting. In Proceedings of the 14th AAMAS Conference, pages 107-115. IFAAMAS, 2015.

[12] [Aziz et al., 2015d] H. Aziz, S. Gaspers, S. Mackenzie, N. Mat- tei, N. Narodytska, and T. Walsh. Manipulating the probabilis- tic serial rule. In Proceedings of the 14th AAMAS Conference, pages 1451-1459, 2015.

[13] [Aziz et al., 2016a] H. Aziz, S. Bouveret, J. Lang, and S. Mackenzie. Complexity of manipulating sequential allocation. 2016.

[14] [Aziz et al., 2016b] H. Aziz, P. Goldberg, and T. Walsh. Equi- libria in sequential allocation. 2016.

[15] [Aziz et al., 2016c] H. Aziz, J. Lang, and J. Monnot. Computing Pareto Optimal Committees. In Proceedings of the 25th IJCAI, 2016. IJCAI

[16] [Aziz et al., 2016d] H. Aziz, O. Lev, N. Mattei, J. S. Rosenchein, and T. Walsh. Strategyproof peer selection: Mechanisms, anal- yses, and experiments. In Proceedings of the 30th AAAI Con- ference, 2016.

[17] [Aziz et al., 2016e] H. Aziz, G. Rauchecker, G. Schryen, and Toby Walsh. Approximation algorithms for max-min share allocations of indivisible chores and goods. 2016.

[18] [Aziz et al., 2016f] H. Aziz, I. Schlotter, and T. Walsh. Control of fair division. In Proceedings of the 25th IJCAI, 2016.

[19] [Aziz, 2013] H. Aziz. Maximal Recursive Rule: A New Social Decision Scheme. In Proceedings of the 23nd IJCAI, pages 34-40. AAAI Press, 2013. IJCAI

[20] [Bouveret and Lang, 2011] S. Bouveret and J. Lang. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd IJCAI, pages 73-78. AAAI Press, 2011. IJCAI

[21] [Bouveret et al., 2016] S. Bouveret, Y. Chevaleyre, and N. Maudet. Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12. Cambridge University Press, 2016.

[22] [Brams and Taylor, 1996] S. J. Brams and A. D. Taylor. Fair Di- vision: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.

[23] [Brandl et al., 2015] F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Technical report, http://arxiv.org/abs/1503.00694, 2015. Link

[24] [Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.

[25] [Branzei and Miltersen, 2013] S. Branzei and P. B. Miltersen. Equilibrium analysis in cake cutting. In Proceedings of the 12th AAMAS Conference, pages 327-334. IFAAMAS, 2013.

[26] [Branzei et al., 2014] S. Branzei, Y. Chen, X. Deng, A. Filos- Ratsikas, S. K. S. Frederiksen, and J. Zhang. The fisher mar- ket game: Equilibrium and welfare. In Proceedings of the 28th AAAI Conference, pages 587-593. AAAI Press, 2014.

[27] [Brânzei et al., 2016] S. Brânzei, I. Caragiannis, D. Kurokawa, and A. D. Procaccia. An algorithmic framework for strategic fair division. In Proceedings of the 30th AAAI Conference. AAAI Press, 2016.

[28] [Chen et al., 2013] Y. Chen, J. K. Lai, D. C. Parkes, and A. D. Procaccia. Truth, justice, and cake cutting. Games and Eco- nomic Behavior, 77(1):284-297, 2013.

[29] [Chevaleyre et al., 2007] Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A short introduction to computational social choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOF- SEM), volume 4362 of LNCS, pages 51-69. Springer, 2007.

[30] [Christodoulou et al., 2015] G. Christodoulou, A. Filos- Ratsikas, S. K. S. Frederiksen, P. W. Goldberg, J. Zhang, and J. Zhang. Welfare ratios in one-sided matching mechanisms. Technical report, arXiv.org, 2015.

[31] [Conitzer, 2010] V. Conitzer. Making decisions based on the preferences of multiple agents. Communications of the ACM, 53(3):84-94, 2010.

[32] [de Clippel et al., 2008] G. de Clippel, H. Moulin, and N. Tide- man. Impartial division of a dollar. Journal of Economic The- ory, 139:176-191, 2008.

[33] [Edmonds and Pruhs, 2006] J. Edmonds and K. Pruhs. Cake cut- ting really is not a piece of cake. In Proceedings of the 17th SODA, pages 271-278, 2006.

[34] [Elkind et al., 2014] E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of multiwinner voting rules. In Proceed- ings of the 13th AAMAS Conference, pages 53-60. IFAAMAS, 2014.

[35] [Hazon et al., 2012] N. Hazon, Y. Aumann, S. Kraus, and M. Wooldridge. On the evaluation of election outcomes un- der uncertainty. Artificial Intelligence, 189:1-18, 2012.

[36] [Holzman and Moulin, 2013] R. Holzman and H. Moulin. Im- partial nominations for a prize. Econometrica, 81(1):173-196, 2013.

[37] [Kalinowski et al., 2013] T. Kalinowski, N. Narodytska, T. Walsh, and L. Xia. Strategic behavior when allocating indivisible goods sequentially. In Proceedings of the 27th AAAI Conference, pages 452-458. AAAI Press, 2013.

[38] [Kilgour, 2010] D. M. Kilgour. Approval balloting for multi- winner elections. In Handbook on Approval Voting, chapter 6. Springer, 2010.

[39] [Kurokawa et al., 2015] D. Kurokawa, O. Lev, J. Morgenstern, and A. D. Procaccia. Impartial peer review. In Proceedings of the 23rd IJCAI, pages 582-588. AAAI Press, 2015.

[40] [Lang and Xia, 2016] J. Lang and L. Xia. Voting in combinato- rial domains. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational So- cial Choice, chapter 9. Cambridge University Press, 2016.

[41] [Lindner and Rothe, 2015] C. Lindner and J. Rothe. Cake- cutting: Fair division of divisible goods. In J. Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Divi- sion, chapter 7. Springer-Verlag, 2015.

[42] [Manlove, 2013] D. Manlove. Algorithmics of Matching Under Preferences. World Scientific Publishing Company, 2013.

[43] [Nguyen et al., 2015] N-T. Nguyen, D. Baumeister, and J. Rothe. Strategy-proofness of scoring allocation correspon- dences for indivisible goods. In Proceedings of the 23rd IJCAI, pages 1127-1133. AAAI Press, 2015. IJCAI

[44] [Peterson and Su, 1998] E. Peterson and F. E. Su. Exact proce- dures for envy-free chore division. 1998.

[45] [Procaccia and Wang, 2014] A. D. Procaccia and J. Wang. Fair enough: Guaranteeing approximate maximin shares. In Pro- ceedings of the 15th ACM Conference on E-Commerce, pages 675-692. ACM Press, 2014.

[46] [Procaccia, 2009] A. D. Procaccia. Thou shalt covet thy neigh- bor's cake. In Proceedings of the 21st IJCAI, pages 239-244. AAAI Press, 2009. IJCAI

[47] [Procaccia, 2010] A. Procaccia. Can approximation circumvent Gibbard-Satterthwaite? In Proceedings of the 24th AAAI Con- ference, pages 836-841. AAAI Press, 2010.

[48] [Procaccia, 2016] A. D. Procaccia. Cake cutting algorithms. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procac- cia, editors, Handbook of Computational Social Choice, chap- ter 13. Cambridge University Press, 2016.

[49] [Robertson and Webb, 1998] J. M. Robertson and W. A. Webb. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters, 1998.

[50] [Roth and Sotomayor, 1990] A. E. Roth and M. A. O. So- tomayor. Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press, 1990.

[51] [Rothe, 2015] J. Rothe, editor. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational So- cial Choice, and Fair Division. Springer, 2015.

[52] [Skowron et al., 2016] P. Skowron, P. Faliszewski, and A. Slinko. Axiomatic characterization of committee scoring rules. Technical Report 1604.01529, arXiv.org, 2016.