50, Argumentation and Game Theory

Good paper (by Iyad Rahwan and Kate Larson) to come back to later when considering self-interested agents (i.e. those only interested in furthering individual goals) that argue strategically.

An agent type is such that an agent is capable of putting forward only a subset of all possible arguments in the argumentation framework. The notion of defeat (i.e. the defeat relation) is assumed common to all agents.

The kind of manipulation (lying) considered is that wherein agents hide some of their arguments. ("By refusing to reveal certain arguments, an agent might be able to break defeat chains in the argument framework, thus changing the final set of acceptable arguments.") An external verifier is assumed so that agents cannot create new arguments that they do not have in their argument set.

Reiterating, the key assumptions are:

1. There is a common language for describing/understanding arguments.
2. The defeat relation is common knowledge.
3. The set of all possible arguments that might be presented is common knowledge.
4. Agents do not know who has what arguments.
5. Not all arguments may end up being presented by their respective agents.

Even with the above assumptions, the authors show that agents may still have incentive to manipulate the outcome by hiding arguments.

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

New Argument-Based Negotiation Policy

Setting:
- An agent is initially allocated a set of resources, possibly none.
- Resources are not divisible. An agent either has a particular resource or it does not.
- Resources are not shareable. No two agents have the same resource.
- An agent has at most one goal, possibly none.
- Goals are fulfilled by single resources.
- A certain goal may be fulfilled by a choice of different resources.
- A certain resource may fulfil a choice of different goals.

Allowed dialogues:
- Request dialogue between two agents (an initiator and a responder), each agent involved gives away at most one resource.
- Proposal dialogue between three or more agents (an initiator and a set of responders), each agent involved gives away at most one resource.
- A reason (Conclusion, Support) is provided with refusal/rejection only.

Pros of the policy:
- Computes the right solution (i.e. maximum number of agents fulfil their goal) when agents share all resource-goal 'fulfils' plans (from the outset).
- It is an 'any-time algorithm', i.e. resources are reallocated in such a way that the 'social welfare' does not decrease at any point. Also, the resource allocation can be modified as agents enter the system (without decreasing the 'social welfare' at any point).

Cons of the policy:
- Wasteful in number of requests/proposals. Instead, maybe, agents should ask initially, "do you have any resource that can fulfil my goal given that I know these resources (Rs) fulfil my goal?"

Experimentation

Note to self: Test any (multi-agent resource reallocation) (argument-based) negotiation policies I propose/develop against alternatives proposed/developed by others, argument- or interest- based or otherwise, even if it means mapping/translating. Also, test outcomes (and maybe efficiency, complexity and such measures) of any negotiation policies I propose/develop against outcomes reached by a centralized (all-knowing, maybe) procedure.

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

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?