1 Scope
The scope of this specification is Interaction Protocols. More specific this IP specification contains a voting/election mechanism that represents the true wishes of participating voters. The protocol contains a suitable structure to reach an agreement.
2 Main Specification Body
In the FIPA Borda Count IP, the initiator agent attempts to find a consensus choice that represents the true preferences in a group’s election. The participant agents in the group election constitute collective rational behaviour in the sense that they have rankings, which are complete and transitive. The term “Borda Count” derives from the mechanism proposed by Borda [Borda, 1781], who recommended this election system that gave a better representation of what the people really want (better than the ‘one man, one vote’ system and the pairwise comparison). Using the Borda Count mechanism means that, in principle, points are allocated to a collection of alternative strategies. In a collection of X alternatives, X points will be allocated to the most preferred strategy, X-1 to the next best, and so on down to the least preferred strategy, which is allocated one point. The protocol requires that all voters have to rank their preferences among the X alternatives, except if the Borda Count calculator decides otherwise. The protocol is used then at a central location to add up the allocated points. The preferences are collected centrally to rank the scores given to each strategy, and to select the strategy with the maximum score as the winner. This specification presents a version of the Borda Count mechanism in which co-operating agents find a most preferred choice within a set of alternatives.
2.1 Explanation of the Protocol flow
The Initiator starts the Borda Count protocol by soliciting proposals from other agents by issuing a request act to n agents and a parameter “in-reply-to” as time constraint. The set of alternatives has been made known in advance and the task/action to be performed is ranking the alternatives. The n agents receiving the request (the participants) are able to generate proposals to perform the requested action/task as propose acts. Alternatively, the other agents may refuse to propose or send a not-understood. Once the deadline passes; the Initiator checks any received proposals and starts to make the Borda Count calculations. The Borda Count calculation, as described above, takes place between the propose and inform acts in figure 1. The Borda Count calculation gives the Borda Count winner that represents the winning candidate (alternative). When the calculation is made by the Initiator he wants to propose this final result to the other agents as an inform act. The result is the winning alternative, which can be performed as action, since it represents an strategy.
When the number one preference (the Borda Count winner) of the group is calculated the Initiator can refine it by iterating the mechanism. The Participants can have the ability to make another proposal when the Initiator decides to make a new request. This opportunity to make a new (second) proposal is almost the same as used in the English Auction IP and is especially used to refine the result. The decision for a second request is the responsibility of the Initiator. If there is not time enough the Initiator just calculates the Borda Count winner, which defines the action to be taken. After the calculation the Initiator sends the inform act.
The main reason why the Initiator would send another request will be made clear in the following description. After the agents have send their proposals the Initiator can make a reject-proposal or accept-proposal depending on the preference-proposal send. Then the Initiator takes some time to consider whether he undertakes:
Action A: He makes his final decision.
or,
Action B: He asks for more proposals (in case when he received reject-proposals he can decide to make a new iteration)
For action A he send the agents the inform act to inform all the agents which alternative strategy is going to be followed. For action B he makes another request (request2 in figure 1).
The representation of this IP is given in Figure 1.
|
Figure 1: FIPA Borda Count Interaction Protocol |
2.2 Exception to Interaction Protocol Flow
Real world issues of cancelling actions, asynchrony, abnormal or unexpected IP termination, nested IPs, and the like, are explicitly not addressed here
3 References
[FIPA00023] FIPA Agent Management Specification. Foundation for Intelligent Physical Agents, 2000. http://www.fipa.org/specs/fipa00023/
[Saari, 1994] Prof. Dr. Donald G. Saari, Geometry of voting, studies in Economic Theory 3, Springer-Verlag ISBN 3-540-57199-X, Northwestern University.
[Hopmans & Braspenning, 2002] Reaching consensus in agent systems with the help of the Borda Count Interaction Protocol. Abstract available and presented at the International workshop on Multi-Agent Interoperability, 25th German Conference on Artificial Intelligence (KI-2002) September 2002, Aachen Germany, sponsored by FIPA http://www.tzi.de/mai02/.
[Borda, 1781] Borda, J.C., 1781, Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, Paris.
[Mukherjee et al. 2001] Rajatish Mukherjee, Partha Sarathi Dutta and Sandip Sen, Movies2Go – A new approach to online movie recommendation, http://www.lumio.com/lc/ijcai/papers/mukherjee.pdf
[Hopmans, 2002] Hopmans, G., F-One Racing-MAS & the Borda Count Interaction Protocol, Co-operating agents to achieve a collective goal in Formula One Racing. Master of Science Thesis, University of Maastricht, November 2002, http://www.fipa.org/resources/details.html#F-OneRacing