Vincent Conitzer

Computational Aspects of Preference Aggregation Degree Type: Ph.D. in Computer Science
Advisor(s): Tuomas Sandholm
Graduated: August 2006

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 that will elicit this information from them, and make the decision. Examples include voting protocols, auctions, and exchanges. Mechanism design is the study of designing preference aggregation protocols in such a way that they work well in the face of strategic (self-interested) agents. In most real-world settings, mechanism design is confronted with various computational issues. One is the complexity of executing the mechanism. Particularly in expressive preference aggregation settings (such as combinatorial auctions), many mechanisms become hard to execute. Another is the complexity of designing the mechanism. When general mechanisms do not apply to, or are suboptimal for, the setting at hand, a custom mechanism needs to be designed for it, which is a nontrivial problem that is best solved by computer (automated mechanism design). Finally, there is the complexity of participating in the mechanism. In complex settings, agents with limited computational capabilities (bounded agents) will not necessarily be able to act optimally, which should be taken into account in the mechanism design process.

My thesis statement is that we can employ the study of computational aspects of the mechanism design process to significantly improve the generated mechanisms in a hierarchy of ways, leading to better outcomes (and a more efficient process). The dissertation outlines this hierarchy, and illustrates and addresses representative issues at various levels of the hierarchy with new results. It also serves as a significant step towards a longer-term research goal: realizing a mechanism design approach that addresses all of these issues simultaneously, comprehensively, and optimally, in settings with real-world complexity.

Thesis Committee:
Tuomas Sandholm (Chair)
Avrim Blum
Tom Mitchell
Craig Boutilier (University of Toronto)
Christos Papadimitriou (University of California, Berkeley)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Artificial intelligence, multiagent systems, electronic commerce, game theory, mechanism design, auctions and exchanges, voting