• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •

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.

(unavailable)

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.

@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 Mon Nov 16, 2020 22:25:46