A nested family of k-total effective rewards for positional games

DOI10.1007/S00182-016-0532-ZMaRDI QIDQ521891zbMATHOpenAlexDBLPWikidataFDO

Authors Endre Boros, Kazuhisa Makino, Khaled Elbassioni, Vladimir Gurvich

Publication date 12 April 2017

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6072

zbMATH Keywords

mean payoffzero-sumtotal rewardcyclic gamesstochastic game with perfect informationtwo-person

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $$ we introduce an effective reward function, called $k$-total. For $k=0$ and $1$ this function is known as {it mean payoff} and {it total reward}, respectively. We restrict our attention to the deterministic case. For all $k$, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that $k$-total reward games can be embedded into $(k+1)$-total reward games.

Recommendations

• scientific article; zbMATH DE number 4162687
• Total reward stochastic games and sensitive average reward strategies
• scientific article; zbMATH DE number 4020880
• The bad match; a total reward stochastic game
• Markov decision processes and stochastic games with total effective payoff

Cites work

• scientific article; zbMATH DE number 3128733 (Why is no real title available?)
• scientific article; zbMATH DE number 3542195 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 2013849 (Why is no real title available?)
• scientific article; zbMATH DE number 5685899 (Why is no real title available?)
• scientific article; zbMATH DE number 3333895 (Why is no real title available?)
• A stochastic game with complete information and without equilibrium situations in pure stationary strategies
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Cyclic games and linear programming
• Cyclical games with prohibitions
• Discrete Dynamic Programming
• Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
• Extensions of two person zero sum games
• Markov decision processes and stochastic games with total effective payoff
• Mathematical Foundations of Computer Science 2004
• Maximizing the minimum source-sink path subject to a budget constraint
• Mean cost cyclical games
• On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games
• On canonical forms for zero-sum stochastic mean payoff games
• On short paths interdiction problems: Total and node-wise limited interdiction
• Positional strategies for mean payoff games
• Scheduling with AND/OR Precedence Constraints
• Shortest-path network interdiction
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff
• Stochastic games
• The bad match; a total reward stochastic game
• The complexity of mean payoff games on graphs
• Total reward stochastic games and sensitive average reward strategies

Cited in

(2)

• Deterministic \(n\)-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
• On Nash-solvability of \(n\)-person graphical games under Markov and a-priori realizations

This page was built for publication: A nested family of \(k\)-total effective rewards for positional games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521891)