Obiekt
Tytuł: A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria
Współtwórca:
Byrski, Aleksander - ed. ; Kisiel-Dorohinicki, Marek - ed. ; Dobrowolski, Grzegorz - ed.
Podtytuł:
Tytuł publikacji grupowej:
Abstract:
Consider games where players wish to minimize the cost to reach some state. A subgame-perfect Nash equilibrium can be regarded as a collection of optimal paths on such games. Similarly, the well-known state-labeling algorithm used in model checking can be viewed as computing optimal paths on a Kripke structure, where each path has a minimum number of transitions. ; We exploit these similarities in a common generalization of extensive games and Kripke structures that we name "graph games". By extending the Bellman-Ford algorithm for computing shortest paths, we obtain a model-checking algorithm for graph games with respect to formulas in an appropriate logic. Hence, when given a certain formula, our model-checking algorithm computes the subgame-perfect Nash equilibrium (as opposed to simply determining whether or not a given collection of paths is a Nash equilibrium). ; Next, we develop a symbolic version of our model checker allowing us to handle larger graph games. We illustrate our formalism on the critical-path method as well as games with perfect information. Finally, we report on the execution time of benchmarks of an implementation of our algorithms.
Wydawca:
Zielona Góra: Uniwersytet Zielonogórski
Identyfikator zasobu:
DOI:
Strony:
Źródło:
AMCS, volume 25, number 3 (2015) ; kliknij tutaj, żeby przejść
Jezyk:
Prawa do dysponowania publikacją:
Biblioteka Uniwersytetu Zielonogórskiego
Kolekcje, do których przypisany jest obiekt:
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Jednostki organizacyjne > Wydział Informatyki, Elektrotechniki i Automatyki
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Typy utworów > Artykuły
- Zielonogórska Biblioteka Cyfrowa > Repozytorium > Czasopisma naukowe i serie wydawnicze UZ > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2015)
Data ostatniej modyfikacji:
2024-05-06
Data dodania obiektu:
2024-05-06
Liczba wyświetleń treści obiektu:
25
Wszystkie dostępne wersje tego obiektu:
https://zbc.uz.zgora.pl/publication/88904
Wyświetl opis w formacie RDF:
Wyświetl opis w formacie OAI-PMH:
-
International Journal of Applied Mathematics and Computer Science (AMCS)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 26 (2016)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25, number 1 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25, number 2 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25, number 3 (2015)
- A situation-based multi-agent architecture for handling misunderstandings in interactions
- A belief revision approach for argumentation-based negotiation agents
- A strategy learning model for autonomous agents based on classification
- An agent-oriented hierarchic strategy for solving inverse problems
- A study on meme propagation in multimemetic algorithms
- A multi-agent brokerage platform for media content recommendation
- A sixth-order finite volume method for the 1D biharmonic operator: Application to intramedullary nail simulation
- Analysis of the descriptor Roesser model with the use of the Drazin inverse
- An H[the sign of infinity] sliding mode observer for Takagi-Sugeno nonlinear systems with simultaneous actuator and sensor faults
- Design of passive fault-tolerant controllers of a quadrotor based on sliding mode theory
- A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria
- Bottom-up learning of hierarchical models in a class of deterministic POMDP environments
- A repeated imitation model with dependence between stages: Decision strategies and rewards
- Acoustic analysis assessment in speech pathology detection
- On the order equivalence relation of binary association measures
- Signature verification: A comprehensive study of the hidden signature method
- Computing with words with the use of inverse RDM models of membership functions
- Building the library of RNA 3D nucleotide conformations using the clustering approach
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25, number 4 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 25, number 1 (2015)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 24 (2014)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 23 (2013)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 22 (2012)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 21 (2011)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 20 (2010)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 19 (2009)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 18 (2008)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 17 (2007)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 16 (2006)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 15 (2005)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 13 (2003)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 12 (2002)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 11 (2001)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 10 (2000)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 9 (1999)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 8 (1998)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 7 (1997)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 6 (1996)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 5 (1995)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 4 (1994)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 3 (1993)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 2 (1992)
-
International Journal of Applied Mathematics and Computer Science (AMCS),volume 1 (1991)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 26 (2016)
| Nazwa wydania | Data |
|---|---|
| A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria | 2024-05-06 |
