Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "Bellman-Ford algorithm" wg kryterium: Temat


Wyświetlanie 1-1 z 1
Tytuł:
A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria
Autorzy:
Góngora, P. A
Rosenblueth, D. A.
Powiązania:
https://bibliotekanauki.pl/articles/329934.pdf
Data publikacji:
2015
Wydawca:
Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:
shortest path
Bellman–Ford algorithm
Nash equilibrium
BDD
model checking
najkrótsza ścieżka
równowaga Nasha
sprawdzanie modelu
Opis:
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.
Źródło:
International Journal of Applied Mathematics and Computer Science; 2015, 25, 3; 577-596
1641-876X
2083-8492
Pojawia się w:
International Journal of Applied Mathematics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-1 z 1

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies