Computational Social Choice: Algorithmic, Strategic, and Combinatorial Aspects

Опубликовано 17 августа 2016, 0:34

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.