RI: Small: New Directions in Computational Social Choice and Mechanism Design

Duke University, Durham NC

Investigators

Abstract

We often need to make collective decisions: who will represent us as president, where will we all go out for dinner tonight, who will receive the award, and so on. Similar problems are faced in multiagent systems in artificial intelligence. What are the best procedures for reaching such decisions? The agents could vote over the outcome, but what should the exact procedure be? This is studied in the theories of social choice and mechanism design, with the latter focusing particularly on agents that act strategically in their own self-interest. However, an ever-increasing amount of activity is moving online, and collective decision making is no exception. For example, we rate or vote on content, products, and people online. Key aspects of these novel applications are not present in the traditional models of social choice and mechanism design. For example, in an Internet-based mechanism, who gets to and who will participate? How can we know that a single agent is not participating multiple times? How can we allow agents to meaningfully participate when the number of voting events is potentially overwhelming? The proposed research aims to extend the traditional models to incorporate these aspects and to develop new algorithmic and other techniques to ensure outcomes are meaningful and increase economic efficiency and human welfare. In many domains, multiple self-interested agents need to make a collective decision. The theory of social choice concerns how such collective decisions should be made. Closely related, the theory of mechanism design concerns how to design mechanisms for such problems that result in good outcomes even when agents behave strategically. In recent years, major progress has been made on understanding the computational aspects of both social choice and mechanism design. In the proposed research, the PI and his team set out to adapt these techniques to novel domains such as those enabled by the Internet or the availability of new data. For example, one key issue is the identity of the participating agents. In an Internet-based mechanism, who gets to and who will participate? How can we know that a single agent is not participating multiple times? The PI and his team aim to address such issues with techniques based on social network structure, as well as on the effort that agents expend participating. Another key issue is the possibility of agents strategically providing inaccurate data. Again, explicit modeling of the agents' effort costs in doing so will play a key role.