Exploring Network Economics Dah Ming Chiu Department of Information

Exploring Network Economics Dah Ming Chiu Department of Information Engineering Chinese University of Hong Kong August 6, 2012 DM Chiu, CUHK

Outline What is network economics? – Why are we interested – Examples – Some classic models and tools – Some opinions and advices DM Chiu, WY Ng, “Exploring network economics”, arxiv preprint server , (http://arxiv.org/pdf/1106.1282v1.pdf), Jun 2011 August 6, 2012 DM Chiu, CUHK

Why are we interested? Engineering: – Is about building things But a network (especially the Internet) is – Basic infrastructure (like air, water) – Shared by many users – Managed, owned by different entities Faced with many economic issues August 6, 2012 DM Chiu, CUHK

Consider congestion control It is an engineering problem: – How to detect congestion? – How to control it without oscillation It is also an economic problem: – E.g. who should yield first? – Whose resource is allowed to congest more? – One person welfare affected by others’ actions, known as “externalities” in economics August 6, 2012 DM Chiu, CUHK

Congestion control with fairness A fairness measure derived axiomatically: – R Jain, DM Chiu and W Hawe, “A Quantitative Measure of Fairn ess and Discrimination for Resource Allocation in Shared Comp uter Systems”, DEC Tech Report 301, 1984, Arxiv preprint cs.NI/ 9809099, 1998. A simple distributed algorithm – Additive In crease Multiplicative Decrease (AIMD) – DM Chiu and R Jain, “Analysis of Increase and Decrease Algorit hms for Congestion Avoidance in Computer Networks”, Journal of Computer Networks and ISDN, 17(1), 1989 August 6, 2012 DM Chiu, CUHK

Utility maximization – Frank Kelly Maximize U(x1) U(x2) U(xn) – Subject to capacity constraints on xi, Ax c – U() is concave, non-decreasing, “elastic” – If all flows sharing a single bottleneck Clearly, more equal more optimal – If flows sharing different paths in a network Proportional fairness suggested by model F Kelly, AK Maulloo and D Tan, “Rate control for communication netwo rks: shadow prices, proportional fairness and stability”, Journal of th e Operational Research Society, 49(237-252), 1998. August 6, 2012 DM Chiu, CUHK

The issue is hardly settled What if flows are selfish? – “Price of anarchy”: study gap between optimal and anarchy – Game theory concepts used What if utility functions are not elastic? – TCP-friendly congestion control – Admission control together with congestion control When users have different utility functions – Auction, submodular utility maximization, matching algorithms – Combinatorial algorithms, theoretical computer science Should network operators interfere? – Net neutrality – Cloud computing, private networks August 6, 2012 DM Chiu, CUHK

Selfish behavior “Tragedy of the Commons” – William Forster Lloyd, Cambridge professor, in his criti que of Adam Smith’s “Invisible Hand”, in 1800s – Garrett Harding, ecologist, wrote the article with that ti tle, published in Science in1968. Price of anarchy – A phrase coined by C Papadimitriou (UC Berkeley) – Focus on determining the gap between the decentrali zed equilibrium, and the optimal – E.g. R Johari (MIT, Stanford) showed the gap is not bi g (for congestion control) under some assumptions August 6, 2012 DM Chiu, CUHK

Braess Paradox T number of cars going from START to END 4000 t time it takes on each road Adding a super highway between A and B makes the time longer for everyone! August 6, 2012 DM Chiu, CUHK

Selfish routing For general networks of the kind in Braess Para dox, what is the gap between “selfish routing” an d optimal routing? – T Roughgarder’s PhD thesis (Cornell), around 2002 – He answered the question for some special cases onl y August 6, 2012 DM Chiu, CUHK

Accommodating different interests In general, different users have different utility fu nctions – How to maximize social welfare, or profit? – Usually combinatorial problem: computationally hard Some mechanisms studied/used commonly: – Auctions – Matching algorithms While more optimal, harder to apply in real-time Excellent book: “Combinatorial Auctions”, Edited by Peter Cramton, Yoav Shoham and Richard Steinberg, The MIT press, 2006 August 6, 2012 DM Chiu, CUHK

Auctions Many variations for different applications: – Single good, divisible vs non-divisible goods, multiple copies of same good, combinations of goods – Application to communication network resources need to consider their characteristics – Notable use: wireless spectrum allocation Strategy-proof auctions – Attracts a lot of theoretical interests – Most well-known: 2nd price auction, or VCG auction August 6, 2012 DM Chiu, CUHK

The Stable Marriage Problem A different formulation – – – – Preference lists instead of utility functions Stable matching vs optimal matching Very practical problem/formulation Less general than utility based formulation, but existe nce of simple practical algorithms D. Gale and L. S. Shapley: "College Admissions and the Stability of Ma rriage", American Mathematical Monthly 69, 9-14, 1962 Jian Liu, Dah Ming Chiu: Reciprocating Preferences Stablizes Matchin g: College Admissions Revisited CoRR abs/1011.1135: (2010) August 6, 2012 DM Chiu, CUHK

Mechanism design Set some rules, so that the “selfish behavior” automatically leads to optimal solution (social welfare or profit) – “Allow only to catch lobsters less than one pound” – At the HK Internet Exchange, only multi-lateral peering is accepted – VCG auctions August 6, 2012 DM Chiu, CUHK

Game theory Formulation – Two or more players – Each players payoff (utility) is defined as a function of the actions of all players – Many types of games, different rules etc The important concept is equilibrium: – The choice of an action by each player that she will not deviate from given actions by the other players Theorist also care about uniqueness, stability, computation complexity August 6, 2012 DM Chiu, CUHK

Network effect Congestion - negative externality Network effect - positive externality What is network effect? – The value brought by population of a network Examples – Communications network – Social network – Content distribution network August 6, 2012 DM Chiu, CUHK

Network valuation Metcalf’s Law – A network with n nodes allows up to O(n2) connection s, hence value is O(n2) Odlyzko’s Law – Each node (user) only connects to a small subset of o ther nodes, e.g. log(n), hence value is O(nlog(n)) – Blamed Metcalf’s Law for Internet bubble of 2000 Content distribution model – Value is number of eyeballs, O(n)? August 6, 2012 DM Chiu, CUHK

ISP networks and peering ISPs are collaborators as well as competitors – If networks are not connected, they are worth less – If connected, how to share the created value? In the Internet today bilateral peering – Terms based on perceived service or value exchange – A transit provider charges access ISPs and content IS Ps for transit service – Local (access ISPs) may peer with each other for free – Local ISPs eyeballs, content ISPs has content – When local ISP peers with content ISP, who pays wh o? August 6, 2012 DM Chiu, CUHK

ISP problems C B T ISP ISP ISP 1. When Content ISP peers with Eyeball ISP, who pays who? 2. How do they pay transit providers? 3. Can transit providers charge differently, e.g. by providing different services? The Net Neutrality debate For information, visit “Workshop of Internet Economics 2011”, http://www.caida.org/workshops/wie/1112/ August 6, 2012 DM Chiu, CUHK

Shapley Values A theory on cooperation – For a team of collaborators, how to evaluate each member’s con tribution? – Exhaustively remove each member to determine the value of tha t member Lloyd S. Shapley. "A Value for n-person Games". In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mat hematical Studies v. 28, pp. 307–317. Princeton University Press, 1953 We tried to apply this to the ISP problem RTB Ma, DM Chiu, JCS Lui, V Misra, D Rubenstein, "Internet Economics: The use of Shapley value for ISP settlement", IEEE/ACM Transcations on Netwo rking, 18(3), pp 775-789, 2010 August 6, 2012 DM Chiu, CUHK

P2P Network formation Will a network form, given free-riders? – Assume cost of contributing depends inversely on number of con tributors – Each peer has a “generosity” level, when it is higher than the cos t, the peer contributes M Feldman et al, “Free-riding and whitewashing in peer-to-peer systems”, PINS Workshop, part of Sigcomm 2004. We tried a different formulation – Peers join if there is sufficient “interest”, based on other peers alr eady joined WY Ng, DM Chiu and WK Lin, “Club Formation by Rational Sharing: Content, Viability an d Community Structure”, Algorithmica 52(1), 80-94, 2008 August 6, 2012 DM Chiu, CUHK

Hotelling’s model Example of a simple model that can be adapted for analy zing ISP and its users – Competing ISPs need to make some decisions – Users decide their actions based on ISPs’ actions – ISPs can decided based on known user reactions H Hotelling, "Stability in Competition", Economic Journal 39 (153): 41–57, 1929 August 6, 2012 DM Chiu, CUHK

Paris Metro Pricing Divide network into two parts, charging different (or the s ame) prices – Users decide which network to join – Will the overall network better than a single network, in terms of social welfare or profit? – We can analyze this using a similar approach as Hotelling’s – The answer is, it depends on the user’s utility function, which ne eds to be “multiplexing preferring” rather than “partitioning prefer ring”. Chi-Kin Chau, Qian Wang, Dah-Ming Chiu: On the Viability of Paris Metro Prici ng for Communication and Service Networks. INFOCOM 2010: 929-937 August 6, 2012 DM Chiu, CUHK

The nightmare of P2P traffic Problems: Strong local ISP providing transit service to users in other ISPs P2P users using unfair amount of bandwidth Our works: JH Wang, DM Chiu and JCS Lui, " Modeling the Peering and Routing Tussl e between ISPs and P2P Applications", IEEE IWQoS, 2006 Q Wang, DM Chiu and JCS Lui, "ISP Uplink Pricing in a Competitive Marke t", ICT 2008, St Petersburg. August 6, 2012 DM Chiu, CUHK

Some advices Be careful choosing “network economics” as a research area – Harder to publish papers, and make a career Instead, study networking problems using economics knowledge Good results tend to be qualitative – Key is to bring new insights to real problems – Formulate problem carefully, consider all important stakeholders – Check result with intuition, people in the trade August 6, 2012 DM Chiu, CUHK

Advices continued Mathematical tools are important, but spend ti me to appreciate economic thinking A couple of books for easy reading: 1) 2) “Invitation to Economics – Understanding Argument and Policy” b y T Harding, Wiley-Blackwell, 2009 “Principles of Economics”, by NG Mankiw, South-Western Cenga ge Learning, textbook from Harvard University August 6, 2012 DM Chiu, CUHK