اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComparison of Algorithms for Simple Stochastic Games (Full Version)
79
0
0.0
(
0
)
نشر من قبل
Maximilian Weininger
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Simple stochastic games are turn-based 2.5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms -- value iteration, strategy iteration and quadratic programming -- both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.
قيم البحث
اقرأ أيضاً
Simple stochastic games are turn-based 2.5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known class
es of algorithms -- value iteration, strategy iteration and quadratic programming -- both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.
Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the
existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The permutation-enumeration algorithm performs an exhaustive search among these strategies, while the permutation-improvement algorithm is based on successive improvements, `a la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.
This study investigates simple games. A fundamental research question in this field is to determine necessary and sufficient conditions for a simple game to be a weighted majority game. Taylor and Zwicker (1992) showed that a simple game is non-weigh
ted if and only if there exists a trading transform of finite size. They also provided an upper bound on the size of such a trading transform, if it exists. Gvozdeva and Slinko (2011) improved that upper bound; their proof employed a property of linear inequalities demonstrated by Muroga (1971).In this study, we provide a new proof of the existence of a trading transform when a given simple game is non-weighted. Our proof employs Farkas lemma (1894), and yields an improved upper bound on the size of a trading transform. We also discuss an integer-weight representation of a weighted simple game, improving the bounds obtained by Muroga (1971). We show that our bound on the quota is tight when the number of players is less than or equal to five, based on the computational results obtained by Kurz (2012). Furthermore, we discuss the problem of finding an integer-weight representation under the assumption that we have minimal winning coalitions and maximal losing coalitions.In particular, we show a performance of a rounding method. Lastly, we address roughly weighted simple games. Gvozdeva and Slinko (2011) showed that a given simple game is not roughly weighted if and only if there exists a potent certificate of non-weightedness. We give an upper bound on the length of a potent certificate of non-weightedness. We also discuss an integer-weight representation of a roughly weighted simple game.
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative $omega$-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show th
at the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability $1$ when starting at a given energy level $k$, is decidable and in $NP cap coNP$. The same holds for checking if such a $k$ exists and if a given $k$ is minimal.
The prior independent framework for algorithm design considers how well an algorithm that does not know the distribution of its inputs approximates the expected performance of the optimal algorithm for this distribution. This paper gives a method tha
t is agnostic to problem setting for proving lower bounds on the prior independent approximation factor of any algorithm. The method constructs a correlated distribution over inputs that can be generated both as a distribution over i.i.d. good-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms distributions. Prior independent algorithms are upper-bounded by the optimal algorithm for the latter distribution even when the true distribution is the former. Thus, the ratio of the expected performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on the prior independent approximation ratio. The techniques of the paper connect prior independent algorithm design, Yaos Minimax Principle, and information design. We apply this framework to give new lower bounds on several canonical prior independent mechanism design problems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
