Search Results

Documents authored by Pauly, Arno

Document
DOI: 10.4230/DagRep.11.10.72
Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)

Authors: Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova

Published in: Dagstuhl Reports, Volume 11, Issue 10 (2022)

Abstract
Computability and continuity are closely linked - in fact, continuity can be seen as computability relative to an arbitrary oracle. As such, concepts from topology and descriptive set theory feature heavily in the foundations of computable analysis. Conversely, techniques developed in computability theory can be fruitfully employed in topology and descriptive set theory, even if the desired results mention no computability at all. In this Dagstuhl Seminar, we brought together researchers from computable analysis, from classical computability theory, from descriptive set theory, formal topology, and other relevant areas. Our goals were to identify key open questions related to this interplay, to exploit synergies between the areas and to intensify collaboration between the relevant communities.
Cite as

Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova. Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461). In Dagstuhl Reports, Volume 11, Issue 10, pp. 72-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{hoyrup_et_al:DagRep.11.10.72,
  author =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  title =	{{Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)}},
  pages =	{72--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{10},
  editor =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.10.72},
  URN =		{urn:nbn:de:0030-drops-159293},
  doi =		{10.4230/DagRep.11.10.72},
  annote =	{Keywords: computable analysis, enumeration degrees, quasi-polish spaces, synthetic topology}
}
Document
DOI: 10.4230/LIPIcs.CSL.2021.22
Computing Measure as a Primitive Operation in Real Number Computation

Authors: Christine Gaßner, Arno Pauly, and Florian Steinberg

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Abstract
We study the power of BSS-machines enhanced with abilities such as computing the measure of a BSS-decidable set or computing limits of BSS-computable converging sequences. Our variations coalesce into just two equivalence classes, each of which also can be described as a lower cone in the Weihrauch degrees. We then classify computational tasks such as computing the measure of Δ⁰₂-set of reals, integrating piece-wise continuous functions and recovering a continuous function from an L₁([0, 1])-description. All these share the Weihrauch degree lim.
Cite as

Christine Gaßner, Arno Pauly, and Florian Steinberg. Computing Measure as a Primitive Operation in Real Number Computation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganer_et_al:LIPIcs.CSL.2021.22,
  author =	{Ga{\ss}ner, Christine and Pauly, Arno and Steinberg, Florian},
  title =	{{Computing Measure as a Primitive Operation in Real Number Computation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.22},
  URN =		{urn:nbn:de:0030-drops-134564},
  doi =		{10.4230/LIPIcs.CSL.2021.22},
  annote =	{Keywords: BSS-machine, Weihrauch reducibility, integrable function, Lebesgue measure, computable analysis}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.34
Computing Haar Measures

Authors: Arno Pauly, Dongseong Seon, and Martin Ziegler

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
According to Haar’s Theorem, every compact topological group G admits a unique (regular, right and) left-invariant Borel probability measure μ_G. Let the Haar integral (of G) denote the functional ∫_G:?(G)∋ f ↦ ∫ f d μ_G integrating any continuous function f:G → ℝ with respect to μ_G. This generalizes, and recovers for the additive group G=[0;1)mod 1, the usual Riemann integral: computable (cmp. Weihrauch 2000, Theorem 6.4.1), and of computational cost characterizing complexity class #P_1 (cmp. Ko 1991, Theorem 5.32). We establish that in fact, every computably compact computable metric group renders the Haar measure/integral computable: once using an elegant synthetic argument, exploiting uniqueness in a computably compact space of probability measures; and once presenting and analyzing an explicit, imperative algorithm based on "maximum packings" with rigorous error bounds and guaranteed convergence. Regarding computational complexity, for the groups SO(3) and SU(2), we reduce the Haar integral to and from Euclidean/Riemann integration. In particular both also characterize #P_1.
Cite as

Arno Pauly, Dongseong Seon, and Martin Ziegler. Computing Haar Measures. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pauly_et_al:LIPIcs.CSL.2020.34,
  author =	{Pauly, Arno and Seon, Dongseong and Ziegler, Martin},
  title =	{{Computing Haar Measures}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.34},
  URN =		{urn:nbn:de:0030-drops-116779},
  doi =		{10.4230/LIPIcs.CSL.2020.34},
  annote =	{Keywords: Computable analysis, topological groups, exact real arithmetic, Haar measure}
}
Document
DOI: 10.4230/DagRep.8.9.1
Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361)

Authors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly

Published in: Dagstuhl Reports, Volume 8, Issue 9 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18361 "Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis". It includes abstracts of talks presented during the seminar and open problems that were discussed, as well as a bibliography on Weihrauch complexity that was started during the previous meeting (Dagstuhl seminar 15392) and that saw some significant growth in the meantime. The session "Solved problems" is dedicated to the solutions to some of the open questions raised in the previous meeting (Dagstuhl seminar 15392).
Cite as

Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361). In Dagstuhl Reports, Volume 8, Issue 9, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.8.9.1,
  author =	{Brattka, Vasco and Dzhafarov, Damir D. and Marcone, Alberto and Pauly, Arno},
  title =	{{Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (Dagstuhl Seminar 18361)}},
  pages =	{1--28},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{9},
  editor =	{Brattka, Vasco and Dzhafarov, Damir D. and Marcone, Alberto and Pauly, Arno},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.9.1},
  URN =		{urn:nbn:de:0030-drops-103270},
  doi =		{10.4230/DagRep.8.9.1},
  annote =	{Keywords: Computability and complexity in analysis, computations on real numbers, reducibilities, descriptive complexity, computational complexity, reverse and}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.38
Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Authors: Stéphane Le Roux, Arno Pauly, and Mickael Randour

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objective setting. We show that our framework encompasses important classes of games from the literature, and permits to go further, using a unified approach. While such an approach cannot match ad-hoc proofs with regard to tightness of memory bounds, it has two advantages: first, it gives a widely-applicable criterion for FM determinacy; second, it helps to understand the cornerstones of FM determinacy, which are often hidden but common in proofs for specific (combinations of) winning conditions.
Cite as

