We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by [PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of 3 2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6 5-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of @math for the metric min-max facility location problem, where n is the number of clients.
@cite_13 investigated NCGs, where agents cannot buy every possible edge. Furthermore, @cite_17 recently analyzed a bounded-budget version. Both versions seem realistic, but in the following we do not restrict the set of edges which can be bought or the budget of an agent. Clearly, such restrictions reduce the qualitative gap between simple and arbitrary strategy-changes and would lead to weaker results for our analysis. Note, that this indicates that outcomes found by simple agents in the edge or budget-restricted version may be even more stable than we show in the following sections.
@cite_13 @cite_17
2225272567 2555059222 2007583146 2132936659
We study the complexity of motivating time-inconsistent agents to complete long term projects in a graph-based planning model as proposed by Kleinberg and Oreni¾?[5]. Given a task graph G with n nodes, our objective is to guide an agent towards a target node t under certain budget constraints. The crux is that the agent may change its strategy over time due to its present-bias. We consider two strategies to guide the agent. First, a single reward is placed at t and arbitrary edges can be removed from G. Secondly, rewards can be placed at arbitrary nodes of G but no edges must be deleted. In both cases we show that it is NP-complete to decide if a given budget is sufficient to guide the agent. For the first setting, we give complementing upper and lower bounds on the approximability of the minimum required budget. In particular, we devise a @math 1+n-approximation algorithm and prove NP-hardness for ratios greater than @math n 3. Finally, we argue that the second setting does not permit any efficient approximation unless @math P=NP. We study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is locally envy-free if no agent envies a neighbor's allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors' allocations. We generalize the classical Cut and Choose" protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious single-cutter protocol can give locally envy-free (thus also locally-proportional) allocations. We study the price of envy-freeness , which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of @math on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more flexibility asymptotically with respect to the quality of envy-free allocations. We study network design games where @math self-interested agents have to form a network by purchasing links from a given set of edges. We consider Shapley cost sharing mechanisms that split the cost of an edge in a fair manner among the agents using the edge. It is well known that the price of anarchy of these games is as high as @math . Another line of research has focused on evaluating the price of stability, i.e., the cost of the best Nash equilibrium relative to the social optimum. In this paper we investigate to which extent coordination among agents can improve the quality of solutions. We resort to the concept of strong Nash equilibria, which were introduced by Aumann and are resilient to deviations by coalitions of agents. We analyze the price of anarchy of strong Nash equilibria and develop lower and upper bounds for unweighted and weighted games in both directed and undirected graphs. These bounds are tight or nearly tight for many scenarios. It shows that, by using coordination, the price of anarchy drops from linear to logarithmic bounds. We complement these results by also proving the first superconstant lower bound on the price of stability of standard equilibria (without coordination) in undirected graphs. More specifically, we show a lower bound of @math for weighted games, where @math is the total weight of all the agents. This almost matches the known upper bound of @math . Our results imply that, for most settings, the worst-case performance ratios of strong coordinated equilibria are essentially always as good as the performance ratios of the best equilibria achievable without coordination. These settings include unweighted games in directed graphs as well as weighted games in both directed and undirected graphs. We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. Next, we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. For infinite numbers of n, we construct an equilibrium tree with diameter Θ(n) in the MAX version. Also, we prove that the diameter of any equilibrium tree is O(log n) in the SUM version and this bound is tight. When all vertices have unit budgets (i.e. can establish link to just one vertex), the diameter in both versions is O(1). We give an example of equilibrium graph in MAX version, such that all vertices have positive budgets and yet the diameter is as large as Ω(√log n). This interesting result shows that the diameter does not decrease necessarily and may increase as the budgets are increased. For the SUM version, we prove that every equilibrium graph has diameter 2O(√log n) when all vertices have positive budgets. Moreover, if the budget of every players is at least k, then every equilibrium graph with diameter more than 3 is k-connected.