Silvia Rossi

Lezione n.

Corso di Laurea:

Insegnamento:

Email:

A.A. 2014-2015

Silvia Rossi

Negotiation

17

Informatica

Sistemi

multi-agente

silrossi@unina.it

Reaching Agreements - Negotiations

(W: 7.3, 7.3.1)

2

Negotiation

Auctions are only concerned with the allocation of goods: richer techniques for reaching agreements are required

Negotiation is the process of reaching agreements

on matters of common interest

What is Negotiation?

• Negotiation is a form of interaction in which a group of agents with conflicting interests try to come to a mutually acceptable agreement over some outcome.

• The outcome is typically represented in terms of the

allocation of resources (commodities, services, time, money, CPU cycles, etc.)

• Agents’ interests are conflicting in the sense that they

cannot be simultaneously satisfied, either partially or fully (=

trade-off)

• Automated negotiation would be negotiation that is automated with some computation support, e.g., fully

automated negotiation among computational agents, partially automated negotiation with a computational mediator with

human negotiators, etc.

4

Machines Controlling and Sharing Resources

Electrical grids (load balancing)

Telecommunications networks (routing) PDA’s (schedulers)

Shared databases (intelligent access)

Traffic control (coordination)

Heterogeneous, Self-motivated Agents

The systems:

•  are not centrally designed

•  do not have a notion of global utility

•  are dynamic (e.g., new types of agents)

•  will not act “benevolently” unless it is in their

interest to do so

Broad Working Assumption

•  Designers (from different companies,

countries, etc.) come together to agree on

standards for how their automated agents will interact (in a given domain)

•  Discuss various possibilities and their

tradeoffs, and agree on protocols, strategies, and social laws to be implemented in their

machines

What is Negotiation?

“Negotiation can be seem as a distributed search

through a space of potential agreements.” [Jennings 2001]

[Jennings 2001] N. R. Jennings, P. Faratin, A. R. Lomuscio, S. Parsons, C. Sierra and M. Wooldridge, Automated Negotiation: Prospects, Methods and Challenges, International Journal of Group Decision and Negotiation, 10(2):

199-215, 2001 8

What is Negotiation?

“Negotiation can be seem as a distributed search

through a space of potential agreements.” [Jennings 2001]

[Jennings 2001] N. R. Jennings, P. Faratin, A. R. Lomuscio, S. Parsons, C. Sierra and M. Wooldridge, Automated Negotiation: Prospects, Methods and Challenges, International Journal of Group Decision and Negotiation, 10(2):

199-215, 2001 9

Negotiation

Any negotiation setting will have different components:

•  A negotiation object, which defines the set of possible outcomes (possible proposals that agents can make)

•  A protocol according to which agents search for specific agreement

•  Strategies, one for each agent, which are private, based on their preferences over the outcomes

•  A rule that determines when a deal has been struck and what the agreement deal is

Negotiation usually proceeds in a series of rounds,

with every agent making a proposal at every round

Domain Theory

Task Oriented Domains

!  Agents have tasks to achieve

"  Task redistribution State Oriented Domains

!  Goals specify acceptable final states

!  Side effects

"  Joint plan and schedules Worth Oriented Domains

!  Function rating states’ acceptability

"  Joint plan, schedules, and goal relaxation

Negotiation Outcomes

• There are many ways to define the outcomes.

• Also called as agreements or deals.

• Characteristics

• Continuous or discrete

• Single issue or multiple issues

12

Example 1

• 1.0 litter milk between Alice and Bob

• The issue is (dividing) milk, that is single issue & continuous

• The possible outcome can be

represented as a number in interval [0,1.0].

• One possible outcome is 0.2l for Alice and 0.8l for Bob.

13

Example 2

• Parking slot 1 and 2 for Charles and Daniel

• The issue is 3 parking slots, that is single issue &

discrete

• The possible outcome can be represented as assignment of the parking slot

• One possible outcome is slot 1 for Charles and slot 2 for Bob

14

Example 3

• Buying a house between Seller and Buyer

• The issues are price, design, and place (3 issues), that is multiple issue (& discrete and continuous)

• The possible outcome can be represented as a tuple of values of the issues.

• One possible outcome is ($150,000, modern, Dunedin)

15

Negotiation in Task-Oriented Domains

Imagine that you have three children, each of whom needs to be delivered to a different school each

morning.

Your neighbor has four children, and also needs to take them to school.

•  Delivery of each child can be modeled as an indivisible task.

You and your neighbor can discuss the situation, and come to an agreement that it is better for both of you

(for example, by carrying the other’s child to a shared destination, saving him the trip)

.

--- Rules of Encounter, Rosenschein and Zlotkin, 1994

Negotiation in Task-Oriented Domains

Assumptions:

There is no concern about being able to achieve your task by yourself.

