64-67, References from Master's Project Report

References from my Master's Project Report that I keep forgetting to Blog!...

64, A simple procedure for finding equitable allocations of indivisible goods, by Dorothea Herreiner & Clemens Puppe, 2000.

65, Issues in Multiagent Resource Allocation, by Yann Chevaleyre et al, 2006.

66, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, by Reid G. Smith, 1980.

67, A task-swap negotiation protocol based on the contract net paradigm, by Matteo Golfarelli, Dario Maio & Stefano Rizzi, 1997.

68-69, Coloured Trails (CT) game

Looked through a couple of papers describing and running experiments using the Coloured Trails (CT) game for multi-agent resource negotiation:

68, The Influence of Social Dependencies on Decision-Making: Initial Investigations with a New Game, by Barbara J. Grosz, Sarit Kraus & Shavit Talman, 2004.

69, The Effects of Goal Revelation on Computer-Mediated Negotiation, by Ya'akov Gal et al, 2009.

Implementation referenced in [69] can be found here:
http://www.eecs.harvard.edu/ai/ct

56, Negotiating Socially Optimal Allocations of Resources

Can't believe I haven't blogged this paper ('Negotiating Socially Optimal Allocations of Resources', 2006, by Ulle Endriss et al) til now. Fundamental!

Individual Transferable Quotas

An article (idea) I came across that makes use of distributed negotiation and social welfare concepts:

"Iceland has not quite proved that fish can sing, but it has shown they can continue to flourish, even when hunted by their main predator, man. Central to its policy are the individual transferable quotas given to each fishing boat for each species on the basis of her average catch of that fish over a three-year period. This settles the boat’s share of the total allowable catch of that fish for the entire country. The size of this total is announced each year on the basis of scientific advice from the independent Marine Research Institute.

Subject to certain conditions, quotas can be traded among boats. Bycatch must not be discarded. Instead it must be landed and recorded as part of that boat’s quota. If she has exhausted her quota, she must buy one from another boat, though 20% of a quota may be carried forward a year, and 5% of the next year’s quota can be claimed in advance..."

(Source: The Economist, January 3rd 2009)

Distributed Coordination Procedures

Interesting paragraph found in the 'Related Research' section of 'Collective Iterative Allocation: Enabling Fast and Optimal Group Decision Making' (2008) by Christian Guttman, Michael Georgeff and Iyad Rahwan:

"Distributed coordination procedures are often investigated using the Multi-Agent Systems (MAS) paradigm, because it makes realistic assumptions of the autonomous and distributed nature of the components in system networks [...]. Many MAS approaces do not adequately address the 'Collective Iterative Allocation' problem as they use each agent's models separately to improve coordination as opposed to all agents using their models together. That is, each agent uses its own models to decide on allocating a team to a task even if other, more knowledgeable agents would suggest better allocations..."

49, An Empirical Study of Interest-Based Negotiation

Some notes noted whilst reading 'An Empirical Study of Interest-Based Negotiation' (2007) by Philippe Pasquier, Liz Sonenberg, Iyad Rahwan et al.

Assumptions of the paper (some which differ in my work (in progress)):

• The resources are not shared and all the resources are owned. Agents also have a finite amount of "money", which is part of the resources and it is the only divisible one.
• Uses numerical utility values ("costs", "benefits", "payments" etc based on this).
• Negotiation restricted to 2 agents.
• All agents have shared, common and accurate knowledge.
• No overlap between agents' goals, plans, needed resources etc, which avoids the problems of positive and negative interaction between goals and conflicts for resources.
• Both (i.e. all) agents use the same strategy. (Manipulable given that agents are out to maximise individual gains? Maybe but agents are assumed to be truthful.)

Additionally: "Agents do not have any knowledge about the partner's utility function (not even a probability distribution) and have erroneous estimations of the value of the resources not owned." It seems the primary benefit of IBN in this paper is to explore how agents can correct such erroneous information. (Agents trust each other not to lie about resource valuations.) A comparison is made between agents capable of bargaining only and agents capable of bargaining and reframing.

