research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Publication

Type of publication:Article
Entered by:chita
TitleVoting almost maximizes social welfare despite limited communication
Bibtex cite IDRACTI-RU1-2011-41
Journal Artificial Intelligence
Year published 2011
Number 175
Pages 1655-1671
Abstract
In cooperative multiagent systems an alternative that maximizes the social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) have introduced the concept of distortion to quantify this gap. In this paper, we present the notion of embeddings into voting rules: functions that receive an agent¢s utility function and return the agent¢s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.
Authors
Caragiannis, Ioannis
Procaccia, A.D.
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
carag.pdf (main file)
 
Publication ID893