•  The worst that can happen is that you and your neighbor won’t come to an agreement about setting up a car pool, in which case you are no worse off than if you were alone.

You can only benefit (or do no worse) from your neighbor’s tasks.

•  Assume, though, that one of my children and one of my

neighbors’ children both go to the same school (that is, the cost of carrying out these two deliveries, or two tasks, is the same as the cost of carrying out one of them).

•  It obviously makes sense for both children to be taken

together, and only my neighbor or I will need to make the trip to carry out both tasks.

--- Rules of Encounter, Rosenschein and Zlotkin, 1994

TODs Defined

A TOD is a triple

<T, Ag, c>

where

T is the (finite) set of all possible tasks

Ag = {1,…,n} is the set of participating agents c = ℘(T) → R

defines the cost of executing

each subset of tasks (monotonic) An encounter is a collection of tasks

<T

,…,T

>

where T

⊆ T for each i ∈ Ag

Building Blocks

#  Domain

A precise definition of what a goal is Agent operations

Negotiation Protocol

A definition of a deal A definition of utility

A definition of the conflict deal Negotiation Strategy

In Equilibrium

Incentive-compatible

Deals in TODs

Given encounter <T

, T

>, a deal is an allocation of the tasks T

∪ T

to the agents 1 and 2

The cost to i of deal δ ^{= <D}

^{, D}

> is c(D

), and will be denoted cost

