Search Results

Documents authored by Dütting, Paul

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.69
Online Matroid Embeddings

Authors: Andrés Cristi, Paul Dütting, Robert Kleinberg, Renato Paes Leme, and Neel Patel

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. The existence of such embedding enables a reduction from the version of the matroid secretary problem where the matroid is unknown to the version where the matroid is known in advance. We establish the existence of such an embedding for binary matroids, and use it to relate variants of the binary matroid secretary problem to each other, showing that seemingly simpler problems are in fact equivalent to seemingly harder ones (up to constant-factors). Specifically, we show this to be the case for the version of the matroid secretary problem in which the binary matroid is not known in advance, and where it is known in advance. We also show that the version with known matroid structure is equivalent to the problem where weights are not fully adversarial but drawn from a known pairwise-independent distribution.
Cite as

Andrés Cristi, Paul Dütting, Robert Kleinberg, Renato Paes Leme, and Neel Patel. Online Matroid Embeddings. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 69:1-69:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cristi_et_al:LIPIcs.ICALP.2026.69,
  author =	{Cristi, Andr\'{e}s and D\"{u}tting, Paul and Kleinberg, Robert and Paes Leme, Renato and Patel, Neel},
  title =	{{Online Matroid Embeddings}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{69:1--69:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.69},
  URN =		{urn:nbn:de:0030-drops-264585},
  doi =		{10.4230/LIPIcs.ICALP.2026.69},
  annote =	{Keywords: Matroids, Secretary Problem, Online Algorithm}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2021.86
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract)

Authors: José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, and Bruno Ziliotto

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
A prophet inequality states, for some α ∈ [0,1], that the expected value achievable by a gambler who sequentially observes random variables X_1,… ,X_n and selects one of them is at least an α fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional β n samples for some β ≥ 0. We first give improved lower bounds on α for a wide range of values of β; specifically, α ≥ (1+β)/e when β ≤ 1/(e-1), which is tight, and α ≥ 0.648 when β = 1, which improves on a bound of around 0.635 due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of 1/e for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.
Cite as

José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, and Bruno Ziliotto. Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 86:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{correa_et_al:LIPIcs.ITCS.2021.86,
  author =	{Correa, Jos\'{e} and D\"{u}tting, Paul and Fischer, Felix and Schewior, Kevin and Ziliotto, Bruno},
  title =	{{Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{86:1--86:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.86},
  URN =		{urn:nbn:de:0030-drops-136255},
  doi =		{10.4230/LIPIcs.ITCS.2021.86},
  annote =	{Keywords: Prophet Inequalities, Stopping Theory, Unknown Distributions}
}
Document
DOI: 10.4230/DagRep.7.6.68
Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251)

Authors: Paul W. Goldberg, Yishay Mansour, and Paul Dütting

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)

Abstract
his report documents the program and the outcomes of Dagstuhl Seminar 17251 "Game Theory Meets Computational Learning Theory". While there have been many Dagstuhl seminars on various aspects of Algorithmic Game Theory, this was the first one to focus on the emerging field of its intersection with computational learning theory.
Cite as

Paul W. Goldberg, Yishay Mansour, and Paul Dütting. Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251). In Dagstuhl Reports, Volume 7, Issue 6, pp. 68-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{goldberg_et_al:DagRep.7.6.68,
  author =	{Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul},
  title =	{{Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251)}},
  pages =	{68--85},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.6.68},
  URN =		{urn:nbn:de:0030-drops-82876},
  doi =		{10.4230/DagRep.7.6.68},
  annote =	{Keywords: Algorithmic Game Theory, Computational Learning Theory, Economics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2463
Sponsored Search, Market Equilibria, and the Hungarian Method

Authors: Paul Dütting, Monika Henzinger, and Ingmar Weber

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where $n$ advertisers compete for the assignment of one of $k$ sponsored search results, also known as ``slots'', for certain keywords they are interested in. Here, as in other markets of that kind, market equilibria correspond to stable matchings. In this paper, we show how to modify Kuhn's Hungarian Method (Kuhn, 1955) so that it finds an optimal stable matching between advertisers and advertising slots in settings with generalized linear utilities, per-bidder-item reserve prices, and per-bidder-item maximum prices. The only algorithm for this problem presented so far (Aggarwal et al., 2009) requires the market to be in ``general position''. We do not make this assumption.
Cite as

Paul Dütting, Monika Henzinger, and Ingmar Weber. Sponsored Search, Market Equilibria, and the Hungarian Method. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 287-298, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dutting_et_al:LIPIcs.STACS.2010.2463,
  author =	{D\"{u}tting, Paul and Henzinger, Monika and Weber, Ingmar},
  title =	{{Sponsored Search, Market Equilibria, and the Hungarian Method}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{287--298},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2463},
  URN =		{urn:nbn:de:0030-drops-24636},
  doi =		{10.4230/LIPIcs.STACS.2010.2463},
  annote =	{Keywords: Stable matching, truthful matching mechanism, general position}
}
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