DROPS

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

DOI: 10.4230/LIPIcs.ITCS.2022.105

Interactive Communication in Bilateral Trade

Authors: Jieming Mao, Renato Paes Leme, and Kangning Wang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.

Cite as

Jieming Mao, Renato Paes Leme, and Kangning Wang. Interactive Communication in Bilateral Trade. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 105:1-105:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mao_et_al:LIPIcs.ITCS.2022.105,
  author =	{Mao, Jieming and Paes Leme, Renato and Wang, Kangning},
  title =	{{Interactive Communication in Bilateral Trade}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{105:1--105:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.105},
  URN =		{urn:nbn:de:0030-drops-157014},
  doi =		{10.4230/LIPIcs.ITCS.2022.105},
  annote =	{Keywords: Bayesian persuasion, bilateral trade, information design}
}

Search Results

Documents authored by Paes Leme, Renato

Online Matroid Embeddings

Abstract

Cite as

Interactive Communication in Bilateral Trade

Abstract

Cite as

Thanks for your feedback!

Could not send message