Making Markets and Democracy Work: A Story of Incentives and Computing

1 Introduction

Collective choice settings are the heart of society. Citizens voting determines a president, producers and consumers bid­ ding determines a set of trades, and surfers hitting links in web browsers determines a bandwidth allocation. A key dif­ ficulty in collective choice is that the agents generally have conflicting preferences over the outcomes (e.g., presidents, resource allocations, or task allocations). Work in mechanism design, a subfield of game theory, provides a basis for engi­ neering the incentives into the interaction mechanism (e.g., rules of an election or auction) so that a desirable-according to some objective-outcome is chosen even though every party acts based on self-interest.

However, there are a host of computer science issues not traditionally addressed in game theory that have to be ad­ dressed in order to make mechanisms work in the real world. Those computing, communication, and privacy issues have to be handled while simultaneously handling the economic incentive issues. This is a particularly exciting research area because those issues are intimately intertwined, as I hope to convey. For example, the fact that agents have limited com­ putational capabilities can ruin the incentive properties of es­ tablished auction mechanisms, and give rise to new game­ theoretic issues. On the positive side, computational com­ plexity can be used as a barrier to insincere strategic behavior in settings where economic incentive engineering is known to fall short.

Novel computational approaches and algorithms can also enable new economic institutions. For example, sophisti­ cated market clearing technology with specialized search al­ gorithms enables a new form of interaction that I call ex­ pressive competition: empowering market participants with potent expressiveness akin to human-to-human negotiation while at the same time harnessing the forces of competition, the global scale of the Internet, and the speed and accuracy of algorithmic market clearing with all relevant information in hand. Furthermore, even the mechanism itself (such as the rules of an auction) can be designed automatically-in many cases yielding better mechanisms than the best known to date.

This writeup begins from distributed peer-to-peer negotia­ tion (Section 2), and transitions to markets that have have a mediator such as an auction server (Section 3). In this context I will lay out the vision and technology for expressive com­ petition. Section 4 discusses multiagent preference elicitation in auctions and voting settings: can the mediator elicit the information needed to determine the optimal outcome with­ out requiring the agents to determine and reveal their prefer­ ences about impertinent aspects of the problem? The issue of how carefully computationally constrained agents should de­ termine their preferences is addressed in Section 5. It turns out that the computational constraint undermines desirable incentive properties in established auction mechanisms, and gives rise to new game-theoretic issues, in particular a phe­ nomenon which I call strategic computing: using one's lim­ ited computing to approximate others' preferences at the cost of approximating one's own. The reverse is shown in Sec­ tion 6: computational complexity can be used as a barrier to undesirable strategic behavior. I illustrate this in voting.

Section 7 discusses a new idea which I call automated mechanism design: designing the interaction mechanism computationally for the specific setting at hand. Section 8 shows how mechanism design can not only be used to lead to a desirable outcome in a multiagent system, but also to deter­ mine a way to execute the outcome. In particular, the writeup looks at safe exchange mechanisms for carrying out trades among anonymous parties on the Internet. Finally, conclu­ sions, perspective, and promising avenues for future research are presented.

2 A first tack: Peer-to-peer negotiation

Work on automated negotiation began in peer-to-peer con­ texts where the negotiating agents (humans or software) make deals with each other. A key insight for analyzing such ne­ gotiation is to think about the negotiation process as an AI search algorithm where the outcome is characterized by deci­ sion variables to which the negotiation assigns values [Sathi and Fox, 1989; Sandholm, 1991; Conry et al., 1991; Sycara et al., 1991; Sandholm, 1993]. For example, in task allocation negotiation there is a decision variable for each task, and the variable's value is the name of the agent that the task is allo­ cated to. There are several high-level families of peer-to-peer negotiation search algorithms. For example, the agents might negotiate one variable at a time, committing to the assign­ ment before moving on to the next variable. This is analogous to constructive search in AI. As another example, the search might start from a status quo assignment of values to vari­ ables (for example, the initial assignment of tasks to agents before any negotiation begins), and then the agents might iter­ atively change the variable assignments whenever the agents relevant to the variables in question agree [Sandholm, 1991; 1993]. (For example, the current holder of a task can real­ locate the task to another agent if they both agree.) This is analogous to iterative refinement search in AI.

2.1 Contracting based on marginal cost calculations

In the original contract net framework [Smith, 1980], agents allocated tasks among themselves. However, the framework was for cooperative agents only: an agent was as­ sumed to take on a task whenever that was feasible. For self­ interested agents, more sophisticated methods are needed. A key idea toward this direction was contracting based on marginal costs [Sandholm, 1991; 1993; 1996]. When a con­ tract is proposed to an agent, the agent evaluates the cost of taking on the contract obligations (e.g., tasks) by solving its local planning problem once with the new obligations and once without. The difference in the costs of those two lo­ cal plans is the marginal cost of the obligations. An agent using this scheme accepts the proposal if the proposer pays it more than its marginal cost. Similarly, when proposing a contract, an agent computes its marginal value of unloading some obligations, and pays another agent up to that amount for the other agent to take on those obligations. A desirable engineering facet of this framework is that it separates the domain specific marginal cost calculator (planner) from the agent's domain independent negotiation module.

One practical consideration is that in many settings the lo­ cal planning problems are intractable, so the marginal costs have to be approximated. For example, in the TRACONET system for automatically reallocating trucking tasks among dispatch centers, the local planning problems were N ?­ complete vehicle routing problems with several side con­ straints. The TRACONET work included heuristic meth­ ods for deciding how carefully to approximate marginal costs [Sandholm, 1991; 1993; 1996; Sandholm and Lesser, 1995b]. This issue is revisited more formally in Section 5.

2.2 Iterative reallocation and combinatorial contracts

Another early idea in automated negotiation was to have the agents iteratively reallocate the items (tasks) [Sandholm, 1991; 1993]. An agent that had accepted a task could later contract out that task to some other agent, who in tum could contract it out, and so on. This proved to be highly effective in the TRACONET system. Marginal cost based contract­ ing guarantees that every contract improves the utilities of the contract parties. Therefore, every agent's utility increases monotonically in the distributed negotiation that keeps real­ locating tasks. It follows that the agents can enter and exit the negotiation dynamically without risking a loss.

The marginal cost based iterative reallocation negotiation can be viewed as a distributed hill-climbing search where the height on the hill is the sum of the agents' utilities [Sand­ holm, 1998]. Under this interpretation it is easy to show that contracting one item (task) at a time against a payment (aka. original (0) contract) does not generally lead to an optimal outcome: the search gets stuck in a local optimum. This can be addressed by combinatorial contracts that enlarge the neighborhood in the hill-climbing search: contracts where multiple items are exchanged for a payment (cluster (C) con­ tracts), 1 where items from one agent are exchanged against items from another-potentially with a side payment-(swap (S) contracts), and where the contract can involve more than two agents (multiagent ( M) contracts). If all of these con­ tract types are allowed in a single contract (OCSM contract), then agents that contract using the marginal cost principle will reach a global optimum (that is, a task allocation that maxi­ mizes social welfare, which is simply the sum of the agents' utilities) in a finite number of contracts-and no subset of those contract types suffices [Sandholm, I 998; 2000a]. Thus the agents can myopically make contracts in any order. From a hill-climbing search perspective, the neighborhood is large enough that from any allocation of tasks, a profitable con­ tract exists that takes the agents to any other task allocation. Therein also lies a key weakness. Especially in a distributed setting, it can be difficult to find a combinatorial contract (in­ volving multiple items and multiple agents) that will improve the current solution. Also, the sequence of hill-climbing con­ tracts can be exponentially long in the worst case. There­ fore, in practice, the optimal outcome is not found. Nev­ ertheless, the combinatorial contracts help reach better out­ comes than 0-contracts [Andersson and Sandholm, 1999; 2000].

1 The TRACONET system was the first to use combinatorial bid­ ding to allocate trucking tasks-an approach widely used commer­ cially for procuring trucking services today.

Another approach for avoiding local optima in search is backtracking. It turns out that a backtracking instrument can be constructed for negotiation as well, as the next section shows. It can easily be applied to the reallocation negotiation discussed in this section, instead-or in conjunction with­ the combinatorial contract types [Andersson and Sandholm, 1998]. With that instrument, a backtracking option can be added to each (or only some) of the contracts. However, the backtracking instrument applies to basically any negotiation setting, and I will discuss it in that broader context.

2.3 Leveled commitment contracts to enable backtracking

Negotiating agents usually have to act under uncertainty, yielding behavior that is suboptimal in hindsight. For the purposes of the ensuing discussion, I divide the uncertainties faced by agents in negotiation into two high-level classes:

• Domain uncertainty stems from an agent not knowing how its local situation will change. Such changes affect the value (cost) and feasibility of the deals that the agent has made. For instance, which of an agent's resources will break (or become available) that affect the agent's costs-or even feasibility-of handling different combi­ nations of its tasks? 2
• Negotiation process uncertainty stems from an agent not knowing what future negotiation events will occur. Consider, for instance, the following uncertainties that an agent may face. Which of my pending bids will get accepted? Which (parts) of my tasks will I be able to subcontract out in the future, and at what prices? What tasks will I be offered and at what prices? The answers to all of these questions affect the cost of taking on (or letting go of) other obligation due to complementarity

2 An additional source of uncertainty arises through the other agents' non-negotiation actions. Specifically, how will the others act regarding aspects that have not been contractually bound (this is pertinent in domains where those actions can affect the agent's utility by hindering or helping the agent)?

and substitutability: the cost of taking on an obligation usually depends on what other obligations one has.

In automated negotiation systems for self-interested agents, contracts have traditionally been binding. They do not allow agents to accommodate future events that are uncertain due to domain uncertainty or negotiation process uncertainty. Both of these classes of uncertainty may also include subjec­ tive uncertainty due to an agent's limited capability to pro­ cess information-for example computationally limited ca­ pability to do mental lookahead in a (sequential) negotiation process. If, in a negotiation, an agent has made a commitment that turns out unprofitable in hindsight, the agent would like to backtrack that commitment. For example, more lucrative offers can arrive later, or handling a task can tum out more costly than anticipated.

Backtracking in negotiation search can be enabled using an instrument called a leveled commitment contract, where each contract party can unilaterally decommit from the contract by paying a predetermined penalty [Sandholm and Lesser, 1995b; 2001; 2002]. This mitigates both domain uncertainty and negotiation process uncertainty, whether objective or sub­ jective.3 A concern with this is strategic breach: a rational self-interested agent is reluctant to decomrnit because there is a chance that the other party will decommit, in which case the former agent gets freed from the contract, does not have to pay a penalty, and collects a penalty from the breacher. (This is an example issue that arises due to self-interest, and renders inapplicable traditional backtracking techniques like distributed constraint satisfaction (e.g., [Yokoo, 2000]) which assume that all parties execute the distributed algorithm faith­ fully.) Given the contract price, decomrnitting penalties, and the agents' prior distributions of the value of the contract, one can conduct a Nash equilibrium analysis of the decommitting game (in other words, one can find decommitting strategies for the agents such that each agent's strategy is a best re­ sponse to the other's). Each agent's best-response strategy is defined by a threshold on the value of the contract for that agent. If the value is below that threshold, the agent will decommit. It turns out that strategic breach indeed occurs: an agent does not decomrnit when the contract's value drops below the point where paying the decommitting penalty is worth it; rather it needs to drop to a level further down before the agent decommits. However, despite such strategic breach, leveled commitment contracts improve the expected payoffs of all contract parties compared to any contract where back­ tracking is not an option [Sandholm and Lesser, 200 I]. It follows that leveled commitment also enables contracts that would not be mutually beneficial without the backtracking option.

3 A practical type of subjective uncertainty stems from the fact that computing the value (cost) of taking on the obligations of a con­ tract is often intractable-as discussed-so the agents have to resort to approximate marginal value calculation. Leveled commitment al­ lows an agent to bid based on a rough value calculation. If the agent wins the bid, the agent can invest a more thorough value calculation. If the contract no longer looks beneficial in light of this more refined calculation, the agent can decommit. The fact that only the winning bidders carry out a refined calculation can save computation system wide. Also, the negotiations can be carried out faster because agents can bid based on less computation.

Leveled commitment can be used to increase the speed of ne­ gotiation in an additional way as well. An agent can make (low­ commitment) offers to multiple recipients although those offers are mutually exclusive from the agent's perspective. In case more than one recipient accepts, the agent can backtrack from all but one. This allows the agent to address the recipients in parallel instead of ad­ dressing them one at a time and blocking to wait for an answer be­ fore addressing the next.

Leveled commitment contracts differ based on whether agents have to declare their decommitting decisions sequen­ tially or simultaneously, and whether or not agents have to pay the penalties if both decommit. These mechanisms lead to different Nash equilibria. It is easy to see that in the se­ quential mechanisms the second mover never decommits if the first mover does; if the first mover does not, then the sec­ ond mover will decommit if the value of the contract to him turns out to be so low that it is worth paying the penalty. In the simultaneous game where both pay the penalties if both decommit, as an agent's penalty approaches zero, the agent becomes truthful. On the contrary, in the simultaneous game where neither pays if both decommit, as an agent's penalty approaches zero, the agent does not become truthful but the other contract party does! Despite the fact that the equilibria of these mechanisms differ, surprisingly, among risk-neutral agents each of the mechanisms leads to the same expected payoffs to the agents if the contract price and decommitting penalties are optimized for each mechanism separately [Sand­ holm and Zhou, 2002]. For agents with risk attitudes, the dif­ ferent mechanisms yield a different sum of utilities, and the relative ranking of the mechanisms varies based on the exact utility functions.

Computing plays a key role in operationalizing the idea of leveled commitment. Given the contract price, the de­ committing penalties, and piecewise linear prior distributions on the contract's value for the different contract parties, the Nash equilibrium decommitting thresholds for each mecha­ nism can be computed in polynomial time in the number of pieces [Sandholm et al., 1999]. Furthermore, given the piece­ wise linear priors, it turns out that the contract price and de­ committing penalties that maximize the sum of the contract parties' payoffs can be determined in polynomial time in the number of pieces for each of the leveled commitment mech­ anisms. The reader is invited to try a leveled commitment contract optimizer prototype, eCommitter, on the web [Sand­ holm, 2002b]. Leveled commitment contracts and the algo­ rithms also generalize to deals that involve more than two agents.

The theoretical results discussed above pertain to a single contract. In negotiation there is usually a web of contracts, and an agent's breach can cause the victim of the breach to want to breach on another contract, and so on. There is gen­ erally a tradeoff between allowing enough backtracking to sufficiently explore the space for a good outcome and not wasting time in deep cascades of decommits-or even infi­ nite loops of decommitting and recommitting. That trade­ off can be controlled by carefully increasing the decommit­ ting penalties over time [Andersson and Sandholm, 2001 ; 1998].

3 A paradigm shift to mediated clearing

The Achilles heel of peer-to-peer negotiation is negotiation process uncertainty. Agents make commitments without vis­ ibility into what is going to occur later on in the negotia­ tion process (and what has already transpired in negotiation among other agents). Leveled commitment contracts reduce, but do not eliminate, the negative impact of such uncertainty. This uncertainty also introduces strategic problems. For ex­ ample, if an agent expects a better deal in the future (which it cannot profitably handle if it takes on the contract currently offered to it), the agent may want to pass on the current offer. So, the agent is not best off acting myopically-not even in marginal cost based contracting or leveled commitment con­ tracts as the basic analysis discussed in the previous section assumes. Rather, a rational agent would want to look ahead into the future, which in turn requires speculating what the other agents will do. Acting rationally equates to solving for the agent's best strategy in a game tree whose depth is at least the number of contracts that can occur in the system. Such lookahead is intractable in practice (although leveled com­ mitment contracts have been studied in this context with a small number of tasks to allocate [Andersson and Sandholm, 2001]). Even if an agent can conduct such lookahead, un­ certainty about the other agents' private information (their preferences, tasks, resources, etc.) causes the agent to make commitments that are suboptimal-in light of later negotia­ tion events-for the agent and for social welfare [Andersson and Sandholm, 2001]. As discussed, there is an additional problem in peer-to-peer negotiation: it can be prohibitively complex to find a contract that improves the current solution, especially when using combinatorial contracts involving mul­ tiple items and multiple agents.

In light of these problems, it is clear that in many settings, economically better solutions can be obtained by collecting the agents' information to a mediated clearing point such as an auction server, and conducting a search (aka. a clearing) there to determine the outcome, rather than conducting a dis­ tributed "negotiation" search. The reason is that the mediated clearing has all the information in hand while the distributed search makes decisions based on incomplete views. Further­ more, the mediated clearing can be programmed to execute the search algorithm faithfully while in the distributed search the agents will act based on self-interest-potentially caus­ ing the search not to find an optimal outcome. 4 The mediated approach can be structured so that it motivates the agents to reveal their information truthfully; this will be discussed in Section 3.6. In short, the mediated approach removes the negotiation process uncertainty. (The domain uncertainty re­ mains, and the leveled commitment methodology can be used to mitigate it.) In most electronic commerce applications the mediated approach also saves communication because there is many-to-one communication instead of many-to-many, and because each issue needs to be communicated only once­ rather than repeatedly as is commonly the case in peer-to-peer negotiation.

4 Jn the distributed search it can even be difficult to identify when an optimal solution has been found, and special termination detection algorithms are usually needed [Sandholm, 1993; 1996; Walsh and Wellman, 2000].

The shift to mediated clearing introduces the need for tech­ nology for conducting the clearing. The following subsec­ tions describe the mediated approach in more detail, different forms of the clearing problem, and algorithms for solving it.

3.1 A canonical example: Combinatorial auction

Consider a setting where multiple distinguishable items (e.g. , a right shoe and a left shoe) are auctioned sequentially, and a bidder's valuation for a bundle of items is not the sum of those items' valuations. Most multi-item allocation settings exhibit such nonadditivity, for example, strategic sourcing, alloca­ tion of trucking lanes, electricity markets, as well as many task and resource allocation problems in computer science. To bid appropriately for the item that is auctioned first (right shoe), a bidder needs to guess which other items he will win in the later auction(s) . This requires lookahead in a game tree, which is intractable if numerous items are auctioned. Even with exact lookahead, the bidder generally does not know de­ terministically what will transpire in the auction-due to in­ complete information about the other bidders' valuations of the items. For example, some other bidder could be a col­ lector of left shoes who also likes right shoes somewhat, but less than our bidder. This can cause our bidder to win just the right shoe that has no value to him, that is, a bundle of items that is undesirable to the bidder given the prices. While un­ desirable to our bidder, the outcome (that is, allocation of the items to the agents) also does not maximize social welfare. It would have been better to give both shoes to the other bidder. In general, the outcome might not maximize social welfare even if each bidder wins a bundle that is worth more than the bidder had to pay for it: an even better allocation of the items to the bidders might exist.

These problems, that are due to the negotiation process un­ certainty of a sequential auction, can be overcome via a com­ binatorial auction where bids can be submitted on combina­ tions (bundles) of items [Rassenti et al., 1982]. For exam­ ple, a bidder can say: "I am willing to pay up to $100 for items 2,3, and 7 together". This removes the need for looka­ head and for speculation about others because the bidder can evaluate the value of item 2 in the known context where the bidder hypothetically receives items 3 and 7 as well. The bid­ der cannot get stuck with item 2 in an unprofitable way. This removal of the so called exposure risk makes bidding easier. It also causes the bidders to bid more aggressively because they do not have to factor in the potential downside of getting stuck with undesirable bundles; the aggressive bidding makes the seller better off. Finally, social welfare is maximized be­ cause the goods are allocated to the bidders that value them the most.

3.2 Substitutability and XOR-constraints

