Making Decisions Based on the Preferences of MultipleAgentsVincent ConitzerDepartments of Computer Science and EconomicsDuke UniversityDurham, NC, [email protected] often have to reach a joint decision even thoughthey have conflicting preferences over the alternatives. Ex-amples range from the mundane—such as allocating choresamong the members of a household—to the sublime—suchas electing a government and thereby charting the coursefor a country. The joint decision can be reached by an infor-mal negotiating process or by a carefully specified protocol.Philosophers, mathematicians, political scientists, economists,and others have studied the merits of various protocols forcenturies. More recently, especially over the course of thepast decade or so, computer scientists have also becomedeeply involved in this study. The perhaps surprising ar-rival of computer scientists on this scene is due to a varietyof reasons, including the following.1. Computer networks provide a new platform for com-municating preferences. Examples include auction web-sites, where preferences are communicated in the formof bids, as well as websites that allow one to rate ev-erything from the quality of a product to the attrac-tiveness of a person.2. Within computer science itself, there are increasinglymany settings where a decision must be made basedon the conflicting preferences of multiple parties. Ex-amples include determining whose job gets to run firston a machine, whose network traffic is routed along aparticular link, or whose advertisement is shown nextto a page of search results.3. Greater computing power and better algorithms, aswell as a more computational mindset in the generalpublic, have made it possible to run computationallydemanding protocols that lead to much better out-comes. An example is an auction in which bidderscan bid on arbitrary sets of items, rather than just onindividual items (I will discuss such auctions in moredetail later in this article). Such protocols used to beconsidered theoretical niceties that could never be runPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.in practice (to the extent that they were conceived ofat all), but now they are actually practical.4. The paradigms of computer science give a different anduseful perspective on some of the classic problems ineconomics and related disciplines. For example, vari-ous results in economics prove the existence of an equi-librium, but do not provide an efficient method forreaching such an equilibrium.In this article, I give a (necessarily incomplete) surveyof topics that computer scientists are working on in thisdomain. I will discuss voting and rank aggregation, taskand resource allocation, kidney exchanges, auctions and ex-changes, charitable giving, and prediction markets; in addi-tion, I will discuss the problem of agents acting in their ownbest interest, which cuts across most of these applications. Ialso intersperse a few opinions and predictions about wherefuture research should and will go.In the below, the parties whose preferences we are inter-ested in are not always people: they can also be, amongother things, robots, software agents, or firms.1As is donein both computer science and economics, I will use the termagent to generically refer to one of the parties.1. SETTINGS WITHOUT PAYMENTSI will discuss a variety of settings, so it is helpful to cat-egorize them somewhat. An important aspect is whetherthe setting allows agents to make payments to each other(in some currency). For example, in a voting setting, wetypically do not imagine money changing hands among vot-ers (unethical behavior aside). On the other hand, in anauction, we naturally expect the winning bidder to pay forher winnings. In this section, I discuss various settings inwhich no money changes hands; I will discuss settings withpayments in the next section.1.1 Voting and rank aggregationA natural and very general approach for deciding amongmultiple alternatives is to vote over them. In the generaltheory of voting, agents can do more than vote for a singlealternative: usually, they get to rank all the alternatives.For example, if a group of people is deciding where to go fordinner together, one of them may prefer American food toBrazilian, and Brazilian to Chinese. This person’s vote canthen be expressed as A B C.1In artificial intelligence, there is the study of multiagentsystems, where agents—for example, robots—often need aprotocol for coordinating on (say) a joint plan.Given everyone’s vote, which cuisine should b e chosen?The answer is far from obvious. We need a voting rule thattakes as input a collection of votes, and as output returnsthe winning alternative. A simple rule known as the pluralityrule chooses the alternative that is ranked first the mostoften. In this case, the agents do not really need to givea full ranking: it suffices to indicate one’s most-preferredalternative, so each agent is in fact just voting for a singlealternative.Another rule is the anti-plurality rule, which chooses thealternative that is ranked last the least often. Now, it sufficesfor agents to report their last-ranked alternative—they arevoting against an alternative. Which of these two rules isbetter? It is hard to say. The former tries to maximize thenumber of agents that are happy about the choice; the lattertries to minimize the number that are unhappy. Anotherrule, known as the Borda rule, tries to strike a balance: whenthere are three alternatives, it will give two p oints to analternative whenever it is ranked first, one whenever it isranked second, and zero whenever it is ranked last. Manyother rules, most of them not relying on such a points-basedscheme, have been proposed; social choice theorists analyzethe desirable and undesirable properties of these rules.Rather than just choosing a winning alternative, most ofthese rules can also be used to find an aggregate ranking ofall the alternatives. For example, we can sort the alterna-tives by their Borda score, thereby deciding not only on the“best” alternative but
View Full Document
Unlocking...