Search results for "Computer Science::Computer Science and Game Theory"
showing 10 items of 87 documents
Efficient Parallel Nash Genetic Algorithm for Solving Inverse Problems in Structural Engineering
2015
A parallel implementation of a game-theory based Nash Genetic Algorithm (Nash-GAs) is presented in this paper for solving reconstruction inverse problems in structural engineering. We compare it with the standard panmictic genetic algorithm in a HPC environment with up to eight processors. The procedure performance is evaluated on a fifty-five bar sized test case of discrete real cross-section types structural frame. Numerical results obtained on this application show a significant achieved increase of performance using the parallel Nash-GAs approach compared to the standard GAs or Parallel GAs.
Local regularity for time-dependent tug-of-war games with varying probabilities
2016
We study local regularity properties of value functions of time-dependent tug-of-war games. For games with constant probabilities we get local Lipschitz continuity. For more general games with probabilities depending on space and time we obtain H\"older and Harnack estimates. The games have a connection to the normalized $p(x,t)$-parabolic equation $(n+p(x,t))u_t=\Delta u+(p(x,t)-2) \Delta_{\infty}^N u$.
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
2013
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of $n$ players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any $n$-player symmetric XOR game the entangled value of the game is $\Theta (\frac{\sqrt{\ln{n}}}{n^{1/4}})$ adapting an old result by Salem and Zygmund on the asymptotics of random tr…
Worst case analysis of non-local games
2011
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study …
Values of games with probabilistic graphs
1999
Abstract In this paper we consider games with probabilistic graphs. The model we develop is an extension of the model of games with communication restrictions by Myerson (1977) . In the Myerson model each pair of players is joined by a link in the graph if and only if these two players can communicate directly. The current paper considers a more general setting in which each pair of players has some probability of direct communication. The value is defined and characterized in this context. It is a natural extension of the Myerson value and it turns out to be the Shapley value of a modified game.
REPEATED GAMES WITH PROBABILISTIC HORIZON
2005
Repeated games with probabilistic horizon are defined as those games where players have a common probability structure over the length of the game's repetition, T. In particular, for each t, they assign a probability pt to the event that "the game ends in period t". In this framework we analyze Generalized Prisoners' Dilemma games in both finite stage and differentiable stage games. Our construction shows that it is possible to reach cooperative equilibria under some conditions on the distribution of the discrete random variable T even if the expected length of the game is finite. More precisely, we completely characterize the existence of sub-game perfect cooperative equilibria in finite s…
Stackelberg-Cournot and Cournot equilibria in a mixed markets exchange economy
2012
In this note, we compare two strategic general equilibrium concepts: the Stackelberg-Cournot equilibrium and the Cournot equilibrium. We thus consider a market exchange economy including atoms and a continuum of traders, who behave strategically. We show that, when the preferences of the small traders are represented by Cobb-Douglas utility functions and the atoms have the same utility functions and endowments, the Stackelberg-Cournot and the Cournot equilibrium equilibria coincide if and only if the followers’ best responses functions have a zero slope at the SCE.
Quantum-over-Classical Advantage in Solving Multiplayer Games
2020
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games.
Modular Strategies for Recursive Game Graphs
2006
AbstractMany problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global…
Advantage of Quantum Strategies in Random Symmetric XOR Games
2013
Non-local games are known as a simple but useful model which is widely used for displaying nonlocal properties of quantum mechanics. In this paper we concentrate on a simple subset of non-local games: multiplayer XOR games with 1-bit inputs and 1-bit outputs which are symmetric w.r.t. permutations of players.