Voting in combinatorial domains

Motivations and Classes of Problems This chapter addresses preference aggregation and voting on domains which are the Cartesian product (or sometimes, a subset of the Cartesian product) of finite domain values, each corresponding to an issue, a variable, or an attribute. As seen in other chapters of this handbook, voting rules map a profile (usually, a collection of rankings, see Chapter 1) to an alternative or a set of alternatives. A key question has to do with the structure of the set of alternatives. Sometimes, this set has a simple structure and a small cardinality (e.g., in a presidential election). But in many contexts, it has a complex combinatorial structure. We give here three typical examples: • Multiple referenda. On the day of 2012 U.S. presidential election, voters in California had to decide whether to adopt each of 11 propositions. Five referenda were categorized as budget/tax issues. Specifically, two of them (Propositions 30 and 38) both aimed to raise taxes for education, with different details on the type and rate of the tax. Similarly, in Florida voters had to vote on 11 propositions, eight of which were categorized as budget/tax issues. • Group configuration or group planning. A set of agents sometimes has to make a common decision about a complex object, such as a common menu (composed for instance of a first course, a main course, a dessert and a wine, with a few possible values for each), or a common plan (for instance, a group of friends have to travel together to a sequence of possible locations, given some constraints on the possible sequences). • Committee elections and more generally multiwinner elections. A set of agents has to choose a group of delegates or representatives of some given size, from a larger set of candidates. As another example, a group of friends wants to choose a set of DVDs to purchase collectively, from a larger set, subject to some budget constraints. In these three examples, the set of alternatives has a combinatorial structure: it is a Cartesian product A = D 1 × … × Dp, where for each i, Di is a finite value domain for a variable Xi, or, in the third example, a subset of a Cartesian product (see further). For the menu example, we may have for instance D 1 = {soup, salad, quiche}, D 2 = {beef, salmon, tofu}, and so on.