On multiagent online problems with predictions

Cosmin Bonchis; Gabriel Istrate; Victor Bogdan

REVIEW 3 major objections 4 minor 43 references

On multiagent online problems with predictions

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves exact optimal competitive ratios for multiagent ski-rental with two predictors: $B+1$ when others are unpredictable (even with a perfect self-predictor), an explicit price-sequence formula when others are perfectly…

desk verdict Clean two-predictor framework with exact ratios, but the headline B+1 bound is more contingent on the overpledge settlement rule than the paper admits. read the letter →

arxiv 2507.12486 v1 pith:FZQIS5W6 submitted 2025-07-15 cs.MA cs.AIcs.GT

Gabriel Istrate , Cosmin Bonchis , Victor Bogdan This is my paper · ORCID

classification cs.MAcs.AIcs.GT MSC 68W27

keywords algorithmswithpredictionsmultiagentskirentalcompetitiveanalysislearning-augmentedconsistencyrobustnesstwo-predictormodel

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes exact worst-case bounds for online algorithms with predictions in a multiagent setting, using a group version of the ski-rental problem as its test case. Each agent is endowed with two predictors — one for its own future activity, one for the aggregate pledges of the others — and the paper classifies each as perfect or pessimal. The main results (Theorems 1–4) say that with an unpredictable other side the optimal deterministic competitive ratio is exactly $B+1$ even when the agent knows its own future perfectly; with perfect other-prediction the optimal ratio is the explicit quantity $c_{OPT}(p)=\min(\{P_r/r:r\le M^*(p)\}\cup\{Q_{M^*(p)}/M^*(p)\})$; and with both predictors perfect the ratio drops to 1. A $\lambda$-parameterized algorithm interpolates between the no-prediction optimum and the perfect-prediction follower, trading robustness for consistency in a provable way. If the paper is right, these are exact frontiers, and they show precisely when better predictions of one's own or others' behavior pay off in shared-cost settings.

What carries the argument

The object that carries the argument is the reduction of the multiagent problem to a single-agent 'ski-rental with varying prices' (Definition 3). Only two numbers enter the agent's decision each day: the rent cost 1 and the price $p_i$ of acquiring the group license, equal to the gap $B - \text{(others' total pledge)}$; the others-predictor supplies the sequence $p_i$ and the self-predictor the active horizon $T$. The main identity is the optimal-ratio formula $c_{OPT}(p)=\min(\{P_r/r : r \le M^*(p)\} \cup \{Q_{M^*(p)}/M^*(p)\})$, together with the threshold characterization of non-adaptive algorithms: an algorithm is a list of price thresholds $\theta_i$, buying on day $i$ iff $p_i \le \theta_i$, and Theorems 1–2 identify the exact optimal threshold profiles. The consistency/robustness tradeoff is carried by Algorithm 2, whose two buying days $r_2(\lambda,p)$ and $r_3(\lambda,p)$ are chosen by minimizing $P_t - \lambda\,OPT_t$ over a $\lambda$-dependent interval and then minimizing $P_r/r$ under a ratio constraint, so that $\lambda=1$ recovers the predictionless optimal algorithm and small $\lambda$ approaches the 'buy at the minimum-price day $r_0$' strategy.

What would settle it

Change the settlement rule of Definition 2 so that overpledged amounts are refunded (or capped at the remaining gap), then replay the adversarial gap-price sequences from Theorems 1–2, such as the sequence in which the others' pledges make the agent's price $p_1 = 0$ on day 1 and $p_2 = B$ on day 2; if some deterministic algorithm (for instance, one that pledges $B$ on day 1) then achieves a worst-case competitive ratio strictly below $B+1$, the claimed lower bound and its threshold characterization collapse.

Watch

Extended reading notes

Core claim

