Transcript AI Models of Negotiation For the Social Sciences: What

AI Models of Negotiation For
the Social Sciences:
What Should Be in an AI-and-Law Model of
Negotiation?
Ronald P. Loui
Computer Science and Engineering / Legal Studies
Washington University in St. Louis
USA
Life's To-Do List
…
Lecture at the Sorbonne in French
…
…
Become a President Obama appointee
(was Obama really at ICAIL 2001?)
…
December 06
JURIX 2006 KeyNote 2
Loui
What There Is in AI and Law
on Negotiation:
AI techniques for modelling legal negotiation E Bellucci, J Zeleznikow - … ICAIL, 1999
Family_Winner: integrating game theory and heuristics to provide negotiation support
J Zeleznikow, E Bellucci - JURIX, 2003
…ODR Environment: Dialogue Tools and Negotiation Support Systems …
AR Lodder, J Zeleznikow - Harvard Negotiation Law Review, 2005
Integrating Artificial Intelligence, Argumentation and Game Theory to Develop an Online
Dispute …
E Bellucci, AR Lodder, J Zeleznikow - Tools with Artificial Intelligence, 2004. ICTAI 2004.
A framework for group decision support systems: Combining AI tools and OR techniques
NI Karacapilidis, CP Pappis - European Journal of Operational Research, 1997
Mediation Systems
T Gordon, O Märker - Online-Mediation, 2002
A simple scheme to structure and process the information of parties in online forms of
alternative ODR
GAW Vreeswijk - Proceedings of the First International ODR Workshop (2003)
Model Checking Contractual Protocols
A Daskalopulu - Arxiv preprint cs.SE/0106009, 2001
December 06
JURIX 2006 KeyNote 3
Loui
Where I Start:
December 06
JURIX 2006 KeyNote 4
Loui
Where I Start:
SocSci 174. International Problem Solving. Roger Fisher (Law School).
My first freshman lecture at Harvard, first A, …
Tutorial: The Russian Army will get bogged down in Afghanistan
Term Paper: The Pershing II's should be deployed in Europe
December 06
JURIX 2006 KeyNote 5
Loui
Principled Negotiation
Appeals
To reason or precedent
Not merely to position of power
December 06
JURIX 2006 KeyNote 6
Loui
Principled Negotiation
Appeals
To reason or precedent
PERSUADER, Sycara 89, Parsons-Jennings 96
Persuasive argumentation in negotiation
KP Sycara - Theory and Decision, 1990
Collaborative plans for complex group action
BJ Grosz, S Kraus - Artificial Intelligence, 1996
Negotiation through argumentation—a preliminary report
S Parsons, NR Jennings - ICMAS, 1996
Arguments, dialogue, and negotiation
L Amgoud, S Parsons, N Maudet - ECAI, 2000
Argument-based negotiation among BDI agents
SV Rueda, AJ Garcıa, GR Simari - Journal of Computer Science and
Technology, 2002
December 06
JURIX 2006 KeyNote 7
Loui
Principled Negotiation
Appeals
To reason or precedent
PERSUADER, Sycara 89, Parsons-Jennings 96
Persuasive argumentation in negotiation
KP Sycara - Theory and Decision, 1990
Arguing about plans: Plan representation and reasoning for
mixed-initiative planning
G Ferguson, J Allen - AIPS, 1994
Collaborative plans for complex group action
BJ Grosz, S Kraus - Artificial Intelligence, 1996
Negotiation through argumentation—a preliminary report
S Parsons, NR Jennings – ICMAS, 1996
Arguments, dialogue, and negotiation
L Amgoud, S Parsons, N Maudet - ECAI 2000
Argument-based negotiation among BDI agents
SV Rueda, AJ Garcıa, GR Simari - Journal of Computer Science and Technology, 2002
December 06
JURIX 2006 KeyNote 8
Loui
Principled Negotiation
Appeals
To reason or precedent
PERSUADER, Sycara 89, Parsons-Jennings 96
Persuasive argumentation in negotiation
KP Sycara - Theory and Decision, 1990
Understanding the Role of Negotiation in Distributed Search
Among Heterogeneous Agents
SE Lander, VR Lesser - IJCAI, 1993
Collaborative plans for complex group action
BJ Grosz, S Kraus - Artificial Intelligence, 1996
Negotiation through argumentation—a preliminary report
S Parsons, NR Jennings - ICMAS, 1996
Arguments, dialogue, and negotiation
L Amgoud, S Parsons, N Maudet - ICMAS, 2000
Argument-based negotiation among BDI agents
SV Rueda, AJ Garcıa, GR Simari - Journal of Computer Science and Technology, 2002
December 06
JURIX 2006 KeyNote 9
Loui
Principled Negotiation
Appeals
To reason or precedent
Not To position of power
December 06
JURIX 2006 KeyNote 10
Loui
Un-Principled Negotiation
Appeals
Not To reason or precedent
To position of power
December 06
JURIX 2006 KeyNote 11
Loui
Un-Principled Negotiation
Appeals
To position of power
Enforceable agreements
Unenforceable agreements
No institutional context
Game Theoretical Models of Negotiation
x Solution Concept
x Nash Equilibria
x MultiAgent Ecommerce Systems
December 06
JURIX 2006 KeyNote 12
Loui
Un-Principled Negotiation
Appeals
To position of power
Enforceable agreements
Unenforceable agreements
No institutional context
Game Theoretical Models of Negotiation
x Solution Concept
x Nash Equilibria
- A Beautiful Mind, shared Nobel Prize
x MultiAgent Ecommerce Systems
- Computers & Thought Winner 03
December 06
JURIX 2006 KeyNote 13
Loui
Un-Principled Negotiation
Appeals
To position of power
Enforceable agreements Badly
Unenforceable agreements
mistaken path
No institutional context
Game Theoretical Models of Negotiation
x Solution Concept
x Nash Equilibria
x MultiAgent Ecommerce Systems
December 06
JURIX 2006 KeyNote 14
Loui
Un-Principled Negotiation
Appeals
To position of power
Enforceable agreements
Newer "Institutional Economics" Nobel prizes
Unenforceable agreements
No institutional context
Game Theoretical Models of Negotiation
x Solution Concept
x Nash Equilibria
x MultiAgent Ecommerce Systems
December 06
JURIX 2006 KeyNote 15
Loui
AI Model of Negotiation:
Venk Reddy (Harvard) 93, Mark Foltz (WU/MIT), 95
Kay Hashimoto (Harvard), 96
Diana Moore's (WU) B.Sc. Thesis, 95-97
Anne Jump (Harvard), 97-98
All undergrads
But whom would you have model a social
phenomenon?
People who who have VERY good social skills
OR
Someone who thinks human interaction is like
playing chess (von Neumann)
December 06
JURIX 2006 KeyNote 16
Loui
AI Model of Negotiation:
Diana Moore's B.Sc. Thesis,
Dialogue and Deliberation, 97
Agents that reason and negotiate by arguing
S Parsons, C Sierra, N Jennings - Journal of Logic and
Computation, 1998
Cited by 328
December 06
JURIX 2006 KeyNote 17
Loui
AI Model of Negotiation:
Diana Moore's B.Sc. Thesis, 97
Search
Dialogue/Protocol
Persuasion/Argumentation
Log-rolling/Problem Reformulation
Process
December 06
JURIX 2006 KeyNote 18
Loui
AI Model of Negotiation:
Diana Moore's B.Sc. Thesis, 97
Search
Mixed-initiative planning/NLP-Pragmatics
Heuristic valuation of payoffs
Dialogue/Protocol
This AI and Law community
Persuasion/Argumentation
Multiagent systems community
Log-rolling/Problem Reformulation
Mixed-initiative planning/NLP-Pragmatics
Process
Today's Talk
December 06
JURIX 2006 KeyNote 19
Loui
AI-and-Law Model of
Negotiation
Offer/acceptance at the level of
Scenarios
Phrases
Terms
Uncertainty as to
How claims might fare if pressed
Whether the scenario might occur
How the language might evolve
How the case law (or standards) might evolve
December 06
JURIX 2006 KeyNote 20
Loui
AI-and-Law Model of
Negotiation
BATNA/security expressed as a RISK position
Strong norms for
Progress
Explanation/ Questions and Answers
Start with utility-payoffs
To connect with social scientists
To be precise & compact
I already have a few stories to tell here
December 06
JURIX 2006 KeyNote 21
Loui
Pessimism-Punishment (PP)
Agents
Observation: parties to a negotiation
(can) construct a probability distribution
over potential settlements
December 06
JURIX 2006 KeyNote 22
Loui
December 06
JURIX 2006 KeyNote 23
Loui
Breakdown (BATNA)
December 06
JURIX 2006 KeyNote 24
Loui
Breakdown (BATNA)
December 06
JURIX 2006 KeyNote 25
Loui
December 06
JURIX 2006 KeyNote 26
Loui
Party 1's
aspiration
Party 2's
aspiration
December 06
JURIX 2006 KeyNote 27
Loui
Party 1's
proposals at t
Party 2's
proposals at t
December 06
JURIX 2006 KeyNote 28
Loui
inadmissible
(dominated)
at t
inadmissible
(dominated)
at t
December 06
JURIX 2006 KeyNote 29
Loui
In black:
admissible
settlements
at t
(probability
of agreement
Is non-zero)
December 06
JURIX 2006 KeyNote 30
Loui
Breakdown
column
Breakdown
row
December 06
JURIX 2006 KeyNote 31
Loui
Breakdown
would occur
here
(BATNA)
December 06
JURIX 2006 KeyNote 32
Loui
1's security
level
1 would
rather break
down
2's security
level
2 would
rather break
down
December 06
JURIX 2006 KeyNote 33
Loui
Prob(bd) = ?
Eu1|s = 51
Eu2|s =
49α +54(1-α)
December 06
JURIX 2006 KeyNote 34
Loui
Pessimism-Punishment (PP)
Agents
Observation: parties to a negotiation (can)
construct a probability distribution over
potential settlements
Observation: from a probability distribution
over potential settlements, there is an
expected utility given settlement
Observation: there is a probability of
breakdown p(bd)
December 06
JURIX 2006 KeyNote 35
Loui
Pessimism-Punishment (PP)
Agents
Observation: from a probability
distribution (at t) over potential
settlements, there is an expected utility
given settlement (at t)
Observation: there is a probability of
breakdown pt(bd)
December 06
JURIX 2006 KeyNote 36
Loui
Pessimism-Punishment (PP)
Agents
Definition: At t, calculate
1. An expected utility given settlement (Eut|s) and
2. An expected utility given continued negotiation,
Eut = (Eut |s) (1 - pt(bd)) + u(bd) pt(bd)
Definition: Rationality requires the agent, at t, to:
1. Extend an offer, o, if Eut < u(o)
2. Accept an offer, a, if Eut < u(a),
a  offers-to-you(t)
3. Break down unilaterally if Eut < u(bd)
December 06
JURIX 2006 KeyNote 37
Loui
Pessimism-Punishment (PP)
Agents
Pessimism
Empirical Observation: At sufficient granularity,
p(bd) is decreasing in the time since last progress
December 06
JURIX 2006 KeyNote 38
Loui
Pessimism causes Eu to fall
Next offer is made at this time
Expectation starts to fall again
December 06
JURIX 2006 KeyNote 39
Loui
Agreement reached as Eu < u1
December 06
JURIX 2006 KeyNote 40
Loui
offers
reciprocated offers
December 06
JURIX 2006 KeyNote 41
Loui
Whenever u(acc) > security,
acceptance occurs before breakdown!
Best offer received
security
December 06
JURIX 2006 KeyNote 42
Loui
Would you accept an 11-cent offer if your
security were 10-cents?
Best offer received
security
December 06
JURIX 2006 KeyNote 43
Loui
Pessimism-Punishment (PP)
Agents
Observation: You wouldn't accept 11¢ over 10 ¢
security, nor 51 ¢ over 50 ¢ security
Observation: You wouldn't let your kid do it
Observation: Your Mother wouldn't let you do it
Observation: Your lawyer wouldn't let you do it
Observation: Your accountant wouldn't let you do it
Proposition: We shouldn't automate our agents to do it
December 06
JURIX 2006 KeyNote 44
Loui
Pessimism-Punishment (PP)
Agents
Question: Isn't this an issue of distributive
justice
Answer: Substantive fairness is trivial to
model by transforming utilities
Observation: There may (ALSO) be a
procedural fairness issue
December 06
JURIX 2006 KeyNote 45
Loui
Pessimism-Punishment (PP)
Agents
Procedural fairness:
the more the other party withholds progress,
the more you will punish
When the other party resumes cooperation, you
are willing to forgo punishment
December 06
JURIX 2006 KeyNote 46
Loui
Pessimism-Punishment (PP)
Agents
Resentment
u(bd) = security + resentment(t)
What is resentment?
1.
2.
3.
4.
5.
Dignity
Pride
Investment in society
Protection against non-progressive manipulators
A GENUINE source of satisfaction:
non-material, transactional, personal(?), transitory(?)
December 06
JURIX 2006 KeyNote 47
Loui
Pessimism-Punishment (PP)
Agents
Resentment
ut(bd) = security + resentment(t)
= u(bd) + r(t)
for NP(t), non-progress for a period t
What is resentment?
6. Attached to a speech/dialogue act:
BATNA through breaking down vs.
BATNA through agreement
7. A nonstandard utility (process utility)
8. Specific or indifferent (I-bd-you vs. you-bd-me)
December 06
JURIX 2006 KeyNote 48
Loui
Eu never falls to u1
December 06
JURIX 2006 KeyNote 49
Loui
Actually accepts because
resentment resets with progress
Nontrivial progess
Resentment resets to zero each time there is progress
December 06
JURIX 2006 KeyNote 50
Loui
Agent breaks down before accepting
Resentment might not reset to zero if there is memory
December 06
JURIX 2006 KeyNote 51
Loui
(Assumes no progress)
Linear pess/linear specific pun
low-valued ρ
December 06
high-valued ρ
JURIX 2006 KeyNote 52
Loui
(Assumes no progress)
Linear pess/linear indifferent pun
low-valued ρ
December 06
high-valued ρ
JURIX 2006 KeyNote 53
Loui
(Assumes no progress)
Exponential pess/linear indifferent pun
low-valued ρ
December 06
JURIX 2006 KeyNote 54
high-valued ρ
Loui
(Assumes no progress)
Exponential pess/sigmoidal specific pun
rare alternation between
breakdown and acceptance
December 06
JURIX 2006 KeyNote 55
Loui
Pessimism-Punishment (PP)
Agents
Variety of Plausible Behaviors
Agent
Agent
Agent
Agent
Agent
Agent
Agent
can
can
can
can
can
can
can
make a series of offers, responds to offers
wait, then offer, accept, or break down
accept, offer, or break down immediately
offer before accepting and vice versa
breakdown before accepting and vice versa
offer before breaking down and vice versa
be on path to breakdown, then on path to acceptance
because received offer changes Eu or resentment
because extended offer changes Eu
Concessions in time can be motivated
Laissez-faire paths can be steered
December 06
JURIX 2006 KeyNote 56
Loui
What happens when two P&P agents interact?
Dominated
by BATNA
2's aspiration
Eu2
BATNA =
<u1(bd),u2(bd)>
2's offer in
this round
1's offers in
this round
1's aspiration
December 06
Eu1
JURIX 2006 KeyNote 57
Loui
What happens when two P&P agents interact?
Eu2
Eu1(t=1)
December 06
Eu1(t=2)
JURIX 2006 KeyNote 58
Loui
What happens when two P&P agents interact?
2's
security+
resentment
1's
security+
resentment
1's offers
in this round
December 06
JURIX 2006 KeyNote 59
Loui
What happens when two P&P agents interact?
December 06
JURIX 2006 KeyNote 60
Loui
What happens when two P&P agents interact?
December 06
JURIX 2006 KeyNote 61
Loui
What happens when two P&P agents interact?
1 breaks down
Laissez-faire path
is
<Eu1,Eu2>
through time
Amount of
(specific)
resentment
December 06
JURIX 2006 KeyNote 62
Loui
Both are
generous
at the start
1 is
generous
at start,
2 is not
Does the starting offer affect the laissez-faire path?
December 06
JURIX 2006 KeyNote 63
2 is
generous
at start,
1 is not
Loui
Breakdown
at t=2
(pure
pessimism)
December 06
JURIX 2006 KeyNote 64
Loui
Different
laissez-faire
paths
December 06
JURIX 2006 KeyNote 65
Loui
Breakdown
at t=5
with
resentment
December 06
JURIX 2006 KeyNote 66
Loui
All paths lead to breakdown
December 06
JURIX 2006 KeyNote 67
Loui
Fixed
agent
characteristics
Varied
acceleration
of offers
In a different negotiation,
some paths lead to acceptance, some to breakdown
December 06
JURIX 2006 KeyNote 68
Loui
A third example where player 1 can guarantee
an acceptance outcome with the right initial offers
December 06
JURIX 2006 KeyNote 69
Loui
An Envelope of Normalcy
Can you keep the path
in a narrow envelope?
the axis passes through
< uA(bd), uB(bd) >
If so, then agreement is
Possible.
December 06
JURIX 2006 KeyNote 70
Loui
Where are the laissez-faire states, in terms
of agents' relative power?
When any party
does not have power,
Negotiation ends
power = (ut(bd) – u1)/(Eut – u1)
December 06
JURIX 2006 KeyNote 71
Loui
December 06
JURIX 2006 KeyNote 72
Loui
Pessimism-Punishment (PP)
Agents
An AI model of negotiation
Process
Enforcement of agreement
Procedural fairness / Negotiating norms
Nonstandard utility attached to speech act
Objective probability
Constructivism (rationality is if, not iff)
Purely probabilistic dynamics
December 06
JURIX 2006 KeyNote 73
Loui
Pessimism-Punishment (PP)
Agents
An AI model of negotiation
Process
Enforcement of agreement
Procedural fairness / Negotiating norms
Nonstandard utility attached to speech act
Objective probability
Constructivism (rationality is if, not iff)
Purely probabilistic dynamics
December 06
JURIX 2006 KeyNote 74
Loui
Pessimism-Punishment (PP)
Agents
An AI model of negotiation
Implementable / Plausible / Simple / Memorable
Iconoclast (but better)
un-Nash
non-vonNeumann
anti-GameTheory
Luce/Raiffa simplicity but requires some modern ideas
Brings one main Legal Idea (procedural fairness) into
familiar economic setting
Victor Lesser: computational value of emotion
December 06
JURIX 2006 KeyNote 75
Loui
Pessimism-Punishment (PP)
Agents
An AI model of negotiation
Implementable / Plausible / Simple / Memorable
Iconoclast (but better)
un-Nash
non-vonNeumann
anti-GameTheory
Luce/Raiffa simplicity but requires some modern ideas
Brings one main Legal Idea (procedural fairness) into
familiar economic setting
Victor Lesser: computational value of emotion
December 06
JURIX 2006 KeyNote 76
Loui
December 06
JURIX 2006 KeyNote 77
Loui
AI Model of Negotiation:
Diana Moore's B.Sc. Thesis, 97
Search
Another beautiful story:
how making a proposal in a negotiation dialogue focuses
heuristic search which causes utility estimates to build in
the more probable settlement areas
Dialogue/Protocol
Persuasion/Argumentation
Log-rolling/Problem Reformulation
Process
December 06
JURIX 2006 KeyNote 78
Loui
AI Model of Negotiation:
Diana Moore's B.Sc. Thesis, 97
Search
Dialogue/Protocol
Another beautiful story:
How agents can ask each other "WHY NOT?" questions
and respond with the specific constraints that cause their
objective functions to fall below aspiration
Persuasion/Argumentation
Log-rolling/Problem Reformulation
Process
December 06
JURIX 2006 KeyNote 79
Loui
AI-and-Law Model of
Negotiation
What beautiful stories will we soon be able to
tell here?
December 06
JURIX 2006 KeyNote 80
Loui
What Is At Stake?
A Personal View
Intellectual History
AI (w/AI and Law) will rewrite the
mathematical foundations of the social
sciences
Actual Negotiation Practice
What electronic world do you want to live
in?
Can agreement be found in the Middle
East?
December 06
JURIX 2006 KeyNote 81
Loui