example, various results in economics
prove the existence of an equilibrium,
but do not provide an efficient method
for reaching such an equilibrium.
ILLus Tr ATIon by John h ErsEy
In this article, I give a (
necessarily incomplete) survey of topics that
computer scientists are working on in
this domain. I discuss voting and rank
aggregation, task and resource allocation, kidney exchanges, auctions and
exchanges, charitable giving, and prediction markets. I examine the problem
of agents acting in their own best interest, which cuts across most of these applications. I also intersperse a few opinions and predictions about where future
research should and will go.
Here, parties whose preferences we
are interested in are not always human;
they can also be, among other things,
robots, software agents, or firms.a As
is done in both computer science and
economics, I use the term “agent” to
refer to any one of the parties.
Settings Without Payments
I will discuss a variety of settings, so it is
helpful to categorize them somewhat.
An important aspect is whether the set-
a In artificial intelligence, there is the study of
multiagent systems, where agents—for exam-
ple, robots—often need a protocol for coordi-
nating on (say) a joint plan.
ting allows agents to make payments
to each other (in some currency). For
example, in a voting setting, we typically do not imagine money changing
hands among voters (unethical behavior aside). On the other hand, in an auction, we naturally expect the winning
bidder to pay for her winnings. First,
I discuss various settings in which no
money changes hands.
Voting and rank aggregation. A natural and very general approach for deciding among multiple alternatives is to
vote over them. In the general theory of
voting, agents can do more than vote for
a single alternative: usually, they get to
rank all the alternatives. For example, if
