Gal A. Kaminka's Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Practical Voting Rules with Partial Information

Meir Kalech, Sarit Kraus, Gal A. Kaminka, and Claudia V. Goldman. Practical Voting Rules with Partial Information. Journal of Autonomous Agents and Multi-Agent Systems, 22(1):151–182, 2011.

Download

(unavailable)

Abstract

Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous works typically assume that the voters send their complete set of preferences to calculate, and in fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send a complete set of preferences due to communication limitations. This goal of this paper is to empirically evaluating algorithms to reduce communication on various sets of experiments. To this goal we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments with simulated and real-world data show that this algorithm results in approximately 50% savings in communications, while guaranteeing to find the actual winning candidate. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee finding a true winning candidate, we show that in practice, it finds close approximations.

Additional Information

BibTeX

@Article{jaamas11voting,
 author = {Meir Kalech and Sarit Kraus and Gal A. Kaminka and Claudia V. Goldman},
 title = {Practical Voting Rules with Partial Information},
 journal = JAAMAS,
 year = {2011},
 OPTkey = {},
 volume = {22},
 number = {1},
 pages = {151--182},
 OPTmonth = {Jan},
 OPTnote = {},
 abstract = { Voting is an essential mechanism that allows multiple agents to reach a joint 
  decision. The joint decision, representing the preferences of all agents, is the winner among 
  all possible (candidate) decisions.  To compute the winning candidate, previous works 
  typically assume that the voters send their complete set of preferences to calculate, and in 
  fact this has been shown to be required in the worst case. However, in practice, it may be 
  infeasible for all agents to send a complete set of preferences due to communication 
  limitations. This goal of this paper is to empirically evaluating algorithms to reduce 
  communication on various sets of experiments. To this goal we propose an iterative 
  algorithm that allows the agents to send only part of their preferences, incrementally. 
  Experiments with simulated and real-world data show that this algorithm results in 
  approximately 50\% savings in communications, while guaranteeing to find the actual winning 
  candidate. A second algorithm applies a greedy heuristic to save up to 90\% of 
  communications. While this heuristic algorithm cannot guarantee finding a true winning 
  candidate, we show that in practice, it finds close approximations. },
 OPTannote = {}
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Jul 23, 2017 22:08:49