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