J1

50 %
50 %
Information about J1
Entertainment

Published on October 16, 2007

Author: Kestrel

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

J1 – wichtige Vorsorge für Jugendliche » Teenager: J1 bis ...

Diese vorletzte, sehr wichtige Vorsorgeuntersuchung beim Kinder- und Jugendarzt sollte zwischen 12 und 14 Jahren (vom 12. Geburtstag bis zum vollendeten 15.
Read more

J1 | Vorsorgeuntersuchung | Gesundes-Kind

J1: mit 13 Jahren. Diese Vorsorgeuntersuchung bietet für Eltern nun letztmalig die Gelegenheit, den allgemeinen Gesundheits- und Entwicklungsstand ihrer ...
Read more

Die Jugend-Vorsorgeuntersuchungen J1 und J2 - Familie.de

Die Jugend-Vorsorgeuntersuchungen J1 und J2 sind eine Fortsetzung der Vorsorgeuntersuchungen der U-Reihe, die von den ersten Lebensstunden bis zum Alter ...
Read more

J2 – bald erwachsen » Teenager: J1 bis J2 ...

Diese Vorsorgeuntersuchung soll Jugendlichen auch nach der J1 (vom 12. Geburtstag bis zum vollendeten 15. Lebensjahr) eine Möglichkeit zum Gesundheits ...
Read more

Die 10 wichtigsten Fragen zur Vorsorgeuntersuchung "J1 ...

Die zehn wichtigsten Fragen zur Vorsorgeuntersuchung "J1" Die U-Vorsorgeuntersuchungen kennen fast alle Eltern. Weniger bekannt: Die J1, die sich an ...
Read more

Die J1 Untersuchung | kindergesundheit-info.de

Auf eine Vorsorgeuntersuchung (J1) hat Ihr Kind von 12 bis 14 Jahren erneut Anspruch. Eine gute Gelegenheit, sich allein und vertraulich beraten zu lassen.
Read more

J-1 Visa

The J-1 Visa offers cultural and educational exchange opportunities in the United States through a variety of programs overseen by the U.S. State Department.
Read more

J-1 visa - Wikipedia, the free encyclopedia

A J-1 visa is a non-immigrant visa issued by the United States to research scholars, professors and exchange visitors participating in programs that ...
Read more

J1 | recreating the world's first all-metal aircraft

J1-Project in Dessau – Originalgetreuer 1:1-Nachbau des weltweit ersten Ganzmetallflugzeugs , Junkers J1 | recreating the world’s first all-metal aircraft
Read more

Die J1-Untersuchung- Was ist die J1-Untersuchung?

Die J1-Untersuchung ist eine kostenlose Vorsorgeuntersuchung für Jugendliche im Alter zwischen 12 und 14 Jahren. Erfahre mehr über die J1-Untersuchung.
Read more