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)".

45, Mass argumentation and the semantic web

This paper ('Mass argumentation and the semantic web' by Iyad Rahwan) contains some useful links (footnotes 1-5 & 9) and a very useful background (Sections 1 and 2). The rest of the paper is not really (directly) related to my research though.

Content of the paper: "Argumentation theory - a crash course", "Arguing on today's web", "Arguing on the semantic web", "An infrastructure for unified semantic argument annotation".

44, Towards Interest-Based Negotiation

Some thoughts following on from reading 'Towards Interest-Based Negotiation' (2003) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:

The paper contains some nice ideas about goal selection which would (/could!) be useful in a (larger) context of multi-agent negotiation (/resource allocation) and in building a generative model (as I intend), but the work here leaves much unspecified and is not generative in and of itself. What is presented in Section 5 ("Dialogues about Goals") is a protocol. No policy or strategy is defined. This is left for future work. I will read the authors' newer paper ('An Empirical Study of Interest-Based Negotiation') to see if this is done and also any other related (later papers) by the authors.

In addition, the framework deals with agent systems consisting of two agents only.

Content of the paper: "Arguing about goals vs Arguing about beliefs", "Agents and goal support" (goals and beliefs/subgoals/supergoals/roles/adoption), "How to attack a goal" (attacking beliefs/subgoals/supergoals), "Dialogues about goals".

"Goal arguments" are presented to be of the form (H:G), where H is the triple support (SuperGoal,Beliefs,SubGoals) for G.

An interesting question, identified as outside the scope of this paper, is: How does an agent, given a top-level goal, generate (from the various options) the set of (sub-) goals to achieve? Suggested approaches: consider the costs of adopting different plans as well as the utilities of the goals achieved, or, identify the goal(s) with the strongest support.

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?

Microfinance / BRAC

I made a mental note yesterday to read up on ‘microfinance’ later today when, lo and behold, I conveniently stumbled upon this advert on my way to university earlier today (the ...’s identify parts that I have skipped):

“... Crowded into thousands of impoverished villages. Powerless and therefore poor. Poor and therefore powerless.

Where to begin?...

Start with one village. Identify the stakeholders, the believers, the leaders who could make change happen. That would be women.

First, disaster relief. Then... Then... Then microfinance, the indispensible multiplier, the key to scaling up.

Money to pay for a cow. Fresh milk and something wondrous called ‘income’. The cow became a dairy, then a milk distribution business...

Soon there was $5 billion in micro-loans, 7 million borrowers, 265,000 village organizations, 52,000 schools, 8.5 million jobs and new ventures in eight other Asian and African countries...”

(Source: ‘BRAC’ advert found in ‘The Economist’, www.brac.net)

If anyone has information or recommended reading/listening/viewing regarding microfinance/microloans, please share. Thanks.

jabberwacky chatbot

Really cool chatbot:
http://www.jabberwacky.com
Have a conversation with it, or one of its variants:
http://www.jabberwacky.com/george
http://www.icogno.com/joan.html

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."

Argument evaluation in implementations of negotiation policies

Finished modifying the implementations of the eumas- and aamas- negotiation policies to use (call) the new general argument evaluation procedure. Seems to be working fine (in Linux).

Running the implementations on Windows

Still having problems compiling and running the eumas- and aamas- implementations in Windows. The problem seems to be with the Windows Sicstus prologbeans libraries but I am not entirely sure. Will leave this for know, complete the implementations for Linux and maybe return to this later.