We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means graph in which nodes represent agents and edge weights the degree preference corresponding endpoints. The happiness or utility an agent for being is average value she ascribes to its members. adopt Nash stable outcomes as target solution concept; we focus on states no improve her unilaterally changing own group. provide existence, efficiency complexity results played...

We study the existence of allocations indivisible goods that are envy-free up to one good (EF1), under additional constraint each bundle needs be connected in an underlying item graph G. When items arranged a path, we show EF1 guaranteed exist for arbitrary monotonic utility functions over bundles, provided either there at most four agents, or any number agents but they all have identical functions. Our proofs based on classical arguments from divisible cake-cutting setting, and involve...

To what extent does the structure of players' strategy space influence efficiency decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games which players can only choose among single resources. We consider three different concepts, namely, approximate pure Nash equilibria, one-round walks generated by selfish aiming at minimizing their personal cost and cooperative marginal increase sum costs....

Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium network congestion games with adversarial link failures, where agents need to route traffic from a source destination node. Given an integer [Formula: see text], ρ-uniform strategy is which agent plays exactly ρ edge-disjoint paths probability; therefore, tuple strategies, one for each agent, no can lower her cost deviating another strategy. For weighted and affine...

In the non cooperative version of classical minimum bin packing problem, an item is charged a cost according to percentage used space it requires. We study game induced by selfish behavior items which are interested in being packed one bins so as minimize their cost. prove that such always converges pure Nash equilibrium starting from any initial items, estimate number steps needed reach equilibrium, hardness computing good equilibria and give upper lower bound for price anarchy game. Then,...

We consider broadcast network design games in undirected networks which every player is a node wishing to receive communication from distinguished source s and the cost of each link equally shared among downstream receivers according Shapley value. prove that Price Stability such constant, thus closing long-standing open problem raised [2]. Our result obtained by means homogenization, new technique that, any intermediate state locally diverging given optimal solution T*, able restore local...

We consider fractional hedonic games, where self-organized groups (or clusters) are created as a result of the strategic interactions independent and selfish players happiness each player in group is average value she ascribes to its members. adopt Nash stable outcomes, that states no can improve her utility by unilaterally changing own group, target solution concept. study quality best outcome refer ratio social welfare one an optimal clustering price stability. remark has natural meaning...

We consider the efficiency of taxation in congestion games with polynomial latency functions along line research initiated by [Caragiannis et al., ACM Transactions on Algorithms, 2010] who focused both pure and mixed Nash equilibria affine latencies only. By exploiting primal-dual method [Bilo, Proceedings 10th Workshop Approximation Online 2012], we obtain interesting upper bounds respect to a variety different solution concepts ranging from approximate up coarse correlated equilibria,...

We study the complexity of decision problems about symmetric Nash equilibria for multi-player games. These concern existence a equilibrium with certain natural properties. show that handful such are Existential-R-complete; is, they exactly as hard deciding Existential Theory Reals.

Abstract Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential explains how such clusters even if all agents are tolerant, i.e., they agree live mixed neighborhoods. For occur, it needs slight bias towards preferring similar neighbors. Very recently, has been investigated from...

In hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on stable outcome. this work, we initiate the study games with fixed-size coalitions, where structures is restricted as follows: there are k each has fixed size, and sum sizes coalitions equals n. We focus basic model additively separable symmetric preferences, an agent's preference captured by utility function which sums up contribution due any other agent in same coalition....

In the non cooperative version of classical minimum bin packing problem, an item is charged a cost according to percentage used space it requires. We study game induced by selfish behavior items which are interested in being packed one bins so as minimize their cost. prove that such always converges pure Nash equilibrium starting from any initial items, estimate number steps needed reach equilibrium, hardness computing good equilibria and give upper lower bound for price anarchy game. Then,...

After almost seven years from its definition, 2 the price of stability undirected network design games with fair cost allocation remains to be elusive. Its exact characterization has been achieved only for basic case two players 2,7 and, as soon number increases, gap between known upper and lower bounds becomes super-constant, even in special variants multicast broadcast games. Motivated by intrinsic difficulties that seem characterize this problem, we analyze already challenging three...

We consider the efficiency of taxation in congestion games with polynomial latency functions along line research initiated by Caragiannis et al. [ ACM Transactions on Algorithms , 2010], who focused both pure and mixed Nash equilibria affine latencies only. By exploiting primal-dual method [Bilò, Proceedings 10th Workshop Approximation Online 2012], we obtain interesting upper bounds respect to a variety different solution concepts ranging from approximate up coarse correlated equilibria,...