1,721,004 research outputs found
The Price of Stability for Undirected Broadcast Network Design with Fair Cost llocation is Constant
No full textWe consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the
Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in [2]. Our
result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T*, is able to restore local similarity by exploiting cost diffrences
between nearby players in T*
On the Convergence of Multicast Games in Directed Networks
No full textWe investigate the convergence of the price of anarchy after a limited number
of moves in the classical multicast communication game when the underlying
communication network is directed. Namely, a subset of nodes of the network are
interested in receiving the transmission from a given source node and can share the
cost of the used links according to fixed cost sharing methods. At each step, a single
receiver is allowed to modify its communication strategy, that is to select a communication
path from the source, and assuming a selfish or rational behavior, it will make
a best response move, that is it will select a solution yielding the minimum possible
payment or shared cost. We determine lower and upper bounds on the price of anarchy,
that is the highest possible ratio among the overall cost of the links used by
the receivers and the minimum possible cost realizing the required communications,
after a limited number of moves under the fundamental Shapley cost sharing method.
In particular, assuming that the initial set of connecting paths can be arbitrary, we
show an O(r
√
r) upper bound on the price of anarchy after 2 rounds, during each of
which all the receivers move exactly once, and a matching lower bound, that we also extend to Ω(r^(1+1/k)) for any number k ≥ 2 rounds, where r is the number of receivers.
Similarly, exactly matching upper and lower bounds equal to r are determined for
any number of rounds when starting from the empty state in which no path has been
selected. Analogous results are obtained also with respect to other three natural cost
sharing methods considered in the literature, that is the egalitarian, path-proportional
and egalitarian-path proportional ones. Most results are also extended to the undirected
case in which the communication links are bidirectional
The speed of Convergence in Congestion Games under Best Response Dynamics
No full textWe investigate the speed of convergence of best response dynamics to approximately optimal solutions in congestion games with linear delay functions. In Ackermann et al. [2008] it has been shown that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n. Motivated by such a negative result, we focus on the study of the states (not necessarily being equilibria) reached after a limited number of players' selfish moves, and we show that Θ(n log log n) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that every O(n) steps each player performs a constant (and nonnull) number of best responses. We show that such result is tight also for the simplest case of singleton congestion games
The price of stability for undirected broadcast network design with fair cost allocation is constant
No full textWe consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in Anshelevich et al. (2008). Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T^*, is able to restore local similarity by exploiting cost differences between nearby players in T^*
- …
