13 Search Results for "Jurdzinski, Marcin"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.44
A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games

Authors: K. S. Thejaswini, Pierre Ohlmann, and Marcin Jurdziński

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
The classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. This work pinpoints the mechanism that is responsible for this relative underperformance and proposes a new technique that eliminates it. The culprit is the wasteful manner in which the results obtained from recursive calls are indiscriminately discarded by the algorithm whenever subgames on which the algorithm is run change. Our new technique is based on firstly enhancing the algorithm to compute attractor decompositions of subgames instead of just winning strategies on them, and then on making it carefully use attractor decompositions computed in prior recursive calls to reduce the size of subgames on which further recursive calls are made. We illustrate the new technique on the classic example of the recursive McNaughton-Zielonka algorithm, but it can be applied to other symmetric attractor-based algorithms that were inspired by it, such as the quasi-polynomial versions of the McNaughton-Zielonka algorithm based on universal trees.
Cite as

K. S. Thejaswini, Pierre Ohlmann, and Marcin Jurdziński. A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{thejaswini_et_al:LIPIcs.FSTTCS.2022.44,
  author =	{Thejaswini, K. S. and Ohlmann, Pierre and Jurdzi\'{n}ski, Marcin},
  title =	{{A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.44},
  URN =		{urn:nbn:de:0030-drops-174365},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.44},
  annote =	{Keywords: Parity games, Attractor decomposition, Quasipolynomial Algorithms, Universal trees}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.63
Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees

Authors: Zhuan Khye Koh and Georg Loho

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches is a universal tree, as identified by Czerwiński et al. (SODA 2019). By proving a quasi-polynomial lower bound on the size of a universal tree, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial running time. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree. As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Our main technical contribution is an efficient method for computing the least fixed point of 1-player games. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdziński and Lazić (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time O(mn²log nlog d) and O(mn²log³ n log d) respectively per iteration.
Cite as

Zhuan Khye Koh and Georg Loho. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koh_et_al:LIPIcs.MFCS.2022.63,
  author =	{Koh, Zhuan Khye and Loho, Georg},
  title =	{{Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.63},
  URN =		{urn:nbn:de:0030-drops-168619},
  doi =		{10.4230/LIPIcs.MFCS.2022.63},
  annote =	{Keywords: parity games, strategy iteration, value iteration, progress measure, universal trees}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.123
The Strahler Number of a Parity Game

Authors: Laure Daviaud, Marcin Jurdziński, and K. S. Thejaswini

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smallest Strahler number of the tree of any of its attractor decompositions. It is proved that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices n and linear in (d/(2k))^k, where d is the number of priorities and k is the Strahler number. This complexity is quasi-polynomial because the Strahler number is at most logarithmic in the number of vertices. The proof is based on a new construction of small Strahler-universal trees. It is shown that the Strahler number of a parity game is a robust, and hence arguably natural, parameter: it coincides with its alternative version based on trees of progress measures and - remarkably - with the register number defined by Lehtinen (2018). It follows that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices and linear in (d/(2k))^k, where k is the register number. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys (2020). The running time of the algorithm based on small Strahler-universal trees yields a novel trade-off k ⋅ lg(d/k) = O(log n) between the two natural parameters that measure the structural complexity of a parity game, which allows solving parity games in polynomial time. This includes as special cases the asymptotic settings of those parameters covered by the results of Calude, Jain Khoussainov, Li, and Stephan (2017), of Jurdziński and Lazić (2017), and of Lehtinen (2018), and it significantly extends the range of such settings, for example to d = 2^O(√{lg n}) and k = O(√{lg n}).
Cite as

Laure Daviaud, Marcin Jurdziński, and K. S. Thejaswini. The Strahler Number of a Parity Game. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 123:1-123:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.ICALP.2020.123,
  author =	{Daviaud, Laure and Jurdzi\'{n}ski, Marcin and Thejaswini, K. S.},
  title =	{{The Strahler Number of a Parity Game}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{123:1--123:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.123},
  URN =		{urn:nbn:de:0030-drops-125304},
  doi =		{10.4230/LIPIcs.ICALP.2020.123},
  annote =	{Keywords: parity game, attractor decomposition, progress measure, universal tree, Strahler number}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.10
Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time

Authors: Paweł Parys

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they operate very slowly. On the other side there is Zielonka’s recursive algorithm, which is very simple, exponential in the worst case, and the fastest in practice. We combine these two approaches: we propose a small modification of Zielonka’s algorithm, which ensures that the running time is at most quasi-polynomial. In effect, we obtain a simple algorithm that solves parity games in quasi-polynomial time. We also hope that our algorithm, after further optimizations, can lead to an algorithm that shares the good performance of Zielonka’s algorithm on typical inputs, while reducing the worst-case complexity on difficult inputs.
Cite as

Paweł Parys. Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{parys:LIPIcs.MFCS.2019.10,
  author =	{Parys, Pawe{\l}},
  title =	{{Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.10},
  URN =		{urn:nbn:de:0030-drops-109543},
  doi =		{10.4230/LIPIcs.MFCS.2019.10},
  annote =	{Keywords: Parity games, Zielonka’s algorithm, quasi-polynomial time}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2019.18
Alternating Weak Automata from Universal Trees

Authors: Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)

Abstract
An improved translation from alternating parity automata on infinite words to alternating weak automata is given. The blow-up of the number of states is related to the size of the smallest universal ordered trees and hence it is quasi-polynomial, and it is polynomial if the asymptotic number of priorities is at most logarithmic in the number of states. This is an exponential improvement on the translation of Kupferman and Vardi (2001) and a quasi-polynomial improvement on the translation of Boker and Lehtinen (2018). Any slightly better such translation would (if - like all presently known such translations - it is efficiently constructive) lead to algorithms for solving parity games that are asymptotically faster in the worst case than the current state of the art (Calude, Jain, Khoussainov, Li, and Stephan, 2017; Jurdziński and Lazić, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough.
Cite as

Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen. Alternating Weak Automata from Universal Trees. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.CONCUR.2019.18,
  author =	{Daviaud, Laure and Jurdzi\'{n}ski, Marcin and Lehtinen, Karoliina},
  title =	{{Alternating Weak Automata from Universal Trees}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.18},
  URN =		{urn:nbn:de:0030-drops-109208},
  doi =		{10.4230/LIPIcs.CONCUR.2019.18},
  annote =	{Keywords: alternating automata, weak automata, B\"{u}chi automata, parity automata, parity games, universal trees}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.121
When is Containment Decidable for Probabilistic Automata?

Authors: Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. Pérez, and James Worrell

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The containment problem for quantitative automata is the natural quantitative generalisation of the classical language inclusion problem for Boolean automata. We study it for probabilistic automata, where it is known to be undecidable in general. We restrict our study to the class of probabilistic automata with bounded ambiguity. There, we show decidability (subject to Schanuel's conjecture) when one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Furthermore, we show that this is close to the most general decidable fragment of this problem by proving that it is already undecidable if one of the automata is allowed to be linearly ambiguous.
Cite as

Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. Pérez, and James Worrell. When is Containment Decidable for Probabilistic Automata?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 121:1-121:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.ICALP.2018.121,
  author =	{Daviaud, Laure and Jurdzinski, Marcin and Lazic, Ranko and Mazowiecki, Filip and P\'{e}rez, Guillermo A. and Worrell, James},
  title =	{{When is Containment Decidable for Probabilistic Automata?}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{121:1--121:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.121},
  URN =		{urn:nbn:de:0030-drops-91251},
  doi =		{10.4230/LIPIcs.ICALP.2018.121},
  annote =	{Keywords: Probabilistic automata, Containment, Emptiness, Ambiguity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.44
Mean-Payoff Games on Timed Automata

Authors: Shibashis Guha, Marcin Jurdzinski, Shankara Narayanan Krishna, and Ashutosh Trivedi

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players - Player Min and Player Max - by moving a token along the states of the graph to form an infinite run. The goal of Player Min is to minimize the limit average weight of the run, while the goal of the Player Max is the opposite. Brenguier, Cassez, and Raskin recently studied a variation of these games and showed that mean-payoff games are undecidable for timed automata with five or more clocks. We refine this result by proving the undecidability of mean-payoff games with three clocks. On a positive side, we show the decidability of mean-payoff games on one-clock timed automata with binary price-rates. A key contribution of this paper is the application of dynamic programming based proof techniques applied in the context of average reward optimization on an uncountable state and action space.
Cite as

Shibashis Guha, Marcin Jurdzinski, Shankara Narayanan Krishna, and Ashutosh Trivedi. Mean-Payoff Games on Timed Automata. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{guha_et_al:LIPIcs.FSTTCS.2016.44,
  author =	{Guha, Shibashis and Jurdzinski, Marcin and Krishna, Shankara Narayanan and Trivedi, Ashutosh},
  title =	{{Mean-Payoff Games on Timed Automata}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.44},
  URN =		{urn:nbn:de:0030-drops-68797},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.44},
  annote =	{Keywords: Timed Automata, Mean-Payoff Games, Controller-Synthesis}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2317
The Covering and Boundedness Problems for Branching Vector Addition Systems

Authors: Stéphane Demri, Marcin Jurdzinski, Oded Lachish, and Ranko Lazic

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
The covering and boundedness problems for branching vector addition systems are shown complete for doubly-exponential time.
Cite as

Stéphane Demri, Marcin Jurdzinski, Oded Lachish, and Ranko Lazic. The Covering and Boundedness Problems for Branching Vector Addition Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 181-192, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{demri_et_al:LIPIcs.FSTTCS.2009.2317,
  author =	{Demri, St\'{e}phane and Jurdzinski, Marcin and Lachish, Oded and Lazic, Ranko},
  title =	{{The Covering and Boundedness Problems for Branching Vector Addition Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{181--192},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2317},
  URN =		{urn:nbn:de:0030-drops-23173},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2317},
  annote =	{Keywords: Vector addition systems, Petri nets, covering, boundedness, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1765
Average-Time Games

Authors: Marcin Jurdzinski and Ashutosh Trivedi

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimize the average time per transition and player Max wants to maximize it. A solution of average-time games is presented using a reduction to average-price game on a finite graph. A direct consequence is an elementary proof of determinacy for average-time games. This complements our results for reachability-time games and partially solves a problem posed by Bouyer et al., to design an algorithm for solving average-price games on priced timed automata. The paper also establishes the exact computational complexity of solving average-time games: the problem is EXPTIME-complete for timed automata with at least two clocks.
Cite as

Marcin Jurdzinski and Ashutosh Trivedi. Average-Time Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 340-351, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{jurdzinski_et_al:LIPIcs.FSTTCS.2008.1765,
  author =	{Jurdzinski, Marcin and Trivedi, Ashutosh},
  title =	{{Average-Time Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{340--351},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1765},
  URN =		{urn:nbn:de:0030-drops-17650},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1765},
  annote =	{Keywords: Games on Timed Automata, Mean-payoff Games, Average-Time Games, Game Theory}
}
Document
DOI: 10.4230/DagSemProc.07471.1
07471 Abstracts Collection – Equilibrium Computation

Authors: P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
From 18 to 23 November 2007, the Dagstuhl Seminar 07471 ``Equilibrium Computation'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel. 07471 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{herings_et_al:DagSemProc.07471.1,
  author =	{Herings, P. Jean-Jacques and Jurdzinski, Marcin and Bro Miltersen, Peter and Tardos, Eva and von Stengel, Bernhard},
  title =	{{07471 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.1},
  URN =		{urn:nbn:de:0030-drops-15286},
  doi =		{10.4230/DagSemProc.07471.1},
  annote =	{Keywords: Equilibrium, algorithm, polynomial time, game theory, economics}
}
Document
DOI: 10.4230/DagSemProc.07471.2
Equilibrium Tracing in Bimatrix Games

Authors: Anne Balthasar

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
We analyze the relations of the van den Elzen-Talman algorithm, the Lemke-Howson algorithm and the global Newton method introduced by Govindan and Wilson. It is known that the global Newton method encompasses the Lemke-Howson algorithm; we prove that it also comprises the van den Elzen-Talman algorithm, and more generally, the linear tracing procedure, as a special case. This will lead us to a discussion of traceability of equilibria of index +1. We answer negatively the open question of whether, generically, the van den Elzen-Talman algorithm is flexible enough to trace all equilibria of index +1.
Cite as

Anne Balthasar. Equilibrium Tracing in Bimatrix Games. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{balthasar:DagSemProc.07471.2,
  author =	{Balthasar, Anne},
  title =	{{Equilibrium Tracing in Bimatrix Games}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.2},
  URN =		{urn:nbn:de:0030-drops-15265},
  doi =		{10.4230/DagSemProc.07471.2},
  annote =	{Keywords: Bimatrix games, Equilibrium computation, Homotopy methods, Index}
}
Document
DOI: 10.4230/DagSemProc.07471.3
Homotopy Methods to Compute Equilibria in Game Theory

Authors: P. Jean-Jacques Herings and Ronald Peeters

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke-Howson algorithm and the van den Elzen-Talman algorithm to compute Nash equilibria in 2-person games, and the Herings-van den Elzen, Herings-Peeters, and McKelvey-Palfrey algorithms to compute Nash equilibria in general $n$-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.
Cite as

P. Jean-Jacques Herings and Ronald Peeters. Homotopy Methods to Compute Equilibria in Game Theory. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{herings_et_al:DagSemProc.07471.3,
  author =	{Herings, P. Jean-Jacques and Peeters, Ronald},
  title =	{{Homotopy Methods to Compute Equilibria in Game Theory}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--40},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.3},
  URN =		{urn:nbn:de:0030-drops-15257},
  doi =		{10.4230/DagSemProc.07471.3},
  annote =	{Keywords: Homotopy, Equilibrium computation, Non-cooperative games, Nash Equilibrium}
}
Document
DOI: 10.4230/DagSemProc.07471.4
Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems

Authors: Nir Halman

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl for LP-type problems, we obtain the first strongly subexponential solution for SSGs (a strongly subexponential algorithm has only been known for binary SSGs). Using known reductions between various games, we achieve the first trongly subexponential solutions for Discounted and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs. To the best of our knowledge, the LP-type framework has been used so far only in order to yield linear or close to linear time algorithms for various problems in computational geometry and location theory. Our approach demonstrates the applicability of the LP-type framework in other fields, and for achieving subexponential algorithms. This work has been published in Algorithmica, volume 49 (September 2007), pages 37-50
Cite as

Nir Halman. Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{halman:DagSemProc.07471.4,
  author =	{Halman, Nir},
  title =	{{Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.4},
  URN =		{urn:nbn:de:0030-drops-15274},
  doi =		{10.4230/DagSemProc.07471.4},
  annote =	{Keywords: Subexponential algorithm, LP-type framework}
}
  • Refine by Author
  • 5 Jurdzinski, Marcin
  • 3 Daviaud, Laure
  • 3 Jurdziński, Marcin
  • 2 Herings, P. Jean-Jacques
  • 2 Lazic, Ranko
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Formal languages and automata theory
  • 3 Theory of computation → Logic and verification
  • 2 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Equilibrium computation
  • 2 Parity games
  • 2 parity games
  • 2 progress measure
  • 2 universal trees
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 5 2008
  • 2 2019
  • 2 2022
  • 1 2009
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact