Computational Aspects of Mechanism Design

Abstract

In a preference aggregation setting, a group of agents must jointly make a decision, based on the individual agents’ privately known preferences. To do so, the agents need some protocol (or mechanism) that will elicit this information from them, and make the decision. Examples of such mech-anisms include voting protocols, auctions, and exchanges. In most real-world settings, preference aggregation is con-fronted with the following three computational issues. First, there is the complexity of executing the mechanism. Second, when standard mechanisms do not apply to or are subopti-mal for the setting at hand, there is the complexity of design-ing the mechanism. Third, the agents face the complexity of (strategically) participating in the mechanism. My thesis statement is that by studying these computa-tional aspects of the mechanism design process, we can sig-nificantly improve the generated mechanisms in a hierarchy of ways, leading to increased economic welfare. Outcome optimization Even when all the agents ’ preferences are already known, computing the optimal outcome (for example, the one that maximizes the sum of the agents ’ utilities) can be nontriv-ial. For example, in a combinatorial auction, bidders are allowed to place bids on any subset of the items for sale. While the expressiveness that this provides to the bidders increases economic welfare, the winner determination prob-lem of deciding which bids to accept so as to maximize the total value is known to be NP-complete (Rothkopf, Pekeč, & Harstad 1998), even to approximate (Sandholm 2002). My thesis work includes new work on the winner de-termination problem in combinatorial auctions (Conitzer, Derryberry, & Sandholm 2004). It also introduces an ex-pressive bidding protocol for matching donations to chari-ties (Conitzer & Sandholm 2004e), as well as an expressive bidding protocol for general settings in which agents ’ ac-tions impose externalities on the other agents (that is, affect the other agents ’ utilities). Mechanism design with strategic agents While having a good outcome optimization algorithm is nec-essary for preference aggregation to be successful, it is not sufficient. The reason is that generally, the agents ’ prefer-ences are not known beforehand and will have to be elicited