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

62, Agents that reason and negotiate by arguing

A seminal piece of work ('Agents that reason and negotiate by arguing', 1998, Simon Parsons, Carles Sierra, Nick R Jennings). Finally went through it after 3 years! Need to compare it with my (A)ABA-based ABN framework.

Nice examples of 'negotiation' dialogues (proposal, critique, counter-proposal, explanation) in Section 2.1. Would be nicer if they can be *generated*.

Can't see how the stuff in Sections 3-5 (agent architecture etc) links to the negotiation protocol in Section 2.2.

No concept of 'assumptions' or the ability for agents to reason (make decisions/utterances) despite incomplete information. We allow for this.

No implementation, though it is claimed there is a clear link between the formal (agent architecture) model and its practical instantiation. We support our framework with an implementation.

The framework is based on an ad hoc system of argumentation. Arguments can be classified into rough classes of acceptability, but this is not enough to determine the acceptability of arguments. Also, only inconsistency *between* agents is considered; inconsistency that arises within an agent is not considered/handled. We base our framework on a general argumentation system (AABA) for which the argument acceptability semantics are clearly defined.

This is what I intend to include in the Related Work section of my forthcoming "argmas09paper":

In [61] a negotiation language and protocol is presented that allows for the exchange of complex proposals which can include compelling arguments for why a proposal should be adopted. Whilst [61] does not concentrate on the way in which arguments are built and analysed, the work is extended in [62] by indicating how argumentation can be used to construct proposals, create critiques, provide explanations and meta-information. However, even in [62], further expansion is required for agents to be able to generate and rate arguments, and for any kind of implementation to be produced. In particular, the acceptability classes used in [62] to rank arguments are not sufficient to resolve inconsistencies that may arise within and between agents. A more fine-grained mechanism is required. We use an existing argumentation framework (AABA) for this purpose, that is able to build and determine the acceptability of arguments, even as the knowledge bases of agents change over time (as a result of the dialogues). The AABA framework also allows agents to make assumptions, enabling agents to make decisions even despite incomplete information. Lastly, we supplement our formal model with an implementation.

61, A framework for argumentation-based negotiation

Old paper ('A framework for argumentation-based negotiation', 1998, Carles Sierra et al) but some really good ideas for using negotiation (offer, request, accept, reject and withdraw acts) with persuasion (appeal, threaten and reward acts). However, like most other papers, not fully worked out / generative.

To its advantage, the framework is for multi- (i.e. more than two) agent settings: "Deals are always between two agents, though an agent may be engaged simultaneously in negotiation with many agents for a given deal."

The 'attacks' relationship between "argument pairs" (i.e. argument Arg supporting a formula p) is assumed to be a primitive notion, though however argument pairs are not assumed to be primitive notions. Defining such an 'attacks' relationship could get messy!

An authority relation (between agent roles) is used as the mechanism for comparing arguments, i.e. who puts forward an argument is as important (maybe more so) than what is said. Potentially this doesn't quite make sense in an argument evaluation sense - depends what is meant by "argument". See last paragraph of Section 4.1.1 of 'Argumentation-Based Negotiation' (1998).

60, Dialogue games that agents play within a society

Went through this journal paper ('Dialogue games that agents play within a society', 2009, Nishan C. Karunatillake et al) and the accompanying technical report ('Formal Semantics of ABN Framework', 2008, Nishan C. Karunatillake et al) following going through the main author's thesis. Questions similar to the thesis (see 59). In addition, this is what I plan on including in my forthcoming (argumentation-based negotiation social optimality) paper...

"... The argument-based negotiation framework of [60] is supplemented with a number of concrete negotiation strategies which allow agents to exchange arguments as part of the negotiation process. The example scenario/context considered allows for multiple (more than two) agents. However, contrary to our approach, the semantics of arguments is not considered. Instead, the focus is on using argumentation as a metaphor for characterising communication among agents. Also, deals involving more than two agents are not possible, as is required in our resource allocation setting in order to reach optimal allocations. ..."

59, Argumentation-Based Negotiation in a Social Context

This ('Argumentation-Based Negotiation in a Social Context', Nishan C. Karunatillake, 2006) is the third thesis I have gone through now. I really liked, and read fully, the first three chapters. Quite a few question marks penned when going through the protocol and operational semantics in Chapter 3 - questions regarding the method of arguing (challenging and asserting). Apparantly these questions are addressed in a later journal paper and technical report, which I will go through now. It is worth noting that the negotiation/argumentation strategies defined in later chapters are far (in my opinion) from using the full capacity of the framework defined in Chapter 3.

I really liked the scenario presented in Chapter 4.1. Very good - lots of scope for play/conflicts/etc. Though however, the system model following this in Chapter 4.2 becomes very mathematics/number-based. The "argue" method doesn't really argue. It is quite similar to my "argmas09" paper - the responding agent provides a reason for rejection which the proposing agent incorporates into its knowledge-base for future proposals.

The strategies defined in Chapter 5.1 for the experimentation (empirical analysis) I thought were rather random - seems to be no justification at all for these strategies over any other. I couldn't quite see the general applicability of the results presented in Chapter 5.3 beyond the specific application setting of this paper. I skipped/glossed over to the summary.

