Smoothing Out Focused Demand for Network Resources Kevin Leyton-Brown, Ryan Porter, Shobha Venkataraman, Balaji Prabhakar CS Department, Stanford University, Stanford CA 94305 fkevinlb;rwporter;shobhav;balajigs.stanford.edu ABSTRACT We explore the problem of sharing network resoures when agents' preferenes lead to temporally onentrated, ineÆient use of the network. In suh ases, external inentives must be supplied to smooth out demand. Taking a game-theoreti approah, we onsider a setting in whih bandwidth is available during several time slots at a xed ost, but all agents have a natural preferene for hoosing the same slot. We present four mehanisms that motivate agents to distribute load optimally by probabilistially waiving the ost for eah time slot, and analyze equilibria. 1. INTRODUCTION It is ommon for networks to experiene frequent ongestion even when average demand for the network is muh less than the network's apaity. In some networks, times of peak demand are regular and preditable. Suh foused loading an our beause many agents' utility funtions are maximized by using the network at some foal time. For example, studies of long-distane telephone networks show a spike in usage when rates drop in the evening [7, 1℄. Preditably heavy loads also our on web servers just before deadlines or just after new ontent or servies are made available. In this paper, we provide a game-theoreti analysis of several solutions to the problem of foused loading. There exists a substantial body of existing work on managing ongestion in networks. In partiular, the problem of designing ongestion ontrol and priing mehanisms to provide dierentiated qualities-of-servie (QoS) in the Internet has reeived a lot of attention. The essential issue is alloating network bandwidth fairly among onurrent users, given that agents are likely to at selshly to maximize the bandwidth available to them [9℄. This problem an be addressed with new tehnology: the network an isolate paket ows by ereting \bandwidth rewalls" to ensure fairness or approximate fairness [3, 4℄. An alternate line of researh takes an eonomi approah to ongestion management. The network attempts to indue agents to ondition their ows to presribed parameters, avoiding the implementation omplexity inherent in the tehnologial approah [6, 5, 8℄. Separate onsideration of the ase of foused loads is worthwhile for two main reasons. First, foused loading ours at Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2001 ACM 0-89791-88-6/97/05 ... 5.00. $ very preditable times. This means that it is possible to know in advane the ases for whih suh a speialized solution should be used. Seond, speialized solutions an do a better job of dealing with the problem of foused loading than more general approahes. Foused loading ours beause agents have similar utility funtions|partiularly, funtions that are maximized by using the network at a partiular time. General ongestion management tehniques annot take this information into aount; however, additional knowledge about agent utility funtions makes it possible to design mehanisms that ollet more revenue and make fewer (e.g., omputational) demands on the network. 2. PROBLEM DEFINITION We begin with a anonial example. Consider a telephone network in whih usage is divided into ten-minute bloks from the 5 PM rate drop until 8 PM. All agents prefer to use the phone network from 5:00 to 5:10, having stritly monotonially-dereasing valuations for later slots as ompared to earlier slots. Given that time slots are pried identially, rational agents would all hoose to use the network from 5:00 to 5:10, leading to a foused load. More formally, onsider the operation of a network over t time slots, where eah slot has a xed usage ost of m, and where n risk-neutral agents, a1 : : : an , intend to use the network. Agent ai 's valuation for slot s is given by an arbitrary funtion vi (s). Let vl and vu be lower and upper bounds on every agent's valuation respetively: i.e., 8i; s vl (s) vi (s) v u (s). Thus (for all i) let s = arg maxs vi (s) and s = arg mins vi (s). In setions 3 and 4 we make the assumption that vl = vu and hene that all agents have the same valuations for all slots (here we use the notation v rather than vi to desribe agents' valuations); we relax this assumption in setions 5 and 6. Agents may also have \names"|numerial identiers|denoted name(ai ). To spread out the foused load, the network will provide agents with an inentive to hoose other slots. In this paper we onsider mehanisms in whih agents are spared the usage ost for the slot they hoose aording to a probability depending on the slot hosen and independent of the probabilities orresponding to other slots. More formally, to prevent all agents from hoosing s, the network implements a mehanism to waive the usage ost for q of the t slots, on average. Free slots will be hosen aording to a probability distribution assoiated with eah slot s, whih we all p(s). The distribution of agents is denoted d, and so d(s) is the number of agents who hose slot s. The mehanism implemented by the network speies p; the network must draw (independently) from eah p(s) to determine if the usage ost will atually be waived for slot s. The number of free slots, q, is thus only an expeted value, and there is no guarantee on the total number P of slots that will atually be free. Observe that q = s p(s). We restrit ourselves to onsidering mehanisms in whih partiipation is rational for all agents who want to use the network, in all equilibria arising from that mehanism; thus we assume that all agents will partiipate. An impliation of this restrition is that in all equilibria, the expeted ost of using the network for any agent must be less than or equal to that agent's valuation for the slot he hooses. Finally, we assume that agents are risk neutral. In our model, agents must simply hoose a slot s. The spae of agent strategies may be seen as the spae of all funtions mapping from the information available to a probability distribution over slot hoies. We assume that agents are aware of the mehanism and onsider it when determining their strategies. A given agent's expeted utility for hoosing slot s is ui (s) = vi (s) (1 p(s))m. It might appear that more powerful mehanisms ould be designed if pries ould be varied arbitrarily, as opposed to slots pried at either m or 0. In fat, risk-neutral agents are indierent between any slot pried on the range [0; m℄ and the same slot made free with an appropriate probability. 2.1 Evaluating Outcomes The network has two goals: to balane the load aused by the agents' seletion of slots and to ollet as muh revenue as possible. We denote the network's expeted revenue given a mehanism and distribution d as E [Rj; d℄. The network ollets a payment of m from eah partiipating agent exept for those who reeive free slots. As the number of agents is xed and the mehanism is onstrained so that partiipation is rational for all agents, expeted revenue depends only on the likelihood of the usage fee being waived for eah slot and on whih slots agents selet. We dene g as the monetary value to the network of the variane of load aross the set of time slots. Lower variane orresponds to a more even load and so has a higher dollar value; thus g must derease stritly as variane inreases. We will that load is balaned when g is maximized, whih orresponds to minimal variane. We dene the superlinear summation lass ofP funtions to be the set of funtions in whih g(d) = i h(d(i)), where h is superlinear in d(i) and is a onstant that is used to indiate the relative value of load balaning to the network. Maximizing revenue and maximizing g are oniting goals, as it osts the network more to indue an agent to hoose slot s than it does to indue an agent to hoose slot s. (Indeed, note that revenue is maximized when all agents hoose s|i.e., under foused loading|beause agents are willing to distribute themselves in this way without the appliation of any external inentives.) The network must therefore trade o quality of load balaning against expeted revenue; the degree of trade-o desired may be speied through the hoie of . We dene z, the evaluation of distribution d under equilibrium ' of mehanism : z(; d) = E [Rj; d℄ + g (d). First we dene optimality: Definition 1. A mehanism-equilibrium0 pair (; ') is 0 optimal if and only if for all other pairs ( ; ' ) and for all d; d0 resulting from ' and '0 respetively, z (; d) z (0 ; d0 ), where n is held onstant. This denition of optimality is inappropriate for the ase where agents have dierent valuation funtions that are not known by the network|the ase we take up in setions 5 and 6. In the event that the network's bounds on agents' valuations are not tight, the best mehanism that the network an hoose will not extrat the maximal amount of revenue from eah agent, and so will not be optimal as dened above. Instead, we provide an alternate notion of optimality that bounds the average loss per agent. Definition 2. A mehanism-equilibrium0 pair0 (; ') is optimal if and only if for all other pairs ( ; ' ) and for all d; d0 resulting from ' and '0 respetively, z (; d) + n z (0 ; d0 ), where n is held onstant and > 0. We also use the term optimal to refer to equilibria alone when the mehanism giving rise to the equilibrium is unambiguous. Finally, we give a denition to desribe the best possible distribution of agents given a mehanism. A distribution is ideal if it maximizes z given the mehanism. Definition 3. A distribution d is ideal for mehanism if and only if d= arg maxd z(; d0 ). In suh a ase we supersript d as d 0 to highlight the fat that it is ideal . 3. PENNY MATCHING Here we onsider a simple mehanism designed to make agents indierent between all time slots despite their initial preferenes. We all it `penny mathing', sine agents must guess what slots the network will make free; more formally, we denote this mehanism as 1 . The mehanism follows: 1. Free slots are determined by drawing from p. 2. Agents hoose a slot. All things being equal, agents prefer slot s to slot s. We an overome this preferene by biasing p(s). Reall that an agent's expeted utility is given by ui (s) = v(s) (1 p(s))m. We an make agents indierent between slots by requiring that all time slots will have the same expeted utility for agents: that is, that the expeted utility derived from eah time slot is equal to the average expeted utility over all time slots. This is expressed by the equation v(s) (1 p(s))m = 1 P (v (i) (1 p(i))m). Rearranging, we get: i t 1 (qm + p (s) = t Pi v(i)) v (s) (1) If free slots are awarded aording to p, it is a weak equilibrium for all agents to selet a slot uniformly at random. We all this equilibrium '1 . Consider the ase where all other agents play aording to '1 , and one remaining agent ai must deide his strategy. Sine the hoie of any slot entails equal utility on expetation, ai an do no better than to randomly pik a slot. '1 is a weak equilibrium: indeed, there is no strategy that would make ai worse o. It appears that deviation from '1 will never be protable for agents, sine we have guaranteed that all slots provide the same expeted utility. Consider the most protable deviation, from s to s. We have laimed that utility of both slots is the same: v(s) (1 p(s))m = v(s) (1 p(s))m. Sine we want to interpret p(s) and p(s) as probability measures, p(s) 0 and p(s) 1. Substituting the onstraints into equation (1), we get tv(s) m v(i) q t(v(s)+mm) v(i) . We must also ensure that a value of q exists for a given m and v. Interseting the two bounds and simplifying gives us m i i We now show howPthe network an maximize revenue. We dene vavg as 1t s v(s). The requirement that an agent's utility for slot s must be greater than or equal to zero|i.e., thatv(s) (1 p(s))m q 0|an be rewritten, substituting in p , as vavg (1 t )m 0. The seller's revenue will be maximized qwhen all agents get zero utility. Thus we must have (1 t )m = vavg . There is a range of q and m values that will satisfy this equation; here we show one. We substitute in the lower bound for q from setion 3. Rearranging, we get m = v(s). This satises the onstraint on m, so we are done. Intuitively, we have shown that we an ollet maximum revenue: we an ensure that on expetation eah agent will pay an amount exatly equal to his utility for any slot he hooses. However, '1 is not guaranteed to ahieve an optimal distribution of agents, and therefore, '1 is not optimal. The easiest way to show this is to present another equilibrium of 1 that is optimal. Consider an equilibrium in whih eah of the agents deterministially hooses one slot. (Reall that any strategy is rational under 1 , and thus that any set of strategies is a weak equilibrium.) In one suh equilibrium, agents deterministially hoose slots so that thedistribution of all agents is ideal ; we all this equilibrium '1 . Unsurprisingly: Theorem 1. (1 ; '1 ) is optimal. m v(s) v (s). All proofs are deferred to the full version of the paper. '1 is optimal, but it is extremely unlikely that this equilibrium would arise through the hoies of real agents. This drawbak is inherent to the setting as we have modeled it so far; a \mathing pennies" mehanism an only yield weak equilibria. In the next three setions, we explore more omplex mehanisms that give rise to strit equilibria. 4. BULLETIN BOARD SYSTEM In this setion we assume that agents are given a bul: a forum in whih all ommuniations are visible to all agents and the identity of agents is assoiated with their transmissions. For simpliity, we allow a very limited form of ommuniation: agents sequentially indiate the slot that they intend to hoose. Let db (s) denote the number of agents who have indiated that they will hoose slot s. Agents' ommuniations through the bulletin board are heap talk : a tehnial term that indiates that these ommuniations are not binding in any way. Even so, the bulletin board an help agents to oordinate on desirable equilibria without the use of names. Mehanism 2 follows: 1. \Potentially free"1 slots hosen aording to (1+ ")p . 2. Agents ommuniate through the bulletin board. 3. Agents hoose time slots. 4. If d = d , then \potentially free" slots are made to be free. Otherwise, all agents are made to pay. A strit equilibrium in 2 , alled '2 , is for the ith agent to hoose a slot s suh that di 1 (s) < di (s); to indiate his hosen slot s on the bulletin board; and ultimately to hoose that slot s. Consider the ase where all other agents follow '2 and agent ai must deide his strategy. If ai ooperates and hooses slot s then the distribution of agents is guaranteed to be d and so ai will reeive an expeted utility of 1 We redene q as the expeted number of \potentially free" slots; the same redenition is required for setion 6. letin board system (1 (1+ ")p(s))m. If ai defets to slot s0 , one of two ases will result. In the rst ase, agents indiating their hoies after ai will ompensate for his deviation by hoosing dierent slots; thus ai will reeive the same expeted utility as he would have reeived if he had not deviated. In the seond ase, ai will be late enough in the sequene of agents indiating their hoies that the agents who indiate after him will be too few to bring the distribution bak0 to d. In this ase ai will reeive an expeted utility of v(s ) m. Sine ai does not know the total number of agents, he must assign non-zero probability to the seond ase, regardless of the number of agents who have already indiated. Therefore '2 is strit as long as v(s) + (1 + ")p(s)m > v(s0) for all s; s0 suh that 1 s; s0 t. Simplifying, we derive the same onditions on q and m desribed above, exept that the probability of a free slot is inreased to make '2 strit. It is well known that any game having an equilibrium arising from heap talk oordination has other equilibria in whih agents ignore the heap talk [2℄. 2 is no exeption. All agents hoosing s (foused loading) is an equilibrium when the resulting d ould not be transformed into d by one agent hoosing a dierent slot. Note, however, that '2 Pareto-dominates all equilibria where the heap talk is ignored. Beause of this equilibrium, we know that m annot be set above v(s), beause agents would reeive negative utility in equilibrium. For this reason, we an do no better than setting m as in setion 3. Note that there an never be an equilibrium in whih partiipation is irrational if m v(s), beause agents who hoose slot s will always have nonnegative utility. v (s) Theorem 2. whih ' There does not exist an optimal is a strit equilibrium and m v (s). (; ') for However, there exists no equilibrium of any other mehanism yielding z larger than z(2 ; '2 ) + ". Theorem 3. (2 ; '2 ) is "-optimal. Note that in '2 eah agent hooses a slot that would result in an optimal distribution if he were the last agent to post to the bulletin board. In the full version of the paper, we show that we an assign names to agents greedily with the guarantee of ahieving the ideal distribution for whatever number of agents eventually partiipate. 5. COLLECTIVE REWARD We now onsider the more general ase where eah agent may have a dierent vi , bounded by vl and vu , as desribed in setion 2. In this setion we introdue the assignment of agent names as a mehanism for the agents to oordinate to a desirable equilibrium, and also show how olletive reward may be used to prevent agents from deviating. We dene mehanism 3 as follows: 1. 2. 3. 4. Eah agent indiates that he will partiipate. Integral names are assigned to agents from [1; t℄. Eah agent indiates what slot he selets. After all agents have seleted their slots, the network determines whether eah slot will be made free. The hane that slot s will be free, p(s), depends on the number of agents who hose that slot, d(s). Let ount(s) be the number of agents who were given the name s. Dene d+ (s) = d(s) ount(s). For 3 : pl (s) if d+ (s) 0 p(s) = f (2) 0 if d+(s) > 0 Intuitively, we onstrut pl so that eah agent ai will partiipate in the worst ase for 3 : when ai has the lowest possible valuation for the slot orresponding to his name, and the highest possible valuation for all other slots. The derivation of pl ensures that no agent will deviate regardless of his atual v. We follow the derivation of p , with some hanges. The equation lto make agents indierent P between all slots is hanged to: v (s) (1 pl (s))m = 1t i (vu(i) (1 pl (i))m). The left-hand side uses vl so that it represents the lowest possible value for the expeted utility of a slot s that the agent ould reeive free. The right-hand side uses vu beause it represents the most an agent an reeive by hoosing another slot. If this equality holds, then for all possible v funtions for an agent, he will not have inentive to deviate. Algebrai manipulation gives: 1 (qm + P v u (i)) v l (s) i pl (s) = t (3) m As in setion 3, we an derive bounds on q and m. In this ase the most protable possible deviation is from s with a valuation of vl (s) to s with a valuation of vu (s). This leads to the following natural ondition on m whih shows us how to reate a large enough pl to ensure that no agent deviates: m vu (s) vl (s). It also follows that the inequality vu (s) m vl (s) (1 pl (s))m must hold. Substituting in the additional onstraint of pl(s) 0 and rearranging, we get q tv (s) m v (i) . 3 sets m > vu (s) so that it is never rational for an agent to deviate. We then plug m into the bound on q given above and set q as small as possible to maximize expeted revenue. An equilibrium '3 is for eah agent aj to selet the slot orresponding to its number. Consider the ase where all other agents follow this strategy, and one remaining agent ai deides his strategy. If agent ai selets slot s as above then his expeted utility is ui (s)0 = vi (s) 0 (1 pl(s))m. Deviating 0 to slot s gives him ui (s ) = vi (s ) m. The dierene between these two options is ui (s) ui (s0 ), whih simplies to at least the sum of two positive terms: (vi (s) vl (s)) + (vu (s) vi (s0 )). Sine agents an only lose by deviating, '3 is a strit equilibrium. There are no equilibria of 3 for whih d 6= d . Consider any distribution of agents suh that d 6= d . There must be some s1 suh that d+ (s1 ) < 0, and some other s2 suh that d+ (s2 ) > 0. An agent in s2 thus has no hane of a free slot, and he reeives negative utility for this slot, beause m > v u (s). If he swithes to s1 , then his probability of reeiving a free slot beomes pl(s1 ) beause d+ (s1 ) 0. Sine pl is onstruted to make partiipation rational, the agent must reeive nonnegative expeted utility for this slot, ontraditing the laim that staying in s2 was an equilibrium. Theorem 4. '3 is -optimal, = maxs (vu (s) vl (s)). whih ould be ostly to the network. Also, 2 has nonoptimal equilibria. Finally, irrational agents an harm others in both 2 and 3 . These problems are eliminated by 4 , whih makes use of agent names and also disriminates by oering dierent free slots to dierent agents: 1. Eah agent indiates that he will partiipate. 2. Integral names are assigned to agents from [1; t℄. 3. \Potentially free" slots are hosen aording to pl . 4. Eah agent indiates what slot he selets. 5. The network heks only those agents in eah slot si that was piked to be \potentially free". If agent aj in slot si has name(aj ) = si then he reeives the free slot; otherwise he is made to pay. Agent ai 's dominant strategy is to hoose the slot that may be free for him. The analysis is the same as for '3 ; we all this equilibrium '4 . Sine '4 results from (strongly) dominant strategies, it is unique. By theorem (4), dl is u l optimal for 4 , = maxs (v (s) v (s)). It may seem disappointing from a game-theoreti point of view that neither strategy nor even payos under 4 depend on the ations of other agents. However, we feel that this is an advantage of 4 , sine irrational agents are not able to harm others, retroative payments to agents are not required, and the only equilibrium that exists is -optimal. 6. [8℄ l i u DISCRIMINATORY MECHANISM A disadvantage of both 2 and 3 is that they reimburse some agents at the end of the game rather than simply waiving their fees. This requires traking individual agents' behavior and exeuting more nanial transations, both of 7. CONCLUSION Foused loading is a preditable problem that ours in real networks. We present a theoretial model of the problem and disuss four mehanisms that indue selsh agents to smooth out their resoure demands. We show a simple mehanism that ahieves a weak load-balaning equilibrium, and three more omplex mehanisms that balane load in strit equilibria or dominant strategies. Two of our mehanisms assume that all agents value time slots identially, and two generalize to the ase where only upper and lower bounds are known on agent valuations. In the future we intend to examine the ases where agents have unrestrited valuations for time slots, and make resoure demands of different magnitudes. 8. [1℄ [2℄ [3℄ [4℄ [5℄ [6℄ [7℄ [9℄ REFERENCES D. Blair. Impat of the Internet on ore swithing network. In Pro. of ENPW'98, Les Ars, Frane, Marh 1998. V.P. Crawford and J. Sobel. Strategi information transmission. Eonometria, 50(6):1431{1451, November 1982. A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queuing algorithm. Journal of internetworking researh and experiene, pages 3{26, Otober 1990. S. Floyd and V. Jaobson. Random early detetion gateways for ongestion avoidane. IEEE/ACM Transations on Networking, 1(4):397{413, August 1993. R. Gibbens and F. Kelly. Resoure priing and the evolution of ongestion ontrol. Automatia, 35:1969{1985, 1999. J.K. MaKie-Mason and H. Varian. Priing the internet. In B. Kahin and J. Keller, editors, Publi Aess to the Internet. Prentie-Hall, 1994. B. Mithell. Priing poliies in seleted European telephone systems. In Proeedings of 6th Conferene on Teleommuniations Poliy Researh, pages 437{475, 1978. A. Odlyzko. A modest proposal for preventing internet ongestion. Tehnial Report TR 97.35.1, AT&T Researh, September 1997. S. Shenker. Making greed work in networks: A game-theoreti analysis of swith servie disiplines. IEEE/ACM Transations on Networking, 3:819{831, 1995.

1/--страниц