Transcript Algorithmic Game Theory and Internet Computing

Algorithmic Game Theory
Computation
Competitive
and InternetofComputing
Equilibria
Amin Saberi
Stanford University
Outline

History

Economic theory and equilibria
(existence, dynamics, stability)

An algorithmic approach: computation,
polynomial time computability
A bit history

Rabbi Samuel ben Meir (12th century, France): 2nd century
text: “You shall have inspectors of weights and measures but
not inspectors of prices.”
Commentary (Aumann): If one seller charges too high a price,
then another will undercut him.

Adam Smith (1776): Capital flows from low-profit to highprofit industries (demand function implicit?)
The beginning of analytical work

Standard analysis

demand functions: Cournot (1838)
 supply functions: Jenkin (1870)
 excess demand: Hicks (1939).

Dynamics in 1870’s: Is out-of-equilibrium
behavior modeled by demand and supply?
Walras, Fisher, Pareto, Hicks

Walras [1871, 1874]:
first formulator of competitive general equilibrium theory.
Recognized need for stability (how to get into equilibrium)
His name: tatonnements (gropings).
Walras, Fisher, Pareto, Hicks

Walras [1871, 1874]:
first formulator of competitive general equilibrium theory.
Recognized need for stability (how to get into equilibrium)
His name: tatonnements (gropings).

Fisher (1891): tried to compute the equilibrium prices
First computational approach!
 Fisher (1891): Hydraulic apparatus for calculating
equilibrium
Walras, Fisher, Pareto, Hicks

Walras [1871, 1874]: tatonnements

Pareto (1904): Pointed out that even a simple economy requires
a large set of equations to define equilibrium. Argued that
market was an effective way to solve large systems of
equations, better than an “ordinateur” (his word in the French
translation). I believe this is the word now used to translate,
“computer.”
Walras, Fisher, Pareto, Hicks

Walras [1871, 1874]: tatonnements

Fisher (1894), Pareto (1904): Markets and computation

Hicks (1939): convergence and “Hicksian” condition
on the Jacobian of the excess demand functions
(the determinants of the minors be positive if of even order
and negative if of odd order)
Samuelson and successors

Samuelson [1944]: Hicksian conditions neither necessary
nor sufficient for stability.

Metzler [1945]: if off-diagonal elements of Jacobian are
non-negative (commodities are gross substitutes), then
Hicksian conditions are sufficient.

Arrow [1974]: Hicksian conditions were actually equivalent
to the statement that the real roots of the Jacobian are
negative.
Arrow, Debreu and…

Arrow-Hurwicz et. al. papers [1977]: Sufficient
conditions for stability of Samuelson-Lange system
Gross substitution implies that Euclidean norm decreases
Will talk about these dynamics in details in the next lecture

Arrow-Debreu: existence of equilibrium prices
(will show a variation of Debreu’s proof)
End of the program?

Scarf’s example, Saari-Simon Theorem: For any dynamic
system depending on first-order information (z) only,
there is a set of excess demand functions for which
stability fails.

Uzawa: Existence of general equilibrium is equivalent to
fixed-point theorem (will show in this lecture)

Linear complementarity Programs (LCP) and algorithms:
Scarf, Eaves, Cottle…(later in the quarter)
Outline

History

Economic theory and equilibria
(existence, dynamics, stability)

An algorithmic approach: computation,
polynomial time computability
Last 10 years
 New applications: Internet, Sponsored search, combinatorial
auctions
 Computation as a lense!
 First papers: Megiddo 80’s, DPS 01
prices and ND communication complexity
 Lots of new algorithm: convex programs
combinatorial algorithms
A CES Market
 n buyers, with specified money
 m divisible goods (unit amount)
 Buyers have CES utility functions:
Contains several interesting special cases:
=1
linear
=0
Cobb-Douglas
 = -1
Leontief (rate allocation in a network)
A CES Market
 n buyers, with specified money
 m divisible goods (unit amount)
 Buyers have CES utility functions:
Contains several interesting special cases:
=1
linear
=0
Cobb-Douglas
 = -1
Leontief (rate allocation in a network)
Market Equilibrium
 n buyers, with specified money mi
 m divisible goods (unit amount)
 Buyers have CES utility functions:
Find prices such that
 buyers spend all their money
 Market clears
Market Equilibrium
 Buyers’ optimization program:
 Global Constraint:
Eisenberg-Gale’s convex program
 The space of feasible allocations is:
 How do you aggregate the utility functions U1, U2, … Un ?
Eisenberg-Gale’s convex program
 The space of feasible allocations is:
 How do you aggregate the utility functions U1, U2, … Un ?
First observation: Adding them up is not the answer!
Eisenberg-Gale’s convex program
Buyer i should not gain (or loose) by
 Doubling all uij s
 By splitting himself into two buyers with half of the
money
Eisenberg-Gale’s convex program
Buyer i should not gain (or loose) by
 Doubling all uij s
 By splitting himself into two buyers with half of the
money
 Eisenberg-Gale’s solution:
Eisenberg-Gale’s convex program
Eisenberg-Gale’s convex program

Optimum dual: Equilibrium prices (also unique)

Gives a poly-time algorithm for computing the
equilibrium
Eisenberg-Gale’s convex program

Optimum dual: Equilibrium prices (also unique)

Gives a poly-time algorithm for computing the
equilibrium

Market is “proportionally” fair
for every other allocation achieving
Eisenberg-Gale’s convex program

Optimum dual: Equilibrium prices (also unique)

Gives a poly-time algorithm for computing the
equilibrium

The program works for all homogenous utility
functions, generalized to homothetic KVY 03
(homothetic: U(f(y)) U is homogeneous of degree
one and f is a monotone)
Application: Congestion Control
x1
x1  x3  1
x1  x2  1
x2
Maximize x1 x2 x3
1
2
x1  ; x2  x3  ;
3
3
x3
Congestion Control
$
p1
p2
$
$
Maximize x1 x2 x3
Find the right prices in a
Leontief market
p1 = p2 = 3/2
Congestion Control
 Primal-dual scheme
primal: packet rates at sources
dual: congestion measures (shadow prices)
A market equilibrium in a distributed setting!
Kelly, Low, Doyle, Tan, ….
Exchange Economy
Agents buy and sell at the same time:
Exchange Economy
Agents buy and sell at the same time:

-1
At least as hard as
solving Nash Equilibria
(CVSY 05)
-1
OPEN!!
0
1
Polynomial-time
algorithms known
(DPSV 02, J 03, CMK
03 , GKV 04, ...
Nash = Leontief
Use LCP as an intermediate step:
Nash equilibria for a
symmetric game H
x is equilibrium if:
Finding the solution of
LCP for H > 0
Nash = Leontief
Leontief: H the rate matrix;
agent i owns good i
x is at equilibrium if:
Finding the solution of
LCP for H > 0
Open Questions

Exchange economies with -1 <  < -1

Markets with indivisible goods
 Price

equilibria; proportional fair allocation
Core of a Game:
 LP-based
algorithm for transferable payoff
 Still open for NTU games
Nash = Leontief
In Leontief markets, agents consume goods in fixed proportions:
Let H > 0 be the utility matrix. Assume agent i owns good i
x is an equilibrium if