Thursday, 15 January 2009

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?