Lecture 1: Introduction
Negotiation
1
Motivating example:
Homes with electricity generating infrastructure can feed power into the network to help meet demand
Multiple power companies could be in a position to buy this power and sell it on to different clients
We need software agents to negotiate on our behalf to agree a fair price
Slide ‹#› out of 117
Today
Mechanisms for finding agreement
Key game theory concepts
Negotiation protocols
Task redistribution negotiations
Deception in negotiation
Slide ‹#› out of 117
Agreement mechanisms
Autonomous, self-interested agents need reach agreements on things such as how to allocate resources or tasks
An agreement protocol defines:
What moves the agents can make, e.g. offers, bids…
The permitted sequences of moves, e.g. you must respond to an offer with either an accept or reject
When the interaction terminates, e.g. one agent accepts the other’s offer, or no more bids are made within a set time frame
What the outcome of the interaction is, e.g. the highest bidder gets the item and must pay the amount that they bid
An agent’s strategy is how it decides which move to make at each point during the interaction
Slide ‹#› out of 117
Negotiation example
Golden balls game show
Each player has two golden balls, inside each one says split and one says steal.
Have to secretly look at which ball is which and choose one.
Both choose split, they share the jackpot.
Both choose steal, they get nothing.
One chooses split and the other chooses steal, the stealer gets all the money and the splitter gets nothing.
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
Dominant strategies
We can use concepts from game theory to analyse a negotiation
A strategy S is dominant if no matter what the other participants do, you can’t do any better than play S.
Exercise:
Is there a dominant strategy for a Golden Balls player?
What happens if they both behave rationally?
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
Nash equilibrium
A set of strategies, corresponding to a strategy for each of the participants (an outcome), are in Nash equilibrium if no participant can benefit from changing its strategy assuming the strategies of the others remain unchanged (stable).
Exercise:
If both Golden Balls players steal, is this a Nash equilibrium?
If both players split, is this a Nash equilibrium?
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
Pareto optimal outcomes
An outcome is Pareto optimal if in every other outcome where an agent is better off, at least one agent is worse off.
Exercise:
Which Golden Balls outcomes are Pareto optimal?
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
Social welfare
An outcome maximises social welfare if it maximises the sum of utility gained by all the agents.
Exercise:
Which Golden Balls outcomes maximise social welfare?
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
What would you do?
Player 2
Split Steal
Player 1 Split ££ ££££
££
Steal
££££
Slide ‹#› out of 117
Properties of agreement mechanisms
An agreement mechanism is…
individual rational if no agent will end up worse off as a result of participating
symmetric if the rules are the same for all participants
fair if participants have equal opportunity to influence outcome
Pareto optimal if it guarantees a Pareto optimal outcome
maximises social utility if it guarantees an outcome that maximises social utility
guaranteed to terminate if there is no way that participants following the protocol can continue to interact indefinitely
stable if a Nash Equilibrium exists
simple if it is easy to work out what the best strategy is
Slide ‹#› out of 117
Negotiation
For a negotiation setting, the negotiation set is the possible proposals that agents can make.
Negotiation usually proceeds in a series of rounds, with every agent making a proposal at every round.
Proposals made are defined by the agent’s strategy, must be drawn from the negotiation set, and must be legal as defined by the protocol.
Slide ‹#› out of 117
Negotiation
Negotiations can be single issue, e.g. over the price of a good
Preferences are symmetric
Obvious what represents a concession
or they can be multiple issue, e.g. a mobile phone contract with included call minutes, texts, data usage, upfront payment, monthly payment, flexibility to leave, upgrade possibilities…
Not obvious what represents a concession (can be exploited!)
Number of possible deals is for attributes with possible values, meaning it is often not feasible to consider all deals
In addition, negotiations may be one-to-one, many-to-one (e.g. an auction) or many-to-many
Slide ‹#› out of 117
Alternating offers protocol
The alternating offers protocol is a one-to-one protocol for bargaining for resource division
Agent 1 begins by making proposal x
Agent 2 can either accept or reject
If accepted, deal x is implemented
Otherwise negotiation moves to another round where agent 2 now starts by making a proposal
It is not guaranteed to terminate: agents can just keep rejecting
If there’s no agreement, we say the result is the conflict deal
We assume the conflict deal is the worst outcome, i.e. each agent prefers any other outcome over no agreement
Slide ‹#› out of 117
14
Alternating offers protocol
Consider we’re dividing a pie, so the negotiation set is:
Let’s start by assuming there is only 1 round (ultimatum game)
Agent 1 has all the power.
If Agent 1 proposes (1, 0), then this is still better for Agent 2 than the conflict deal
Agent 1 can do no better than this either (Nash equilibrium)
Slide ‹#› out of 117
Alternating offers protocol
If we have two rounds, the power passes to Agent 2.
Whatever Agent 1 proposes, Agent 2 rejects it.
Then Agent 2 proposes (0, 1).
Just as before this is still better for Agent 1 than the conflict deal and so it is accepted.
In general, if we set the number of rounds to some fixed value, whoever goes last will get all the pie.
Slide ‹#› out of 117
Alternating offers protocol
What if we have an indefinite number of rounds?
Let’s say that Agent 1 uses this strategy: Always propose (1, 0) and always reject any offer from Agent 2.
How should Agent 2 respond?
If agent 2 rejects, then there will never be agreement. – Conflict deal.
So accept. And there is no point in not accepting on the first round…
Depends on agent 2 knowing agent 1’s strategy!
Slide ‹#› out of 117
Alternating offers protocol
Players can be impatient: for outcome at times , agents prefer at
We model this as a discount on the outcome, where for each agent i: higher means more patience
A 1-round game is still the ultimatum game
With 2 rounds, agent 2 can again reject 1’s offer and offer (0,1) and get the whole pie, but it will be worth only
Agent 1 can take this into account and offer , ): agent 2 might as well accept as it can’t do better
If agent is offered , then the value of the slice is:
at time 0
at time 1
at time 2
…..
at time
Slide ‹#› out of 117
Alternating offers protocol
With unbounded rounds, agent 1 makes the proposal that gives agent 2 what they would be able to enforce for themselves in the second round, which agent 2 accepts
It works out that agent 1 gets of the pie and agent 2 gets the remainder
The more patient either player is the more pie they get.
Depends on strategic thinking about the other agent. Depends on knowing their strategy, and knowing their discount factor.
Slide ‹#› out of 117
If both have discount factor of ½:
1 gets (0.5)/0.75 = 2/3
2 gets (0.5-0.25)/0.75 = 1/3
If both have discount factor of 0.99
1 gets 0.5025
2 gets 0.4975
The more patient they both are, the result tends towards even split
19
Task Oriented Domains (TOD)
In a task oriented domain (TOD), agents have tasks to achieve and negotiation leads to task redistribution.
An example [Rosenschein and Zlotkin 1994]:
Your 3 children each need delivering to a different school each morning
Your neighbour has 4 children and also needs to take them to school
One of your children and one of your neighbour’s go to the same school
It makes sense for both children to be taken together, and only my neighbour or I will need to make the trip to carry out both tasks
You and your neighbour could come to an agreement better for both of you by carrying children to shared destinations, saving trips
The worst that happens is that you don’t agree and you are no worse off than if you were alone: you can only benefit from negotiation
Slide ‹#› out of 117
Task Oriented Domains (TOD)
A TOD is
An encounter is an initial allocation of task sets to agents
A deal δ is the allocation of task sets to agents after negotiation
The cost to i of deal δ, costi(δ), is c(Di) for δ =
The utility of deal δ to agent i is utilityi(δ) = c(Ti) – costi(δ)
The conflict deal is the deal with same allocation as encounter
Deal δ is individual rational if no agent prefers the conflict deal
The negotiation set is those deals that are individual rational and Pareto optimal
Slide ‹#› out of 117
Exercise
Tasks: {shop, cook, washUp, getVideo, tidy, buyWine}
Agents: {1, 2}
c({shop, cook, washUp}) = 12, c({getVideo, tidy, buyWine}) = 10,
c({cook, tidy, washUp}) = 9, c({shop, getVideo, buyWine}) = 6
Encounter: < {shop, cook, washUp}, {getVideo, tidy, buyWine} >
Deal: < {cook, tidy, washUp}, {shop, getVideo, buyWine} >
What is the cost of the deal to each agent?
What is the utility of the deal to each agent?
Is the deal individual rational?
Slide ‹#› out of 117
Monotonic concession protocol
Monotonic concession is a negotiation protocol for two agents:
Each round the agents simultaneously propose a deal
If in a round, one agent finds the other’s proposal is as good or better than its own, agreement is reached (if each proposal matches or exceeds the other then one is randomly selected)
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 u
If neither agent makes a concession in some round (no different proposal than the previous round), then negotiation terminates with the conflict deal
Slide ‹#› out of 117
Zeuthen strategy
The Zeuthen strategy determines what an agent should do by answering three questions.
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 equal risk, random).
If an agent concedes, then how much should it concede?
Just enough to change the balance of risk.
The strategy is in Nash equilibrium: if one agent is using the strategy the other can do no better than use it itself
This means there is no need for secrecy: an agent’s strategy can be publicly known without that being exploited
Slide ‹#› out of 117
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.
Willingness of i to risk conflict =
utility i loses by conceding and accepting j’s offer
utility i loses by not conceding and causing conflict
= utilityi(δi) – utilityi(δj)
utilityi(δi)
If utilityi (δi) = 0 (same as conflict deal), willingness to risk = 1.
δi = i’s current offer
δj = j’s current offer
Slide ‹#› out of 117
Exercise
Utility for agent i
Utility for agent j
Θ
δ4
δ1
δ3
1
6
7
2
4
5
6
δ5
δ6
δ2
2
A set of deals are shown, with utility given for
participating agents i and j negotiating using
the Zeuthen strategy.
What happens in the negotiation and why?
3
Slide ‹#› out of 117
Exercise
Postal workers A and B start at the post office and must deliver letters to houses. A task is represented by the house a letter must be delivered to. The cost of a set of tasks is the minimum distance the postal workers must travel to visit each of the houses she/he must deliver to and return to the post office.
The initial allocation of tasks is shown below, where nodes represent houses and the distance between each node is assumed to be 1. This encounter is formalised as ({b,f},{e}). The cost of the conflict deal to A is 8, and to B is 8.
The agents use the monotonic concession protocol
and the Zeuthen strategy.
What happens in the negotiation?
Slide ‹#› out of 117
Deception in TODs
An agent could pretend not to have been allocated all the tasks they have been: a hidden task
From the previous exercise, if A hides the fact that
he/she has been assigned task b in the
initial encounter, the only individual
rational and Pareto optimal deal is
({}, {e,f})
The final allocation will be ({b}, {e,f})
A will have utility 8 – 2 = 6
B will have utility 0
Slide ‹#› out of 117
Another scenario
In the example shown, the initial encounter is ({a,b},{a,b}) and the cost of this encounter to each agent is 6.
The Pareto optimal deals are where there is no
duplication of agents visiting the same house:
({a,b},{}), ({},{a,b}), ({a},{b}), ({b},{a}). All are
individual rational.
A will first propose ({}, {a,b}) and B will first
propose ({a,b}, {}).
Their willingness to risk conflict is the same:
A: (6 – 0)/6 = 1, B: (6-0)/6 = 1, so they concede
with equal chance.
If A concedes to ({b}, {a}), their willingness to concede becomes A: (4-0)/4 = 1, B: (6-2)/6 = 2/3. So B concedes.
If B now concedes to ({a}, {b}), willingness to risk is A: (4-2)/4 = 1/2, B: (4-2)/4 =1/2. So flip a coin, 50/50 chance that they will end up with each of ({a}, {b}) or ({b}, {a}).
Each agent’s expected utility is (0.5*2) + (0.5*4) = 3.
Slide ‹#› out of 117
Exercise
An agent could pretend to have been allocated a task it has not: a phantom task.
In the prior example, A lies to say that they have also been assigned the task of delivering to house c, giving the untruthful situation below.
What are the expected utilities of the
agents now?
Slide ‹#› out of 117
Summary
Mechanisms for finding agreement
Key game theory concepts
Negotiation protocols
Task redistribution negotiations
Deception in negotiation
Slide ‹#› out of 117
/docProps/thumbnail.jpeg