Computational Social Choice: Algorithmic, Strategic, and Combinatorial Aspects

January 19, 2011
Lirong Xia | Duke University

When agents have conflicting preferences over a set of alternatives and they want to make a joint decision, a natural way to do so is by voting. How to design and analyze desirable voting rules has been studied by economists for centuries. In recent decades, technological advances, especially those in the Internet economy, have introduced many new applications for voting theory. For example, we can rate movies based on people’s preferences, as done on many movie recommendation sites. However, in such new applications, we always encounter a large number of alternatives or an overwhelming amount of information, which makes computation in voting processes a big challenge. Such challenges have led to a burgeoning area—computational social choice, aiming to address problems in computational aspects of preference representation and aggregation in multi-agent scenarios. The high-level goal of my research is to better understand and prevent the agents’ (strategic) behavior in voting systems, as well as to design computationally efficient ways for agents to present their preferences and make a joint decision.
Specifically, in this talk I will focus on a type of complete information voting games, where voters vote one after another sequentially. In such games a natural solution concept is subgame perfect equilibrium. I will discuss computational aspects of computing the winner, which is the same in all subgame perfect equilibria. Moreover, I will illustrate a ubiquitous paradox, which states that such a winner is sometimes extremely undesirable for almost every agent.

Speaker Details

Lirong Xia is a Ph.D. candidate of Computer Science at Duke University, under the supervision of Dr. Vincent Conitzer. He obtained an M.A. in Economics from Duke University in 2010 and plan to graduate with a Ph.D. degree in Computer Science in 2011. His research focuses on the intersection of computer science and microeconomics, in particular computational social choice, which has wide applications ranging from Economics and Political Science (e.g., presidential elections) to Computer Science (e.g., multi-agent systems). Among other topics, he has been working on computing and analyzing solution concepts in voting games, using computational complexity as a barrier against strategic behavior in voting systems, and developing and evaluating novel voting methods when the set of alternatives is exponentially large and has a combinatorial structure.