Search results for "Computer Science::Computer Science and Game Theory"
showing 10 items of 87 documents
Population Games with Vector Payoff and Approachability
2016
This paper studies population games with vector payoffs. It provides a new perspective on approachability based on mean-field game theory. The model involves a Hamilton-Jacobi-Bellman equation which describes the best-response of every player given the population distribution and an advection equation, capturing the macroscopic evolution of average payoffs if every player plays its best response.
Graphical Structure of Attraction Basins of Hidden Chaotic Attractors : The Rabinovich-Fabrikant System
2019
The attraction basin of hidden attractors does not intersect with small neighborhoods of any equilibrium point. To the best of our knowledge this property has not been explored using realtime interactive three-dimensions graphics. Aided by advanced computer graphic analysis, in this paper, we explore this characteristic of a particular nonlinear system with very rich and unusual dynamics, the Rabinovich–Fabrikant system. It is shown that there exists a neighborhood of one of the unstable equilibria within which the initial conditions do not lead to the considered hidden chaotic attractor, but to one of the stable equilibria or are divergent. The trajectories starting from any neighborhood o…
Empirical Evaluation of the Bayesian Learning Automaton Family
2009
Masteroppgave i informasjons- og kommunikasjonsteknologi 2009 – Universitetet i Agder, Grimstad The two-armed bandit problem is a classical optimization problem where a player sequentially selects and pulls one of two arms attached to a gambling machine, and each arm pull results in either a reward or penalty to the player. Each arm is associated with a certain reward probability which is unknown to the player, and the player needs to sequentially select and play an arm and receive a reward or a penalty in order to discover its true reward probability. The overall goal for the player is reward maximization, and the player needs to balance between exploiting existing knowledge or obtaining n…
A Game Theory Approach and Tariff Strategy for Demand Side Management
2018
Demand side management in smart grid environment with smart meters, renewable energy sources, different kind of consumers etc. is a complex problem. To optimize the problem game theory methodology is used. Game theory approach provide win-win situation between consumers and utilities. Objective of the paper is to find the Nash equilibrium between consumer and utility when utility is supplied through green energy sources. Mathematical modeling of consumption and utilization derived a Nash equilibrium point where consumer and utility both get maximum payoffs. Results shows that energy consumption cost is reduce by applying game theory approach.
Claws contained in all n-tournaments
1993
Abstract We prove that any claw of order n with degree d≤ 3 8 n is n-unavoidable, which means that any tournament of order n contains it as a subdigraph. A simple corollary is that any tournament has a directed Hamiltonian path.
On symmetric nonlocal games
2013
Abstract Nonlocal games are used to display differences between the classical and quantum world. In this paper, we study symmetric XOR games, which form an important subset of nonlocal games. We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player. We illustrate those methods with two examples. One example is an N -player game (due to Ardehali (1992) [3] ) that provides the maximum quantum-over-classical advantage. The second example comes from generalization of CHSH game by letting the referee to choose arbitrary symmetric distribution of players’ inputs.
Graph connectivity and monadic NP
2002
Ehrenfeucht games are a useful tool in proving that certain properties of finite structures are not expressible by formulas of a certain type. In this paper a new method is introduced that allows the extension of a local winning strategy for Duplicator, one of the two players in Ehrenfeucht games, to a global winning strategy. As an application it is shown that graph connectivity cannot be expressed by existential second-order formulas, where the second-order quantification is restricted to unary relations (monadic NP), even, in the presence of a built-in linear order. As a second application it is stated, that, on the other hand, the presence of a linear order increases the power of monadi…
Two-Player Noncooperative Games over a Freight Transportation Network''
2004
A game between two players acting on the same road transportation network is considered in this paper. The first player aims at minimizing the transportation costs, whereas the second player aims at maximizing her profit (or, in general, her utility) that is proportional to the flow passing through the arcs under her control. We introduce bilevel linear programming formulations for this problem. We derive conditions of existence and properties of the equilibrium points and propose an algorithm finding a local optimal solution. Finally, we present an application of the model to a real system involving trucks travelling through Europe from a Middle Eastern country.
Visibly pushdown modular games,
2014
Games on recursive game graphs can be used to reason about the control flow of sequential programs with recursion. In games over recursive game graphs, the most natural notion of strategy is the modular strategy, i.e., a strategy that is local to a module and is oblivious to previous module invocations, and thus does not depend on the context of invocation. In this work, we study for the first time modular strategies with respect to winning conditions that can be expressed by a pushdown automaton. We show that such games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state automat…
On the Complexity of Solving Subtraction Games
2018
We study algorithms for solving Subtraction games, which sometimes are referred to as one-heap Nim games. We describe a quantum algorithm which is applicable to any game on DAG, and show that its query compexity for solving an arbitrary Subtraction game of $n$ stones is $O(n^{3/2}\log n)$. The best known deterministic algorithms for solving such games are based on the dynamic programming approach. We show that this approach is asymptotically optimal and that classical query complexity for solving a Subtraction game is generally $\Theta(n^2)$. This paper perhaps is the first explicit "quantum" contribution to algorithmic game theory.