NDLI: Practical voting rules with partial information

Content Provider	Springer Nature Link
Author	Kalech, Meir Kraus, Sarit Kaminka, Gal A. Goldman, Claudia V.
Copyright Year	2010
Abstract	Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous work has typically assumed that voters send their complete set of preferences for computation, 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 and willingness to keep as much information private as possible. The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly, 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 an average of 35% savings in communications, while guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in practice, close approximations are obtained.
Starting Page	151
Ending Page	182
Page Count	32
File Format	PDF
ISSN	13872532
Journal	Autonomous Agents and Multi-Agent Systems
Volume Number	22
Issue Number	1
e-ISSN	15737454
Language	English
Publisher	Springer US
Publisher Date	2010-05-07
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multi-agent systems Computational social choice Voting User Interfaces and Human Computer Interaction Software Engineering/Programming and Operating Systems Computing Methodologies Computer Systems Organization and Communication Networks Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multi-agent learning

2APL: a practical agent programming language

Automated organization design for multi-agent systems

Multi-agent based classification using argumentation from experience

Formal approaches to multi-agent sysems

Agent communication and social concepts

Hierarchical multi-agent reinforcement learning

Guest editorial: special issue on computational social choice

Modeling dynamic environments in multi-agent simulation

Practical voting rules with partial information

Similar Documents

Multi-agent learning

2APL: a practical agent programming language

Automated organization design for multi-agent systems

Multi-agent based classification using argumentation from experience

Formal approaches to multi-agent sysems

Agent communication and social concepts

Hierarchical multi-agent reinforcement learning

Guest editorial: special issue on computational social choice

Modeling dynamic environments in multi-agent simulation

Practical voting rules with partial information