close

Вход

Забыли?

вход по аккаунту

История 2. Учитель;pdf

код для вставкиСкачать
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/--страниц
Пожаловаться на содержимое документа