Content of the paper:

• Introduction and Motivations
• Agents with hierarchical goals (/plans)
• The Negotiation Framework (Bargaining and Reframing Protocols/Strategies)
• Simulation and Example
• Experimental Results (Frequency and Quality of the deals; Negotiation complexity)
• Conclusion and Future Work

47, Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types

Just read 'Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types' (1999) by Martin Andersson and Tuomas Sandholm following on from reading [46] yesterday. Some thoughts:

Nice discussion of distributed reallocative negotiation "versus" (centralized) (combinatorial) auctions at the end of page 1 continuing on page 2.

Multiagent Travelling Salesman Problem (page 2). Interesting.

The contracting system between agents ("contract sequencing") described on pages 4 and 5 is in essence an exhaustive search. Naturally, slow and cumbersome. Multi-agent dialogues and interest-based negotiation could perhaps play a role here. Also, no "algorithm" (contracting system) provided for OCSM-contracts, or even, contracts of mixed/different types.

I like the presentation of the results, i.e. comparing the different contract types in terms of (i) the outcomes (solution quality in terms of social welfare) reached, and (ii) the number of contracts tried and performed before an (local) optimum is reached.

Decentralized multiagent contracts

"Decentralized multiagent contracts can be implemented for example by circulating the contract message among the parties and agreeing that the contract becomes valid if every agent signs." ('Contract Types for Satisficing Task Allocation: I Theoretical Results' (1998) by T. W. Sandholm)

Alternatively to passing the contract around, something else to try: an agent noticing that a multiagent contract is necessary could broadcast a proposal of the multiagent contract to all prospective agents and if all agents agree, then the initiating agent could broadcast a confirmation to the recipients sealing the contract.

46, Contract Types for Satisficing Task Allocation: I Theoretical Results

Classification of contract types below taken from 'Contract Types for Satisficing Task Allocation: I Theoretical Results' (1998) by Tuoumas W. Sandholm. Very very important/related paper to keep referring back to. Will need to realise the OCSM-contract to achieve completeness in my work.

O-contract: one task given by an agent i to an agent j (+ contract price i pays to j for handling the task set).

C-contract: a cluster (more than 1) of tasks given by an agent i to an agent j (+ contract price i pays to j for handling the task set).

S-contract: swaps of tasks where agent i subcontracts a (single) task to agent j and vice-versa (+ amount i pays to j and amount j pays to i).

M-contract: A multi-agent contract involving at least three agents, wherein each agent involved gives away a single resource to another agent (+ payment).

Each contract type above is necessary (and avoids some of the local optima that the other three do not) but is not sufficient in and of itself for reaching the global optimum via "individually rational" contracts.

OCSM-contract: combines/merges characteristics of the above contract types into one contract type - where the ideas of the above four contract types can be applied simultaneously (atomically).

44, Towards Interest-Based Negotiation

Goal Arguments (which justify agents' adoption of certain goals) in the paper 'Towards Interest-Based Negotiation' (TIBN) by Iyad Rahwan et al take the form ((SuperG,B,SubG):G), i.e. an agent adopts (intends) a goal (G) because it believes G is instrumental to achieve its supergoal (SuperG), believes the context (B) which justifies G to be true and believes the plan (SubG) for achieving G to be achievable.

We identify here a few forms of attacks allowed (in TIBN) on these Goal Arguments for which we have equivalents in our multi-agent setting of 'On the Benefits of Argumentation for Negotiation' (OBAN).

(1)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬b where b is a belief in B, i.e. disqualifying a context condition.
- Similar attack in OBAN: Agent Y argues "I do not have resource R", where "you have resource R" is a belief agent X has (& utters) as part of either requesting R from Y or requesting R2 from Y. In the latter case, X's prior argument would be: "Y does not need R2 because Y has R (which alone is sufficient for fulfilling Y's goal)".

(2)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬p where p is a goal in SubG, i.e. a subgoal is unachievable.
- Similar attack in OBAN: Agent Y argues "I need to retain resource R (and hence your (sub)goal of obtaining R is unachievable)", where R is a resource agent X requests from Y.

(3)
- Attack: For a Goal Argument ((SuperG,B,SubG):R), show set of goals P such that achieve(P,G) where G is a goal in SuperG and R is not a goal in P, i.e. there is an alternative plan P which achieves the supergoal G and does not include R.
- Similar attacks in OBAN (in the case where R is a resource ("goal" in the language of TIBN) agent X requests from agent Y):
--- X argues "you do not need resource R (since you have a resource R2 that alone is sufficient for fulfilling your supergoal G)".
--- X argues "you do not need resource R (since I have a resource R2 that alone is sufficient for fulfilling your supergoal G and I will exchange with you R2 for R)".

27, On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation

Some thoughts following on from re-reading 'On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation' (2007) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:

• What is presented is a protocol and not a generative model as such.


• The negotiation framework consists of (/is limited to) two agents.


• Agents' preferences over (sets of) resources is specified as a (pre-given) numerical utility function. "Deals" between agents (to reallocate resources) make use of "side payments" based on this utility function.


• The relationship "sub" (linking a goal to "sub" -goals and/or -resources needed to achieve it) seems shared between all agents (though agents have no prior knowledge of each other's main goals or preferences).


• Much in this paper rests on the existence/allowance of "partial plans" (wherein leaf nodes may be goals as well as resources) and the setting of positive interaction between agents' "shared"/"common" goals such that an agent may benefit from a common goal (or sub-goal) achieved by the other agent.

EUMAS 08 Conference

Attended and presented at the EUMAS conference last week in Bath. Received some useful questions/feedback to think about, as follows:

• The title ('On the benefits of argumentation for negotiation - preliminary version') is a bit misleading (given the narrow scope of this work). Also, should think about potential/real drawbacks of using argumentation for negotiation as well as its benefits, i.e. look at things more objectively.


• Look at game-theoretic models. Contrast my work with theirs. Agents providing reasons/justifications with requests as in this paper would not be enough (in and of itself) to argue argumentation-based negotiation (ABN) over game-theoretic (GT) approaches. For example, the act of an agent providing a reason with a request may not always be advantageous; providing a reason could rule out an "offer" (in the mind of the recipient agent) that would otherwise have been acceptable. It may (also) not always be strategically advantageous for an agent to provide reasons with its requests since the recipient agent could use this against the requesting agent.


• Agents providing reasons with dialogue moves doesn't increase the number of solutions possible unless agents provide their overlying goals with their reasons, like the "hammer and nail" example in an earlier paper. Otherwise agents are only justifying their dialogue moves.


• How come reasons can be provided with a 'refuse' response but not with an 'accept'?


• The work of Nicolas Hormazabal ('Trust aware negotiation') could be useful.


• The presentation was perhaps overly simplistic. Looks a bit like I have created/used a problem/solution to justify argumentation and not the other way round, i.e. rather than creating/using an argumentative approach to solve a real problem. Also, sequences/concurrency of the dialogues: it was not clear from the presentation; it came across as though only one dialogue move/instance is made at a time in sequence regardless of the number of agents in the agent system.


• A story from Cuba (spurred by my bilateral agent negotiation approach): each person prefers the house of his neighbour (only) over his own, creating a big circle of potential swaps. Eventually, (if/) once the circle is established/known, each person moves into the house of his neighbour resulting in a happier society. Point being: why not have everyone report their desires/preferences publicly and have the final result/allocation decided upon centrally like in an auction? Wouldn't that be easier?

Multiagent Resource Alloaction

Nice definition (taken from the '3rd MARA Get-Together: Workshop on Multiagent Resource Allocation'):

"the allocation of resources within a system of autonomous agents that not only have preferences over alternative allocations of resources but also actively participate in computing an allocation."