ternatives undergoes a combinatorial explosion. Ideally, the agents would have an expressive language in which they can naturally and concisely represent their preferences. One good language for representing such preferences is that of CP-nets4 (which bear some resemblance to Bayesian networks). A CP-net allows a voter to specify that her preferences for one issue depend on the decisions on some other issues—for example, “If we are eating early, I prefer Brazilian; otherwise, I prefer Chinese.” Given a language, we must design new voting rules that can operate on preferences represented in this language, as well as algorithms for running these rules.

While such combinatorial voting20, 38 is in its infancy, it is easy to see its potential value by considering how ad hoc the methods are that we use today for these types of situations. For example, members of Congress must vote on bills that address many different issues, and would often prefer to express preferences on individual issues. Unfortunately, voting on the individual issues separately can easily lead to undesirable results, because there is no guarantee that the issues are resolved in a consistent way. For instance, in the dining example, it may happen that most agents, in general, prefer to eat at a Brazilian steakhouse; and that, in general, most agents prefer to eat late; but most agents do not want to eat at a Brazilian steakhouse late at night. If they vote on the issues separately, the result may well be a late dinner at a Brazilian steakhouse. This is why the language for expressing preferences needs to allow the agents to specify some interactions among the issues.

ILLus Tr ATIon by John h ErsEy

Allocating tasks and resources. A vot-
ing scheme allows an agent to submit
arbitrary preferences over the alter-
natives. While this generality is nice,
in many settings, it is not needed,
because we can safely make some as-
sumptions about agents’ preferences.
Let us consider again the example of
allocating chores in a household. One
alternative might be: “Alice will vac-
uum and take out the trash, and Bob
will do the dishes.” It seems safe to as-
sume that Bob will prefer this alterna-
tive to the alternative: “Alice will take
out the trash, and Bob will vacuum
and do the dishes,” since the latter al-
ternative gives Bob an additional task.
On the other hand, if we are allocating
desirable resources instead of cum-
bersome tasks, then presumably more
is preferred to less. For example, if the
agents jointly own a car, an alternative
might be: “Alice gets to use the car on
Friday, and Bob gets to use it on Satur-
day and Sunday,” which Bob presum-
ably prefers to the alternative “Alice
gets to use the car on Friday and Satur-
day, and Bob gets to use it on Sunday.”
Here, the use of the car on a particular
day is a “resource.” These assump-
tions about preferences—receiving
more tasks or fewer resources is never
tion. It is not always completely accu-
rate—Alice may dislike the alternative
where Carol never gets the car slightly
more, for example because Carol will
ask Alice to run errands for her in that
case—but it is usually assumed.

preferred—are commonly referred to as monotonicity assumptions.

Another reasonable assumption
about preferences is that an agent only
cares about which tasks or resources
are allocated to her. For example, Alice
is likely to be indifferent between “Alice
gets the car on Friday, Bob on Saturday,
and Carol on Sunday” and “Alice gets
the car on Friday, Bob on Saturday and
Sunday, and Carol never.” In economics,
the assumption that an agent, given her
own resources and tasks, does not care
about how the remaining resources and
tasks are allocated to the other agents is
known as the no-externalities assump-
instead of time with a car. Also, instead
of allocating the chores of a household
to its inhabitants, we may allocate jobs
to machines.