Abstract: We focus on the problem of computing approximateNash equilibria and well-supported approximateNash equilibria in random bimatrix games, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with common expectations. We show that the completely mixed uniform strategy profile, i.e. the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is an almost Nashequilibrium for random bimatrix games, in the sense that it is, with high probability, an {\aa}-well-supported Nashequilibrium where {\aa} tends to zero as n tends to infinity.
Abstract: We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user routes its traffic on links that minimize its expected latency cost.
Our structural results provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria and that under a certain condition, the social cost of any Nashequilibrium is within a factor of 6 + epsi, of that of the fully mixed Nashequilibrium, assuming that link capacities are identical.
Our complexity results include hardness, approximability and inapproximability ones. Here we show, that for identical link capacities and under a certain condition, there is a randomized, polynomial-time algorithm to approximate the worst social cost within a factor arbitrarily close to 6 + epsi. Furthermore, we prove that for any arbitrary integer k > 0, it is -hard to decide whether or not any given allocation of users to links can be transformed into a pure Nashequilibrium using at most k selfish steps. Assuming identical link capacities, we give a polynomial-time approximation scheme (PTAS) to approximate the best social cost over all pure Nash equilibria. Finally we prove, that it is -hard to approximate the worst social cost within a multiplicative factor . The quantity is the tight upper bound on the ratio of the worst social cost and the optimal cost in the model of identical capacities.
Abstract: In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess's paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as \Omega(n^{0.121}) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any constant \eps > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. The running time is determined by the total number of paths, and is quasipolynomial when the number of paths is quasipolynomial.
Abstract: We focus on the problem of computing approximateNash equilibria and well-supported approximateNash equilibria in random bimatrix games, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a TeX -Nashequilibrium and a TeX -well supported Nashequilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nashequilibrium for random bimatrix games, since it is, with high probability, an ϵ-well-supported Nashequilibrium where ϵ tends to zero as n tends to infinity.
Abstract: We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nashequilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.
We provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nashequilibrium is within a factor of 2h(1+ɛ) of that of the fully mixed Nashequilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.
Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is View the MathML source-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1).
Abstract: We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nashequilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.We provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nashequilibrium is within a factor of 2h(1 + {\aa}) of that of the fully mixed Nashequilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is N P-hard to approximate the worst social cost within a multiplicative factor better than 2 - 2/(m + 1).
