Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
The Price of Anarchy in Bilateral Network Formation in an Adversary Model  [PDF]
Lasse Kliemann
Computer Science , 2013,
Abstract: We study network formation with the bilateral link formation rule (Jackson and Wolinsky 1996) with $n$ players and link cost $\alpha>0$. After the network is built, an adversary randomly destroys one link according to a certain probability distribution. Cost for player $v$ incorporates the expected number of players to which $v$ will become disconnected. This model was previously studied for unilateral link formation (K. 2011). We prove existence of pairwise Nash equilibria under moderate assumptions on the adversary and $n\geq 9$. As the main result, we prove bounds on the price of anarchy for two special adversaries: one destroys a link chosen uniformly at random, while the other destroys a link that causes a maximum number of player pairs to be separated. We prove bounds tight up to constants, namely $O(1)$ for one adversary (if $\alpha>1/2$), and $\Theta(n)$ for the other (if $\alpha>2$ considered constant and $n \geq 9$). The latter is the worst that can happen for any adversary in this model (if $\alpha=\Omega(1)$).
The Calculation and Simulation of the Price of Anarchy for Network Formation Games  [PDF]
Shaun Lichter,Christopher Griffin,Terry Friesz
Mathematics , 2011,
Abstract: We model the formation of networks as the result of a game where by players act selfishly to get the portfolio of links they desire most. The integration of player strategies into the network formation model is appropriate for organizational networks because in these smaller networks, dynamics are not random, but the result of intentional actions carried through by players maximizing their own objectives. This model is a better framework for the analysis of influences upon a network because it integrates the strategies of the players involved. We present an Integer Program that calculates the price of anarchy of this game by finding the worst stable graph and the best coordinated graph for this game. We simulate the formation of the network and calculated the simulated price of anarchy, which we find tends to be rather low.
The Price of Anarchy in Cooperative Network Creation Games  [PDF]
Erik D. Demaine,Mohammadtaghi Hajiaghayi,Hamid Mahini,Morteza Zadimoghaddam
Computer Science , 2009,
Abstract: In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost \alpha. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in n for all values of α in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in n. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of \alpha (at most n polylg n). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of \alpha and \infty). We prove the first assemblage of upper and lower bounds for this context, stablishing nontrivial tight bounds for many ranges of \alpha, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of \alpha, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.
The Price of Anarchy (POA) of network coding and routing based on average pricing mechanism  [PDF]
Wang Gang,Dai Xia
Mathematics , 2011,
Abstract: The congestion pricing is an efficient allocation approach to mediate demand and supply of network resources. Different from the previous pricing using Affine Marginal Cost (AMC), we focus on studying the game between network coding and routing flows sharing a single link when users are price anticipating based on an Average Cost Sharing (ACS) pricing mechanism. We characterize the worst-case efficiency bounds of the game compared with the optimal, i.e., the price-of anarchy (POA), which can be low bound 50% with routing only. When both network coding and routing are applied, the POA can be as low as 4/9. Therefore, network coding cannot improve the POA significantly under the ACS. Moreover, for more efficient use of limited resources, it indicates the sharing users have a higher tendency to choose network coding.
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms  [PDF]
George Christodoulou,Kurt Mehlhorn,Evangelia Pyrga
Computer Science , 2012,
Abstract: We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if $\ell_e(x)$ is the latency function of an edge $e$, we replace it by $\hat{\ell}_e(x)$ with $\ell_e(x) \le \hat{\ell}_e(x)$ for all $x$. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\CM(r)$ denotes the cost of the worst Nash flow in the modified network for rate $r$ and $\Copt(r)$ denotes the cost of the optimal flow in the original network for the same rate then [\ePoA = \max_{r \ge 0} \frac{\CM(r)}{\Copt(r)}.] We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.
Anarchy is free in network creation  [PDF]
Ronald Graham,Linus Hamilton,Ariel Levavi,Po-Shen Loh
Computer Science , 2013,
Abstract: The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the game theoretic study of network formation, and our paper considers one of the most-well studied models, originally proposed by Fabrikant et al. In it, each of N agents corresponds to a vertex, which can create edges to other vertices at a cost of alpha each, for some parameter alpha. Every edge can be freely used by every vertex, regardless of who paid the creation cost. To reflect the desire to be close to other vertices, each agent's cost function is further augmented by the sum total of all (graph theoretic) distances to all other vertices. Previous research proved that for many regimes of the (alpha, N) parameter space, the total social cost (sum of all agents' costs) of every Nash equilibrium is bounded by at most a constant multiple of the optimal social cost. In algorithmic game theoretic nomenclature, this approximation ratio is called the price of anarchy. In our paper, we significantly sharpen some of those results, proving that for all constant non-integral alpha > 2, the price of anarchy is in fact 1+o(1), i.e., not only is it bounded by a constant, but it tends to 1 as N tends to infinity. For constant integral alpha >= 2, we show that the price of anarchy is bounded away from 1. We provide quantitative estimates on the rates of convergence for both results.
Strong Price of Anarchy and Coalitional Dynamics  [PDF]
Yoram Bachrach,Vasilis Syrgkanis,Eva Tardos,Milan Vojnovic
Computer Science , 2013,
Abstract: We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of non-cooperative games. Coalitional smoothness implies bounds on the strong price of anarchy, the loss of quality of coalitionally stable outcomes, as well as bounds on coalitional versions of coarse correlated equilibria and sink equilibria, which we define as out-of-equilibrium myopic behavior as determined by a natural coalitional version of best-response dynamics. Our coalitional smoothness framework captures existing results bounding the strong price of anarchy of network design games. We show that in any monotone utility-maximization game, if each player's utility is at least his marginal contribution to the welfare, then the strong price of anarchy is at most 2. This captures a broad class of games, including games with a very high price of anarchy. Additionally, we show that in potential games the strong price of anarchy is close to the price of stability, the quality of the best Nash equilibrium.
Strong Price of Anarchy of Coalition Formation Game with Fair Cost Sharing and Bounded Capacity for Sharing Economy  [PDF]
Chi-Kin Chau,Khaled Elbassioni
Computer Science , 2015,
Abstract: This paper studies a coalition formation game subject to the capacity of $K$ participants per coalition. The participants in each coalition are supposed to split the associated cost according to a given cost sharing solution. A stable coalition structure is established, when no group of participants can opt out to form another coalition that leads to lower individual payments. We investigate the strong price of anarchy (PoA) comparing a worst-case stable coalition structure and a social optimum considering several fair cost sharing solutions (e.g., equal-split, proportional-split, egalitarian and Nash bargaining solutions of bargaining games, and usage based cost sharing). Our coalition formation game is motivated by applications in sharing economy, where users form coalitions to share certain replaceable resources. Our model can be applied to several problems such as hotel room sharing among travelers, taxi-ride sharing among passengers, and pass sharing among users. We show that the strong PoA for equal-split, proportional-split, and usage based cost sharing (under certain conditions) is $\Theta(\log K)$, whereas the one for egalitarian and Nash bargaining solutions is $O(\sqrt{K} \log K)$. We also study the existence of a stable coalition structure in these cost sharing solutions.
The price of anarchy in basketball  [PDF]
Brian Skinner
Physics , 2009, DOI: 10.2202/1559-0410.1217
Abstract: Optimizing the performance of a basketball offense may be viewed as a network problem, wherein each play represents a "pathway" through which the ball and players may move from origin (the in-bounds pass) to goal (the basket). Effective field goal percentages from the resulting shot attempts can be used to characterize the efficiency of each pathway. Inspired by recent discussions of the "price of anarchy" in traffic networks, this paper makes a formal analogy between a basketball offense and a simplified traffic network. The analysis suggests that there may be a significant difference between taking the highest-percentage shot each time down the court and playing the most efficient possible game. There may also be an analogue of Braess's Paradox in basketball, such that removing a key player from a team can result in the improvement of the team's offensive efficiency.
Price of Anarchy for Greedy Auctions  [PDF]
Brendan Lucier,Allan Borodin
Computer Science , 2009,
Abstract: We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multi-parameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show for a variety of equilibrium concepts, including Bayes-Nash equilibrium and correlated equilibrium, the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.