CS代考 Lecture 1: Introduction – cscodehelp代写
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?
