16 Search Results for "Babaioff, Moshe"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.75
Prior-Independent and Subgame Optimal Online Algorithms

Authors: Jason Hartline, Aleck Johnsen, and Anant Shah

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
This paper develops two game-theoretic notions of beyond worst-case analysis that give better than worst-case guarantees on natural inputs. We illustrate them through the finite-horizon ski-rental problem. First, we consider prior-independent design and analysis of online algorithms where, rather than choosing a worst-case input, the adversary chooses a worst-case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial-time approximation scheme to compute them. Second, we consider the worst-case design of algorithms. We define "subgame optimality" which is stronger than worst-case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst-case input. Algorithms that focus only on the worst case can be far from subgame optimal. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework. Finally, we analyze the structure of their decisions across input sequences: the prior-independent algorithm exhibits more extreme adaptations to observed data, in contrast with the more conservative behavior of worst-case and subgame optimal algorithms.
Cite as

Jason Hartline, Aleck Johnsen, and Anant Shah. Prior-Independent and Subgame Optimal Online Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hartline_et_al:LIPIcs.ITCS.2026.75,
  author =	{Hartline, Jason and Johnsen, Aleck and Shah, Anant},
  title =	{{Prior-Independent and Subgame Optimal Online Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{75:1--75:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.75},
  URN =		{urn:nbn:de:0030-drops-253622},
  doi =		{10.4230/LIPIcs.ITCS.2026.75},
  annote =	{Keywords: online algorithms, prior-independent algorithm design, zero-sum games}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.58
One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Authors: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal’s utility), reward, and welfare. Our first result is a strong impossibility: For submodular reward functions, no randomized poly-time algorithm can approximate the optimal budget-feasible value within any finite factor, even with demand-oracle access. This result rules out extending known constant-factor guarantees from either (i) unbudgeted settings with combinatorial actions or (ii) budgeted settings with binary actions, to their combination. The hardness is tight: It holds even when all but one agent have binary actions and the remaining agent has just one additional action. On the positive side, we show that gross substitutes rewards (a well-studied strict subclass of submodular functions) admit a deterministic poly-time O(1)-approximation, using only value queries. Our results thus draw the first sharp separation between budgeted and unbudgeted settings in combinatorial contracts, and identifies gross substitutes as a tractable frontier for budgeted combinatorial contracts. Finally, we present an FPTAS for additive rewards, demonstrating that arbitrary approximation is tractable under any budget. This constitutes the first FPTAS for the multi-agent combinatorial-actions setting, even in the absence of budget constraints.
Cite as

Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 58:1-58:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ITCS.2026.58,
  author =	{Feldman, Michal and Gal-Tzur, Yoav and Ponitka, Tomasz and Schlesinger, Maya},
  title =	{{One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{58:1--58:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.58},
  URN =		{urn:nbn:de:0030-drops-253459},
  doi =		{10.4230/LIPIcs.ITCS.2026.58},
  annote =	{Keywords: Combinatorial Contracts, Algorithmic Contract Design, Budget-Feasible Contracts}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.65
Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

Authors: Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Roughgarden [Roughgarden, 2020] initiates the study of Transaction Fee Mechanisms (TFMs), and posits that the on-chain game of a "good" TFM should be on-chain simple (OnC-S), i.e., incentive compatible for both the users and the miner. Recent work of Ganesh, Thomas an Weinberg [Ganesh et al., 2024] posit that they should additionally be Off-Chain Influence-Proof (OffC-IP), which means that the miner cannot achieve any additional revenue by separately conducting an off-chain auction to determine on-chain inclusion. They observe that a cryptographic second-price auction satisfies both properties, but leave open the question of whether other mechanisms (such as those not dependent on cryptography) satisfy these properties. In this paper, we characterize OffC-IP TFMs: They are those satisfying a burn identity relating the burn rule to the allocation rule. In particular, we show that auction is OffC-IP if and only if its (induced direct-revelation) allocation rule X̄(⋅) and burn rule B̅(⋅) (both of which take as input users' values v₁, … , v_n) are truthful when viewing (X̄(⋅), B̅(⋅)) as the allocation and pricing rule of a multi-item auction for a single additive buyer with values (φ(v₁),…, φ(v_n)) equal to the users' virtual values. Building on this burn identity, we characterize OffC-IP and OnC-S TFMs that are deterministic and do not use cryptography: They are posted-price mechanisms with specially-tuned burns. As a corollary, we show that such TFMs can only exist with infinite supply and prior-dependence. However, we show that for randomized TFMs, there are additional OnC-S and OffC-IP auctions that do not use cryptography (even when there is {finite} supply, under prior-dependence with a bounded prior distribution). Holistically, our results show that while OffC-IP is a fairly stringent requirement, families of OffC-IP mechanisms can be found for a variety of settings.
Cite as

Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg. Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 65:1-65:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ITCS.2026.65,
  author =	{Ganesh, Aadityan and Thomas, Clayton and Weinberg, S. Matthew},
  title =	{{Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{65:1--65:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.65},
  URN =		{urn:nbn:de:0030-drops-253527},
  doi =		{10.4230/LIPIcs.ITCS.2026.65},
  annote =	{Keywords: Transaction Fee Mechanism Design, Off-Chain Influence Proofness, Blockchain, Decentralized Finance, Simple Auctions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.86
The Secretary Problem with Predictions and a Chosen Order

Authors: Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023). In this variant, the decision-maker has access to machine-learned predictions of candidate values in advance. The key challenge is to balance consistency and robustness: when the predictions are accurate, the algorithm should hire a near-best secretary; however, if they are inaccurate, the algorithm should still achieve a bounded competitive ratio. We consider both the standard Random Order Secretary Problem (ROSP), where candidates arrive in a uniform random order, and a more natural model in the learning-augmented setting, where the decision-maker can choose the arrival order based on the predicted candidate values. This model, which we call the Chosen Order Secretary Problem (COSP), can capture scenarios such as an interview schedule that is set by the decision-maker. We propose a novel algorithm that applies to both ROSP and COSP. Building on the approach of Fujii and Yoshida, our method switches from fully trusting predictions to a threshold-based rule when a large deviation of a prediction is observed. Importantly, unlike the algorithm of Fujii and Yoshida, our algorithm uses randomization as part of its decision logic. We show that if ε ∈ [0,1] denotes the maximum multiplicative prediction error, then for ROSP our algorithm achieves competitive ratio max {0.221, (1-ε)/(1+ε)}, improving on a previous bound of max {0.215, (1-ε)/(1+ε)} due to Fujii and Yoshida [Fujii and Yoshida, 2023]. For COSP, our algorithm achieves max {0.262, (1-ε)/(1+ε)}. This surpasses a 0.25 upper bound on the worst-case competitive ratio that applies to the approach of Fujii and Yoshida, and gets closer to the classical secretary benchmark of 1/e ≈ 0.368, which is an upper bound for any algorithm. Our result for COSP highlights the benefit of integrating predictions with arrival-order control in online decision-making.
Cite as

Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco. The Secretary Problem with Predictions and a Chosen Order. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 86:1-86:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karisani_et_al:LIPIcs.ITCS.2026.86,
  author =	{Karisani, Helia and Daneshvaramoli, Mohammadreza and Beyhaghi, Hedyeh and Hajiesmaili, Mohammad and Musco, Cameron},
  title =	{{The Secretary Problem with Predictions and a Chosen Order}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{86:1--86:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.86},
  URN =		{urn:nbn:de:0030-drops-253734},
  doi =		{10.4230/LIPIcs.ITCS.2026.86},
  annote =	{Keywords: Secretary problem, learning-augmented algorithms, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.96
Robust Resource Allocation via Competitive Subsidies

Authors: David X. Lin, Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With n symmetric agents, a natural benchmark for each agent is the utility realized by her favorite 1/n-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be 1/2-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of 0.59, which cannot be improved beyond 0.6 using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is 1-1/e≈ 0.63. In this work, we break the 0.6 first-price barrier to get a new 0.625-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when k agents bid, then the winner pays proportional to k/(k+1), varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of 5/(3e) ≈ 0.61 (and the optimal 1-1/e factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.
Cite as

David X. Lin, Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos. Robust Resource Allocation via Competitive Subsidies. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITCS.2026.96,
  author =	{Lin, David X. and Fikioris, Giannis and Banerjee, Siddhartha and Tardos, \'{E}va},
  title =	{{Robust Resource Allocation via Competitive Subsidies}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{96:1--96:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.96},
  URN =		{urn:nbn:de:0030-drops-253835},
  doi =		{10.4230/LIPIcs.ITCS.2026.96},
  annote =	{Keywords: Online Resource Allocation, Non-Monetary Mechanisms}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.24
Multidimensional Blockchain Fees Are (Essentially) Optimal

Authors: Guillermo Angeris, Theo Diamandis, and Ciamac Moallemi

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
In this paper we show that, using only mild assumptions, dynamic multidimensional blockchain fee markets have strong performance guarantees, even against worst-case adversaries. In particular, we show that the average welfare gap between the following two scenarios is at most O(1/√T), where T is the length of the time horizon considered. In the first scenario, the designer knows all future actions by users and is allowed to fix the optimal prices of resources ahead of time, based on the designer’s oracular knowledge of those actions. In the second, the prices are updated by a very simple algorithm that does not have this oracular knowledge, special cases of which are EIP-4844 and EIP-1559, both fee mechanisms used by the Ethereum blockchain. Roughly speaking, this means that, on average, over a reasonable timescale, there is no difference in welfare between "correctly" fixing the prices, with oracular knowledge of the future, when compared to the proposed algorithm. We show a matching lower bound of Ω(1/√T) for any implementable algorithm and also separately consider the case where the adversary is known to be stochastic.
Cite as

Guillermo Angeris, Theo Diamandis, and Ciamac Moallemi. Multidimensional Blockchain Fees Are (Essentially) Optimal. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angeris_et_al:LIPIcs.AFT.2025.24,
  author =	{Angeris, Guillermo and Diamandis, Theo and Moallemi, Ciamac},
  title =	{{Multidimensional Blockchain Fees Are (Essentially) Optimal}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.24},
  URN =		{urn:nbn:de:0030-drops-247433},
  doi =		{10.4230/LIPIcs.AFT.2025.24},
  annote =	{Keywords: Blockchains, transaction fees, online optimization, convex optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.52
Beating Competitive Ratio 4 for Graphic Matroid Secretary

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.
Cite as

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating Competitive Ratio 4 for Graphic Matroid Secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ESA.2025.52,
  author =	{Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Kowalski, Dariusz R. and Krysta, Piotr and Mittal, Danny and Olkowski, Jan},
  title =	{{Beating Competitive Ratio 4 for Graphic Matroid Secretary}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.52},
  URN =		{urn:nbn:de:0030-drops-245205},
  doi =		{10.4230/LIPIcs.ESA.2025.52},
  annote =	{Keywords: online algorithms, graphic matroids, secretary problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.19
Dynamic Algorithms for Submodular Matching

Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The Maximum Submodular Matching (MSM) problem is a generalization of the classical Maximum Weight Matching (MWM) problem. In this problem, given a monotone submodular function f: 2^E → ℝ^{≥ 0} defined over subsets of edges of a graph G(V, E), we are asked to return a matching whose submodular value is maximum among all matchings in graph G(V, E). In this paper, we consider this problem in a fully dynamic setting against an oblivious adversary. In this setting, we are given a sequence 𝒮 of insertions and deletions of edges of the underlying graph G(V, E), along with an oracle access to the monotone submodular function f. The goal is to maintain a matching M such that, at any time t of sequence 𝒮, its submodular value is a good approximation of the value of the optimal submodular matching while keeping the number of operations minimal. We develop the first dynamic algorithm for the submodular matching problem, in which we maintain a matching whose submodular value is within expected (8 + ε)-approximation of the optimal submodular matching at any time t of sequence 𝒮 using expected amortized poly(log n, 1/(ε)) update time. Our approach incorporates a range of novel techniques, notably the concept of Uniform Hierarchical Caches (UHC) data structure along with its invariants, which lead to the first algorithm for fully dynamic submodular matching and may be of independent interest for designing dynamic algorithms for other problems.
Cite as

Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic Algorithms for Submodular Matching. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ICALP.2025.19,
  author =	{Banihashem, Kiarash and Biabani, Leyla and Goudarzi, Samira and Hajiaghayi, MohammadTaghi and Jabbarzade, Peyman and Monemizadeh, Morteza},
  title =	{{Dynamic Algorithms for Submodular Matching}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.19},
  URN =		{urn:nbn:de:0030-drops-233969},
  doi =		{10.4230/LIPIcs.ICALP.2025.19},
  annote =	{Keywords: Matching, Submodular, Dynamic, Polylogarithmic}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.18
q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Authors: Kiril Bangachev and S. Matthew Weinberg

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
For a set M of m elements, we define a decreasing chain of classes of normalized monotone-increasing valuation functions from 2^M to ℝ_{≥ 0}, parameterized by an integer q ∈ [2,m]. For a given q, we refer to the class as q-partitioning. A valuation function is subadditive if and only if it is 2-partitioning, and fractionally subadditive if and only if it is m-partitioning. Thus, our chain establishes an interpolation between subadditive and fractionally subadditive valuations. We show that this interpolation is smooth (q-partitioning valuations are "nearly" (q-1)-partitioning in a precise sense, Theorem 6), interpretable (the definition arises by analyzing the core of a cost-sharing game, à la the Bondareva-Shapley Theorem for fractionally subadditive valuations, Section 3.1), and non-trivial (the class of q-partitioning valuations is distinct for all q, Proposition 3). For domains where provable separations exist between subadditive and fractionally subadditive, we interpolate the stronger guarantees achievable for fractionally subadditive valuations to all q ∈ {2,…, m}. Two highlights are the following: 1) An Ω ((log log q)/(log log m))-competitive posted price mechanism for q-partitioning valuations. Note that this matches asymptotically the state-of-the-art for both subadditive (q = 2) [Paul Dütting et al., 2020], and fractionally subadditive (q = m) [Feldman et al., 2015]. 2) Two upper-tail concentration inequalities on 1-Lipschitz, q-partitioning valuations over independent items. One extends the state-of-the-art for q = m to q < m, the other improves the state-of-the-art for q = 2 for q > 2. Our concentration inequalities imply several corollaries that interpolate between subadditive and fractionally subadditive, for example: 𝔼[v(S)] ≤ (1 + 1/log q)Median[v(S)] + O(log q). To prove this, we develop a new isoperimetric inequality using Talagrand’s method of control by q points, which may be of independent interest. We also discuss other probabilistic inequalities and game-theoretic applications of q-partitioning valuations, and connections to subadditive MPH-k valuations [Tomer Ezra et al., 2019].
Cite as

Kiril Bangachev and S. Matthew Weinberg. q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bangachev_et_al:LIPIcs.ICALP.2025.18,
  author =	{Bangachev, Kiril and Weinberg, S. Matthew},
  title =	{{q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.18},
  URN =		{urn:nbn:de:0030-drops-233956},
  doi =		{10.4230/LIPIcs.ICALP.2025.18},
  annote =	{Keywords: Subadditive Functions, Fractionally Subadditive Functions, Posted Price Mechanisms, Concentration Inequalities}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.137
Universal Online Contention Resolution with Preselected Order

Authors: Junyao Zhao

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which - in the case of matroids - given a matroid and a prior distribution of active elements, selects a subset of active elements that satisfies the matroid constraint in an online fashion. OCRS has been studied mostly for product distributions in the literature. Recently, universal OCRS, that works even for correlated distributions, has gained interest, because it naturally generalizes the classic notion, and its existence in the random-order arrival model turns out to be equivalent to the matroid secretary conjecture. However, currently very little is known about how to design universal OCRSs for any arrival model. In this work, we consider a natural and relatively flexible arrival model, where the OCRS is allowed to preselect (i.e., non-adaptively select) the arrival order of the elements, and within this model, we design simple and optimal universal OCRSs that are computationally efficient. In the course of deriving our OCRSs, we also discover an efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model, answering a question posed in [Dughmi, 2020].
Cite as

Junyao Zhao. Universal Online Contention Resolution with Preselected Order. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 137:1-137:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao:LIPIcs.ICALP.2025.137,
  author =	{Zhao, Junyao},
  title =	{{Universal Online Contention Resolution with Preselected Order}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{137:1--137:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.137},
  URN =		{urn:nbn:de:0030-drops-235147},
  doi =		{10.4230/LIPIcs.ICALP.2025.137},
  annote =	{Keywords: Matroids, online contention resolution schemes, secretary problems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.84
Quantum Communication Complexity of Classical Auctions

Authors: Aviad Rubinstein and Zixin Zhou

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the buyer and the seller. Specifically, we ask whether using quantum communication can be more efficient than classical communication. We have two sets of results, revealing a surprisingly rich landscape - which looks quite different from both quantum communication in non-strategic parties, and classical communication in mechanism design. We first study the expected communication complexity of approximately optimal auctions. We give quantum auction protocols for buyers with unit-demand or combinatorial valuations that obtain an arbitrarily good approximation of the optimal revenue while running in exponentially more efficient communication compared to classical approximately optimal auctions. However, these auctions come with the caveat that they may require the seller to charge exponentially large payments from a deviating buyer. We show that this caveat is necessary - we give an exponential lower bound on the product of the expected quantum communication and the maximum payment. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting: additive buyer’s valuations over two items. We show the following separations: - There exists a prior where the optimal classical auction protocol requires infinitely many bits, but a one-way message of 1 qubit and 2 classical bits suffices. - There exists a prior where no finite one-way quantum auction protocol can obtain the optimal revenue. However, there is a barely-interactive revenue-optimal quantum auction protocol with the following simple structure: the seller prepares a pair of qubits in the EPR state, sends one of them to the buyer, and then the buyer sends 1 qubit and 2 classical bits. - There exists a prior where no multi-round quantum auction protocol with a finite bound on communication complexity can obtain the optimal revenue.
Cite as

Aviad Rubinstein and Zixin Zhou. Quantum Communication Complexity of Classical Auctions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 84:1-84:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2025.84,
  author =	{Rubinstein, Aviad and Zhou, Zixin},
  title =	{{Quantum Communication Complexity of Classical Auctions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{84:1--84:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-227124},
  doi =		{10.4230/LIPIcs.ITCS.2025.84},
  annote =	{Keywords: Mechanism design, Communication complexity, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.41
Query Complexity of Stochastic Minimum Vertex Cover

Authors: Mahsa Derakhshan, Mohammad Saneian, and Zhiyang Xun

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the stochastic minimum vertex cover problem for general graphs. In this problem, we are given a graph G = (V, E) and an existence probability p_e for each edge e ∈ E. Edges of G are realized (or exist) independently with these probabilities, forming the realized subgraph 𝒢. The existence of an edge in 𝒢 can only be verified using edge queries. The goal of this problem is to find a near-optimal vertex cover of 𝒢 using a small number of queries. Previous work by Derakhshan, Durvasula, and Haghtalab [STOC 2023] established the existence of 1.5 + ε approximation algorithms for this problem with O(n/ε) queries. They also show that, under mild correlation among edge realizations, beating this approximation ratio requires querying a subgraph of size Ω(n ⋅ RS(n)). Here, RS(n) refers to Ruzsa-Szemerédi Graphs and represents the largest number of induced edge-disjoint matchings of size Θ(n) in an n-vertex graph. In this work, we design a simple algorithm for finding a (1 + ε) approximate vertex cover by querying a subgraph of size O(n ⋅ RS(n)) for any absolute constant ε > 0. Our algorithm can tolerate up to O(n ⋅ RS(n)) correlated edges, hence effectively completing our understanding of the problem under mild correlation.
Cite as

Mahsa Derakhshan, Mohammad Saneian, and Zhiyang Xun. Query Complexity of Stochastic Minimum Vertex Cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 41:1-41:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derakhshan_et_al:LIPIcs.ITCS.2025.41,
  author =	{Derakhshan, Mahsa and Saneian, Mohammad and Xun, Zhiyang},
  title =	{{Query Complexity of Stochastic Minimum Vertex Cover}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{41:1--41:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-226691},
  doi =		{10.4230/LIPIcs.ITCS.2025.41},
  annote =	{Keywords: Sublinear algorithms, Vertex cover, Query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.9
Making Auctions Robust to Aftermarkets

Authors: Moshe Babaioff, Nicole Immorlica, Yingkai Li, and Brendan Lucier

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can typically trade these allowances among themselves in an aftermarket that may not be fully under the auctioneer’s control. While the uniform-price auction is approximately efficient in isolation, we show that speculation and resale in aftermarkets might result in a significant welfare loss. Motivated by this issue, we consider three approaches, each ensuring high equilibrium welfare in the combined market. The first approach is to adopt smooth auctions such as discriminatory auctions. This approach is robust to correlated valuations and to participants acquiring information about others' types. However, discriminatory auctions have several downsides, notably that of charging bidders different prices for identical items, resulting in fairness concerns that make the format unpopular. Two other approaches we suggest are either using posted-pricing mechanisms, or using uniform-price auctions with anonymous reserves. We show that when using balanced prices, both these approaches ensure high equilibrium welfare in the combined market. The latter also inherits many of the benefits from uniform-price auctions such as price discovery, and can be introduced with a minor modification to auctions currently in use to sell carbon emission allowances.
Cite as

Moshe Babaioff, Nicole Immorlica, Yingkai Li, and Brendan Lucier. Making Auctions Robust to Aftermarkets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ITCS.2023.9,
  author =	{Babaioff, Moshe and Immorlica, Nicole and Li, Yingkai and Lucier, Brendan},
  title =	{{Making Auctions Robust to Aftermarkets}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.9},
  URN =		{urn:nbn:de:0030-drops-175122},
  doi =		{10.4230/LIPIcs.ITCS.2023.9},
  annote =	{Keywords: carbon markets, aftermarkets, price of anarchy, multi-unit auctions, posted prices}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2021.84
Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)

Authors: Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier

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

Abstract
Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.
Cite as

Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 84:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ITCS.2021.84,
  author =	{Babaioff, Moshe and Cole, Richard and Hartline, Jason and Immorlica, Nicole and Lucier, Brendan},
  title =	{{Non-Quasi-Linear Agents in Quasi-Linear Mechanisms}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{84:1--84: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.84},
  URN =		{urn:nbn:de:0030-drops-136230},
  doi =		{10.4230/LIPIcs.ITCS.2021.84},
  annote =	{Keywords: Return on investment, Non-quasi-linear agents, Transferable Welfare, Simultaneous Second-Price Auctions}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.134
Selling Complementary Goods: Dynamics, Efficiency and Revenue

Authors: Moshe Babaioff, Liad Blumrosen, and Noam Nisan

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We consider a price competition between two sellers of perfect-complement goods. Each seller posts a price for the good it sells, but the demand is determined according to the sum of prices. This is a classic model by Cournot (1838), who showed that in this setting a monopoly that sells both goods is better for the society than two competing sellers. We show that non-trivial pure Nash equilibria always exist in this game. We also quantify Cournot's observation with respect to both the optimal welfare and the monopoly revenue. We then prove a series of mostly negative results regarding the convergence of best response dynamics to equilibria in such games.
Cite as

Moshe Babaioff, Liad Blumrosen, and Noam Nisan. Selling Complementary Goods: Dynamics, Efficiency and Revenue. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 134:1-134:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ICALP.2017.134,
  author =	{Babaioff, Moshe and Blumrosen, Liad and Nisan, Noam},
  title =	{{Selling Complementary Goods: Dynamics, Efficiency and Revenue}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{134:1--134:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian 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.ICALP.2017.134},
  URN =		{urn:nbn:de:0030-drops-74757},
  doi =		{10.4230/LIPIcs.ICALP.2017.134},
  annote =	{Keywords: Complements, Pricing, Networks, Game Theory, Price of Stability}
}
  • Refine by Type
  • 16 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 7 2025
  • 1 2023
  • 1 2021
  • 1 2017
  • Show More...

  • Refine by Author
  • 4 Babaioff, Moshe
  • 2 Banihashem, Kiarash
  • 2 Blumrosen, Liad
  • 2 Hajiaghayi, MohammadTaghi
  • 2 Hartline, Jason
  • Show More...

  • Refine by Series/Journal
  • 16 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Algorithmic mechanism design
  • 4 Theory of computation → Online algorithms
  • 2 Theory of computation → Algorithmic game theory
  • 2 Theory of computation → Computational pricing and auctions
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 3 online algorithms
  • 2 Complements
  • 2 Game Theory
  • 2 Networks
  • 2 Price of Stability
  • 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