We propose here a multi-party negotiation game where agents exchange offers over a single issue. Contrary to most of existing works, we capture the agents' rationality with incomplete (weak and partial) preferences rather than with utility functions. We prove that our negotiation process is always successful and reach fair agreements when the agents are cooperative. In order to illustrate how our negotiation game can tackle distributed problem solving, we introduce a toy problem: two or more agents are paratroopers landed in an unknown maze. Since they aim to meet as soon as possible, they negotiate a rendezvous during their exploration. Our experimentations show that the added value of negotiation is a fast resolution since this adaptive heuristic shares the efforts performed by the agents.
AlpernS. and GalS., The Theory of Search Games and Rendezvous, Springer, 2003.
2.
AydoganR., BaarslagT., HindriksK.V., JonkerC.M. and YolumP., Heuristic-based approaches for CP-nets in negotiation, in: Complex Automated Negotiations, Springer, (2013), 113-123.
3.
BaarslagT., DirkzwagerA., HindriksK.V. and JonkerC.M., The significance of bidding, accepting and opponent modeling in automated negotiation, in: Proc of 21st European Conference on Artificial Intelligence, IOS Press, Prague, Czech Republic, (2014), 27-32.
4.
BaarslagT., FujitaK., GerdingE.H., HindriksK., ItoT., JenningsN.R., JonkerC., KrausS., LinR., RobuV. and WilliamsC.R., Evaluating practical negotiating agents: Results and analysis of the 2011 international competition, Artificial Intelligence198 (2013), 73-103.
5.
BarberàS., BossertW. and PattanaikP.K., Handbook of Utility Theory, chapter Ranking sets of objects, Springer, 2004.
6.
BouveretS., EndrissU. and LangJ., Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods., in: Proc of the 17th European Conference on Artificial Intelligence (ECAI), Lisbon, Portugal, (2010), 387-392.
7.
HerreinerC.P.D., A simple procedure for finding equitable allocations of indivisible goods, Social Choice and Welfare19(2) (2002), 415-430.
8.
EndrissU., Monotonic concession protocols for multilateral negotiation, in: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), ACM, Hakodate, Japan, (2006), 392-399.
9.
EstivieS., ChevaleyreY., EndrissU. and MaudetN., How equitable is rational negotiation? in: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), ACM, Hakodate, Japan, (2006), 866-873.
10.
FaratinP., SierraC. and JenningsN.R., Negotiation decision functions for autonomous agents, Robotics and Autonomous Systems24(3-4) (1998), 159-182.
11.
FatimaS. and RahwanI., Multiagent Systems, chapter Negotiation and Bargaining, MIT Press, 2013, pp. 143-176, second edition.
12.
GoodmanL.A. and MarkowitzH., Social welfare functions based on individual rankings, American Journal of Sociology58(3) (1952), 257-262.
13.
JenningsN., FaratinP., LomuscioA., ParsonsS., WooldridgeM. and SierraC., Automated negotiation: Prospects methods and challenges, Group Decision and Negotiation (GDN)10(2) (2001), 199-215.
14.
KrausS., Strategic Negociation in Multiagent Environments, MIT Press, 2001.
15.
MorgeM. and MancarellaP., Arguing over goals for negotiation: Adopting an assumption-based argumentation decision support system, Group Decision and Negotiation23(5) (2014), 979-1012.
16.
NongaillardA., MathieuP. and JaumardB., A multi-agent resource negotiation for the utilitarian welfare, in: Engineering Societies in the Agents World IX, 9th International Workshop (ESAW), Revised Selected Papers, Saint-Etienne, France, (2008), 208-226.
17.
M. Öztürk, TsoukiàsA. and VinckeP., Multiple Criteria Decision Analysis: State of the Art, chapter Preference Modelling, Springer, 2012.
RahwanI., RamchurnS.D., JenningsN.R., McburneyP., ParsonsS. and SonenbergL., Argumentation-based negotiation, The Knowledge Engineering Review (KER)18(4) (2004), 343-375.
20.
RawlsJ., A Theory of Justice, Harvard University Press, 1971.
21.
RosenscheinJ. and ZlotkinG., Rules of Encounter - Designing Conventions for Automated Negotiation Among Computers, MIT Press, 1994.
22.
RubinsteinA., Perfect equilibrium in a bargaining model, Econometrica50(1) (1982), 97-102.
23.
SandholmT. and VulkanN., Bargaining with deadlines, in: Proc of Sixteenth National Conference on Artificial Intelligence (AAAI), Orlando, Florida, (1999), 44-51.
24.
ShohamY. and Leyton-BrownK., Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2008.
25.
SycraK., Persuasive argumentation in negotiation, Theory and Decision28(3) (1990), 203-242.
26.
BoellaG. and Van Der TorreL., A game theoretic approach to contracts in multiagent systems, guido boella and leendert van der torre, IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews6(1) (2006), 68-79.
