18 citations · 42 across the 38 of their papers we have counts for
9 papers · 1 filter
On Nash-Solvability of Finite Two-Person Tight Vector Game Forms
Vladimir Gurvich, Mariya Naumova
We consider finite two-person normal form games. The following four properties of their game forms are equivalent: (i) Nash-solvability, (ii) zero-sum-solvability, (iii) win-lose-s…
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
Endre Boros, Paolo Giulio Franciosa, Vladimir Gurvich +1
We prove that a deterministic n-person shortest path game has a Nash equlibrium in pure and stationary strategies if it is edge-symmetric (that is (u,v) is a move whenever (v,u) is…
On Nash-solvability of finite -person shortest path games; bi-shortest path conjecture
Vladimir Gurvich
We formulate a conjecture from graph theory that is equivalent to Nash-solvability of the finite two-person shortest path games with positive local costs. For the three-person game…
On Nash-solvability of finite -person deterministic graphical games; Catch 22
Vladimir Gurvich
We consider finite -person deterministic graphical (DG) games. These games are modelled by finite directed graphs (digraphs) which may have directed cycles and, hence, infin…
Polynomial algorithms computing two lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
Vladimir Gurvich, Mariya Naumova
In 1975 the first author proved that every finite tight two-person game form is Nash-solvable, that is, for every payoffs and of two players the obtained game …
A three-person deterministic graphical game without Nash equilibria
Endre Boros, Vladimir Gurvich, Martin Milanič +2
We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique…
A Potential Reduction Algorithm for Two-person Zero-sum Mean Payoff Stochastic Games
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real , let us call a stochastic game -erg…
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph , with local rewards $r: E \to \ZZ$, and three t…
On the computational complexity of solving stochastic mean-payoff games
Vladimir Gurvich, Peter Bro Miltersen
We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the followin…