3 Search Results for "Ventre, Carmine"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.76
Strong Approximations and Irrationality in Financial Networks with Derivatives

Authors: Stavros D. Ioannidis, Bart de Keijzer, and Carmine Ventre

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. Furthermore, Schuldenzucker et al. (2016) have shown that finding a weakly (or "almost") approximate (rational) fixed point is PPAD-complete. We further study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate solutions may misrepresent the actual financial state of an institution. On this basis, we study the complexity of finding a strongly (or "near") approximate solution, and show FIXP-completeness. We then study the structural properties required for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of non-linear polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of, PPAD.
Cite as

Stavros D. Ioannidis, Bart de Keijzer, and Carmine Ventre. Strong Approximations and Irrationality in Financial Networks with Derivatives. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 76:1-76:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ioannidis_et_al:LIPIcs.ICALP.2022.76,
  author =	{Ioannidis, Stavros D. and de Keijzer, Bart and Ventre, Carmine},
  title =	{{Strong Approximations and Irrationality in Financial Networks with Derivatives}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{76:1--76:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.76},
  URN =		{urn:nbn:de:0030-drops-164172},
  doi =		{10.4230/LIPIcs.ICALP.2022.76},
  annote =	{Keywords: FIXP, Financial Networks, Systemic Risk}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.71
Obviously Strategyproof Single-Minded Combinatorial Auctions

Authors: Bart de Keijzer, Maria Kyropoulou, and Carmine Ventre

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

Abstract
We consider the setting of combinatorial auctions when the agents are single-minded and have no contingent reasoning skills. We are interested in mechanisms that provide the right incentives to these imperfectly rational agents, and therefore focus our attention to obviously strategyproof (OSP) mechanisms. These mechanisms require that at each point during the execution where an agent is queried to communicate information, it should be "obvious" for the agent what strategy to adopt in order to maximise her utility. In this paper we study the potential of OSP mechanisms with respect to the approximability of the optimal social welfare. We consider two cases depending on whether the desired bundles of the agents are known or unknown to the mechanism. For the case of known-bundle single-minded agents we show that OSP can actually be as powerful as (plain) strategyproofness (SP). In particular, we show that we can implement the very same algorithm used for SP to achieve a √m-approximation of the optimal social welfare with an OSP mechanism, m being the total number of items. Restricting our attention to declaration domains with two values, we provide a 2-approximate OSP mechanism, and prove that this approximation bound is tight. We also present a randomised mechanism that is universally OSP and achieves a finite approximation of the optimal social welfare for the case of arbitrary size finite domains. This mechanism also provides a bounded approximation ratio when the valuations lie in a bounded interval (even if the declaration domain is infinitely large). For the case of unknown-bundle single-minded agents, we show how we can achieve an approximation ratio equal to the size of the largest desired set, in an OSP way. We remark this is the first known application of OSP to multi-dimensional settings, i.e., settings where agents have to declare more than one parameter. Our results paint a rather positive picture regarding the power of OSP mechanisms in this context, particularly for known-bundle single-minded agents. All our results are constructive, and even though some known strategyproof algorithms are used, implementing them in an OSP way is a non-trivial task.
Cite as

Bart de Keijzer, Maria Kyropoulou, and Carmine Ventre. Obviously Strategyproof Single-Minded Combinatorial Auctions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 71:1-71:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dekeijzer_et_al:LIPIcs.ICALP.2020.71,
  author =	{de Keijzer, Bart and Kyropoulou, Maria and Ventre, Carmine},
  title =	{{Obviously Strategyproof Single-Minded Combinatorial Auctions}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{71:1--71:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.71},
  URN =		{urn:nbn:de:0030-drops-124781},
  doi =		{10.4230/LIPIcs.ICALP.2020.71},
  annote =	{Keywords: OSP Mechanisms, Extensive-form Mechanisms, Single-minded Combinatorial Auctions, Greedy algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.46
Obviously Strategyproof Mechanisms for Machine Scheduling

Authors: Diodato Ferraioli, Adrian Meier, Paolo Penna, and Carmine Ventre

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms and approximation algorithms. Obviously strategyproof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the "right" definition rather than on the construction of these mechanisms. We here give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design.
Cite as

Diodato Ferraioli, Adrian Meier, Paolo Penna, and Carmine Ventre. Obviously Strategyproof Mechanisms for Machine Scheduling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 46:1-46:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ferraioli_et_al:LIPIcs.ESA.2019.46,
  author =	{Ferraioli, Diodato and Meier, Adrian and Penna, Paolo and Ventre, Carmine},
  title =	{{Obviously Strategyproof Mechanisms for Machine Scheduling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.46},
  URN =		{urn:nbn:de:0030-drops-111677},
  doi =		{10.4230/LIPIcs.ESA.2019.46},
  annote =	{Keywords: Bounded Rationality, Extensive-form Mechanisms, Approximate Mechanism Design}
}
  • Refine by Author
  • 3 Ventre, Carmine
  • 2 de Keijzer, Bart
  • 1 Ferraioli, Diodato
  • 1 Ioannidis, Stavros D.
  • 1 Kyropoulou, Maria
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 Extensive-form Mechanisms
  • 1 Approximate Mechanism Design
  • 1 Bounded Rationality
  • 1 FIXP
  • 1 Financial Networks
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact