Stanford

67 %
33 %
Information about Stanford
Entertainment

Published on October 13, 2007

Author: AscotEdu

Source: authorstream.com

Algorithmic Game Theory and Internet Computing:  Algorithmic Game Theory and Internet Computing Vijay V. Vazirani Markets and the Primal-Dual Paradigm Markets :  Markets Stock Markets:  Stock Markets Internet :  Internet Slide5:  Revolution in definition of markets Slide6:  Revolution in definition of markets New markets defined by Google Amazon Yahoo! Ebay Slide7:  Revolution in definition of markets Massive computational power available for running these markets in a centralized or distributed manner Slide8:  Revolution in definition of markets Massive computational power available for running these markets in a centralized or distributed manner Important to find good models and algorithms for these markets Theory of Algorithms:  Theory of Algorithms Powerful tools and techniques developed over last 4 decades. Theory of Algorithms:  Theory of Algorithms Powerful tools and techniques developed over last 4 decades. Recent study of markets has contributed handsomely to this theory as well! AdWords Market :  AdWords Market Created by search engine companies Google Yahoo! MSN Multi-billion dollar market – and still growing! Totally revolutionized advertising, especially by small companies. Historically, the study of markets:  Historically, the study of markets has been of central importance, especially in the West Historically, the study of markets:  Historically, the study of markets has been of central importance, especially in the West General Equilibrium Theory Occupied center stage in Mathematical Economics for over a century Leon Walras, 1874:  Leon Walras, 1874 Pioneered general equilibrium theory Arrow-Debreu Theorem, 1954:  Arrow-Debreu Theorem, 1954 Celebrated theorem in Mathematical Economics Established existence of market equilibrium under very general conditions using a deep theorem from topology - Kakutani fixed point theorem. Kenneth Arrow:  Kenneth Arrow Nobel Prize, 1972 Gerard Debreu:  Gerard Debreu Nobel Prize, 1983 General Equilibrium Theory:  General Equilibrium Theory Also gave us some algorithmic results Convex programs, whose optimal solutions capture equilibrium allocations, e.g., Eisenberg & Gale, 1959 Nenakov & Primak, 1983 Cottle and Eaves, 1960’s: Linear complimentarity Scarf, 1973: Algorithms for approximately computing fixed points General Equilibrium Theory :  An almost entirely non-algorithmic theory! General Equilibrium Theory What is needed today?:  What is needed today? An inherently algorithmic theory of market equilibrium New models that capture new markets and are easier to use than traditional models Slide23:  Beginnings of such a theory, within Algorithmic Game Theory Started with combinatorial algorithms for traditional market models New market models emerging A central tenet:  A central tenet Prices are such that demand equals supply, i.e., equilibrium prices. A central tenet:  A central tenet Prices are such that demand equals supply, i.e., equilibrium prices. Easy if only one good Supply-demand curves:  Supply-demand curves Irving Fisher, 1891:  Irving Fisher, 1891 Defined a fundamental market model Slide30:  utility Utility function amount of milk Slide31:  utility Utility function amount of bread Slide32:  utility Utility function amount of cheese Total utility of a bundle of goods:  Total utility of a bundle of goods = Sum of utilities of individual goods For given prices, :  For given prices, For given prices, find optimal bundle of goods:  For given prices, find optimal bundle of goods Fisher market:  Fisher market Several goods, fixed amount of each good Several buyers, with individual money and utilities Find equilibrium prices of goods, i.e., prices s.t., Each buyer gets an optimal bundle No deficiency or surplus of any good Combinatorial Algorithm for Linear Case of Fisher’s Model:  Combinatorial Algorithm for Linear Case of Fisher’s Model Devanur, Papadimitriou, Saberi & V., 2002 Using the primal-dual schema Primal-Dual Schema:  Primal-Dual Schema Highly successful algorithm design technique from exact and approximation algorithms Exact Algorithms for Cornerstone Problems in P::  Exact Algorithms for Cornerstone Problems in P: Matching (general graph) Network flow Shortest paths Minimum spanning tree Minimum branching Approximation Algorithms:  Approximation Algorithms set cover facility location Steiner tree k-median Steiner network multicut k-MST feedback vertex set scheduling . . . Slide43:  No LP’s known for capturing equilibrium allocations for Fisher’s model Slide44:  No LP’s known for capturing equilibrium allocations for Fisher’s model Eisenberg-Gale convex program, 1959 Slide45:  No LP’s known for capturing equilibrium allocations for Fisher’s model Eisenberg-Gale convex program, 1959 DPSV: Extended primal-dual schema to solving a nonlinear convex program Fisher’s Model:  Fisher’s Model n buyers, money m(i) for buyer i k goods (unit amount of each good) : utility derived by i on obtaining one unit of j Total utility of i, Fisher’s Model:  Fisher’s Model n buyers, money m(i) for buyer i k goods (unit amount of each good) : utility derived by i on obtaining one unit of j Total utility of i, Find market clearing prices An easier question:  An easier question Given prices p, are they equilibrium prices? If so, find equilibrium allocations. An easier question:  An easier question Given prices p, are they equilibrium prices? If so, find equilibrium allocations. Equilibrium prices are unique! Bang-per-buck:  At prices p, buyer i’s most desirable goods, S = Any goods from S worth m(i) constitute i’s optimal bundle Bang-per-buck Slide51:  For each buyer, most desirable goods, i.e. Slide52:  Max flow m(1) m(2) m(3) m(4) p(1) p(2) p(3) p(4) infinite capacities Slide53:  Max flow m(1) m(2) m(3) m(4) p(1) p(2) p(3) p(4) p: equilibrium prices iff both cuts saturated Idea of algorithm:  Idea of algorithm “primal” variables: allocations “dual” variables: prices of goods Approach equilibrium prices from below: start with very low prices; buyers have surplus money iteratively keep raising prices and decreasing surplus Idea of algorithm:  Idea of algorithm Iterations: execute primal & dual improvements Two important considerations:  Two important considerations The price of a good never exceeds its equilibrium price Invariant: s is a min-cut Slide57:  Max flow m(1) m(2) m(3) m(4) p(1) p(2) p(3) p(4) p: low prices Two important considerations:  Two important considerations The price of a good never exceeds its equilibrium price Invariant: s is a min-cut Identify tight sets of goods Two important considerations:  Two important considerations The price of a good never exceeds its equilibrium price Invariant: s is a min-cut Identify tight sets of goods Rapid progress is made Balanced flows Slide60:  Network N m p buyers goods bang-per-buck edges Slide61:  Balanced flow in N m p W.r.t. flow f, surplus(i) = m(i) – f(i,t) i Balanced flow:  Balanced flow surplus vector: vector of surpluses w.r.t. f. Balanced flow:  Balanced flow surplus vector: vector of surpluses w.r.t. f. A flow that minimizes l2 norm of surplus vector. Property 1:  Property 1 f: max flow in N. R: residual graph w.r.t. f. If surplus (i) < surplus(j) then there is no path from i to j in R. Slide65:  Property 1 i surplus(i) < surplus(j) j R: Slide66:  Property 1 i surplus(i) < surplus(j) j R: Slide67:  Property 1 i Circulation gives a more balanced flow. j R: Property 1:  Property 1 Theorem: A max-flow is balanced iff it satisfies Property 1. Pieces fit just right!:  Pieces fit just right! Balanced flows Invariant Bang-per-buck edges Tight sets How primal-dual schema is adapted to nonlinear setting:  How primal-dual schema is adapted to nonlinear setting A convex program:  A convex program whose optimal solution is equilibrium allocations. A convex program:  A convex program whose optimal solution is equilibrium allocations. Constraints: packing constraints on the xij’s A convex program:  A convex program whose optimal solution is equilibrium allocations. Constraints: packing constraints on the xij’s Objective fn: max utilities derived. A convex program:  A convex program whose optimal solution is equilibrium allocations. Constraints: packing constraints on the xij’s Objective fn: max utilities derived. Must satisfy If utilities of a buyer are scaled by a constant, optimal allocations remain unchanged If money of buyer b is split among two new buyers, whose utility fns same as b, then union of optimal allocations to new buyers = optimal allocation for b Money-weighed geometric mean of utilities:  Money-weighed geometric mean of utilities Eisenberg-Gale Program, 1959:  Eisenberg-Gale Program, 1959 Eisenberg-Gale Program, 1959:  Eisenberg-Gale Program, 1959 prices pj KKT conditions:  KKT conditions Slide79:  Therefore, buyer i buys from only, i.e., gets an optimal bundle Slide80:  Therefore, buyer i buys from only, i.e., gets an optimal bundle Can prove that equilibrium prices are unique! Will relax KKT conditions:  Will relax KKT conditions e(i): money currently spent by i w.r.t. a special allocation surplus money of i Will relax KKT conditions:  Will relax KKT conditions e(i): money currently spent by i w.r.t. a balanced flow in N surplus money of i KKT conditions:  KKT conditions e(i) e(i) Potential function:  Potential function Will show that potential drops by an inverse polynomial factor in each phase (polynomial time). Potential function:  Potential function Will show that potential drops by an inverse polynomial factor in each phase (polynomial time). Point of departure:  Point of departure KKT conditions are satisfied via a continuous process Normally: in discrete steps Point of departure:  Point of departure KKT conditions are satisfied via a continuous process Normally: in discrete steps Open question: strongly polynomial algorithm? Another point of departure:  Another point of departure Complementary slackness conditions: involve primal or dual variables, not both. KKT conditions: involve primal and dual variables simultaneously. KKT conditions:  KKT conditions KKT conditions:  KKT conditions Primal-dual algorithms so far:  Primal-dual algorithms so far Raise dual variables greedily. (Lot of effort spent on designing more sophisticated dual processes.) Primal-dual algorithms so far:  Primal-dual algorithms so far Raise dual variables greedily. (Lot of effort spent on designing more sophisticated dual processes.) Only exception: Edmonds, 1965: algorithm for weight matching. Primal-dual algorithms so far:  Primal-dual algorithms so far Raise dual variables greedily. (Lot of effort spent on designing more sophisticated dual processes.) Only exception: Edmonds, 1965: algorithm for weight matching. Otherwise primal objects go tight and loose. Difficult to account for these reversals in the running time. Our algorithm:  Our algorithm Dual variables (prices) are raised greedily Yet, primal objects go tight and loose Because of enhanced KKT conditions Deficiencies of linear utility functions:  Deficiencies of linear utility functions Typically, a buyer spends all her money on a single good Do not model the fact that buyers get satiated with goods Slide96:  utility Concave utility function amount of j Concave utility functions:  Concave utility functions Do not satisfy weak gross substitutability Concave utility functions:  Concave utility functions Do not satisfy weak gross substitutability w.g.s. = Raising the price of one good cannot lead to a decrease in demand of another good. Concave utility functions:  Concave utility functions Do not satisfy weak gross substitutability w.g.s. = Raising the price of one good cannot lead to a decrease in demand of another good. Open problem: find polynomial time algorithm! Slide100:  utility Piecewise linear, concave amount of j Slide101:  utility PTAS for concave function amount of j Piecewise linear concave utility:  Piecewise linear concave utility Does not satisfy weak gross substitutability Slide103:  utility Piecewise linear, concave amount of j Slide104:  Differentiate Slide105:  rate amount of j money spent on j Slide106:  rate rate = utility/unit amount of j money spent on j Spending constraint utility function $20 $40 $60 Spending constraint utility function:  Spending constraint utility function Happiness derived is not a function of allocation only but also of amount of money spent. Slide108:  $20 $40 $100 Extend model: assume buyers have utility for money rate Slide110:  Theorem: Polynomial time algorithm for computing equilibrium prices and allocations for Fisher’s model with spending constraint utilities. Furthermore, equilibrium prices are unique. Satisfies weak gross substitutability!:  Satisfies weak gross substitutability! Old pieces become more complex + there are new pieces:  Old pieces become more complex + there are new pieces But they still fit just right!:  But they still fit just right! Don Patinkin, 1956:  Don Patinkin, 1956 Money, Interest, and Prices. An Integration of Monetary and Value Theory Pascal Bridel, 2002: Euro. J. History of Economic Thought, Patinkin, Walras and the ‘money-in-the-utility- function’ tradition An unexpected fallout!!:  An unexpected fallout!! An unexpected fallout!!:  An unexpected fallout!! A new kind of utility function Happiness derived is not a function of allocation only but also of amount of money spent. An unexpected fallout!!:  An unexpected fallout!! A new kind of utility function Happiness derived is not a function of allocation only but also of amount of money spent. Has applications in Google’s AdWords Market! A digression:  A digression Slide119:  The view 5 years ago: Relevant Search Results Slide121:  Business world’s view now : (as Advertisement companies) So how does this work?:  Bids for different keywords Daily Budgets So how does this work? An interesting algorithmic question!:  An interesting algorithmic question! Monika Henzinger, 2004: Find an on-line algorithm that maximizes Google’s revenue. AdWords Allocation Problem :  AdWords Allocation Problem Search Engine Whose ad to put How to maximize revenue? LawyersRus.com Sue.com TaxHelper.com asbestos Search results Ads AdWords Problem:  AdWords Problem Mehta, Saberi, Vazirani & Vazirani, 2005: 1-1/e algorithm, assuming budgets>>bids AdWords Problem:  AdWords Problem Mehta, Saberi, Vazirani & Vazirani, 2005: 1-1/e algorithm, assuming budgets>>bids Optimal! AdWords Problem:  AdWords Problem Mehta, Saberi, Vazirani & Vazirani, 2005: 1-1/e algorithm, assuming budgets>>bids Optimal! Slide128:  Spending constraint utilities AdWords Market AdWords market:  AdWords market Assume that Google will determine equilibrium price/click for keywords AdWords market:  AdWords market Assume that Google will determine equilibrium price/click for keywords How should advertisers specify their utility functions? Choice of utility function:  Choice of utility function Expressive enough that advertisers get close to their ‘‘optimal’’ allocations Choice of utility function:  Choice of utility function Expressive enough that advertisers get close to their ‘‘optimal’’ allocations Efficiently computable Choice of utility function:  Choice of utility function Expressive enough that advertisers get close to their ‘‘optimal’’ allocations Efficiently computable Easy to specify utilities Slide134:  linear utility function: a business will typically get only one type of query throughout the day! Slide135:  linear utility function: a business will typically get only one type of query throughout the day! concave utility function: no efficient algorithm known! Slide136:  linear utility function: a business will typically get only one type of query throughout the day! concave utility function: no efficient algorithm known! Difficult for advertisers to define concave functions Easier for a buyer:  Easier for a buyer To say how much money she should spend on each good, for a range of prices, rather than how happy she is with a given bundle. Online shoe business:  Online shoe business Interested in two keywords: men’s clog women’s clog Advertising budget: $100/day Expected profit: men’s clog: $2/click women’s clog: $4/click Considerations for long-term profit:  Considerations for long-term profit Try to sell both goods - not just the most profitable good Must have a presence in the market, even if it entails a small loss Slide140:  If both are profitable, better keyword is at least twice as profitable ($100, $0) otherwise ($60, $40) If neither is profitable ($20, $0) If only one is profitable, very profitable (at least $2/$) ($100, $0) otherwise ($60, $0) Slide141:  $60 $100 men’s clog rate 2 1 rate = utility/click Slide142:  $60 $100 women’s clog rate 2 4 rate = utility/click Slide143:  $80 $100 money rate 0 1 rate = utility/$ AdWords market:  AdWords market Suppose Google stays with auctions but allows advertisers to specify bids in the spending constraint model AdWords market:  AdWords market Suppose Google stays with auctions but allows advertisers to specify bids in the spending constraint model expressivity! AdWords market:  AdWords market Suppose Google stays with auctions but allows advertisers to specify bids in the spending constraint model expressivity! Good online algorithm for maximizing Google’s revenues? Slide147:  Goel & Mehta, 2006: A small modification to the MSVV algorithm achieves 1 – 1/e competitive ratio! Open :  Open Is there a convex program that captures equilibrium allocations for spending constraint utilities? Spending constraint utilities satisfy:  Equilibrium exists (under mild conditions) Equilibrium utilities and prices are unique Rational With small denominators Spending constraint utilities satisfy Linear utilities also satisfy:  Equilibrium exists (under mild conditions) Equilibrium utilities and prices are unique Rational With small denominators Linear utilities also satisfy Proof follows from Eisenberg-Gale Convex Program, 1959:  Proof follows from Eisenberg-Gale Convex Program, 1959 For spending constraint utilities, proof follows from algorithm, and not a convex program!:  For spending constraint utilities, proof follows from algorithm, and not a convex program! Open :  Open Is there an LP whose optimal solutions capture equilibrium allocations for Fisher’s linear case? Use spending constraint algorithm to solve piecewise linear, concave utilities:  Use spending constraint algorithm to solve piecewise linear, concave utilities Open Algorithms & Game Theory common origins:  Algorithms & Game Theory common origins von Neumann, 1928: minimax theorem for 2-person zero sum games von Neumann & Morgenstern, 1944: Games and Economic Behavior von Neumann, 1946: Report on EDVAC Dantzig, Gale, Kuhn, Scarf, Tucker … Slide157:  utility Piece-wise linear, concave amount of j Slide158:  Differentiate Slide159:  Start with arbitrary prices, adding up to total money of buyers. Slide160:  rate money spent on j Slide161:  Start with arbitrary prices, adding up to total money of buyers. Run algorithm on these utilities to get new prices. Slide162:  Start with arbitrary prices, adding up to total money of buyers. Run algorithm on these utilities to get new prices. Slide163:  Start with arbitrary prices, adding up to total money of buyers. Run algorithm on these utilities to get new prices. Fixed points of this procedure are equilibrium prices for piecewise linear, concave utilities!