Chapter 6 proceeds by simplifying the experimental scenario defined in Chapter 4.1 for the argumentation strategies to be defined in this chapter. Really not clear what the defeat-status computation (to determine the validity of a claim/premise) used in these strategies is. Also, I couldn't quite work out how the argumentation was done in the strategies - not clear what is being challenged/asserted. This chapter could have done with some examples.

48, A Multi-Agent Resource Negotiation for the Utilitarian Social Welfare

Very good point about compensatory side payments (and limits of agent budgets) on page 4 (Section 2 - Transaction).

Also, good summary of Toumas Sandholm's peer-to-peer negotiation work (rational and non-rational sequences of transactions, optima, etc) on page 4 (Section 2.1 - Convergence).

Nice conclusion to return back to.

48, A Multi-Agent Resource Negotiation for the Utilitarian Social Welfare

Quite related to my (work in progress) paper 'On the benefits of argumentation for negotiation'. The paper studies various "agent behaviours" in order to identify which one leads the most often (by means of local interactions between the agents) to an (global? T(ransaction)-global?) "optimal" resource allocation.

Main contribution of the paper: Providing/designing/exhibiting an (explicit negotiation) process that is able to converge, in practice, either towards a global optimum, or towards a near optimal solution (resource allocation). Also, to compare the social value of the resource allocation that is reached at the end of the negotiation process with the globally optimum social value (obtained by means of a 0-1 linear program).

Not sure how this work differs from Andersson & Sandholm's (1999) [47] except in considering incomplete 'contact networks'.

Assumptions of the paper:
- Bilateral Transactions (i.e. transactions betweens 2 agents only).
- Positive additive utility function which is comparable between agents.
- Resources are discrete, not shareable, not divisible, not consumable (static) and unique.
- No compensatory side payments.
- Sequential negotiations, i.e. only one agent at a time is able to (initiate) negotiation, though this does not seem significant in affecting the quality of the (social welfare of the) final allocation reached.
- (Implicitly:) Agents are truthful in reporting utilities. (This works in the case of "socially" transacting agents since agents are out to maximise social welfare and not individual welfare).
- All agents in a "contact network" (agent system) must use the same transaction type.

Content of the paper:
- Introduction (MARA problem; Contact network; Social welfare)
- Transaction (Convergence; Acceptability criteria; Transaction type; Communication Protocol)
- Experiments (Experiment protocol; Evaluation criteria; Optimal value determination)
- Social Gift (Behaviour variants; Behaviour efficiency; Proof of convergence; Egalitarian efficiency of the social gift)

Linking it to my work:
- It may be an idea to define argumentative negotiation policies that are based on "rational transactions" as well as "social transactions" (gifts, swaps and cluster-swaps) and to compare outcomes from each.
- What if agents could use gift, swap and cluster-swap transactions intermittently, as well as transactions involving multiple (3+) agents? Would that improve outcomes of negotiation (wrt the global optimum)? The former (mixing transaction types) is not considered in this paper. The latter (multi-agent transactions) is not possible (using the communication protocol of figure 1).
- Could interest-based negotiation (exchanging arguments etc) offer benefits in terms of path to solution in the original set-up as well as the two-additional set-ups described in the previous point?

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.

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

European Workshop on Multi-Agent Systems

Quick update to say that I participated in the Fifth European Workshop on Multi-Agent Systems (EUMAS 07) earlier this month, which took place in Hammamet, Tunisia.

A great first-time experience, every step of the way: from writing the paper (Bilateral Agent Negotiation with Information-Seeking) and getting it reviewed to presenting and discussing it with those unfamiliar with my work. To add, it was really beneficial listening in and getting a feel for other ongoing research in the field of Multi-Agent Systems, especially that which is still in the early preliminary stages, like mine.

38, Agent Technology for e-Commerce

Contents of 'Agent Technology for e-Commerce' (2007), Maria Fasli

1, Introduction

(A paradigm shift; Electronic commerce; Agents and e-commerce)

2, Software Agents

(Characteristics; Agents as intentional systems; Making decisions; Planning; Learning; Architectures)

3, Multi-agent Systems

(Interaction; Agent communication; Ontologies; Cooperative problem-solving)

4, Shopping Agents

5, Middle Agents

6, Recommender Systems

7, Elements of Strategic Interaction

(Economics; Game Theory)

8, Negotiation I

(Protocols; Auctions)

9, Negotiation II

(Bargaining; Coalitions; Social choice problems; Argumentation)

10, Mechanism Design

11, Mobile Agents

12, Trust, Security and Legal Issues

(Trust; Electronic institutions; Reputation systems; Security; Cryptography)

Distinguishing Agents

Quotes taken from 'Agent Technology for e-Commerce' (2007), Maria Fasli

A paradigm shift (page 5):

"... What distinguishes agents from other pieces of software is that computation is not simply calculation, but delegation and interaction; users do not act upon agents as they do with other software programs, but they delegate tasks to them and interact with them in a conversational rather than in a command mode. Intrinsically, agents enable the transition from simple static algorithmic-based computation to dynamic interactive delegation-based service-oriented computation..."

