Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConvergence to Equilibrium in Local Interaction Games and Ising Models
242
0
0.0
(
0
)
Added by
Andrea Montanari
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Coordination games describe social or economic interactions in which the adoption of a common strategy has a higher payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies. Here we consider a two-strategies coordination game played asynchronously between the nodes of a network. Agents behave according to a noisy best-response dynamics. It is known that noise removes the degeneracy among equilibria: In the long run, the ``risk-dominant behavior spreads throughout the network. Here we consider the problem of computing the typical time scale for the spread of this behavior. In particular, we study its dependence on the network structure and derive a dichotomy between highly-connected, non-local graphs that show slow convergence, and poorly connected, low dimensional graphs that show fast convergence.
rate research
Read More
This paper considers a non-cooperative game in which competing users sharing a frequency-selective interference channel selfishly optimize their power allocation in order to improve their achievable rates. Previously, it was shown that a user having the knowledge of its opponents channel state information can make foresighted decisions and substantially improve its performance compared with the case in which it deploys the conventional iterative water-filling algorithm, which does not exploit such knowledge. This paper discusses how a foresighted user can acquire this knowledge by modeling its experienced interference as a function of its own power allocation. To characterize the outcome of the multi-user interaction, the conjectural equilibrium is introduced, and the existence of this equilibrium for the investigated water-filling game is proved. Interestingly, both the Nash equilibrium and the Stackelberg equilibrium are shown to be special cases of the generalization of conjectural equilibrium. We develop practical algorithms to form accurate beliefs and search desirable power allocation strategies. Numerical simulations indicate that a foresighted user without any a priori knowledge of its competitors private information can effectively learn the required information, and induce the entire system to an operating point that improves both its own achievable rate as well as the rates of the other participants in the water-filling game.
The term rational has become synonymous with maximizing expected payoff in the definition of the best response in Nash setting. In this work, we consider stochastic games in which players engage only once, or at most a limited number of times. In such games, it may not be rational for players to maximize their expected payoff as they cannot wait for the Law of Large Numbers to take effect. We instead define a new notion of a risk-averse best response, that results in a risk-averse equilibrium (RAE) in which players choose to play the strategy that maximizes the probability of them being rewarded the most in a single round of the game rather than maximizing the expected received reward, subject to the actions of other players. We prove the risk-averse equilibrium to exist in all finite games and numerically compare its performance to Nash equilibrium in finite-time stochastic games.
We consider the question of whether, and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games where each players weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation towards Poisson random variables whose expected values are Wardrop equilibria of a different nonatomic game with suitably-defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players towards Poisson games.
We consider a game-theoretic model of information retrieval with strategic authors. We examine two different utility schemes: authors who aim at maximizing exposure and authors who want to maximize active selection of their content (i.e. the number of clicks). We introduce the study of author learning dynamics in such contexts. We prove that under the probability ranking principle (PRP), which forms the basis of the current state of the art ranking methods, any better-response learning dynamics converges to a pure Nash equilibrium. We also show that other ranking methods induce a strategic environment under which such a convergence may not occur.
Computing Nash equilibrium in bimatrix games is PPAD-hard, and many works have focused on the approximate solutions. When games are generated from a fixed unknown distribution, learning a Nash predictor via data-driven approaches can be preferable. In this paper, we study the learnability of approximate Nash equilibrium in bimatrix games. We prove that Lipschitz function class is agnostic Probably Approximately Correct (PAC) learnable with respect to Nash approximation loss. Additionally, to demonstrate the advantages of learning a Nash predictor, we develop a model that can efficiently approximate solutions for games under the same distribution. We show by experiments that the solutions from our Nash predictor can serve as effective initializing points for other Nash solvers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