Add a comment

Related presentations

Related pages

Stanford University

Stanford University is one of the world's leading research and teaching institutions. It is located in Stanford, California.
Read more

Stanford University – Wikipedia

Stanford University; Motto: Die Luft der Freiheit weht: Gründung: 1891: Trägerschaft: privat: Ort: Stanford, Vereinigte Staaten von Amerika: Präsident ...
Read more

Stanford (Kalifornien) – Wikipedia

Stanford ist ein Census-designated place mit 13.900 Einwohnern (Stand: 2004) im Santa Clara County im US-Bundesstaat Kalifornien in der Nähe von Palo Alto.
Read more

Home | Stanford Graduate School of Business

Jonathan Levin, former chair of the Stanford Department of Economics, will be the tenth dean of Stanford Graduate School of Business
Read more

Stanford - YouTube

Carla Shatz, Stanford professor of neurobiology and of biology and the director of Stanford Bio-X, has won the 2016 Kavli Neuroscience Prize for her work ...
Read more

Stanford University | Stanford | Best College | US News

Is Stanford the best college for you? Find out at US News. See if Stanford is ranked and get info on admission, tuition, student life, and more.
Read more

Home | Stanford Medicine

Stanford Medicine integrates a premier medical school with world-class hospitals to advance human health.
Read more

Stanford Online

Sharing as we innovate: Stanford Online is a university-wide initiative coordinated by the Office of the Vice Provost for Teaching & Learning (VPTL).
Read more

Courses - Stanford Online

Crisis Code: Teaching Crisis Management Skills to Enhance Management of Advanced Cardiac Life Support: Cancer Clinical Trials: Practical Tips to Improve ...
Read more

Stanford Village,Overberg,South Africa

With the Kleinrivier running through it, mountain views, and just 30minutes from the sea-side town of Hermanus,Stanford is ideally positioned for couples and
Read more