"Why We're So Nice: We're Wired to Cooperate" Natalie Angier New York Times, 23 July 2002 What feels as good as chocolate on.

Report
"Why We're So Nice: We're Wired to Cooperate"
Natalie Angier
New York Times, 23 July 2002
What feels as good as chocolate on the tongue or money in the bank but won't make you
fat or risk a subpoena from the Securities and Exchange Commission?
Hard as it may be to believe in these days of infectious greed and sabers unsheathed,
scientists have discovered that the small, brave act of cooperating with another person,
of choosing trust over cynicism, generosity over selfishness, makes the brain light up with quiet joy.
Studying neural activity in young women who were playing a classic laboratory game called
the Prisoner's Dilemma, in which participants can select from a number of greedy or cooperative
strategies as they pursue financial gain,researchers found that when the women chose mutualism
over "me-ism," the mental circuitry normally associated with reward-seeking behavior swelled to life.
And the longer the women engaged in a cooperative strategy, the more strongly flowed the
blood to the pathways of pleasure.
The researchers, performing their work at Emory University in Atlanta, used magnetic resonance
imaging to take what might be called portraits of the brain on hugs.
"The results were really surprising to us," said Dr. Gregory S. Berns, a psychiatrist and an author
on the new report, which appears in the current issue of the journal Neuron. "We went in
expecting the opposite."
The researchers had thought that the biggest response would occur in cases where one
person cooperated and the other defected, when the cooperator might feel that she was
being treated unjustly.
Also: Paul Glimcher invited talk on “Neuroeconomics” [email protected]
Internet Connectivity
[Courtesy CAIDA]
International Trade
[Krempel&Pleumper
A mixture of scales; detailed structure
Corporate Partnerships
Political and Governmental
Control
[Krempel]
Online Social Relationships
[Isbell et al.]
Multi-Player Game Theory:
Powerpoint Notation Translation
•
•
•
•
•
Players 1,…,n
Actions (0 and 1 w.l.o.g.); joint action x in {0,1}^n
Mixed strategy for i: probability p_i of playing 0
Payoff matrices M_i[x] for each i (size 2^n)
(Approximate) Nash equilibrium:
– Joint mixed strategy p (product distribution)
– p_i is (approximate) best response to p for every player i
• Nash equilibria always exist; may be exponentially many
Given the M_i, how can we compute/learn Nash equilibria?
General problem is HARD.
Graphical Models for Game Theory
•
•
•
•
•
•
•
•
•
Undirected graph G capturing local interactions
Each player represented by a vertex
N_i(G) = neighbors of i in G (includes i)
Assume: M_i(x) expressible as M’_i(x’) over only N_i(G)
Graphical game: (G,{M’_i})
Compact representation of game
Exponential in max degree (<< # of players)
Ex’s: geography, organizational structure, networks
Analogy to Bayes nets: special structure
8
1
7
3
2
4
5
6
An Abstract Tree Algorithm
U1
U2
V
U3 T(w,v) = 1 <--> $ an “upstream” Nash
where V = v given W = w
<--> $ u: T(v,ui) = 1 for all i, and
v is a best response to u,w
W
• Downstream Pass:
• Upstream Pass:
– Each node V receives
– V receives values (w,v)
T(v,ui) from each Ui
from W s.t. T(w,v) = 1
– V computes T(w,v) and
– V picks witness u for
witness lists for each
T(w,v), passes (v,ui) to Ui
T(w,v) = 1
How to represent?
How to compute?
An Approximation Algorithm
• Discretize u and v in T(v,u), 1 represents
approximate Nash
• Main technical lemma: If k is max degree,
grid resolution t ~ e/(2^k) preserves
global e-Nash equilibria
• An efficient algorithm:
– Polynomial in n and 2^k ~ size of rep.
U1
– Represent an approx. to every Nash
– Can generate random Nash, or specific Nash
U2
U3
V
W
•
•
•
•
•
Table dimensions are probability of playing 0
Black shows T(v,u) = 1
Ms want to match, Os to unmatch
Relative value modulated by parent values
t = 0.01, e = 0.05
Extension to exact algorithm:
each table is a finite union of
rectangles, exponential in depth
Can also compute a single equilibrium
exactly in polynomial time
NashProp for Arbitrary Graphs
• Two-phase algorithm:
– Table-passing phase
– Assignment-passing phase
• Table-passing phase:
U1
– Initialization: T[0](w,v) = 1 for all (w,v)
– Induction: T[r+1](w,v) = 1 iff $ u:
• T[r](v,ui) = 1 for all i
• V=v a best response to W=w, U=u
U2
U3
V
W
• Table consistency stronger than best response
Convergence of Table-Passing
• Table-passing obeys contraction:
•
•
•
•
•
– {(w,v):T[r+1](w,v) = 1} contained in {(w,v):T[r](w,v) = 1}
Tables converge and are balanced
Discretization scheme: tables converge quickly
Never eliminate an equilibrium
Tables give a reduced search space
Assignment-passing phase:
– Use graph to propagate a solution consistent with tables
– Backtracking local search
• Allow e and t to be parameters
• Alternative approach [Vickrey&Koller]:
– Constraint propagation on junction tree
Graphical Games: Related Work
• Koller and Milch: graphical influence diagrams
• La Mura: game networks
• Vickrey & Koller: other methods on graphical games
Summarization Games with Bounded Influence
• Have global summarization function S(x)
• Payoff to player i depends only on x_i, S(x):
– Arbitrary payoff function F_i(x_i,S(x))
• Common examples:
– Voting (linear S)
– Financial markets
• Assume bounded influence of S
• Often expect influence t to decay with n!
• Assume bounded derivatives of the F_i
• Every player weakly influences every other
A Potential Function Argument
summarization value after best responses
summarization value for any mixed strategy
Learning Equilibria, Linear Summarization
summarization value after best responses
summarization value for any mixed strategy
Results
• Algorithm for computing O(e + t)-Nash in
time polynomial in 1/e
• Algorithm for learning O(e + t)-Nash in
time polynomial in 1/e, linear S case
• Benefits of a large population

similar documents