J1

Information about J1

Published on October 16, 2007

Author: Kestrel

Source: authorstream.com

Content

Algorithmic Game Theory and Internet Computing:  Algorithmic Game Theory and Internet Computing Vijay V. Vazirani Polynomial Time Algorithms For Market Equilibria 1) History and Basic Notions:  1) History and Basic Notions Markets :  Markets Stock Markets:  Stock Markets Internet :  Internet Slide7:  Revolution in definition of markets Slide8:  Revolution in definition of markets New markets defined by Google Amazon Yahoo! Ebay Slide9:  Revolution in definition of markets Massive computational power available Slide10:  Revolution in definition of markets Massive computational power available Important to find good models and algorithms for these markets Adwords Market :  Adwords Market Created by search engine companies Google Yahoo! MSN Multi-billion dollar market Totally revolutionized advertising, especially by small companies. New algorithmic and game-theoretic questions:  New algorithmic and game-theoretic questions Queries are coming on-line. Instantaneously decide which bidder gets it. Monika Henzinger, 2004: Find on-line alg. to maximize Google’s revenue. New algorithmic and game-theoretic questions:  New algorithmic and game-theoretic questions Queries are coming on-line. Instantaneously decide which bidder gets it. Monika Henzinger, 2004: Find on-line alg. to maximize Google’s revenue. Mehta, Saberi, Vazirani & Vazirani, 2005: 1-1/e algorithm. Optimal. How will this market evolve??:  How will this market evolve?? Slide17:  The study of market equilibria has occupied center stage within Mathematical Economics for over a century. Slide18:  The study of market equilibria has occupied center stage within Mathematical Economics for over a century. This talk: Historical perspective & key notions from this theory. 2). Algorithmic Game Theory:  2). Algorithmic Game Theory Combinatorial algorithms for traditional market models 3). New Market Models:  3). New Market Models Resource Allocation Model of Kelly, 1997 3). New Market Models:  3). New Market Models Resource Allocation Model of Kelly, 1997 For mathematically modeling TCP congestion control Highly successful theory A Capitalistic Economy:  A Capitalistic Economy Depends crucially on pricing mechanisms to ensure: Stability Efficiency Fairness Adam Smith:  Adam Smith The Wealth of Nations 2 volumes, 1776. Adam Smith:  Adam Smith The Wealth of Nations 2 volumes, 1776. ‘invisible hand’ of the market Supply-demand curves:  Supply-demand curves Leon Walras, 1874:  Leon Walras, 1874 Pioneered general equilibrium theory Irving Fisher, 1891:  Irving Fisher, 1891 First fundamental market model Fisher’s Model, 1891:  Fisher’s Model, 1891 milk ¢ $$$$$$$$$ $ $$$$ People want to maximize happiness – assume linear utilities. Find prices s.t. market clears Fisher’s Model:  Fisher’s Model n buyers, with specified money, m(i) for buyer i k goods (unit amount of each good) Linear utilities: is utility derived by i on obtaining one unit of j Total utility of i, Fisher’s Model:  Fisher’s Model n buyers, with specified money, m(i) k goods (each unit amount, w.l.o.g.) Linear utilities: is utility derived by i on obtaining one unit of j Total utility of i, Find prices s.t. market clears, i.e., all goods sold, all money spent. Arrow-Debreu Model, 1954 Exchange Economy :  Arrow-Debreu Model, 1954 Exchange Economy Second fundamental market model Celebrated theorem in Mathematical Economics Kenneth Arrow:  Kenneth Arrow Nobel Prize, 1972 Gerard Debreu:  Gerard Debreu Nobel Prize, 1983 Arrow-Debreu Model:  Arrow-Debreu Model n agents, k goods Arrow-Debreu Model:  Arrow-Debreu Model n agents, k goods Each agent has: initial endowment of goods, & a utility function Arrow-Debreu Model:  Arrow-Debreu Model n agents, k goods Each agent has: initial endowment of goods, & a utility function Find market clearing prices, i.e., prices s.t. if Each agent sells all her goods Buys optimal bundle using this money No surplus or deficiency of any good Utility function of agent i:  Utility function of agent i Continuous, monotonic and strictly concave For any given prices and money m, there is a unique utility maximizing bundle for agent i. Arrow-Debreu Model:  Agents: Buyers/sellers Arrow-Debreu Model Initial endowment of goods:  Initial endowment of goods Agents Goods Slide41:  Agents Prices Goods = $25 = $15 = $10 Incomes:  Incomes Goods Agents =$25 =$15 =$10 $50 $40 $60 $40 Prices Slide43:  Goods Agents Maximize utility $50 $40 $60 $40 =$25 =$15 =$10 Prices Find prices s.t. market clears:  Find prices s.t. market clears Goods Agents $50 $40 $60 $40 =$25 =$15 =$10 Prices Maximize utility Slide45:  Observe: If p is market clearing prices, then so is any scaling of p Assume w.l.o.g. that sum of prices of k goods is 1. k-1 dimensional unit simplex Arrow-Debreu Theorem:  Arrow-Debreu Theorem For continuous, monotonic, strictly concave utility functions, market clearing prices exist. Proof :  Proof Uses Kakutani’s Fixed Point Theorem. Deep theorem in topology Proof :  Proof Uses Kakutani’s Fixed Point Theorem. Deep theorem in topology Will illustrate main idea via Brouwer’s Fixed Point Theorem (buggy proof!!) Brouwer’s Fixed Point Theorem:  Brouwer’s Fixed Point Theorem Let be a non-empty, compact, convex set Continuous function Then Brouwer’s Fixed Point Theorem:  Brouwer’s Fixed Point Theorem Idea of proof:  Idea of proof Will define continuous function If p is not market clearing, f(p) tries to ‘correct’ this. Therefore fixed points of f must be equilibrium prices. Use Brouwer’s Theorem:  Use Brouwer’s Theorem When is p an equilibrium price?:  When is p an equilibrium price? s(j): total supply of good j. B(i): unique optimal bundle which agent i wants to buy after selling her initial endowment at prices p. d(j): total demand of good j. When is p an equilibrium price?:  When is p an equilibrium price? s(j): total supply of good j. B(i): unique optimal bundle which agent i wants to buy after selling her initial endowment at prices p. d(j): total demand of good j. For each good j: s(j) = d(j). What if p is not an equilibrium price?:  What if p is not an equilibrium price? s(j) < d(j) => p(j) s(j) > d(j) => p(j) Also ensure Slide56:  Let S(j) < d(j) => S(j) > d(j) => N is s.t. Slide57:  is a cts. fn. => is a cts. fn. of p => is a cts. fn. of p => f is a cts. fn. of p Slide58:  is a cts. fn. => is a cts. fn. of p => is a cts. fn. of p => f is a cts. fn. of p By Brouwer’s Theorem, equilibrium prices exist. Slide59:  is a cts. fn. => is a cts. fn. of p => is a cts. fn. of p => f is a cts. fn. of p By Brouwer’s Theorem, equilibrium prices exist. q.e.d.! Bug??:  Bug?? Slide61:  Boundaries of Slide62:  Boundaries of B(i) is not defined at boundaries!! Kakutani’s Fixed Point Theorem:  Kakutani’s Fixed Point Theorem convex, compact set non-empty, convex, upper hemi-continuous correspondence s.t. Fisher reduces to Arrow-Debreu:  Fisher reduces to Arrow-Debreu Fisher: n buyers, k goods AD: n+1 agents first n have money, utility for goods last agent has all goods, utility for money only. Money :  Money

Related presentations


Other presentations created by Kestrel

English Literature
16. 02. 2008
0 views

English Literature

birth control
10. 10. 2007
0 views

birth control

ramasetu22may2007 1796
30. 09. 2007
0 views

ramasetu22may2007 1796

purpletree
07. 10. 2007
0 views

purpletree

Verdi
08. 10. 2007
0 views

Verdi

preschool
11. 10. 2007
0 views

preschool

playingwithliterature
12. 10. 2007
0 views

playingwithliterature

mlin2
15. 10. 2007
0 views

mlin2

cartoon pool a d
15. 10. 2007
0 views

cartoon pool a d

Corps Safety Council 24 Jul 06
18. 10. 2007
0 views

Corps Safety Council 24 Jul 06

reliable multicast
03. 10. 2007
0 views

reliable multicast

Discovery of Cosmic Rays
13. 10. 2007
0 views

Discovery of Cosmic Rays

State of Georgia Sunum
17. 10. 2007
0 views

State of Georgia Sunum

North Africa
23. 10. 2007
0 views

North Africa

slides ch10
01. 11. 2007
0 views

slides ch10

LaoTzu2
04. 12. 2007
0 views

LaoTzu2

drying
07. 12. 2007
0 views

drying

Mikheev SPM210207
15. 10. 2007
0 views

Mikheev SPM210207

benelux intervet 09 12 2004
16. 10. 2007
0 views

benelux intervet 09 12 2004

mpls
29. 10. 2007
0 views

mpls

Network Series Overview
30. 10. 2007
0 views

Network Series Overview

wu zixin defense
01. 11. 2007
0 views

wu zixin defense

Chapter1
02. 11. 2007
0 views

Chapter1

20050812
23. 10. 2007
0 views

20050812

olnes pki interoperability
07. 11. 2007
0 views

olnes pki interoperability

TomGibbs
21. 10. 2007
0 views

