Computational Aspects of Uncertainty Profiles and Angel-Daemon Games |
| |
Authors: | Joaquim Gabarro Alina Garcia Maria Serna |
| |
Affiliation: | 1. ALBCOM Research Group, Universitat Politècnica de Catalunya, Jordi Girona Salgado, 1-3, Barcelona, 08034, Spain
|
| |
Abstract: | We analyze the complexity of equilibria problems for a class of strategic zero-sum games, called angel-daemon games. Those games were introduced to asses the performance of the execution of a web orchestration on a moderate faulty or under stress environment. Angel-daemon games are a natural example of zero-sum games whose representation is naturally succinct. We show that the problems of deciding the existence of a pure Nash equilibrium or of a dominant strategy for a given player are ${Sigma}^{p}_{2}$ -complete. Furthermore, computing the value of an angel-daemon game is EXP-complete. Thus, our results match the already known classification of the corresponding problems for the generic families of succinctly represented games with exponential number of actions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|