The central claim is that, from a single agent's viewpoint, multiagent ski-rental with predictions is fully captured by a single-agent ski-rental problem with a day-dependent buying price $p_i = B - \text{(total pledged by the others on day } i)$, and that the optimal deterministic competitive ratios for the four combinations of perfect/pessimal predictors are exact. With a pessimal others-predictor, the only optimal algorithm in the baseline case is to rent on day 1 and pledge the full amount $B$ on day 2, giving $B+1$-competitiveness (Theorem 1); perfect self-predictions cannot lower this ratio and only widen the set of optimal algorithms (Theorem 2). With a perfect others-predictor and no self-prediction, the optimal ratio against a fixed price sequence $p$ is $c_{OPT}(p) = \min(\{P_r/r : r \le M^*(p)\} \cup \{Q_{M^*(p)}/M^*(p)\})$, where $P_i = i-1+p_i$, $M^*(p)=\min_i P_i$ and $Q_t=\min_{i\ge t}P_i$, achieved by buying on an argmin day (Theorem 3). When both predictors are perfect, blindly following the self-predictor is $1$-competitive but is not $r$-robust for any finite $r$ (Theorem 4); Algorithm 2 interpolates between the regimes and, for every $\lambda\in(0,1]$, guarantees a competitive ratio at most $\lambda-1+\frac{1}{\lambda}c_{OPT}(p)$ while its consistency improves as $\lambda$ decreases (Theorem 6, Lemma 2).

Load-bearing premise

The bounds assume that when the group license is overpledged, every agent still pays its full pledged amount, so money pledged on a day when the others already cover the license price is completely lost.

Editorial extensions

If this is right