TomGibbs

Presentaci n RSC EFQM francais
16. 11. 2007
0 views

Presentaci n RSC EFQM francais

Parts of a Flower
14. 12. 2007
0 views

Parts of a Flower

L1Ch3 2
17. 12. 2007
0 views

L1Ch3 2

dyfi pathfinder presentation
02. 11. 2007
0 views

dyfi pathfinder presentation

Robot
03. 01. 2008
0 views

Robot

2004Summary
03. 01. 2008
0 views

2004Summary

sdocjung e
09. 10. 2007
0 views

sdocjung e

MOM 7
15. 10. 2007
0 views

MOM 7

01 what is AI
04. 01. 2008
0 views

01 what is AI

Do Air Cleaners Work
19. 11. 2007
0 views

Do Air Cleaners Work

transporte maritimo en CA
22. 10. 2007
0 views

transporte maritimo en CA

Wind Hedges905 2 ppt
04. 10. 2007
0 views

Wind Hedges905 2 ppt

richard hansberger
03. 10. 2007
0 views

richard hansberger

EspositoNOW2006
15. 10. 2007
0 views

EspositoNOW2006

Lochbuhler
17. 10. 2007
0 views

Lochbuhler

PRES Canada US Market
29. 10. 2007
0 views

PRES Canada US Market

davereese july99
30. 10. 2007
0 views

davereese july99

884 philmont05 finalpreparations
28. 11. 2007
0 views

884 philmont05 finalpreparations

ch2 voc2
20. 02. 2008
0 views

ch2 voc2

1 74presentation
19. 10. 2007
0 views

1 74presentation

The Causes of War
06. 03. 2008
0 views

The Causes of War

BF CCC conf 2
23. 11. 2007
0 views

BF CCC conf 2

IndustryForumSlidesF eb16
11. 03. 2008
0 views

IndustryForumSlidesF eb16

EAGER UNECE 2007
15. 10. 2007
0 views

EAGER UNECE 2007

spin05 coverity
26. 02. 2008
0 views

spin05 coverity

IM845
24. 03. 2008
0 views

IM845

PresentationAbridged
03. 10. 2007
0 views

PresentationAbridged

chap08 ppt10thedition
08. 04. 2008
0 views

chap08 ppt10thedition

Be Happier Smarter And Healthier
26. 09. 2007
0 views

Be Happier Smarter And Healthier

benefits e
25. 10. 2007
0 views

benefits e

crec ipv6 apan 2
09. 10. 2007
0 views

crec ipv6 apan 2

Cisco Dec4
18. 04. 2008
0 views

Cisco Dec4

Graphplan
30. 10. 2007
0 views

Graphplan

Patoka Final ALS poster
26. 11. 2007
0 views

Patoka Final ALS poster

real options
28. 04. 2008
0 views

real options

Anderson
07. 05. 2008
0 views

Anderson

The Future of Healthcare
08. 05. 2008
0 views

The Future of Healthcare

Lecture22
08. 05. 2008
0 views

Lecture22

prairiechicken
03. 01. 2008
0 views

prairiechicken

PediatricObesityProb lem
30. 04. 2008
0 views

PediatricObesityProb lem

Innovation
02. 05. 2008
0 views

Innovation

PassingGas Dr Railton
02. 05. 2008
0 views

PassingGas Dr Railton

Guide Lines for Bladder Cancer
02. 05. 2008
0 views

Guide Lines for Bladder Cancer

MECH500
02. 05. 2008
0 views

MECH500

l3
23. 11. 2007
0 views

l3

smallpoxmaster
21. 10. 2007
0 views

smallpoxmaster

endeavour 1 00
21. 11. 2007
0 views

endeavour 1 00

backgr
19. 10. 2007
0 views

backgr

Copenhagen
12. 10. 2007
0 views

Copenhagen

presentacion valparaiso
24. 10. 2007
0 views

presentacion valparaiso

ZP582pp
23. 10. 2007
0 views

ZP582pp

pre e301
21. 10. 2007
0 views

pre e301

Riesgo
31. 10. 2007
0 views

Riesgo

Gallick 1 10 07
16. 10. 2007
0 views

Gallick 1 10 07

podcastingagnews
08. 10. 2007
0 views

podcastingagnews

Berton Astronomie par Internet
15. 11. 2007
0 views

Berton Astronomie par Internet

jean michel lauren
11. 04. 2008
0 views

jean michel lauren

Shining Examples 2007
29. 10. 2007
0 views

Shining Examples 2007

lecture9
10. 12. 2007
0 views

lecture9

kathyppt
06. 11. 2007
0 views

kathyppt

Lawrence CAS2K3
28. 12. 2007
0 views

Lawrence CAS2K3

swieta
20. 11. 2007
0 views

swieta