4 Search Results for "Wilhelmi, Lisa"

Document
DOI: 10.4230/LIPIcs.STACS.2026.14
Computing Tarski Fixed Points in Financial Networks

Authors: Leander Besting, Martin Hoefer, and Lars Huth

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Modern financial networks are highly connected and result in complex interdependencies of the involved institutions. In the prominent Eisenberg-Noe model [Eisenberg and Noe, 2001], a fundamental aspect is clearing - to determine the amount of assets available to each financial institution in the presence of potential defaults and bankruptcy. A clearing state represents a fixed point that satisfies a set of natural axioms. Existence can be established (even in broad generalizations of the model) using Tarski’s theorem. While a maximal fixed point can be computed in polynomial time, the complexity of computing other fixed points is open. In this paper, we provide an efficient algorithm to compute a minimal fixed point. Our algorithm applies in a broad generalization of the Eisenberg-Noe model with any monotone, piecewise-linear payment functions and default costs. We also study claims trading, a local network adjustment to improve clearing, when networks are evaluated with minimal clearing. We provide an efficient algorithm to decide existence of Pareto-improving trades and compute optimal ones if they exist.
Cite as

Leander Besting, Martin Hoefer, and Lars Huth. Computing Tarski Fixed Points in Financial Networks. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{besting_et_al:LIPIcs.STACS.2026.14,
  author =	{Besting, Leander and Hoefer, Martin and Huth, Lars},
  title =	{{Computing Tarski Fixed Points in Financial Networks}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.14},
  URN =		{urn:nbn:de:0030-drops-255038},
  doi =		{10.4230/LIPIcs.STACS.2026.14},
  annote =	{Keywords: Tarski Fixed Points, Financial Networks, Minimal Clearing, Claims Trade}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.2
Dynamic Debt Swapping in Financial Networks

Authors: Henri Froese, Martin Hoefer, and Lisa Wilhelmi

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood. We analyze the computational complexity of debt swapping. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of v-improving debt swaps from which a given bank v strictly profits. For ranking-based clearing, we show that every sequence of semi-positive v-improving swaps has polynomial length. In contrast, for arbitrary v-improving swaps, the problem of reaching a network configuration that allows no further swaps is PLS-complete. We identify cases in which short sequences of semi-positive swaps exist even without the v-improving property.
Cite as

Henri Froese, Martin Hoefer, and Lisa Wilhelmi. Dynamic Debt Swapping in Financial Networks. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{froese_et_al:LIPIcs.SAND.2025.2,
  author =	{Froese, Henri and Hoefer, Martin and Wilhelmi, Lisa},
  title =	{{Dynamic Debt Swapping in Financial Networks}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.2},
  URN =		{urn:nbn:de:0030-drops-230550},
  doi =		{10.4230/LIPIcs.SAND.2025.2},
  annote =	{Keywords: Debt Swap, Financial Networks, Local Search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.42
Algorithms for Claims Trading

Authors: Martin Hoefer, Carmine Ventre, and Lisa Wilhelmi

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The recent banking crisis has again emphasized the importance of understanding and mitigating systemic risk in financial networks. In this paper, we study a market-driven approach to rescue a bank in distress based on the idea of claims trading, a notion defined in Chapter 11 of the U.S. Bankruptcy Code. We formalize the idea in the context of the seminal model of financial networks by Eisenberg and Noe [Eisenberg and Noe, 2001]. For two given banks v and w, we consider the operation that w takes over some claims of v and in return gives liquidity to v (or creditors of v) to ultimately rescue v (or mitigate contagion effects). We study the structural properties and computational complexity of decision and optimization problems for several variants of claims trading. When trading incoming edges of v (i.e., claims for which v is the creditor), we show that there is no trade in which both banks v and w strictly improve their assets. We therefore consider creditor-positive trades, in which v profits strictly and w remains indifferent. For a given set C of incoming edges of v, we provide an efficient algorithm to compute payments by w that result in a creditor-positive trade and maximal assets of v. When the set C must also be chosen, the problem becomes weakly NP-hard. Our main result here is a bicriteria FPTAS to compute an approximate trade, which allows for slightly increased payments by w. The approximate trade results in nearly the optimal amount of assets of v in any exact trade. Our results extend to the case in which banks use general monotone payment functions to settle their debt and the emerging clearing state can be computed efficiently. In contrast, for trading outgoing edges of v (i.e., claims for which v is the debtor), the goal is to maximize the increase in assets for the creditors of v. Notably, for these results the characteristics of the payment functions of the banks are essential. For payments ranking creditors one by one, we show NP-hardness of approximation within a factor polynomial in the network size, in both problem variants when the set of claims C is part of the input or not. Instead, for payments proportional to the value of each debt, our results indicate more favorable conditions.
Cite as

Martin Hoefer, Carmine Ventre, and Lisa Wilhelmi. Algorithms for Claims Trading. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hoefer_et_al:LIPIcs.STACS.2024.42,
  author =	{Hoefer, Martin and Ventre, Carmine and Wilhelmi, Lisa},
  title =	{{Algorithms for Claims Trading}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.42},
  URN =		{urn:nbn:de:0030-drops-197523},
  doi =		{10.4230/LIPIcs.STACS.2024.42},
  annote =	{Keywords: Financial Networks, Claims Trade, Systemic Risk}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.65
Packing Returning Secretaries

Authors: Martin Hoefer and Lisa Wilhelmi

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study online secretary problems with returns in combinatorial packing domains with n candidates that arrive sequentially over time in random order. The goal is to accept a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All 2n arrivals occur in random order. We propose a simple 0.5-competitive algorithm that can be combined with arbitrary approximation algorithms for the packing domain, even when the total value of candidates is a subadditive function. For bipartite matching, we obtain an algorithm with competitive ratio at least 0.5721 - o(1) for growing n, and an algorithm with ratio at least 0.5459 for all n >= 1. We extend all algorithms and ratios to k >= 2 arrivals per candidate. In the second variant, there is a pool of undecided candidates. In each round, a random candidate from the pool arrives. Upon arrival a candidate can be either decided (accept/reject) or postponed (returned into the pool). We mainly focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Theta(n log n) is always sufficient. For matroids, we show that the expected number can be reduced to O(r log (n/r)), where r <=n/2 is the minimum of the ranks of matroid and dual matroid. For bipartite matching, we show a bound of O(r log n), where r is the size of the optimum matching. For general packing, we show a lower bound of Omega(n log log n), even when the size of the optimum is r = Theta(log n).
Cite as

Martin Hoefer and Lisa Wilhelmi. Packing Returning Secretaries. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hoefer_et_al:LIPIcs.ISAAC.2018.65,
  author =	{Hoefer, Martin and Wilhelmi, Lisa},
  title =	{{Packing Returning Secretaries}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{65:1--65:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.65},
  URN =		{urn:nbn:de:0030-drops-100133},
  doi =		{10.4230/LIPIcs.ISAAC.2018.65},
  annote =	{Keywords: Secretary Problem, Coupon Collector Problem, Matroids}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2024
  • 1 2018

  • Refine by Author
  • 4 Hoefer, Martin
  • 3 Wilhelmi, Lisa
  • 1 Besting, Leander
  • 1 Froese, Henri
  • 1 Huth, Lars
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 3 Networks → Network algorithms
  • 2 Theory of computation → Theory and algorithms for application domains
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 3 Financial Networks
  • 2 Claims Trade
  • 1 Coupon Collector Problem
  • 1 Debt Swap
  • 1 Local Search
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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