EUROCORES LogiCCC (collaboration led by Dr. Edith Elkind): Computational Foundations of Social Choice.
Lead Research Organisation:
University of Southampton
Department Name: Electronics and Computer Science
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
Organisations
Publications
Aseere A
(2010)
A Voting-Based Agent System for Course Selection in E-Learning
Aziz H
(2011)
False-Name Manipulations in Weighted Voting Games
in Journal of Artificial Intelligence Research
Aziz H
(2014)
False-Name Manipulations in Weighted Voting Games
Bachrach Y
(2009)
Algorithmic Game Theory
Bachrach Y
(2009)
The Cost of Stability in Coalitional Games
Bošnacki D
(2009)
On commutativity based Edge Lean search
in Annals of Mathematics and Artificial Intelligence
Chalkiadakis G
(2014)
Cooperative Games with Overlapping Coalitions
Chalkiadakis G
(2010)
Cooperative Games with Overlapping Coalitions
in Journal of Artificial Intelligence Research
David, Esther; Gerding, Enrico; Sarne, David; Shehory, Onn
(2010)
Agent-mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets: AAMAS Workshop, AMEC 2009, Budapest, Hungary, May 12, 2009, and IJCAI Workshop, Tada 2009, Pasadena, CA, USA, July 13, 2009, Selected and Revised Papers
| Description | The principal goal of this research is to study foundational issues in social choice theory, which is concerned with decision mechanisms, such as voting and auctions, in order to aggregate individual preferences and reach a collective decision. Traditionally, theoretical research in economics and social sciences was focused on asking whether a certain mechanism has some desirable properties (e.g., incentive compatibility, non-manipulability, etc.). However, to use these results in real-world applications such as e-commerce or online voting, the participants should be able to construct the mechanism and/or compute their strategies. Often, they have to do so in real time, and their computational resources are limited. Therefore, it becomes essential to ensure that the solutions proposed by the research community satisfy the criterion of efficient computability, a concept that originates in computer science, but has found applications to various areas of natural and social sciences. The goal of this project was to design robust mechanisms for a range of problems in social choice using techniques developed in the areas of algorithms and complexity theory. Specifically, we have shown that computational hardness can be used as a barrier to dishonest behaviour in several types of voting scenarios. Furthermore, we developed computationally efficient allocation algorithms for auctions. We considered several voting scenarios, including safe voting, where a manipulation is called safe it is guaranteed to be no worse for the person manipulating. Furthermore, we considered bribery scenarios where a manipulator can try and bribe other voters in order to manipulate the outcome. |
| Exploitation Route | The findings can be used by others in the field of computational social choice and the algorithms could be applied in the real world. |
| Sectors | Creative Economy,Digital/Communication/Information Technologies (including Software) |