1,721,024 research outputs found
An exponential improvement on the MST heuristic for the Minimum Energy Broadcasting problem
No full textThe price of stability for undirected broadcast network design with fair cost allocation is constant
No full textHedonic games with social context
No full textHedonic games are coalition formation games in which coalitions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and studying a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs
Stable outcomes in modified fractional hedonic games
No full textIn coalition formation games self-organized coalitions are created
as a result of the strategic interactions of independent agents. For
each couple of agents (i, j), weight wi,j = wj,i reflects how much
agents i and j benefit from belonging to the same coalition. We
consider the modified fractional hedonic game, that is a coalition
formation game in which agents’ utilities are such that the total
benefit of agent i belonging to a coalition (given by the sum of wi,j
over all other agents j belonging to the same coalition) is averaged
over all the other members of that coalition, i.e., excluding herself.
Modified fractional hedonic games constitute a class of succinctly
representable hedonic games.
We are interested in the scenario in which agents, individually
or jointly, choose to form a new coalition or to join an existing
one, until a stable outcome is reached. To this aim, we consider
common stability notions, leading to strong Nash stable outcomes,
Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general
weights and in the case of 0-1 weights. In particular, we completely
characterize the existence of the considered stable outcomes and
show many tight or asymptotically tight results on the performance
of these natural stable outcomes for modified fractional hedonic
games, also highlighting the differences with respect to the model
of fractional hedonic games, in which the total benefit of an agent
in a coalition is averaged over all members of that coalition, i.e.,
including herself
Uniform Mixed Equilibria in Network Congestion Games with Link Failures
No full textMotivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer p >_ 1, a p-uniform mixed strategy is a mixed strategy in which an agent plays exactly p edge-disjoint paths with uniform probability; therefore, a p-uniform mixed equilibrium is a tuple of p-uniform mixed strategies, one for each agent, in which no agent can lower her cost by deviating to another p-uniform mixed strategy. For games with weighted agents and affine latency functions, we show the existence of p-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted agents, we extend the existential guarantee to any class of latency functions, and restricted to games with affine latencies, we derive a tight characterization of the price of anarchy and the price of stability
Hedonic games with social context
No full textHedonic games are coalition formation games in which coalitions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and studying a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs
On Best Response Dynamics in Weighted Congestion Games with Polynomial Delays
No full textWe investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. In [1] it has been shown that the convergence cane of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, extending the work of [11] we show that Theta(n log log W) (where W is the sum of all the players' weights) 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 non-mill) number of best responses
- …