The model discussed above, and most other work on com­ binatorial auctions (see for example [Rothkopf et al., 1998; DeMartini et al., 1999]), are based on a setting where each bidder can bid on bundles of items, and any number of a bid­ der's bids can be accepted (except, of course, that bids on overlapping bundles cannot be accepted). This works well when bids are superadditive: bi(S US') ~ bi(S) + b;(S'), where b; is the bid of agent i, and S and S' are disjoint sets of items. In other words, the current techniques focus on cap­ turing synergies (complementarities) among items. However, in many auctions in practice, some items can at least partially substitute for others (e.g., when bidding for an umbrella and a raincoat) . For instance when bidding for landing slots for a given airplane flight, the bidder is willing to take any one of a host of slots, but getting more than one adds only slight value because extra slots beyond the first one obtained only serve as backup. Substitutability causes bids to be subaddi­ tive: b;(S US') < b;(S) + b;(S'). This can lead to problems. For example, what happens if agent i bids b; ( { 1}) = $5, b;( {2}) = $4, and bi( {1 , 2}) = $7, and there are no other bidders? The auctioneer could allocate items I and 2 to agent I separately, charging $5 + $4 = $9 instead of $7.

This problem can be removed by using a bidding language where the bidders can submit X OR-bids, that is, bids on bun­ dles such that only one of the bids can get accepted [Sand­ holm, 2002a]. This allows the bidders to express general preferences with both complementarity and substitutability. In other words, the bidder can express any value function v : 2m ---> lR, where m is the number of items for sale in the auction. For example, a bidder in a 4-item auction may submit the following input to the auctioneer:

While XOR-bids are fully expressive, representing one's preferences in that language often leads to large numbers of bids that are all combined with XOR. To maintain full ex­ pressiveness, but at the same time to make the representa­ tion more concise, one can use a bidding language called OR-of-XORs [Sandholm, 2002b; 2000b] . In this language, a set of bids can be combined with XOR, forming an X OR­ disjunct. MultipleXOR-disjuncts can then be combined with non-exclusive ORs to represent independence (much like a lack of an edge represents independence in a Bayes net). For example, a bidder who wants to submit the same offer as in the example above, can do so by submitting the following more concise input to the auctioneer:

[({1}, $4)] OR [( {2} , $4)] OR [({3},$2) XOR ({4},$2) XOR ({3,4},$3)]

The XOR-bidding language is a special case of the OR­ of-XORs language. Therefore, the shortest way to repre­ sent any particular value function in the OR-of-XORs lan­ guage is never longer than in the simple XOR-bidding lan­ guage. The reader is invited to try out XOR bidding and OR-of-XORs bidding in our Internet auction server pro­ totype, eMediator (see http: I I www. cs. emu. edul­ ameml eMediator). Later other logical bidding languages were proposed, namely the XOR-of-ORs language where XORs combine OR-disjuncts, and the OR* language where XOR-constraints can be submitted between arbitrary pairs of bids [Nisan, 2000]. Recently, recursive logical bidding lan­ guages have also been proposed [Hoos and Boutilier, 2001; Boutilier, 2002].

3.3 Expressive competition beyond combinatorial auctions

One can view combinatorial auctions as an extremely special case of a broader approach that I call expressive competition. The vision is to empower market participants with potent ex­ pressiveness akin to human-to-human negotiation while at the same time harnessing the forces of competition (rather than 1-to-1 negotiation), the global scale of Internet auctions, and the speed and accuracy of algorithmjc market clearing with all relevant information in hand.

Market types

There are three high-level market types for expressive com­ petition, each of which can involve bidding on bundles, and expressions of substitutability (for example with XOR con­ straints using the OR-of-XORs language). In a combina­ torial auction, there is one seller, and multiple buyers who bid. The clearing problem (aka. winner determination prob­ lem) is that of determining which bids win and which lose so as to maximize the sum of the winning bids' prices­ under the constraint that every item can be allocated to at most one bid. In a combinatorial reverse auction, there is one buyer with a set of items he wants to procure, and mul­ tiple sellers who bid [Sandholm, 2002b; Sandholm et al., 2002]. The clearing problem is that of determining which bids win and which lose so as to minimize the sum of the winning bids' prices-under the constraint that every item in the set gets procured. In a combinatorial exchange (aka. combinatorial double auctions) there are multiple buyers and multiple sellers [Sandholm, 2002b; Sandholm et al., 2002; Walsh et al., 2000]. A bidder can also act both as a buyer and as a seller, even in one bid. For example, one of his bids may state: "I want to buy a car, sell a boat, buy a bike, and get paid $150". There are two natural clearing objectives for exchanges [Sandholm and Suri, 2003]. In surplus maximiza­ tion, the goal is to maximize the sum of the payments col­ lected from winning bids that offer a payment, minus the sum of the payments paid to winning bids that require a payment. In liquidity maximization, the goal is to maximize the number or dollar volume of trades. In an exchange, the constraint on the clearing is that among the winning bids, supply meets de­ mand on every item (if the exchange sells an item to someone, it also has to buy it from someone).

For each of these market types, there are two variants: the single-unit variant (described above), and the multi-unit vari­ ant. In the latter, there are multiple indistinguishable units of each distinguishable item in the market [Sandholm, 2002b; Sandholm and Suri, 2003; Leyton-Brown et al., 2000b; Gonen and Lehmann, 2000; Sandholm et al., 2002]. For example in a reverse auction, a buyer may want 200,000 nuts and 100,000 bolts. A bidder's bid may state: "I offer 50,000 nuts and 20,000 bolts for $2,500".

Finally, markets differ based on whether or not extra units can be thrown away for free. This is called free disposal. Most markets have free disposal. It makes the clearing prob­ lem easier because any solution where supply equals or ex­ ceeds demand is feasible. Without free disposal, supply needs to equal demand on every item.

Side constraints on the clearing: A form of extremely concise expressiveness

Expressive bidding enables the bidders to express their strengths and to avoid the exposure problem. Bidding on bun­ dles (potentially with a language such as OR-of-XORs to en­ able substitutability to be expressed) is a simple form of ex­ pressive bidding, but representing one's preferences in such a language may require an expression of exponential length in the number of items. More concise forms of expressive­ ness can be used instead-or better, in addition. A key ap­ proach for accomplishing this is to allow bidders to express side constraints on the clearing [Sandholm and Suri, 200 I b; Kalagnanam et al., 2001] . For example in a reverse auction, a bidder could submit a number of bids (maybe on bundles, and potentially with XOR constraints), but in addition he could state that his capacity to produce tomatoes is only 60 tons. This would render infeasible all clearing solutions in which he is allocated more than 60 tons of tomato production. This is an instance of a class of constraints that I call unit con­ straints. Similarly, in an auction, a bidder could submit a number of bids (maybe on bundles, and potentially with XOR constraints), but in addition he could state that he has a bud­ get constraint of $35,000,000. This is an instance of a class of constraints that I call cost constraints. Yet another form of concise expressiveness is to allow bidders to submit discount schedules, e.g., "If I get to supply at least $9,000,000 of toma­ toes to you, I will give you a 2% discount. At $15,000,000, I will raise the discount to 3%." Or the bidder could sub­ mit a supply (demand) curve where the per-unit price of tomatoes is a function of the quantity [Sandholm, 2002b; Sandholm and Suri, 2001a; 2002].

While work on combinatorial auctions has traditionally fo­ cused on increasing the expressiveness for the bidders, I view expressive competition as having two equally important parts, expressive bidding and expressive bid taking. A key approch toward expressive bid taking is to allow the bid taker to sub­ mit side constraints on the clearing. This allows him to model and honor legal constraints, for example the following cost constraint: "minority bidders have to win 10% of the auc­ tion". It also allows the bid taker to horior contractual obli­ gation. For example, the buyer in a reverse auction for trans­ portation services may have a contract that states that Joe's Trucking has to get at least $30,000,000 of business. This can be modeled as a side constraint in the clearing, and the clear­ ing algorithm will decide exactly what services are procured from Joe's Trucking and what services from other providers. This approach allows one to reap the benefits of both long­ term contracts and dynamic pricing-modes of trade tradi­ tionally considered mutually exclusive. Finally, the bid taker can submit his business rules as side constraints. He may use counting constraints such as "I don't want to deal with more than 200 winning suppliers, and I do not have the capability to handle more than 3 at my plant in Chicago". He may also use cost constraints like "I don't want any one supplier to win more than 15% of the business (so that my supply chain stays competitive for the long run)".

The use of side constraints allows one to find a market clearing solution that is implementable in the world because the real-world constraints are honored. By changing side con­ straint and running the clearing algorithm again, the bid taker can also conduct quantitative what-if analyses. For example, "How much would my procurement cost in this reverse auc­ tion increase if I decrease my supply base down to 17 sup­ pliers?" Or, "How much more would I save in this reverse auction if I did not go with a sole-source contract for elec­ trical supplies in my Cincinnati plant, but rather allowed 2 suppliers?"

In the 70 markets with expressive competition that we have fielded to date (see, e.g., [CombineNet, Inc., 2003e; 2003c; 2003b; 2003d; 2003a]), we have seen hundreds of side con­ straint types. We abstracted them into seven general classes, the most prevalent of which are cost constraints, unit con­ straints, and counting constraints. This abstraction allows the clearing algorithm to be designed for a few classes rather than for hundreds of constraint types.

Non-price attributes in the clearing

An additional form of expressive competition stems from the fact that in many markets there are non-price attributes that are pertinent to the clearing problem, such as color, width, delivery date, quality, insurance terms, and so on. There are at least two reasons for introducing multi-attribute techniques into the clearing problem. First, in a basic combinatorial auc­ tion (or reverse auction or exchange), each item has to be completely specified. In many settings, this is overly restric­ tive. It is more desirable to leave some of the item attributes unspecified, so that each bidder can propose in his bids the attribute vector that is most suitable to him. Each bidder can also submit multiple bids with alternative attribute vectors, which is desirable because different attribute vectors are gen­ erally not equally valuable to the bid taker. Second, a bid from one bidder can be more valuable than the same bid from another bidder (due to bidder attributes such as historical data on timeliness and quality), and this should be taken into ac­ count in the clearing.

Multiattribute considerations can be integrated into combi­ natorial auctions and reverse auctions as follows [Sandholm and Suri, 200lb]. Let aj be a vector of attributes. These can be item attributes and/or bidder attributes. Some of the at­ tributes can be specific to one bid (say j) while others might not (such as quality of a certain line of products). The vec­ tor can include attributes revealed by the bidder as well as attributes whose values the bid taker gets from other sources such as historical performance databases. The bid prices can be re-weighted based on the additional attributes. The new price of any bid j is p'. = f(p1, aj), where PJ is the origi­ nal price of that bid. The re-weighting function f is usually expressed by the bid taker (seller in an auction, buyer in areverse auction)-either before or after the auction to character­ ize his preferences. (For example, the buyer of sea freight ser­ vices may give a 4% advantage to bids that include less than 3 interim ports on the route from source to destination.) The clearing problem is then solved using these revised prices.

Unlike in auctions and reverse auctions where multiple at­ tributes can be handled in a preprocessor to the clearing prob­ lem as shown above, in exchanges multiple attributes cannot be handled in a preprocessor. The reason is that in an ex­ change there are multiple bid takers (each buyer and each seller is a bid taker in this sense), and they may have dif­ ferent preference functions f over attribute vectors. Multiple attributes can still be handled, but their handling has to be incorporated into the clearing problem itself. This can be ac­ complished as follows. Treat items that have different values of the item attributes as different items. Then use a separate decision variable not just for each such item, but for each ( item, buyer, seller ) tuple. This way each buyer (seller) can condition his bid price on the item attributes and on whom he is buying from (selling to). Conditioning on whom he is buy­ ing from (selling to) is pertinent when bidder attributes have to be taken into account. 5

3.4 Complexity of the clearing problem

Expressive competition is a new way of conducting business, and has a host of advantages as discussed above. However, it requires solving the clearing problem-a combinatorial op­ timization problem. Many variants of it are hard, and the variants span an intriguing spectrum of worst-case complex­ ity when it comes to the complexity of finding a feasible so­ lution, an approximately optimal solution, or an optimal so­ lution:

• As discussed, in the canonical combinatorial auction there is one unit of each item, bids can be submitted on bundles (and bids on overlapping bundles cannot both win), there is free disposal, and there are no XOR­ constraints or other side constraints. Optimal clearing in this setting is NP-complete [Rothkopf et al., 1998].
• That problem is also inapproximable: no polynomial­ time algorithm can guarantee a solution that is better than a bound n 1 -< from optimal, where n is the num­ ber of bids (unless P=ZPP) [Sandholm, 2002al.
• Optimal clearing in a combinatorial reverse auction and a combinatorial exchange is N ?-complete even if there is only one unit of each item, free disposal, and no X OR­ constraints or other side constraints [Sandholm et al., 2002].
• Combinatorial reverse auctions are not as inapprox­ imable as combinatorial auctions: a bound (1 + In M) can be obtained in polynomial time even in the multi­ unit case, where M is the largest number of units that

5 There also exist auctions and reverse auctions where the multi­ attribute aspects cannot be handled in a preprocessor. This occurs if the bid taker's way of evaluating attributes depends on which bids win. In such cases, as in exchanges, the way in which the attributes are to be taken into account can be modeled in the clearing problem itself.

any bid contains [Sandholm et at., 2002]. (This assumes the canonical setting where there is free disposal, and no XOR-constraints or other side cosntraints.)

• Finding a feasible solution is trivial in combinatorial auctions (accept no bids, or any one bid) and in com­ binatorial reverse auctions (accept all the bids; if this does not cover the demand, then nothing will). Without free disposal, even finding a feasible solution is NP­ complete in these variants, even in the single-unit case with no XOR-constraints or other constraints [Sandholm et at., 2002] (this implies inapproximability to any ra­ tio bound). The same results apply to combinatorial ex­ changes (the hardness applies if the trivial "no bids ac­ cepted" solution is excluded).
• XOR-constraints do not change the approximability of canonical combinatorial auctions [Sandholm et al., 2002] . However, XOR-constraints make finding a fea­ sible solution NP-complete in combinatorial reverse auctions (even in the single-unit case with free dis­ posal) [Sandholm et al., 2002]. In other words, com­ binatorial reverse auctions are more approximable than combinatorial auctions, but this ordering reverses when XOR-constraints are introduced.
• Combinatorial exchanges inherit the inapproximability of both combinatorial auctions and combinatorial re­ verse auctions [Sandholm et al., 2002].
• Cost constraints and unit constraints do not affect the complexity class of the clearing problem when bids can be submitted on bundles: the basic case where bids have to be accepted all or nothing remains NP-complete, and the case where bids can be accepted fractionally can be solved in polynomial time using linear program­ ming [Sandholm and Suri, 2001 bl. However, X OR­ constraints and other counting constraints make even the fractional case N ?-complete [Sandholm and Suri, 200 I b] . There exist severe side constraints that restrict the search space enough so that even the case where bids have to be accepted all or nothing is optimally clearable in polynomial time [Sandholm and Suri, 200lb] .
• If bids can be accepted fractionally, a combinatorial ex­ change (and auction and reverse auction) can be opti­ mally cleared by accepting a very small number of bids fractionally: m + 1 if the objective is to maximize sur­ plus, and m + 2 if the objective is to maximize liq­ uidity [Kothari et al., 2003] . Herem is the number of distinguishable items in the market. This clearing can be found using linear programming. However, if XOR­ constraints are allowed, finding the surplus-maximizing clearing is N ?-complete even in the fractional case, even if there is just one item in the market with multi­ ple units of it [Kothari et al., 2003].
• In an auction where bids can be submitted on indi­ vidual items only (not on bundles), winner determina­ tion is trivial : simply accept the highest bid on each item. Under budget constraints, optimal winner de­ termination becomes N P-complete. Curiously, if in­ stead of a budget constraint each bidder submits a con-
• straint on the number of items he wins, the auction can be optimally cleared in polynomial time using b­ matching [Tennenholtz, 2000]. If bids can be accepted fractionally, winners can be determined in polynomial time using linear programming even with budget con­ straints. Under XOR-constraints (or other counting con­ straints), clearing is N ?-complete even if bids can be accepted fractionally [Sandholm and Suri, 2001b]. (If each bidder places an XOR-constraint between every pair of his bids-so that at most one of his bids can be accepted-then the problem becomes the assign­ ment problem [Sandholm and Suri, 2001 b]. The assign­ ment problem can be solved in polynomial time [Kuhn, 1955].)
• Even if there is just one item in the market (multi­ ple units of it), piecewise linear supply/demand curves are N P-complete to clear optimally (in an exchange, auction, and reverse auction), but with linear sup­ ply/demand curves, optimal clearing can be done in polynomial time [Sandholm and Suri, 2001a; 2002] .

In summary, there is a tradeoff between expressiveness (with its economic and usability advantages) and the com­ putational complexity of clearing the market. While many variants of the clearing problem are hard in the worst case, in practice problems of real-world sizes can usually be solved. (This is most likely due to the co-evolution of clearing tech­ nology and expressive markets.) Experiments show that com­ binatorial reverse auctions tend to be easier to clear optimally than combinatorial auctions, which in tum are easier than combinatorial exchanges [Sandholm et al., 2002].

3.5 Algorithms for the clearing problem

While the idea of a basic canonical combinatorial auction is two decades old, combinatorial auctions have traditionally not been used. The main reason is that the clearing problem is tough. In the last few years, hardware and especially clear­ ing algorithms, have reached a level of scalability that enables combinatorial auctions of real-world sizes to be cleared opti­ mally. As a consequence, numerous combinatorial auctions have emerged in industry.

The rest of this section focuses solely on clearing algo­ rithms that find an optimal solution. Optimal clearing is im­ portant because real money is at stake, because approximate clearing yields solutions extremely far from optimal (at least in the worst case), because a large change in the winners can occur even if the solution changes slightly from optimum, and because suboptimal clearing ruins the incentive properties of the market (as will be discussed in the next subsection).

The first-generation special-purpose clearing algorithms for the canonical combinatorial auction used a search tree where branching was on items (Figure 1 left) [Sandholm, 2002a; 2000b; Fujishima et al., 1999]. The newer, and sig­ nificantly faster, clearing algorithms use a search tree where branching is on bids instead (Figure 1 right) [Sandholm and Suri, 2003; Sandholm et al., 2001]. It has the advantage that there is more flexibility in variable ordering: at each branch point, commitment occurs on only one bid rather than on all of the bids that include a specific item. Another benefit is that, unlike the branch-on-items tree, the branch-on­ bids tree easily supports all of the market designs for expres­ sive competition discussed above [Sandholm and Suri, 2003; Sandholm et al., 2002].

Interestingly, although the problem is NP-complete, both the branch-on-items tree [Sandholm, 2002a] and the branch­ on-bids tree [Sandholm and Suri, 2003] are of polynomial size in the number of bids even in the worst case (and expo­ nential in the number of items). This is desirable because the auctioneer usually controls the number of items for sale, but not the number of bids that happen to be submitted.

The techniques that make the branch-on-bids search fast in practice include bid ordering heuristics that dynamically choose the next bid to branch on, techniques for dynam­ ically choosing the bid ordering heuristic itself based on context, upper bounding based on a linear programming re­ laxation of the remaining subproblem (and intelligent ad­ dition of cutting planes that reduce the size of the linear programming polytope, but do not cut out the optimal in­ teger solution), lower bounding based on rounding tech­ niques, decomposition of the problem when the bid graph (Figure 1 right) splits into independent components, tech­ niques for enhancing upper and lower bounding based on in­ formation from sibling components, and methods for iden­ tifying and solving potential polynomially-solvable special cases at each node. In the interest of flow, I will not go fur­ ther into those techniques here. Many of them are described in detail in specialized papers [Sandholm and Suri, 2003; Sandholm et al., 2001].

Suffice it to say that the CABOB algorithm [Sandholm et al., 2001] is, by and large, the fastest algorithm for the canon­ ical combinatorial auction clearing problem currently, based on the widely adopted approach of evaluating clearing al­ gorithms on standard randomly generated benchmark distri­ butions [Sandholm, 2002a; Fujishima et al., 1999; Leyton­ Brown et al., 2000a; Andersson et al., 2000]. Interest­ ingly, economically motivated random distributions (specif­ ically the ones from CATS [Leyton-Brown et al., 2000a])

tend to be very easy compared to totally random distribu­ tions [Sandholm et al., 2001]. Similarly, real clearing prob­ lems are often easier than totally random ones. Our fielded algorithms systematically solve real reverse auctions with up to tens of thousands of items, hundreds of thousands of bids, and hundreds of thousands of side constraints to optimum.

3.6 Incentives to bid truthfully: The Vickrey-Ciarke-Groves (VCG) mechanism

One concern is that bidders may bid insincerely. For example, in an auction where each winning bidder is charged the sum of the prices of his winning bids, the bidders are motivated to bid less than their true valuations of the items.

This issue can be overcome under the traditional assump­ tion that each bidder i has a quasilinear utility function: u; ( S, Pi) = Vi ( S) - Pi, where S is the bundle that bidder i wins, and Pi is the price that he has to pay. It turns out that un­ der this assumption, a fully expressive bidding language com­ bined with an optimal clearing algorithm is sufficient [Sand­ holm, 2002b; 2000b] and necessary [Nisan and Ronen, 2000] for being able to design auction mechanisms that yield a so­ cial welfare maximizing allocation and where every bidder's dominant strategy is to bid truthfully. 6 With such technology, bidding truthfully can be made a dominant strategy by using the Vickrey-Clarke-Groves (VCG) mechanism [Vickrey, 1961 ; Clarke, 1971; Groves, 1973]. This means that each bidder is motivated to bid truthfully regardless of how others bid- thus rendering speculation about others futile. 7

The VCG mechanism can be applied to markets with ex­ pressive bidding as follows. The optimal clearing outcome is first computed as usual. The amount that an agent needs to pay is the sum of the others' winning bids had the agent not participated, minus the sum of the others' winning bids in the actual optimal outcome. So, the clearing problem has to be solved once overall, and once per winning agent without any of that agent's bids or side constraints. 8

4 Preference elicitation in multiagent systems

Most, but not all, game-theoretic interaction mechanisms are so called direct-revelation mechanisms, where each partici­ pant reveals all of his private information (e.g., bundle valu­ ations in combinatorial auctions) completely up front. There are fundamental results that show that, in the absence of com­ putation/communication limitations, this restriction comes at no loss in any sense (cf the revelation principle [Mas­ Cole!! et a/., 1995]). However, in practice such mechanisms are problematic because the agents may need to determine their own preferences via costly deliberation (e.g., comput­ ing [Sandholm, 1993; 1996; 2000c; Larson and Sandholm, 2001b; 200lc]) or information gathering, and communicat­ ing complete preferences may be undesirable from the per­ spective of privacy or conserving bandwidth.

6 Under extremely strong assumptions about the bidders' util­ ity functions, truth-dominance can be accomplished with approxi­ mate clearing (see e.g., [Lehmann eta/., 2002; Mu'alem and Nisan, 2002]), but because the clearing problem is inapproximable, the al­ location is extremely far from optimal in the worst case.

7 The VCG mechanism has also been used in mediated plan­ ning among software agents [Ephrati and Rosenschein, 1991; 1993; Ephrati, 1994).

8 In auctions, the mechanism is budget balanced: the seller col­ lects the nonnegative amounts paid by the bidders. In exchanges, an external benefactor is usually needed. In fact, with private valuation information on both the buy side and the sell side of the market, there is no mechanism for general quasi linear utility functions-even with just one unit to trade and only one buyer and one seller-that mo­ tivates the parties to participate in the mechanism, yields the social welfare maximizing outcome, and is budget balanced [Myerson and Satterthwaite, 1983] .

This issue can be addressed using a methodology where the mediator incrementally elicits the agents' private information on an as-needed basis in a manner directed to being able to determine the outcome (that would have come about had the agents revealed all of their private information to the medi­ ator) [Conen and Sandholm, 200 1]. It turns out that often the outcome can be determined while eliciting only a small portion of the agents' private information. A key insight is that in multiagent systems, what information is needed from a party depends on what information the other parties have revealed. This is a central motivation for interleaved prefer­ ence elicitation from multiple agents. The approach offers the advantages of incremental problem solving (as in peer­ to-peer negotiation) while reaping the benefits of mediated clearing discussed earlier. The rest of this section studies this approach as applied to combinatorial markets and voting.

4.1 Preference elicitation in combinatorial auctions

Preference elicitation is crucial in combinatorial markets be­ cause each agent has an exponential number of bundles to evaluate (and again, each such evaluation problem can be hard [Sandholm, 1993; Sandholm and Lesser, 1995b; Sandholm, 2000c; Larson and Sandholm, 2001b; 2001c]). Each agent would like to focus on a small number of bun­ dles in order to minimize evaluation effort, communication, and loss of privacy. On the other hand, the social welfare among the agents, the seller's revenue, and the agent's utility will usually suffer if the agent's evaluation of a bundle that he would win is not communicated to the auctioneer. In a usual combinatorial auction it is difficult for the agent to de­ cide which bundles to bid on because others' bids determine what bundles the agent would be competitive on.

To address this problem, we developed a methodology where an elicitor software, residing at the auctioneer, incre­ mentally builds a model of the agents' valuation functions Vi [Conen and Sandholm, 2001]. The elicitor queries the agents about vi , and fully assimilates the answers into its model. The next query to be asked is always chosen based on the answers so far. The elicitor in a sense opens up the clearing algorithm and elicits the inputs needed for determin­ ing the optimal outcome (allocation of items to agents). The agents are never asked for information that the elicitor can already infer from the answers, or that is known to be im­ pertinent for determining the optimal allocation. The elicitor terminates the process when it has found a provably optimal allocation.

The rest of this section will focus on combinatorial auc­ tions under the usual free disposal assumption, which almost always holds in practice. It gives structure to the elicita­ tion problem because for each agent, the value of a bundle is no greater than the value of any superbundle of that bundle (vi(S) ::; vi(S') whenever S C S').

The general case

Even with free disposal, the worst-case communication com­ plexity for even approximately optimally clearing the market is exponential in the number of items, regardless of the query types or the elicitation policy [Nisan and Segal, 2003]. The discussion below will focus on natural value queries: "what is your valuation of bundle S?" (Other query types can increase the efficiency of elicitation [Conen and Sandholm, 2001 ; Hudson and Sandholm, 2002; Conen and Sandholm, 2002b; 2002al. 9 ) It turns out that in practice elicitation is very promising: only a vanishing fraction of all the queries are asked before the elicitor can clear the auction provably opti­ mally [Hudson and Sandholm, 2002]! The preference elici­ tation methodology is also very promising in combinatorial reverse auctions [Hudson and Sandholm, 2003a] and combi­ natorial exchanges [Smith eta/., 2002].

One may also ask whether there exists a universal revela­ tion reducer for combinatorial auctions, that is, a general elic­ itor algorithm that saves some elicitation (finishes finding an optimal outcome and proving its optimality without asking all value queries) on all instances where some instance-specifc elicitor saves some elicitation (that is, where the shortest cer­ tificate for verifying that a proposed outcome is optimal is shorter than the number of agents times the number of bun­ dles). It turns out that a deterministic universal revelation reducer cannot exist, but randomized ones are easy to con­ struct [Hudson and Sandholm, 2003b].

Restricted preferences for which the worst-case number of queries is polynomial in items

For restricted classes of vi functions, the worst-case number of value queries needed is polynomial in the number of items being sold. Many of these classes are rich enough to exhibit both complementarity and substutitability. This subsection will present classes like that, which are also arguably natural for capturing valuation functions.

First, consider read-once formulas. A read-once formula is a function that can be represented as a tree, where the items for sale in the auction are at the leaves, together with the bidder's valuations for the individual items. The for­ mula's output value is obtained by feeding in a bundle S of items to the leaves and reading the valuation vi(S) from the root. A leaf sends the item's valuation up the tree if the item is included in S, otherwise the leaf sends 0. Dif­ ferent types of gates can be used in the nodes of the tree. A SUM node sums the values of its inputs; a MAX node takes the maximum value of its inputs; an ALL node sums its inputs unless one of the inputs is zero, in which case the output is 0. For example, a legal function on 3 inputs might be ALL(2x 1 , MAX(10x2 , 4x3)), which gives value 12 to the bundle { 1 ,2}, 6 to bundle {I ,3}, and 0 to bundle { 2,3}. Read-once formulas of this type allow for many natural pref­ erences. For example, suppose items are flights and hotel rooms in different locations (e.g., input Xi,j ,O represents the i th flight to location j, and Xi,j , I represents the ith hotel room in location j) and we want to take just one trip. Then for each location j we could compute ALL(MAX { Vi ,j,OXi ,j ,O }i, MAX{ v i ,j ,IXi ,j,I}i), and then atthe root ofthe tree we would take a MAX over the different destinations. More general gates are also possible. Let MAXk output the sum of the k highest inputs, and ATLEASTk output the sum of its inputs if there are at least k positive inputs, and 0 otherwise. Finally, let GENERALk,l be a parameterized gate capable of repre­ senting all the above types of gates. For instance, imagine that on a vacation to the Bahamas, Alice wanted entertainment. If she got to go out on at least three nights, then the trip would be worthwhile. Otherwise, she would rather stay home. Each night, she takes the maximum valued entertainment option. Then there is an ATLEAST3 node combining all of the dif­ ferent nights. In a different situation, imagine that Joe wants a more relaxing vacation in Hawaii, where he does not want to go out more than three nights. In this case, a MAX3 gate will be useful. For each night, he chooses the best possible enter­ tainment given to him. Then, he takes the best three nights of entertainment. Finally, imagine that Maggie wants a moder­ ately active vacation, and is interested in going to Paris for a week, and wants at least three but no more than four nights of entertainment. Then a GENERAL3,4 gate will describe her preferences. It turns out that if the user's valuation function v i can be expressed as a read-once formula with these gates (even if the user is not aware of that), then vi can be elicited with a number of value queries that is polynomial in the num­ ber of items in the auction even in the worst case [Zinkevich et al., 2003]. 1 ° Furthermore, if a bidder's valuation function vi is close to some read-once function with the gates discussed above, then a close model of vi can be constructed with a polynomial number of value queries.

9 Ascending combinatorial auctions (e.g., [Bikhchandani et a!. , 2001; Parkes and Ungar, 2000; Wurman and Wellman, 2000]) can be viewed as a special case of the preference elicitation framework where the queries are of the form: "Given these prices on items (and possibly also on bundles), which bundle would you prefer the most?".

Second, consider the class of preferences that can be ex­ pressed as monotone polynomials. For example, vi(x) = ax1x2 + bxzx3X4 + cx3X4. This class is called Toolbox DNF because it captures settings where each agent has a set of tasks to accomplish (one per term in the polynomial), each task requiring a specific set of tools (the variables in the term) and each having its own value (the coefficient on that term). For example, the tools may be medical patents, and producing each medicine requires a specific set of patents. The value of a set of items to the agent is the sum of the values of the tasks that the agent can accomplish with those items. It turns out that any toolbox DNF valuation function vi can be elicited in a polynomial number of value queries [Zinkevich et at., 2003].

10 An analogous issue arises with shopping agents. Consider the following scenario. Alice goes to her software agent and asks it to help her purchase a vacation. In order to act on her behalf, the agent first needs to find out Alice's preferences (how much is a trip to Hawaii worth compared to a trip to the Bahamas, does it sub­ stantially increase the value to her if she can get some entertainment booked in advance, etc.). Then, after scouring the Internet, the agent needs to solve the computational problem of deciding on the best vacation package-the one that maximizes Alice's valuation minus the cost of the trip. In this scenario, there is no auctioneer. Rather, the elicitor is the buyer's helper. Again, the amount of querying can be prohibitively large when the buyer has general (monotone) pref­ erences, but with these types of read-once preferences, Alice's val­ uation function can be determined in a polynomial number of value queries.

The power of interleaved preference elicitation from multiple parties

The above two example classes of valuation functions can be elicited efficiently even if there is only one party whose pref­ erences are to be elicited. So, the efficiency does not derive from the fact that information from other agents restricts the amount of information needed. The next class, on the other hand, derives its ease of elicitation from this phenomenon.

Consider a combinatorial auction with two buyers that have their valuation functions in the form of the XOR bidding lan­ guage discussed earlier, where each bidder can submit bids on bundles, and all of the bidder's bids are mutually exclu­ sive. It turns out that if no bid includes more than log 2 m items (where m is the number of items in the auction), then the provably optimal allocation of items to the bidders can be determined in a worst-case polynomial number of value queries [Blum et al., 2003].

Interestingly, there are classes of vi functions where learn­ ing the functions requires an exponential number of value queries, while the provably optimal allocation can be con­ structed in a polynomial number of value queries [Blum et al., 2003]. For other classes of vi, being able to elicit enough to find the provably optimal allocation in a polynomial num­ ber of value queries implies that the vi functions themselves can be learned in a polynomial number of value queries. So, sometimes there is an exponential benefit to interleaving the queries made to the different parties, while at other times the benefit between that and eliciting each agent's preferences separately is polynomially bounded.

Incentives to answer truthfully: Ex post equilibrium in an incremental push-pull multiagent elicitation mechanism

Motivating the bidders to answer queries truthfully is another key issue, and is exacerbated by the fact that the elicitor's queries leak information to the bidder about the answers that other bidders have given. Recently, a methodology was pro­ posed by which elicitors can be made incentive compatible in the sense that every bidder (with a quasilinear utility func­ tion) answering the queries truthfully is an ex post equilib­ rium [Conen and Sandholm, 2001]. This means that bidding truthfully is each bidder's best strategy (for any prior proba­ bility distribution that he may hold about the other bidders) given that the other bidders bid truthfully. In other words, truthful bidding strategies form a (Bayesian) Nash equilib­ rium even in hindsight. (This does not mean that bidding truthfully is a dominant strategy; if some of the other agents bid insincerely and conditional on the elicitor's query stream to them, one may do better by bidding insincerely. In sum­ mary, implementation in ex post equilibrium is stronger than implementation in (Bayesian) Nash equilibrium, but weaker than implementation in dominant strategies.)

The methodology is the following. The mechanism is structured so that if all the bidders answer truthfully, the final allocation and payments follow the VCG mechanism. The amount a bidder has to pay is the sum of the others' re­ vealed valuations for the bundles they get had the bidder not been given any of the items, minus the sum of the others' revealed valuations for the bundles they get in the actual op­ timal allocation. The elicitor can determine these payments by asking enough queries to be able to determine the welfare maximizing allocation overall, and by asking extra queries to determine the welfare maximizing allocation for the auc­ tions where each agent is ignored in turn. The extra queries needed to determine the VCG payments are a negligible frac­ tion of the queries needed to determine the optimal allocation in practice [Hudson and Sandholm, 2003a], and in some elic­ itation policies that information comes purely as a side effect with no extra queries at all [Conen and Sandholm, 2002b; 2002a].

Truthful answering is an ex post equilibrium even in elici­ tation mechanisms where the bidders are allowed to pass on some queries (as long as they answer enough queries to de­ termine the optimal allocation and the VCG payments) and to answer queries that were never asked [Conen and Sandholm, 2001 ]. This yields a pull-push mechanism where the elici­ tor guides the preference revelation, but each bidder can also proactively reveal values on bundles on which it thinks it is competitive.

4.2 Preference elicitation in voting

Multiagent preference elicitation can also improve the effi­ ciency of running elections [Conitzer and Sandholm, 2002d]. To determine the optimal outcome for a given voting proto­ col, it is generally not necessary to elicit complete preferences from all voters, and some voters' preferences may not need to be elicited at all. Selective preference elicitation increases privacy, and reduces the cost of voting (traveling to the vot­ ing site, spending time, etc.). Again, what, if any, information should be elicited from an agent depends on what other agents have revealed about their preferences so far.

However, it turns out that effective vote elicitation gives rise to challenging computational problems. In the Sin­ gle Transferable Vote protocol (defined later), even knowing when enough has been elicited to determine the provably opti­ mal outcome is NP-complete, while this is easy for all other common voting protocols (defined later). Even for these pro­ tocols, determining whose votes to elicit is NP-complete, even with perfect suspicions about how the agents will vote. (The exception is the plurality protocol-the most common voting protocol. There, everyone votes for one candidate and the candidate with the largest number of votes wins. In that protocol, effective elicitation is easy.) If the elicitor's sus­ picions are imperfect, then effective elicitation can even be PSPACE-hard.

Elicitation can also introduce additional opportunities for strategic manipulation by the voters because the elicitor's queries leak information among the voters. In coarse elic­ itation (where each voter's entire ranking of candidates is elicited if the voter is queried at all) this can be avoided by making sure that the voter does not know how many voters have been queried before him. In fine elicitation (where a voter is asked pairwise preferences one pair of candidates at a time) this can be avoided by making sure that the voter does not know what/how many queries have been made to others, and by making sure that the order in which queries are made to this voter is fixed up front rather than dependent on others' answers.

5 Hard valuation problems

As discussed in the previous section, preference elicitation can significantly reduce the agents' effort of evaluating bun­ dles in combinatorial auctions. However, it cannot eliminate the need to evaluate at least some bundles to some extent. In this section I present a deeper look into an agent's evaluation problem with an explicit model of computation, and illustrate new strategic issues that stem from it.

In many markets, even computing one's valuation for a sin­ gle bundle (or individual item) is complex. For example when bidding for trucking lanes (i.e., tasks), this involves solving two N ?-complete local planning problems: the vehicle rout­ ing problem with the new lanes of the bundle and the problem without them [Sandholm, 1993]. The difference in the costs of those two local plans is the cost (valuation) of taking on the new lanes.

However, in practice bidders (humans or their software agents) have limited computation and time, so they cannot exactly evaluate all, or even any, bundles-at least not with­ out cost!

This leads to interesting incentive issues. For example, even in an auction where one object is being sold, should a bidder evaluate the object if there is a cost to doing so? Ac­ cording to traditional auction theory, truthful bidding is the dominant strategy in the celebrated Vickrey auction where the object is given to the highest bidder at the price of the second­ highest bid [Vickrey, 1961] (this is the VCG mechanism, dis­ cussed earlier, applied to single-object auctions). However, it turns out that the Vickrey auction loses its dominant-strategy property if the bidder has the option to evaluate the object or not [Sandholm, 2000c]. Whether or not the bidder should pay the evaluation cost depends on the other bidders' valuations.

The issues run even deeper. If a bidder has the opportunity to approximate its valuation to different degrees, how much computing time should the bidder spend on refining its val­ uation? If there are multiple items for sale, how much com­ puting time should the bidder allocate on different bundles? A bidder may even allocate some computing time to evaluate other bidders' valuations (e.g., how much it would cost for a competing trucking company to take on a given set of lanes) so as to be able to bid more strategically; I call this strategic computing.

To answer these questions, we developed a deliberation control method called a performance profile tree for pro­ jecting how an anytime algorithm (a blackbox from the per­ spective of the deliberation controller) will change the valu­ ation if additional computing is allocated toward refining (or improving) it [Larson and Sandholm, 200 I c; 200 I b; 200 I a;

2002]. Unlike earlier deliberation control methods for any­ time algorithms, the performance profile tree is a fully nor­ mative model of bounded rationality: it takes into account all the information that an agent can use to make its deliberation control decisions. (This is necessary in the game-theoretic context; otherwise a self-interested agent could take into ac­ count some information that the model does not.) Specifi­ cally, the projection of the anytime algorithm's performance is conditioned on the path of the run on the current problem instance, as well as static instance features.

Using this deliberation control method, the auction can be modeled as a game, where computing actions are part of the game. At every point, each agent can decide on which bun­ dle to allocate its next step of computing as a function of the agent's computing results so far (and in open-cry auction for­ mat also the others' bids observed so far). At every point, the agent can also decide to submit bids. One can then solve this model for the (Bayesian) Nash equilibrium, where each agent's (deliberation and bidding) strategy is a best-response to the others' strategies. I call this a deliberation equilibrium. Table 1 shows in which settings strategic computing can and cannot occur in equilibrium. First, this depends on the auction mechanism. 11 Interestingly, this also depends on whether the agent has limited computing (such as a free desktop computer on which it can run until the auction's deadline) (Larson and Sandholm, 2001b] or costly computing (such as being able to buy any amount of supercomputing time where each cycle comes at a cost) (Larson and Sandholm, 2001c]. 12

11 The Vickrey and VCG mechanisms were discussed earlier. The first-price auctions are sealed-bid auctions where the winning bidders pay their winning bid prices. The Dutch auction is a descending-price auction where the first bidder gets the object at the current price. The English auction is an open-cry ascending auction where the highest bidder wins and pays the price of his bid.

12 In these settings one can also determine how much such self­ ish computing hurts social welfare in the worst deliberation equilib­ rium [Larson and Sandholm, 2003).

6 Using computational complexity as a barrier to strategic manipulation

As the discussion of valuation computation in the previous section shows, agents' computational limitations can have ad­ verse effects on the incentive properties of interaction mech­ anisms. This section demonstrates that the reverse can also be made to be true: one can use the fact that agents are com­ putationally limited to achieve things that are not achievable via any mechanism among perfectly rational agents. In par­ ticular, I illustrate in a voting context that computational in­ tractability can be used as a barrier to undesirable strategic behavior, thus circumventing a seminal economic impossibil­ ity result.

One key problem voting mechanisms are confronted with is that of manipulation by the voters. An agent is said to manipulate (vote strategically) when it does not rank the al­ ternatives according to its true preferences, but rather so as to make the eventual outcome most favorable to itself. For ex­ ample, if an agent prefers Nader to Gore to Bush, but knows that Nader has too few other supporters to win, while Gore and Bush are close to each other, the agent would be better off by declaring Gore as its top candidate. Manipulation is an undesirable phenomenon because collective choice schemes are tailored to aggregate preferences in a socially desirable way, and if the agents reveal their preferences insincerely, a socially undesirable candidate may be chosen.

The issue of strategic voting has been studied extensively. A seminal negative result, the Gibbard-Satterthwaite theo­ rem, states that if there are three or more candidates, then in any nondictatorial voting scheme, there are candidate rank­ ings of the other voters, and preferences of the agent un­ der which the agent is better off voting strategically than sincerely (Gibbard, 1973; Satterthwaite, 1975]. (A voting scheme is called dictatorial if one of the voters dictates the outcome no matter how the others vote). So, a reasonable general nonmanipulable voting protocol does not exist! One approach around this impossibility is to construct desirable general nondictatorial voting protocols (under which manip­ ulations exist by the impossibility theorem), but under which finding a beneficial manipulation is prohibitively hard com­ putationally.

In order to discuss specific hardness results, I first review the most common protocols. In each protocol, each voter ex­ presses his preferences as a linear order over candidates. The protocol then takes those expressions and imposes one of the candidates as the chosen outcome. In the protocols that are based on scores, the candidate with the highest score wins. In each of the listed protocols (even the ones that have multiple rounds), the voters submit their preferences up front. That is, the voters are not allowed to change their preference revela­ tions during the execution of the protocol.

· scoring protocols. Let iS. = (a:1 , ... , a: c) be a vector of integers such that 0:1 ::=: 0:2 ... ::=: O:c. For each voter, a candidate receives a:1 points if it is ranked first by the voter, a:2 if it is ranked second etc. The score sa of a candidate is the total number of points the candi­ date receives. The Borda protocol is the scoring proto­ col with iS. = (c- 1, c- 2, ... , 0). The plurality pro-

tocol (aka. majority rule) is the scoring protocol with a= (1, 0, .. . , 0). The veto protocol is the scoring pro­ tocol with a= (1, 1, ... ' 1, 0) .

• maximin (aka. Simpson). For any two distinct candidates i and j, let N ( i, j) be the number of voters who prefer i to j. The maximin score of i is s(i) = min#i N(i,j).
• Copeland. For any two distinct candidates i and j, let C(i,j) = +1 if N(i,j) > N(j, i) (in this case we say that i beats j in their pairwise election), C( i, j) = 0 if N(i,j) = N(j,i) and C(i,j) = -1 if N(i,j) < N(j , i). The Copeland score of candidate i is s(i) = L ]#i C(i,j).
• single transferable vote (STY). The protocol proceeds through a series of c - 1 rounds. At each round, the candidate with the lowest plurality score (i.e., the least number of voters ranking it first among the remaining candidates) is eliminated. The winner is the last remain­ ing candidate.
• plurality with run-off. In this protocol, a first round elim­ inates all candidates except the two with the highest plu­ rality scores. Then votes are transferred to these (as in the STV protocol). After that, a second round determines the winner among these two.
• cup (sequential binary comparisons). The cup is defined by a balanced binary tree T with one leaf per candidate, and an assignment of candidates to leaves (each leaf gets one candidate). Each non-leaf node is assigned the win­ ner of the pairwise election of the node's children; the candidate assigned to the root wins. The cup protocol assumes that the assignment of candidates to leaves is known by the voters before they vote. In the random­ ized cup protocol [Conitzer and Sandholm, 2002bl, the assignment of candidates to leaves is chosen uniformly at random after the voters have voted.

There are two natural alternative goals of manipulation. In constructive manipulation, the manipulator tries to find an or­ der of candidates that he can reveal so that his favorite candi­ date wins. In destructive manipulation, the manipulator tries to find an order of candidates that he can reveal so that his hated candidate does not win. These are special cases of the utility-theoretic notion of improving one's utility, so the hard­ ness results carry over to that setting.

6.1 Complexity of manipulation when the number of voters and the number of candidates grows

Unfortunately, finding a constructive manipulation is in P for the plurality, Borda, and maximin voting protocols [Bartholdi et al., 1989], which are commonly used. The only voting protocol for which constructive manipulation is known to be NP-hard is the STY protocol [Bartholdi and Orlin, 1991]. 13

However, by slightly tweaking the voting protocols that are easy to manipulate, they can be changed into ones that are hard to manipulate. In particular, we revise them so that before the original protocol is executed, one pairwise elimination round is executed among the candidates, and only the winning candidates survive to the original proto­ col (so, about half of the candidates are eliminated in the preround). This makes the protocols N P-hard, #P-hard, or PSPACE-hard to manipulate constructively, depending on whether the schedule of the preround is determined be­ fore the votes are collected, after the votes are collected, or the scheduling and the vote collecting are carefully inter­ leaved, respectively [Conitzer and Sandholm, 2003e]. We proved general sufficient conditions on voting protocols for this tweak to introduce the hardness, and showed that the plurality, Borda, maximin, and STY protocols satisfy those conditions. So, these commonly used voting protocols can be made hard to manipulate by simply using one elimination round.

13 It is N P-hard also for the Second Order Copeland proto­ col [Bartholdi eta/., 1989], but the hardness is driven solely by the tie-breaking rule.

6.2 Complexity of manipulation when the number of candidates is constant

All of the hardness results discussed above rely on both the number of voters and the number of candidates growing. The number of candidates can be large in some domains, for ex­ ample when voting over task or resource allocations, but in many elections-such as presidential elections-the number of candidates is small. If the number of candidates is a con­ stant, both constructive and destructive manipulation are in P, regardless of the number of voters [Conitzer and Sand­ holm, 2002b]. This holds even if the voters are weighted, or if a coalition of voters tries to manipulate, but not both. When a coalition of weighted voters tries to manipulate, complexity can arise even for a constant number of candidates, as sum­ marized in Tables 2 and 3 [Conitzer and Sandholm, 2002b; Conitzer et al., 2003]. One lesson is that randomizing over instantiations of the mechanisms (such as schedules of a cup) can be used to make manipulation hard.

All of the hardness results discussed above hold even if the manipulators know the nonmanipulators' votes exactly. Un­ der weak assumptions, if weighted coalitional manipulation with complete information about the others' votes is hard in some voting protocol, then individual and unweighted ma­ nipulation is hard when there is uncertainty about the others' votes [Conitzer and Sandholm, 2002b].

Computation not only serves as a means to circumventing incentive problems as dicussed above, but it can also serve as the means for designing appropriate incentives as discussed in the next section.

7 Automated mechanism design

The aggregation of conflicting preferences for choosing an outcome is a central problem in multiagent systems, be the agents humans or software. The key difficulty is that the agents may report their preferences insincerely (i.e., manip­ ulate, as we just discussed in a voting setting). Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a desirable outcome is chosen. 14 The desirability objective can be, for example, social welfare, seller's revenue, fairness, or some tradeoff among these.

Mechanism design has traditionally been a manual en­ deavor. The designer uses experience and intuition to hy­ pothesize that a certain rule set is desirable in some ways, and then tries to prove that this is the case. Alternatively, the de­ signer formulates the mechanism design problem mathemat­ ically and characterizes desirable mechanisms analytically in that framework. These approaches have yielded a small num­ ber of canonical mechanisms over the last 40 years, each of which is designed for a class of settings and a specific objec­ tive. For example, the VCG and dAGVA [d' Aspremont and Gerard-Varet, 1979; Arrow, 1979] maximize social welfare among the agents in the class of settings where the agents have quasilinear utility functions. Mechanism design re­ search has also yielded impossibility results that state that no mechanism works across a class of settings (for varying def­ initions of "works" and varying classes). For example, the Gibbard-Satterthwaite theorem discussed in the previous sec­ tion states that for the class of general preferences, no mech­ anism works in the sense that 1) the mechanism's outcome can be any one of at least three candidates, 2) the mechanism is nondictatorial, and 3) every agent's dominant strategy is to reveal his preferences truthfully.

In sharp contrast to manual mechanism design, I envision a systematic approach where the mechanism is automatically created for the setting and objective at hand. This has sev­ eral advantages. First, it can be used even in settings that do not satisfy the assumptions of the classical mechanisms. Sec­ ond, it may allow one to circumvent the impossibility results: when the mechanism is designed to the setting (instance) at hand, it does not matter that it would not work on prefer­ ences beyond those in that setting (e.g., for a class of settings).

14 A central result in game theory, the revelation principle, allows the designer to restrict attention to such truthful mechanisms without loss in the objective [Mas-Colell et al., 1995).

Even when the optimal mechanism--created automatically­ does not circumvent the impossibility, it always minimizes the pain entailed by impossibility. Third, it may yield better mechanisms (in terms of stronger nonmanipulability guaran­ tees and/or better outcomes) than the canonical mechanisms because the mechanism capitalizes on the particulars of the setting (the probabilistic information that the mechanism de­ signer has about the agents' preferences). Given the vast amount of information that parties have about each other to­ day, it is astonishing that the canonical mechanisms (such as first-price reverse auctions), which largely ignore that infor­ mation, have prevailed thus far. I foresee an imminent revolu­ tion, where future mechanisms will be created automatically. For example, imagine a Fortune 1000 company automatically creating its procurement mechanism based on its statistical knowledge about its suppliers (and potentially also the public prices of the suppliers' inputs, etc.). I call this vision auto­ mated mechanism design [Conitzer and Sandholm, 2002c]. 15

7.1 The computational problem

As a first step toward fulfilling this vision, we modeled mech­ anism design as an optimization problem, and studied its complexity. In the model, each agent can have any one of a finite number of utility functions. An agent's utility func­ tion is private information. The mechanism designer has a prior probability distribution over each agent's possible util­ ity functions. The first constraint to the problem (the incen­ tive compatibility constraint) is that each agent has to be moti­ vated to reveal its utility function truthfully regardless of what utility function the agent has. This comes in two variants. In the first (called dominant strategy implementation), the agent has to be no worse off by revealing his true utility function regardless of what utility functions the other agents reveal. In the second, the agent has to be no worse off, in expec­ tation, by revealing his true utility function. (The expecta­ tion is taken as a weighted average over the possible truth­ ful utility function revelations of the other agents). The sec­ ond constraint to the problem (the participation constraint) is that each agent has to be no worse off by participating in the mechanism than not participating (otherwise a rational agent would not participate). This again comes in two variants. In the first, the agent has to be no worse off regardless of what utility functions the other agents reveal. In the second, the agent has to be no worse off in expectation. The input to the optimization also includes the designer's objective. The out­ put is a mapping from utility function revelations to outcomes (or in the case of randomized mechanisms, to probability dis­ tributions over outcomes).

In settings without side payments, such as voting, design­ ing an optimal (e.g., expected social welfare maximizing) de­ terministic mechanism is NP-complete [Conitzer and Sand­ holm, 2002c] . 16 If side payments are allowed, designing a deterministic mechanism is easy if the designer's objective is social welfare, but N ?-complete more generally (for ex­ ample, if the objective is to maximize the expected revenue collected from the bidders-as is the objective in some auc­ tions) [Conitzer and Sandholm, 2003bl. Interestingly, if one allows randomized mechanisms, the mechanism design prob­ lem becomes solvable in polynomial time using linear pro­ gramming.17 In other words, the designer can tackle the com­ putational complexity, introduced by its uncertainty about the agents, by making the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the mecha­ nism designer's objective.

15 Note that automated mechanism design is completely different from so called algorithmic mechanism design [Nisan and Ronen, 2001). In the latter, the mechanism is designed manually with the goal that executing the mechanism is computationally tractable. On the other hand, in automated mechanism design, the mechanism it­ self is designed automatically.

16 This actually holds for any solution concept from noncoopera-

If the agents' utility functions are additively decomposable into independent issues, the input to automated mechanism design can be represented (potentially exponentially) more concisely. In that representation it is N ?-complete (even under strong restrictions) to design a mechanism that maxi­ mizes one of the following objectives: I) expected social wel­ fare when payments are not possible, 2) a general objective function even when payments are possible, and 3) expected revenue collected from the agents [Conitzer and Sandholm, 2003cl. Again, a randomized mechanism can be designed in polynomial time. So, the complexity as a function of the input length is the same in the concise representation as it is in the flat representation. In other words, due to its potentially ex­ ponentially shorter input length, the structured representation allows potentially exponentially faster automated mechanism design.

7.2 Applications

In initial experiments, automated mechanism design pro­ duced the following highlights [Conitzer and Sandholm, 2003a]:

• It reinvented the celebrated Myerson auction [Myerson, 1981], which maximizes the seller's expected revenue in a 1-object auction.
• It created expected revenue maximizing combinatorial auctions. This has been a long-standing recognized open research problem in (manual) mechanism design [Av­ ery and Hendershott, 2000; Vohra, 20011. The general form for such an auction is still unknown, but automated mechanism design created prior-specific optimal mecha­ nisms. (In the manual mechanism design literature, even the problem with only two objects for sale is open; only a case with very special form of complementarity and no substitutability has been solved [Armstrong, 2000].)
• It created optimal mechanisms for divorce settlements, both with a benevolent arbitrator that tries to maximize the sum of the divorcees' utilities (with and without side payments), and an arbitrator that tries to maximize rev­ enues collected from the divorcees.
• It created optimal mechanisms for a public good problem (deciding whether or not to build a bridge). The

tive game theory [Conitzer and Sandholm, 2002a), not just the ones discussed through the constraints above. All of the hardness results discussed in this section hold even with just 2 agents.

17 This holds for any mechanism design objective that is linear in the outcome probabilities.

VCG mechanism could be used in this setting as long as each agent's utility function is quasilinear. However, in the VCG mechanism, nonnegative payments are c.Jl­ lected from the voters (intuitively, the payments are col­ lected in order to avoid the free rider problem), and those payments have to be burned. According to a seminal impossibility result, this problem plagues any mecha­ nism that applies to general quasi linear utility functions, yields a social welfare maximizing decision, and makes truthful reporting of utility functions a dominant strat­ egy [Green and Laffont, 1979]. The automated mecha­ nism design approach allowed us to incorporate money burning as a loss in the social welfare objective, and maximize that revised objective. We had automated mechanism design create an optimal mechanism for the bridge building scenario under each variant of the incen­ tive compatibility constraint discussed above (with the deterministic participation constraint). In neither vari­ ant was money ever burned. In the probabilistic variant, the bridge was always built if and only if that was best for the agents. (In the deterministic variant this was not always the case.) For the probabilistic variant of incen­ tive compatibility, the general-purpose dAGVA mecha­ nism could be used to yield the social welfare maximiz­ ing choice without burning money [d' Aspremont and Gerard-Varet, 1979; Arrow, 1979]. However, a seminal economic impossibility result shows that no mechanism for general quasilinear utility functions yields the social welfare maximizing choice, maintains budget balance, and satisfies the participation constraint (even the prob­ abilistic variant) [Myerson and Satterthwaite, 1983] . As the experiment above showed, automated mechanism design can circumvent this impossibility. It constructed a mechanism that satisfies all these desiderata, and actu­ ally the deterministic (i.e., stronger) variant of the par­ ticipation constraint.

• It created optimal mechanisms for public goods prob­ lems with multiple goods. This is the public goods ana­ log of combinatorial auctions.

8 Safe exchange mechanism design

Mechanism design is not only needed for deciding on an out­ come among agents. It is also key for executing the outcome. For example, if the outcome is a joint plan, how should it be executed so that no agent is motivated to deviate along the way [Braynov, 1994; Braynov and Sandholm, 1999]? From the perspective of markets, an important type of joint plan is the plan for exchanging items and payments between par­ ties. Nondelivery is a major problem in exchanges, especially in electronic commerce: the supplier might not deliver the goods or the demander might not pay. A recent study shows that 6% of consumers with on-line shopping experience re­ ported products or services that were paid for, but never re­ ceived [National Consumers League, 1999].

8.1 Deal chunking

In some settings, mechanism design can be used to enable safe exchanges without legal enforcement or escrow companies. One such approach is our methodology where the ex­ change is split into chunks which the agents deliver in alterna­ tion [Sandholm, 1996; 1997]. 18 The mechanism is practical when such splitting incurs little cost, as is the case with digital goods, computation time, many web services, and many in­ vestment instruments, for instance. eExchangeHouse, a safe exchange planner prototype, automatically determines a safe exchange plan for the exchange setting at hand such that nei­ ther party has incentive to vanish before completing the ex­ change [Sandholm and Ferrandon, 2000] . Only some ways of splitting the exchange into chunks and some sequences of delivering the chunks are safe in this sense [Sandholm, 1996; Sandholm and Lesser, 1995a]. The planner's algorithms for chunking and chunk sequencing provably find a safe ex­ change plan if one exists, and determine the shortest safe plan. The algorithms, as well as the amount of input that is solicited from the users, vary based on whether the exchanged items and units of each item are dependent or independent in terms of their value to the exchange parties.

8.2 A general model for safe exchange

In order to more broadly study the possibilities of using mechanism design to enable safe exchange, we developed a unified model of exchange mechanisms [Sandholm and Wang, 2002]. A key idea behind the model is that at any point of the exchange, each agent has a (potentially empty) set of items that he possesses, and a (potentially empty) allocation set that includes the items that he can reallocate-except not to himself--<>r destroy. The two sets need not be the same. An item can simultaneously be in one agent's possession set and in another agent's allocation set. Other aspects of the model include transfer costs and defection costs (how much of a reputation loss or risk would an agent face if he defaulted before completing the exchange).

The model captures the disparate earlier safe exchange approaches such as cryptographic coin ripping [Jakobsson, 1995], digital signatures, and our game-theoretic chunking mechanism discussed above. It also allows one to creatively and systematically think about, and analyze, novel exchange mechanisms. For example, our reputation locking mechanism stemmed from this model. It works as follows: 1) agent A al­ lows agent B to encrypt A's reputation in the public database (e.g., eBay), 2) agent B delivers to A, 3) agent A delivers to B, and 4) B decrypts ~s reputation back into plaintext. In this mechanism, A's reputation is used as a virtual item that is is temporarily transferred into B 's allocation set. If A does not deliver, B does not give back the reputation.

Being an overarching framework, the model also allows one to study what is inherently possible and impossible in safe exchange (with and without a trusted third party, and with an offline third party that only gets involved if the ex­ change fails).

9 Conclusions and perspective

Collective choice settings are ubiquitous and important, whether the agents are humans or software. Game theory provides a basis for engineering the incentives into the inter­ action mechanism so that a desirable outcome is chosen even though every agent acts based on self-interest. However, a host of computer science issues not traditionally addressed in game theory have to be addressed in order to make mech­ anisms work in the real world. Those computing, commu­ nication, and privacy issues are deeply intertwined with the economic incentive issues, as this writeup has illustrated.

18 Similar protocols have recently been studied by others, e.g. , [Matsubara and Yokoo, 2000].

Here, I would like to draw some high-level conclusions from the results presented above. Peer-to-peer negotiation suffers from negotiation process uncertainties that can be eliminated by using a mediator, such as an auction server, that collects the agents' private information and runs a clearing algorithm on that data to determine the outcome. 19 Domain uncertainty remains even in this approach, and leveled com­ mitment contracts can be used to mitigate it to the economic benefit of all contract parties. 20 Expressive competition is a new form of interaction that empowers market participants with potent expressiveness akin to human-to-human negotia­ tion (this has economic advantages and makes bidding easier) while at the same time harnessing the forces of competition, the global scale of the Internet, and the accuracy of market clearing with all relevant information in hand. The mediated approach with optimal clearing is feasible at a grand scale even with expressive competition, despite the fact that most variants of the clearing problem are hard and inapproximable in the worst case. The economic and computational efficien­ cies that mediated expressive competition offers suggest that in the future, marketplaces will merge into larger ones. To a certain extent this trend is already underway. For example, in the last couple of years large corporations have undergone a massive transition from plant-based procurement to global procurement.

The mediated approach can be made to require dramati­ cally less information from the agents-especially in combi­ natorial markets-by using selective incremental multiagent preference elicitation. This decreases the agents' valuation determination costs (and other preference determination ef­ forts) and communication costs. It also enhances privacy. It can be made into an incentive-compatible push-pull mecha­ nism where the information revelation is guided by both the elicitor (auctioneer) and each agent. This makes sense because each agent has private information that suggests what should be revealed by the agent, and the auctioneer accrues information about the other agents that affects what informa­ tion from the agent is pertinent.

19 The clearing algorithm-usually a specialized tree search--can run on multiple machines. This is usually the case in large-scale applications, but the machines are usually co-located rather than at each agent's location. Also, there is no notion of one machine repre­ senting one agent. So, the distribution that is motivated by compu­ tational efficiency does not correspond to the distribution of agents (that is, the distribution of self-interest and private information).

20 Leveled commitment can also mitigate the negotiation process uncertainty that arises if an agent participates in negotiations medi­ ated by different mediators, and the negotiations' outcomes are not independent from the perspective of the agent's valuation. In that sense, leveled commitment can serve as part of the "glue" needed between marketplaces. Furthermore, leveled commitment can be used to mitigate the uncertainty that arises if one mediator runs mul­ tiple clearings over time, for example at fixed intervals or every time a new bid arrives. (For online algorithms for market clearing, see [Blum et al., 2002) .)

A deeper look into an agent's evaluation problem shows that valuation determination costs ruin the incentives of clas­ sical auction mechanisms, and give rise to a new phenomenon I call strategic computing: using one's limited computing to approximate others' preferences at the cost of approximating one's own. Whether strategic computing occurs depends on the auction mechanism and the type of computational con­ straint (costly computing vs. limited computing).

While computational constraints can cause strategic prob­ lems, the reverse can also be made to be the case. Compu­ tational hardness can be used as the barrier to manipulation. This is especialy desirable in settings where economic mech­ anism design (incentive engineering) is known to fall short.

Computing can also be used to automatically design the mechanism, for instance the rules of a divorce settlement, auction, or public goods problem. Because the mechanism is designed for the specific setting at hand (objective and infor­ mation about the agents), it often yields a better mechanism than the ones known to date. It can also circumvent seminal impossibility results.

Carefully designed mechanisms are needed not only for choosing an outcome, but also for executing the outcome, such as a joint plan. I illustrated this in the context of de­ signing safe exchange mechanisms for anonymous parties in Internet commerce.

10 Future research directions

This is a fertile and relatively new area where AI and com­ puter science at large can have enormous theoretical and prac­ tical impact. Work on expressive competition includes the on­ going quest for faster clearing algorithms and the pursuit of concise-perhaps application-specific-forms of expressive bidding that are easy to use in bidding and elicitation, and fast to process by a clearing algorithm. Automated mechanism design is still in its infancy, and holds significant promise for future research. It should be tested on new classes of prob­ lems, and applied to real-world settings. It could also be ap­ plied to design safe exchange mechanisms (using the general safe exchange model that we introduced)-an endeavor that has traditionally taken considerable creativity, yet has not de­ livered mechanisms (or impossibility results) for all settings. Known game-theoretic results that characterize properties of mechanisms could be used to reduce the search space in au­ tomated mechanism design. Furthermore, automated mech­ anism design could be used on a variety of settings (real or artificially generated) to see whether new canonical mecha­ nisms and mechanism design principles can be inferred.

Another significant research stream arises from the obser­ vation that mechanism design should take into account the agents' computational constraints. Our performance profile tree based deliberation control method together with the idea of deliberation equilibrium provide a normative model of bounded rationality in multiagent systems, which is needed to determine how computationally constrained self-interested agents would behave in a given mechanism. This allows one to evaluate mechanisms for computationally constrained agents, and hopefully paves the way to designing such mech­ anisms. Not only auction and voting mechanisms, but also multiagent preference elicitation mechanisms should be de­ signed with this methodology. This methodology could also be used to design mechanisms that are computationally hard to manipulate, where hardness is measured not in terms of worst-case complexity, but informed by game-theoretic delib­ eration control. (Other approaches to improving upon worst­ case measures include designing mechanisms where manipu­ lation is average-case hard, or even hard on every-carefully constructed-instance such as in factoring.) This methodol­ ogy could even yield new mechanism design principles. As discussed, the central design principle in mechanism design, the revelation principle, ceases to meaningfully hold under computational or communication constraints. In such set­ tings it can be better to use multi-stage mechanisms such as preference eliciation, unlike the principle suggests. Also, in such settings it has been theoretically demonstrated that there is some benefit to allowing for mechanisms where in­ sincere preference revelation occurs [Conitzer and Sandholm, 2003d], unlike the principle suggests. Is there a significant practical benefit to be gained from such mechanisms? What would such mechanisms look like? Are there principles for constructing them?

Finally, are there unforeseen novel ways-beyond enabling expressive competition, multiagent preference elicitation, and automated mechanism design-of using computing to en­ hance collective choice?