( δ ⁾

The utility of deal δ to agent i is:

utility

( δ ^{) = c(T}

^{) – cost}

⁽ δ ⁾

Deals in TODs

The conflict deal , Θ, is the deal <T

, T

>

consisting of the tasks originally allocated.

Note that utility

(Θ) = 0 for all i ∈ Ag

Deal δ is individual rational if it weakly dominates the conflict deal

A deal that is not dominated is pareto optimal

The Negotiation Set

The set of deals over which agents negotiate are those that are:

individual rational

pareto optimal

Example: Cake division

• When dividing one cake, it is Pareto optimal if the entire cake is completely divided and allocated to members, and there is no remaining pieces

• Pareto optimal does not mean fairness

23

The Negotiation Set Illustrated

Strategy

• Given a set of agents, their preferences, and an agreed protocol, the final ingredient is the agent’s strategy

• The strategy may specify what offer to make next or what information to reveal (truthfully or not).

• A rational agent’s strategy must aim to achieve the best possible outcome for him/her.

• Game-theory is analyzing agents’ strategic behavior.

Approaches

•  Bargaining: Game Theoretic Approaches

•  How game theory can be used to analyze negotiation.

•  Cooperative game or non-cooperative game

•  Assumptions:

•  Rules of the game, preferences & beliefs of all players are common knowledge

•  Full rationality on the part of all players (=unlimited computation)

•  Preferences encoded in a (limited) set of player types (utility functions)

•  Closed systems, predetermined interaction, small sized games

•  Heuristic Approaches (AI approach):

•  No common knowledge or perfect rationality assumptions needed

•  Agent behaviour is modeled directly

•  Suitable for open, dynamic environments

•  Space of possibilities is very large

•  Argumentation Approaches : out of scope in this course

•  Based on formal logics of dialogue games

Game Theoretical Approach: Nash Solution

• Definition: A bargaining problem is defined as a pair (S, d). A bargaining

solution is a function f that maps every barging problem (S, d) to an outcome in S, i.e., f(S,d)-> S

• S is bargaining set that is the set of all utility pairs result from an agreement.

• d is the disagreement point where each agent i gets ui(d) even if there is no agreement

• Definition : Nash solution is defined as follows:

• Nash product : (u1(x)-u1(d)) x (u2(x)-u2(d))

Nash Solution

• Nash proved that the solution that satisfies the five axioms below is Nash solution and its unique.

• Axiom 1 (Individual Rationality) : Each agent can get at least disagreement point. f(S,d) >= d.

• Axiom 2 (Symmetry) : The solution is independent form agent’s name, like A or B.

• Axiom 3 (Pareto Optimality)

• Axiom 4 (Invariance from Afine Transformation) : The solution should not change as a result of linear changes to the utility for either agent

• Axiom 5 (Independence of Irrelevant Alternatives) : Eliminating feasible alternatives that are not chosen should not affect the solution. Namely,

Other solutions: Egalitarial bargaining solution, Kalai-Smorodinsky bargaining solution

Negotiation Protocols

Agents use a product-maximizing negotiation protocol

It should be a symmetric PMM (product maximizing mechanism)

Examples: 1-step protocol, monotonic

concession protocol…

Alternating Offers Protocol

• This game is played over a series of discrete time periods t = 1,2,3,...

• The agents take turns in making offers.

• Concretely,

• t = 1, player A proposes an offer (Xa,t=1). If player B accepts A’s offer, they reach an agreement. If not (reject), goto t = 2.

• t = 2, player B proposes a counter offer (Xb,t=2). If player A accepts B’s offer, they reach an agreement.

If not (reject), goto t = 3.

• t = 3, ...

32

Characteristic of the Alternating offer protocol

• The utility is increasing in the player’s share and decreasing in time.

• This decrease in utility with time is modeled with a discount factor, and .

• If a and b receive a share of xa and xb respectively where xa + xb =1, then their utilities at time t are as follows:

33

Equilibrium of alternating offer protocol

• If this game is played infinitely overtime, then

Rubinstein showed that there is a unique (subgame perfect) equilibrium outcome in which the players immediately reach an agreement on the following shares:

p.s. there is no need to bargain

34

Drawbacks

• Rubinstein’s model does not take “deadlines” into account.

• There is nothing to prevent the agents from haggling for as long as they wish.

• A player’s bargaining power depends on the relative magnitude of the players’ respective costs of haggling.

• A lot of works on this line have been done.

35

Heuristic Approaches

• The heuristic approach is particularly useful when there are multiple issues to negotiate, and finding an equilibrium offer is computationally hard.

• Of course there are Game theoretic approaches to multi- issue negotiations (e.g. [Fatima2006]). However, here, heuristic approaches are more focusing on computational hardness, complex utilities, etc.

• [Fatima2006] S.S.Fatima, M.Wooldridge, and

N.R.Jennings, Multi-issue negotiation with deadlines.

Journal of Artificial Intelligence Research, 27:381-417, 2006.

36

The Monotonic Concession Protocol

Rules of this protocol are as follows…

Negotiation proceeds in rounds

On round 1, agents simultaneously propose a deal from the negotiation set

Agreement is reached if one agent finds that the deal

proposed by the other is at least as good or better than

its proposal

The Monotonic Concession Protocol

If no agreement is reached, then negotiation proceeds to another round of simultaneous proposals

In round u + 1, no agent is allowed to make a proposal that is less preferred by the other agent than the deal it proposed at time u

If neither agent makes a concession in some round

u > 0, then negotiation terminates, with the conflict deal

•  Negotiation is guaranteed to end (with or without agreement) after a finite number of rounds.

•  Does not guarantee that agreement will be reached

quickly.

Time Dependent Concession

• Suppose we have a buyer (the case of the seller is symmetrical) which desires to buy a good for an aspiration price Pmin and

reservation price Pmax (highest he is willing to pay); deadline is a time Tmax

• Price offered at time t will be:

• F(t) gives the fraction of the distance left between the first (best) offer and the reservation value

39

40

Time dependent concession

• Hard-headed (β->0): No concessions, sticks to the initial offer throughout (the opponent may concede, though)

• Linear time-dependent concession (β=1): Concession is linear in the time remaining until the deadline

• Boulware (β<1): Concedes very slowly; initial offer is maintained until just before the deadline

• Conceder (β>1): Concedes to the reservation value very quickly

• Tit-for-tat : Cooperating on the first move and then mirroring whatever the other player did in the preceding round

41

The Zeuthen Strategy

Three problems:

What should an agent’s first proposal be?

Its most preferred deal

On any given round, who should concede?

The agent least willing to risk conflict

If an agent concedes, then how much should it concede?

Just enough to change the balance of risk

Willingness to Risk Conflict

Suppose you have conceded a lot. Then:

Your proposal is now near the conflict deal In case conflict occurs, you are not much

worse off

You are more willing to risk conflict

An agent will be more willing to risk conflict if the difference in utility between its current

proposal and the conflict deal is low

Willingness to Risk Conflict

risk

=

The agent to concede on round t of negotiation

should be the one with the smaller value of risk.

how much?

just enough

If an agent does not concede enough, then on the next round, the balance of risk will indicate that it still has

most to lose from conflict, and so should concede again.

If an agent concedes too much, then it 'wastes' some of its utility.

The smallest concession necessary to change the

balance of risk - so that on the next round, the other agent will concede.

45

Nash Equilibrium Again…

The Zeuthen strategy is in Nash equilibrium:

under the assumption that one agent is using the

strategy the other can do no better than use it himself…

This is of particular interest to the designer of

automated agents. It does away with any need for

secrecy on the part of the programmer. An agent’s

strategy can be publicly known, and no other agent

designer can exploit the information by choosing a

different strategy. In fact, it is desirable that the

strategy be known, to avoid inadvertent conflicts.

Multi-issue Negotiation

• Single issue negotiations

• Example: seller and buyer for a bottle of wine negotiating over a price

• Multi-issue negotiations

• Example: seller and buyer negotiating for a house over multiple issues, price, place, style, architecture, etc.

• Trade-off between issues : An agent can make concessions in one or more issues in order to extract concessions in other issues

preferable to him/her

• Example

• Buyer concede about style instead of proposing nicer place.

• Seller concede about price instead of proposing un-preferred place.

47