How Intractable is the
‘‘Invisible Hand’’:
Polynomial Time Algorithms for
Market Equilibria
Market Equilibrium
Walras, 1874
Arrow-Debreu Theorem, 1954
"Arrow-Debreu Theorem
is highly..."
"Arrow-Debreu Theorem
is highly..."
"Arrow-Debreu Theorem
is highly..."
"Arrow-Debreu Theorem
is highly..."
"Arrow-Debreu Theorem
is highly..."
Market Equilibrium
History
Slide 12
History
History
History
Market Equilibrium
Market Equilibrium
Slide 18
Slide 19
Slide 20
Slide 21
Bang per buck
Slide 23
"Any goods sold in
equality..."
"Any goods sold in
equality..."
Slide 26
Slide 27
Idea of Algorithm
ensuring Invariant initially
How to raise prices?
How to raise prices?
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46
Slide 47
Slide 48
Slide 49
Slide 50
Slide 51
Slide 52
Slide 53
Slide 54
Slide 55
Termination
Polynomial time
Slide 58
Slide 59
Slide 60
Slide 61
"Next freezing:"
"Next freezing:"
Slide 64
Slide 65
Slide 66
Slide 67
Slide 68
Slide 69
Polynomial time
Question
Question
Post-mortem
Primal-Dual Schema
Central Idea Behind
Primal-Dual Schema
Post-mortem
Post-mortem
Post-mortem
Post-mortem
‘‘Primal-Dual-Type’’
Algorithms
Concave utilities
Concave utilities
Slide 83
Slide 84
Slide 85
Slide 86
Slide 87
Slide 88
Slide 89
Slide 90
Spending constraint model
"Theorem:"
"Theorem:"
Slide 94
Slide 95
Slide 96
Slide 97
Devanur & V.,
2003
Devanur & V.,
2003
Devanur & V.,
2003
Devanur & V.,
2003
Devanur & V.,
2003
Algorithmic Game Theory
"Q:"
"Global optimality via
local improvement"
TCP congestion control
Slide 107
Slide 108
"Develop an algorithmic
theory"
"w.r.t."
"w.r.t."
"w.r.t."
"w.r.t."
"Invariant 1:"
"Invariant 1:"
"Invariant 1:"
"Invariant 1:"
"Invariant 1:"
"Invariant 1:"
"Invariant 1:"
"Maintains both
Invariants"
Slide 122
Slide 123
Slide 124