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

DOI10.1007/S00182-016-0532-ZzbMATH Open1398.91089DBLPjournals/ijgt/BorosEGM17arXiv1412.6072OpenAlexW2252303243WikidataQ59560465 ScholiaQ59560465MaRDI QIDQ521891FDOQ521891

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)

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.

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

Recommendations

• scientific article
• 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

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)

Cites Work

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

Cited In (2)

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

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)