When an agent knows nothing about the others, buying a perfect predictor of its own future buys nothing: the competitive ratio stays exactly $B+1$, and the only optimal baseline algorithm is rent-day-1 / pledge-$B$-day-2.
When the others' pledges are perfectly predicted, the best response is a pure function of the gap-price sequence $p$: buy on a day $r \le M^*(p)$ minimizing $P_r/r$, or on the best day at or after $M^*(p)$ with price $Q_{M^*(p)}$, whichever yields the smaller ratio $c_{OPT}(p)$.
A blindly following strategy that is 1-consistent is catastrophically fragile: for every $r>0$ there is an input where its cost is more than $r$ times the optimal cost, so perfect self-predictions are only usable if they never err.
For every $\lambda\in(0,1]$ Algorithm 2 keeps the competitive ratio at or below $\lambda-1+\frac{1}{\lambda}c_{OPT}(p)$ on all inputs and predictions, and its consistency improves as $\lambda$ decreases, becoming optimal for $\lambda < 1/(M^*(p)-r_0+1)$; the guarantee uses the weak (additive-constant) notion of robustness.
The four perfect/pessimal predictor combinations produce four exact competitive ratios that fully classify multiagent ski-rental; only intermediate error regimes for the others-predictor remain unquantified.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same gap-price reduction should transfer to other multiagent problems with a shared public good, so the four-cell perfect/pessimal classification may be a general template for online games with predictions rather than a ski-rental special case.
Theorem 4 has a game-theoretic reading the paper leaves implicit: in a profile where every agent follows the predictor, one agent's self-misprediction makes everyone's cost unboundedly larger than optimum, so predictor-following equilibria are inherently fragile without the robust Algorithm 2 as a safeguard.
Because the paper assumes causal decision theory (Newcomb's problem discussion), the meaning of a 'perfect others-predictor' may change under evidential or superrational decision rules; re-deriving the optimal ratios under those rules is a testable extension.
The paper's random-noise experiments suggest a further testable claim: an intermediate error parameter for the others-predictor (e.g., noise on the gap-price sequence) might admit an average-case analysis even though the worst-case interpolation between Theorem 1 and Algorithm 2 is left open.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The paper is a solid proof-of-concept: it introduces a two-predictor decomposition (self versus others) and gives exact deterministic competitive ratios for a multiagent ski-rental problem under several predictor-quality regimes. The proofs in the appendix are mostly careful, and the reduction to single-agent ski rental with varying prices is clean and reused throughout. If you work on learning-augmented online algorithms, this is worth a look.

The main thing to know before citing it is that the headline result — no algorithm can beat B+1 when the others-predictor is pessimal, even with a perfect self-predictor — depends on the overpledge rule in Definition 2/footnote 3. Under that rule, when the group license is overpledged, every agent pays its full pledge even if the others alone covered B. The lower-bound adversary in Theorem 1 uses exactly this: on a day where the others' pledges already sum to B, the agent's positive threshold pledge is wasted, so paying it is pure loss. If you instead settled overpledges by capping each agent's payment at the residual B − S_others, a positive pledge on such a day costs nothing, and the infinite-ratio argument collapses. For B=2, the strategy θ1=1, θ2=B has worst-case ratio 3/2 under capped settlement, not 3. The paper does not flag this sensitivity. The model is explicit, so it's not an error, but it is a convention that carries a lot of weight; a referee should ask whether it's the right convention for the intended application.

There is also a small typo in the proof of Theorem 1 (A.2): the adversarial sequence is written with p_r=0, but then the algorithm is said to spend r−1+B. For that cost you need p_r=B. Minor, but it should be fixed.

The novelty claim in the introduction is slightly overstated: 'conspicuously absent... multi-agent settings' ignores the learning-augmented mechanism design papers cited a few lines later (e.g., ABG+22). The two-predictor framework is new, but the field is not empty.

Experiments: no code shipped, no error bars. Fine for a theory paper, but the promise of an external link should be honored.

Overall: a serious, citable paper for the learning-augmented community, with one load-bearing modeling assumption that deserves scrutiny. I would send it to review, not desk-reject.

Referee Report

3 major / 4 minor

Summary. The paper introduces a two-predictor framework for online games and applies it to a multiagent version of ski rental, in which agents can pool pledges to buy a group license. The main results are exact competitive-ratio characterizations for combinations of perfect and pessimal self- and other-predictors: pessimal other-predictions yield an optimal ratio of B+1 even with a perfect self-predictor (Theorems 1 and 2); perfect other-predictions yield an input-dependent optimal ratio c_OPT(p) when the self-predictor is pessimal (Theorem 3), and a trivially consistent but non-robust algorithm when both predictors are perfect (Theorems 4 and Algorithm 1). The paper also proposes Algorithm 2 as a consistency--robustness tradeoff and evaluates it experimentally.

Significance. If the main bounds are correct, the paper gives one of the first exact analyses of online problems with predictions in a genuinely multiagent setting, and the two-predictor taxonomy is a useful organizing device. The explicit formulas in Theorem 3 and the interpolation algorithm are concrete contributions, and the appendixed proofs make the results checkable. The significance is tempered by the fact that the headline B+1 bounds depend on a specific and somewhat unusual settlement rule for overpledged group licenses, and by the presence of local but load-bearing formal gaps in the proof and statement of Theorem 2.

major comments (3)

[A.2 and Definition 3] The lower-bound proof of Theorem 1 is not consistent with Definition 3 as written. In Definition 3, p_i is the cost of buying on day i, so a sequence with p_r=0 would make the algorithm pay r-1, not r-1+B, when it buys on day r. The proof only obtains the claimed r-1+B cost because 'buying' in the multiagent model means making a standing pledge under the footnote 3 full-pledge settlement rule. This reduced problem should be defined explicitly as a threshold-pledge problem with cost equal to the pledge when the threshold condition is met; otherwise the lower-bound argument in A.2 is formally unsupported. The distinction is load-bearing because Theorem 1 and the first two rows of Table 1 rest on it.
[Definition 2 and footnote 3] The paper's central pessimal-others results are contingent on the rule that overpledged agents pay their full pledged amounts. Under the alternative settlement rule in which an agent's payment is capped at the residual needed to reach B (or refunded proportionally), the p_1=0 construction used to force theta_1=0 collapses, and the B+1 lower bounds need not hold; for B=2 an algorithm with theta_1=1, theta_2=B can have worst-case ratio 3/2 under capped settlement rather than 3 under the paper's rule. This is not an internal inconsistency, because footnote 3 states the rule clearly, but it is a substantive modeling choice that determines the headline result. The Limitations section should acknowledge this sensitivity and explain why the full-pledge settlement is the intended model.
[Theorem 2 and A.3] The characterization of optimal algorithms in Theorem 2 appears to be stated too restrictively, and the proof in A.3 contains a corresponding error. In Claim 1, the claimed competitive ratio max(Theta_2,...,Theta_bT,bT) omits the rental costs accumulated before the buying day; the correct quantity is max_{2<=j<=bT}(j-1+Theta_j, bT). With the corrected expression, the condition for ratio bT is Theta_j <= bT-j+1, not Theta_j <= bT-j as stated in the theorem. For example, for bT=2 and B>=2, the algorithm with theta_1=0 and theta_2=1 is also 2-competitive in the paper's model, even though the theorem states that only theta_2=0 works. The optimal ratio bT is not affected, but the 'only' claim and the algorithm description in Table 1 need correction.

minor comments (4)

[Section 7] The text states that experiments use z=0, z=0.5, and z=0.1, while the Figure 1 captions report z=0, z=0.5, and z=1; these should be aligned.
[A.9] The proof of Lemma 2(a) refers to displayed equations labeled (10) and (11), but no such numbered equations appear in the appendix; the labels should be added or the references removed.
[Theorem 6] The expression 'lambda-1 + 1/lambda c_OPT(p)' is ambiguous in the main text; it should be parenthesized as (lambda-1) + (1/lambda)c_OPT(p) to match the proof.
[Abstract and Section 1] There are several typos in the abstract and introduction, including 'atwo predictor framework' and 'amultiagent version'; these should be corrected before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the competitive-ratio bounds are derived from the stated model via standard adversarial analysis, and the only self-citations are non-load-bearing related-work and discussion references.

full rationale

The derivation chain is self-contained. Definitions 2 and 3 fix the multiagent ski-rental payoffs and the single-agent varying-price problem; Theorems 1-3 are proved by explicit adversary constructions (e.g., the p_1=0 and p_r=0 sequences in A.2) and by comparing algorithms A_r through the ratio P_r/OPT_r (Lemma 4, A.4). No constant is fitted to any dataset and then relabeled as a prediction: the self-predictor and others-predictor are inputs to the problem, and the competitive ratios in Table 1 are worst-case quantifications over those inputs. The dependency of the B+1 bound on footnote 3's convention that overpledged agents pay their full pledged sums is a stated modeling assumption, not a hidden identification of an output with an input; changing the settlement rule would change the payoff model, which is a correctness or modeling concern, not circularity. The 1-consistency of Algorithm 1 is transparent: its decision rule is exactly the offline optimality condition when bT=T, and the paper does not present this trivial direction as an independent derivation. Algorithm 2's tradeoff is analyzed via Theorems 5-6 and benchmarked experimentally with no fitted parameters. The self-citations ([IB22], [Ist21]) appear only in related-work and discussion contexts and are not used as premises; no uniqueness theorem is imported from the authors' prior work. The paper's Section 8 and A.8 openly state limitations (no intermediate error regime for the others' predictor; weaker, non-strong robustness than [KPS18]), which supports rather than undermines the non-circularity verdict.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claims rest on the cost model of overpledged sums, the deterministic nonadaptive algorithm class, and the perfect-others assumption reducing the problem to known varying prices. No new physical or algorithmic entity is postulated beyond the problem definition; lambda is a free design parameter, not a fitted constant.

free parameters (1)

lambda = lambda in (0,1]
Design parameter in Algorithm 2 that interpolates between the no-predictions strategy (lambda=1) and the predictor-following strategy (lambda near 0). It is not fitted to data, but the robustness and consistency bounds in Theorem 6 depend on it.

assumptions (5)

domain assumption When the group license is overpledged, agents pay their full pledged amounts, not just the residual needed.
Definition 2 and footnote 3. Drives the B+1 lower bound: an agent can be forced to waste a large pledge on a day when the license would be free.
domain assumption Algorithms are deterministic, nonadaptive, and do not observe the total amounts pledged by other agents.
Section 2.1 and Definition 2. Restricts the strategy space and is essential for the threshold-based characterizations in Theorems 1-3.
domain assumption With a perfect others' predictor, the agent knows the residual price p_i = B - total pledged by others on each day, reducing the problem to ski-rental with known varying prices.
Section 4 and Definition 3. This is the bridge from multiagent to single-agent analysis.
domain assumption The self-predictor is monotonically decreasing: once a player is predicted to stop, it is predicted to stop forever.
Section 2.1, used throughout the model and in the analysis of active times.
standard math Standard definitions of competitive ratio, robustness, and consistency apply.
Section 2, Definitions 1 and 2, based on classical competitive analysis as in BEY05 and KPS18.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On multiagent online problems with predictions." pith.science (2026). https://pith.science/paper/FZQIS5W6

@misc{pith2026250712486,
  author       = {Pith},
  title        = {Pith review of: On multiagent online problems with predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FZQIS5W6}},
  note         = {Machine review of arXiv:2507.12486}
}

read the original abstract

We study the power of (competitive) algorithms with predictions in a multiagent setting. We introduce a two predictor framework, that assumes that agents use one predictor for their future (self) behavior, and one for the behavior of the other players. The main problem we are concerned with is understanding what are the best competitive ratios that can be achieved by employing such predictors, under various assumptions on predictor quality. As an illustration of our framework, we introduce and analyze a multiagent version of the ski-rental problem. In this problem agents can collaborate by pooling resources to get a group license for some asset. If the license price is not met then agents have to rent the asset individually for the day at a unit price. Otherwise the license becomes available forever to everyone at no extra cost. In the particular case of perfect other predictions the algorithm that follows the self predictor is optimal but not robust to mispredictions of agent's future behavior; we give an algorithm with better robustness properties and benchmark it.

Figures

Figures reproduced from arXiv: 2507.12486 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 38 canonical work pages

[1]

Learning-augmented mechanism design: Leveraging predictions for facility location

Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning-augmented mechanism design: Leveraging predictions for facility location. Proceedings of EC'22 , pages 497--528, 2022

work page 2022
[2]

Online computation with untrusted advice

Spyros Angelopoulos, Christoph D \"u rr, Shendan Jin, Shahin Kamali, and Marc Renault. Online computation with untrusted advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2020

work page 2020
[3]

Learning-Augmented Private Algorithms for Multiple Quantile Release

Kareem Amin, Travis Dick, Mikhail Khodak, and Sergei Vassilvitskii. Private algorithms with private predictions. arXiv preprint arXiv:2210.11222 , 2022

work page Pith review arXiv 2022
[4]

Online algorithms with multiple predictions

Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning , volume 162 of Proceedings of Machine Learning Research , pages 582--598. PMLR...

work page 2022
[5]

Customizing ML predictions for online algorithms

Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In International Conference on Machine Learning , pages 303--313. PMLR, 2020

work page 2020
[6]

Evidential decision theory

Arif Ahmed. Evidential decision theory . Cambridge University Press, 2021

work page 2021
[7]

Improving online rent-or-buy algorithms with sequential decision making and ML predictions

Soumya Banerjee. Improving online rent-or-buy algorithms with sequential decision making and ML predictions. Advances in Neural Information Processing Systems , 33:21072--21080, 2020

work page 2020
[8]

Complexity classes for online problems with and without predictions

Magnus Berg, Joan Boyar, Lene M Favrholdt, and Kim S Larsen. Complexity classes for online problems with and without predictions. arXiv preprint arXiv:2406.18265 , 2024

work page arXiv 2024

Show all 43 references

[9]

Online computation and competitive analysis

Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis . Cambridge University Press, 2005

2005
[10]

Online mechanism design with predictions

Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, and Cherlin Zhu. Online mechanism design with predictions. Technical report, arXiv.org/cs.GT/2310.02879, 2023

2023 arXiv
[11]

Canonne, Kenny Chen, and Julián Mestre

Clément L. Canonne, Kenny Chen, and Julián Mestre. With a little help from my friends: Exploiting probability distribution advice in algorithm design. Technical Report 2505.04949, arXiv.org, 2025

2025 arXiv
[12]

Triangle and four cycle counting with predictions in graph streams

Justin Y Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In International Conference on Learning Representations , 2022

2022
[13]

Randomized learning-augmented auctions with revenue guarantees

Ioannis Caragiannis and Georgios Kalantzis. Randomized learning-augmented auctions with revenue guarantees. arXiv preprint arXiv:2401.13384 , 2024

2024 arXiv
[14]

Paradoxes of rationality and cooperation: Prisoner's dilemma and Newcomb's problem

Richmond Campbell and Lanning Sowden. Paradoxes of rationality and cooperation: Prisoner's dilemma and Newcomb's problem . U.B.C. Press, 1985

1985
[15]

Marsili D

M. Marsili D. Challet and Y-C. Zhang. Minority Games: Interacting Agents in Financial Markets . Oxford University Press, 2004

2004
[16]

Algorithms with prediction portfolios

Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems , 2022

2022
[17]

Learning online algorithms with distributional advice

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning , volume 139 of Proceedi...

2021
[18]

Online algorithms with costly predictions

Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , volume 206 of P...

2023
[19]

Equilibria in online games

Roee Engelberg and Joseph Seffi Naor. Equilibria in online games. SIAM Journal on Computing , 45(2):232--267, 2016

2016
[20]

Perfect prediction in normal form: Superrational thinking extended to non-symmetric games

Ghislain Fourny. Perfect prediction in normal form: Superrational thinking extended to non-symmetric games. Journal of Mathematical Psychology , 96:102332, 2020

2020
[21]

Learned data structures

Paolo Ferragina and Giorgio Vinciguerra. Learned data structures. In Recent Trends in Learning From Data , pages 5--41. Springer, 2020

2020
[22]

Improved price of anarchy via predictions

Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In Proceedings of EC'22 , pages 529--557, 2022

2022
[23]

Online algorithms for rent-or-buy with expert advice

Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning , pages 2319--2327. PMLR, 2019

2019
[24]

Mechanism design with predictions for obnoxious facility location

Gabriel Istrate and Cosmin Bonchi s . Mechanism design with predictions for obnoxious facility location. arXiv preprint arXiv:2212.09521 , 2022

2022 arXiv
[25]

Game-theoretic models of moral and other-regarding agents

Gabriel Istrate. Game-theoretic models of moral and other-regarding agents. Proceedings of the Eighteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK'2021), Electronic Proceedings in Theoretical Computer Science 335 , pages 213--228, 2021

2021
[26]

Financial market complexity

Neil F Johnson, Paul Jefferies, and Pak Ming Hui. Financial market complexity . Oxford University Press, 2003

2003
[27]

Woodruff

Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. Learning-augmented data stream algorithms. In International Conference on Learning Representations , 2020

2020
[28]

Rational learning leads to N ash equilibrium

Ehud Kalai and Ehud Lehrer. Rational learning leads to N ash equilibrium. Econometrica: Journal of the Econometric Society , pages 1019--1045, 1993

1993
[29]

Improving online algorithms via ML predictions

Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ML predictions. Advances in Neural Information Processing Systems , 31, 2018

2018
[30]

Learning augmented binary search trees

Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning , volume 162 of Proc...

2022
[31]

Algorithms with predictions webpage, 2022

Alexander Lindermayr and Nicole Megow. Algorithms with predictions webpage, 2022. accessed January 2025

2022
[32]

A model for learned B loom filters and optimizing by sandwiching

Michael Mitzenmacher. A model for learned B loom filters and optimizing by sandwiching. Advances in Neural Information Processing Systems , 31, 2018

2018
[33]

Sitaraman, and Zhenhua Liu

Jessica Maghakian, Russell Lee, Mohammad Hajiesmaili, Jian Li, Ramesh K. Sitaraman, and Zhenhua Liu. Applied online algorithms with heterogeneous predictors. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Int...

2023
[34]

Mitzenmacher and S

M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Chapter 29 in T. Roughgarden (Ed.). Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021

2021
[35]

Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J. Ratliff. Multiplayer performative prediction: Learning in decision-dependent games. Journal of Machine Learning Research , 24(202):1--56, 2023

2023
[36]

How We Cooperate: A Theory of Kantian Optimization

John E Roemer. How We Cooperate: A Theory of Kantian Optimization . Yale University Press, 2019

2019
[37]

Online algorithms with uncertainty-quantified predictions

Bo Sun, Jerry Huang, Nicolas Christianson, Mohammad Hajiesmaili, and Adam Wierman. Online algorithms with uncertainty-quantified predictions. arXiv preprint arXiv:2310.11558 , 2023

2023 arXiv
[38]

Algorithms with calibrated machine learning predictions

Judy Hanwen Shen, Ellen Vitercik, and Anders Wikum. Algorithms with calibrated machine learning predictions. Technical Report 2502.02861, arXiv.org, 2025

2025
[39]

Causal decision theory

Paul Weirich. Causal decision theory. Cambridge University Press , 2008

2008
[40]

Optimal robustness-consistency trade-offs for learning-augmented online algorithms

Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Advances in Neural Information Processing Systems , 33:8042--8053, 2020

2020
[41]

Satzilla: portfolio-based algorithm selection for SAT

Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Satzilla: portfolio-based algorithm selection for SAT . Journal of Artificial Intelligence Research , 32:565--606, 2008

2008
[42]

Mechanism design with predictions

Chenyang Xu and Pinyan Lu. Mechanism design with predictions. Proceedings of IJCAI'22 , pages 571--577, 2022

2022
[43]

Strategic learning and its limits

H Peyton Young. Strategic learning and its limits . Oxford University Press, 2004

2004

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Learning-augmented mechanism design: Leveraging predictions for facility location

Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning-augmented mechanism design: Leveraging predictions for facility location. Proceedings of EC'22 , pages 497--528, 2022

work page 2022

[2] [2]

Online computation with untrusted advice

Spyros Angelopoulos, Christoph D \"u rr, Shendan Jin, Shahin Kamali, and Marc Renault. Online computation with untrusted advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2020

work page 2020

[3] [3]

Learning-Augmented Private Algorithms for Multiple Quantile Release

Kareem Amin, Travis Dick, Mikhail Khodak, and Sergei Vassilvitskii. Private algorithms with private predictions. arXiv preprint arXiv:2210.11222 , 2022

work page Pith review arXiv 2022

[4] [4]

Online algorithms with multiple predictions

Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning , volume 162 of Proceedings of Machine Learning Research , pages 582--598. PMLR...

work page 2022

[5] [5]

Customizing ML predictions for online algorithms

Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In International Conference on Machine Learning , pages 303--313. PMLR, 2020

work page 2020

[6] [6]

Evidential decision theory

Arif Ahmed. Evidential decision theory . Cambridge University Press, 2021

work page 2021

[7] [7]

Improving online rent-or-buy algorithms with sequential decision making and ML predictions

Soumya Banerjee. Improving online rent-or-buy algorithms with sequential decision making and ML predictions. Advances in Neural Information Processing Systems , 33:21072--21080, 2020

work page 2020

[8] [8]

Complexity classes for online problems with and without predictions

Magnus Berg, Joan Boyar, Lene M Favrholdt, and Kim S Larsen. Complexity classes for online problems with and without predictions. arXiv preprint arXiv:2406.18265 , 2024

work page arXiv 2024