Slide 1OutlineInternet Algorithms Game TheoryInternet Algorithmic Game TheorySlide 5Slide 6Market EquilibriumSlide 8Market EquilibriumMarket EquilibriumMarket EquilibriumSlide 12Slide 13Slide 14Equality SubgraphEquality SubgraphEquality SubgraphEquality SubgraphEquality SubgraphEquality SubgraphEquality SubgraphExampleExampleExampleBalanced FlowExampleExampleSlide 28Slide 29Slide 30Slide 31Slide 32Next step: dealing with integral goodsCore of a GameStability in RoutingStability in RoutingOptimal Auction DesignOptimal Auction DesignSlide 39OutlineThe Internet GraphThe Internet GraphSlide 43Slide 44Slide 45Slide 46Slide 47Slide 48Algorithmic Game Theoryand Internet ComputingAmin SaberiAlgorithmic Game Theory and Networked SystemsOutlineGame Theory and Algorithmsefficient algorithms for game theoretic notionsComplex networks andperformance of basic algorithmsInternetAlgorithms Game Theory efficiency, distributed computation, scalabilityHuge, distributed, dynamicowned and operated by different entities strategies, fairness, incentive compatibilityInternetAlgorithmic Game Theory efficiency, distributed computation, scalability strategies, fairness, incentive compatibility Fusing ideas of algorithms and game theoryHuge, distributed, dynamicowned and operated by different entitiesFind efficient algorithms for computing game theoretic notions like: Market equilibria Nash equilibria Core Shapley valueAuction ...Find efficient algorithms for computing game theoretic notions like: Market equilibria Nash equilibria Core Shapley valueAuction ...Market EquilibriumArrow-Debreu (1954): Existence of equilibrium prices (highly non-constructive, using Kakutani’s fixed-point theorem)Fisher (1891): Hydraulic apparatus for calculating equilibriumEisenberg & Gale (1959): Convex program (ellipsoid implicit)Scarf (1973): Approximate fixed point algorithmsUse techniques from modern theory of algorithmsIs linear case in P? Deng, Papadimitriou, Safra (2002)n buyers, with specified moneym divisible goods (unit amount)Linear utilities: uij utility derived by i on obtaining one unit of jFind prices such thatbuyers spend all their money Market clearsMarket EquilibriumBuyer i’s optimization program:Global Constraint:Market EquilibriumMarket EquilibriumDevanur, Papadimitriou, S., Vazirani ‘03: A combinatorial (primal-dual) algorithm for finding the prices in polynomial time.Devanur, Papadimitriou, S., Vazirani ‘03: A combinatorial (primal-dual) algorithm for finding the prices in polynomial time. Start with small prices so that only buyers have surplus gradually increase prices until surplus is zeroPrimal-dual scheme: Allocation PricesDevanur, Papadimitriou, S., Vazirani ‘03: A combinatorial (primal-dual) algorithm for finding the prices in polynomial time. Start with small prices so that only buyers have surplus gradually increase prices until surplus is zeroPrimal-dual scheme: Allocation Prices Measure of progress: l2-norm of the surplus vector.Buyers Goods $20 10/20$40 20/40$10 4/10$60 2/60102042Bang per buck: utility of worth $1 of a good. Equality SubgraphEquality SubgraphBuyers Goods Bang per buck: utility of worth $1 of a good. Buyers will only buy the goods with highest bang per buck:$20 10/20$40 20/40$10 4/10$60 2/60102042Buyers Goods Bang per buck: utility of worth $1 of a good. Buyers will only buy the goods with highest bang per buck:Equality SubgraphBuyers Goods $20 $40 $10$60$100 $60 $20$140 Buyers Goods How do we compute the sales in equality subgraph ? Equality SubgraphBuyers Goods How do we compute the sales in equality subgraph ? maximum flow!20 40 1060100 60 20140 Equality SubgraphBuyers Goods 100 60 20140 always saturated (by invariant)How do we compute the sales in equality subgraph ? maximum flow!Equality SubgraphBuyers Goods buyers may have always saturated surplus (by invariant)How do we compute the sales in equality subgraph ? maximum flow!Equality Subgraph100602014020401060Example20/10020/6020/2070/140Example20/2040/4010/1060/60106020202020/10020/6020/2070/140Example20/2040/4010/1060/601060202020Surplus vector = (80, 40, 0, 70)Balanced FlowBalanced Flow: the flow that minimizes the l2-norm of the surplus vector. tries to make surplus of buyers as equal as possibleTheorem: Flow f is balanced iff there is no path from i to j with surplus(i) < surplus(j) in the residual graph corresponding to f .20/10020/6020/2070/140Example20/2040/4010/1060/601060202020Surplus vector = (80, 40, 0, 70)50/10010/600/2070/140Example20/2040/4010/1060/601060301020(80, 40, 0, 70) (50, 50, 20, 70)70/140How to raise the prices? Raise prices proportionatelyWhich goods ? goods connected to the buyers with the highest surplusijlj ijl ilp up u=l2-norm of the surplus vector decreases:  total surplus decreases Flow becomes more balancedNumber of max-flow computations:Buyers Goods 2 2( ( log log ))O n n U Mn+AlgorithmBuyers Goods l2-norm of the surplus vector decreases:  total surplus decreases Flow becomes more balancedNumber of max-flow computations:2 2( ( log log ))O n n U Mn+AlgorithmJain, Mahdian, S. (‘03): people can sell and buy at the same timeKakade, Kearns, Ortiz (‘03): Graphical economicsKapur, Garg (‘04): Auction AlgorithmDevanur, Vazirani (‘04): Spending ConstraintJain (‘04), Ye (‘04): Non-linear program for a general caseChen, Deng, Sun, Yao (‘04): Concave utility functionsFurther work, extensionsPrimal-dual scheme (Kelly, Low, Tan, …): primal: packet rates at sources dual: congestion measures (shadow prices) A market equilibrium in a distributed setting!Congestion ControlNext step: dealing with integral goodsApproximate equilibria:Surplus or deficiency unavoidableMinimize the surplus: NP-hard (approximation algorithm)Fair allocation: Max-min fair allocation (maximize minimum happiness) Minimize the envy (Lipton, Markakis, Mossel, S. ‘04)Core of a Game•••••V(S): the total gain of playing the game within