Stéphane Le Roux, Arno Pauly, and Mickael Randour. Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.FSTTCS.2018.38,
  author =	{Le Roux, St\'{e}phane and Pauly, Arno and Randour, Mickael},
  title =	{{Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.38},
  URN =		{urn:nbn:de:0030-drops-99373},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.38},
  annote =	{Keywords: games on graphs, finite-memory determinacy, multiple objectives}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.10
Beyond Admissibility: Dominance Between Chains of Strategies

Authors: Nicolas Basset, Ismaël Jecker, Arno Pauly, Jean-François Raskin, and Marie Van den Bogaard

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.
Cite as

Nicolas Basset, Ismaël Jecker, Arno Pauly, Jean-François Raskin, and Marie Van den Bogaard. Beyond Admissibility: Dominance Between Chains of Strategies. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{basset_et_al:LIPIcs.CSL.2018.10,
  author =	{Basset, Nicolas and Jecker, Isma\"{e}l and Pauly, Arno and Raskin, Jean-Fran\c{c}ois and Van den Bogaard, Marie},
  title =	{{Beyond Admissibility: Dominance Between Chains of Strategies}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.10},
  URN =		{urn:nbn:de:0030-drops-96774},
  doi =		{10.4230/LIPIcs.CSL.2018.10},
  annote =	{Keywords: dominated strategies, admissible strategies, games played on finite graphs, reactive synthesis, reachability games, safety games, cofinal, order theory}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CONCUR.2017.2
Admissibility in Games with Imperfect Information (Invited Talk)

Authors: Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
In this invited paper, we study the concept of admissible strategies for two player win/lose infinite sequential games with imperfect information. We show that in stark contrast with the perfect information variant, admissible strategies are only guaranteed to exist when players have objectives that are closed sets. As a consequence, we also study decision problems related to the existence of admissible strategies for regular games as well as finite duration games.
Cite as

Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur. Admissibility in Games with Imperfect Information (Invited Talk). In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{brenguier_et_al:LIPIcs.CONCUR.2017.2,
  author =	{Brenguier, Romain and Pauly, Arno and Raskin, Jean-Fran\c{c}ois and Sankur, Ocan},
  title =	{{Admissibility in Games with Imperfect Information}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.2},
  URN =		{urn:nbn:de:0030-drops-78066},
  doi =		{10.4230/LIPIcs.CONCUR.2017.2},
  annote =	{Keywords: Admissibility, non-zero sum games, reactive synthesis, imperfect infor- mation}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.16
Noetherian Quasi-Polish spaces

Authors: Matthew de Brecht and Arno Pauly

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
In the presence of suitable power spaces, compactness of X can be characterized as the singleton {X} being open in the space O(X) of open subsets of X. Equivalently, this means that universal quantification over a compact space preserves open predicates. Using the language of represented spaces, one can make sense of notions such as a Sigma^0_2-subset of the space of Sigma^0_2-subsets of a given space. This suggests higher-order analogues to compactness: We can, e.g., investigate the spaces X where {X} is a Delta^0_2-subset of the space of Delta^0_2-subsets of X. Call this notion nabla-compactness. As Delta^0_2 is self-dual, we find that both universal and existential quantifier over nabla-compact spaces preserve Delta^0_2 predicates. Recall that a space is called Noetherian iff every subset is compact. Within the setting of Quasi-Polish spaces, we can fully characterize the nabla-compact spaces: A Quasi-Polish space is Noetherian iff it is nabla-compact. Note that the restriction to Quasi-Polish spaces is sufficiently general to include plenty of examples.
Cite as

Matthew de Brecht and Arno Pauly. Noetherian Quasi-Polish spaces. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{debrecht_et_al:LIPIcs.CSL.2017.16,
  author =	{de Brecht, Matthew and Pauly, Arno},
  title =	{{Noetherian Quasi-Polish spaces}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.16},
  URN =		{urn:nbn:de:0030-drops-76988},
  doi =		{10.4230/LIPIcs.CSL.2017.16},
  annote =	{Keywords: Descriptive set theory, synthetic topology, well-quasi orders, Noetherian spaces, compactness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.50
Minkowski Games

Authors: Stéphane Le Roux, Arno Pauly, and Jean-François Raskin

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We introduce and study Minkowski games. In these games, two players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded (while the other wants to escape to infinity), and safety games, where one player wants to stay within a given set (while the other wants to leave it). We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.
Cite as

Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. Minkowski Games. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.STACS.2017.50,
  author =	{Le Roux, St\'{e}phane and Pauly, Arno and Raskin, Jean-Fran\c{c}ois},
  title =	{{Minkowski Games}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.50},
  URN =		{urn:nbn:de:0030-drops-69849},
  doi =		{10.4230/LIPIcs.STACS.2017.50},
  annote =	{Keywords: Control in R^d, determinacy, polytopic/arbitrary, coNP-complete, undecidable}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.58
Dividing by Zero - How Bad Is It, Really?

Authors: Takayuki Kihara and Arno Pauly

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way. In this note we investigate the strength of the computational problem Robust division: Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility. As application for Robust division, we show that it suffices to execute Gaussian elimination.
Cite as

Takayuki Kihara and Arno Pauly. Dividing by Zero - How Bad Is It, Really?. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kihara_et_al:LIPIcs.MFCS.2016.58,
  author =	{Kihara, Takayuki and Pauly, Arno},
  title =	{{Dividing by Zero - How Bad Is It, Really?}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.58},
  URN =		{urn:nbn:de:0030-drops-64702},
  doi =		{10.4230/LIPIcs.MFCS.2016.58},
  annote =	{Keywords: computable analysis, Weihrauch reducibility, recursion theory, linear algebra}
}
Document
DOI: 10.4230/DagRep.5.9.77
Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)

Authors: Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly

Published in: Dagstuhl Reports, Volume 5, Issue 9 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15392 "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis." It includes abstracts on most talks presented during the seminar, a list of open problems that were discussed and partially solved during the meeting as well as a bibliography on the seminar topic that we compiled during the seminar.
Cite as

Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly. Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392). In Dagstuhl Reports, Volume 5, Issue 9, pp. 77-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.5.9.77,
  author =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  title =	{{Measuring the Complexity of Computational Content (Dagstuhl Seminar 15392)}},
  pages =	{77--104},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Brattka, Vasco and Kawamura, Akitoshi and Marcone, Alberto and Pauly, Arno},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.9.77},
  URN =		{urn:nbn:de:0030-drops-56861},
  doi =		{10.4230/DagRep.5.9.77},
  annote =	{Keywords: Computability and complexity in analysis, computations on real numbers, reducibilities, descriptive complexity, computational complexity, reverse and constructive mathematics}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.CCA.2009.2271
How Discontinuous is Computing Nash Equilibria? (Extended Abstract)

Authors: Arno Pauly

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We investigate the degree of discontinuity of several solution concepts from non-cooperative game theory. While the consideration of Nash equilibria forms the core of our work, also pure and correlated equilibria are dealt with. Formally, we restrict the treatment to two player games, but results and proofs extend to the $n$-player case. As a side result, the degree of discontinuity of solving systems of linear inequalities is settled.
Cite as

Arno Pauly. How Discontinuous is Computing Nash Equilibria? (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 197-208, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{pauly:OASIcs.CCA.2009.2271,
  author =	{Pauly, Arno},
  title =	{{How Discontinuous is Computing Nash Equilibria?}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{197--208},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2271},
  URN =		{urn:nbn:de:0030-drops-22719},
  doi =		{10.4230/OASIcs.CCA.2009.2271},
  annote =	{Keywords: Game Theory, computable analysis, Nash equilibrium, discontinuity}
}
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 About DROPS Imprint Privacy Contact