The novelty in agents (page 8):

"So what is it that makes agents different, over and beyond other software? Whereas traditional software applications need to be told explicitly what it is that they need to accomplish and the exact steps that they have to perform, agents need to be told what the goal is but not how to achieve it. Then, being 'smart', they will actively seek ways to satisfy this goal, acting with the minimum intervention from the user. Agents will figure out what needs to be done to ahieve the delegated goal, but also react to any changes in the environment as they occur, which may affect their plans and goal accomplishment, and then subsequently modify their course of action..."

32, Reaching Agreements Through Argumentation

Notes taken from 'Reaching agreements through argumentation: a logical model and implementation' (1998), Sarit Kraus, Katia Sycara, Amir Evenchik

1, Introduction

2, The Mental Model

Classification of intentions:
- "Intend-to-do", refers to actions within the direct control of the agent.
- "Intend-that", refers to propositions not directly within the agent's realm of control, that the agent must rely on other agents for satisfying.

(The Formal Model, Syntax, Semantics)

Agent Types: Bounded Agent, An Omniscient Agent, A Knowledgeable Agent, An Unforgetful Agent, A Memoryless Agent, A Non-observer, Cooperative Agents

3, Axioms for Argumentation and for Argument Evaluation

The argument types we present (in order of decreasing strength) are:
(1) Threats to produce goal adoption or goal abandonment on the part of the persuadee.
(2) Enticing the persuadee with a promise of a future reward.
(3) Appeal to past reward.
(4) Appeal to precendents as counterexamples to convey to the persuadee a contradiction between what she/he says and past actions.
(5) Appealing to "prevailing practice" to convey to the persuadee that the proposed action will further his/her goals since it has furthered others' goals in the past.
(6) Appeal to self-interest to convince a persuadee that taking this action will enable achievement of a high-importance goal.

"... Agents with different spheres of expertise may need to negotiate with each other for the sake of requesting each others' services. Their expertise is also their bargaining power..."

(Arguments Involving Threats, Evaluation of Threats, Promise of a Future Reward, Appeal to Past Promise, Appeal to "Prevailing Practice", Appeal to Self Interest, Selecting Arguments by an Agent's Type, An Example: Labor Union vs. Management Negotiation, Contract Net Example)

4, Automated Negotiation Agent (ANA)

The general structure of an agent consists of the following main parts:
- Mental state (beliefs, desires, goals, intentions)
- Characteristics (agent type, capabilities, belief verification capabilities)
- Inference rules (mental state update, argument generation, argument selection, request evaluation)

(The Structure of an Agent and its Life Cycle, Inference Rules for Mental State Changes, Argument Production and Evaluation, Argument Selection Rules, Request Evaluation Rules, The Blocks World Environment, Simulation of a Blocks World Scenario)

5, Related Work

(Mental State, Agent Oriented Languages, Multi-agent Planning, Automated Negotiation, Defeasible Reasoning and Computational Dialectics, Game Theory's Models of Negotiation, Social Psychology)

6, Conclusions

Group Buying

Taken from 'Performance of software agents in non-transferable payoff group buying' (2006), by Frederick Asselin and Brahim Chaib-Draa

... Group buying is a natural application domain for research on coalition formation in a multi-agent system (MAS). Consumers have an incentive to regroup with the unit price reduction as a function of the number of units bought by the group. However, as more and more consumers become members of the same group, there is an increase in the number of compromises that each consumer must make in order to agree on the product bought by the group...

Supply Chain Library

Taken from 'Modelling Supply Chain Dynamics: A Multiagent Approach' (1998), Jayashankar M. Swaminathan, Stephen F. Smith and Norman M. Sadeh

"We classify different elements in the supply chain library into two broad categories - Structural Elements and Control Elements. Structural elements (modeled as agents) are involved in actual production and transportation of products, and control elements help in coordinating the flow of products in an efficient manner with the use of messages. Structural elements correspond to agents and control elements correspond to the control policies in our framework. Structural and Control elements are further classified as follows:

Structural Elements
- Production (Retailer, Distributor, Manufacturer, Supplier)
- Transportation (Vehicles)

Control Elements
- Flow (Loading, Routing)
- Inventory (Centralized, Decentralized)
- Demand (Forecast, Marketing)
- Supply (Contracts)
- Information (Real-time, Periodic)

As well as the above, there is also the Customer.

26.4-6, Argument-based Negotiation among BDI Agents

Notes taken from 'Argument-based Negotiation among BDI Agents' (2002), by Sonia V. Rueda, Alejandro J. Garcia, Guillermo R. Simari

4, Collaborative Agents

Collaborative MAS: A collaborative Multi-Agent System will be a pair of a set of argumentative BDI agents and a set of shared beliefs.

(Negotiating Beliefs; Proposals and Counterproposals; Side-effects; Failure in the Negotiation)

5, Communication Languages

(Interaction Protocol; Interaction Language; Negotiation Primitives)

6, Conclusions and Future Work...