On multiagent online problems with predictions

• URL: http://arxiv.org/abs/2507.12486v1
• Date: Tue, 15 Jul 2025 08:52:12 GMT
• Title: On multiagent online problems with predictions
• Authors: Gabriel Istrate, Cosmin Bonchis, Victor Bogdan,
• Abstract summary: We study the power of (competitive) algorithms with predictions in a multiagent setting.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Competitive Algorithms for Cooperative Multi-Agent Ski-Rental Problems [35.95355517827071]
  This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting.<n>In our model, each agent can either rent at a fixed daily cost, or purchase a pass at an individual cost, with an additional third option of a discounted group pass available to all.<n>We consider scenarios in which agents' active days differ, leading to dynamic states as agents drop out of the decision process.
  arXiv  Detail & Related papers  (2025-07-21T15:36:34Z)
• Performative Prediction on Games and Mechanism Design [69.7933059664256]
  We study a collective risk dilemma where agents decide whether to trust predictions based on past accuracy.<n>As predictions shape collective outcomes, social welfare arises naturally as a metric of concern.<n>We show how to achieve better trade-offs and use them for mechanism design.
  arXiv  Detail & Related papers  (2024-08-09T16:03:44Z)
• Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
  Online decision-makers often obtain predictions on future variables, such as arrivals, demands, and so on. Prediction accuracy is unknown to decision-makers a priori, hence blindly following the predictions can be harmful. We develop algorithms that utilize predictions in a manner that is robust to the unknown prediction accuracy.
  arXiv  Detail & Related papers  (2024-02-21T04:57:32Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL) This paper first refines the AVLPR framework by Wang et al. (2023), with an insight of designing pessimistic estimation of the sub-optimality gap. We give the first algorithm that tackles the curse of multi-agents, attains the optimal $O(T-1/2) convergence rate, and avoids $textpoly(A_max)$ dependency simultaneously.
  arXiv  Detail & Related papers  (2024-02-11T01:51:15Z)
• CAMMARL: Conformal Action Modeling in Multi Agent Reinforcement Learning [5.865719902445064]
  We propose a novel multi-agent reinforcement learning algorithm CAMMARL. It involves modeling the actions of other agents in different situations in the form of confident sets. We show that CAMMARL elevates the capabilities of an autonomous agent in MARL by modeling conformal prediction sets.
  arXiv  Detail & Related papers  (2023-06-19T19:03:53Z)
• QCNeXt: A Next-Generation Framework For Joint Multi-Agent Trajectory Prediction [5.312631388611489]
  Estimating the joint distribution of on-road agents' future trajectories is essential for autonomous driving. We propose a next-generation framework for joint multi-agent trajectory prediction called QCNeXt. Our approach ranks 1st on the Argoverse 2 multi-agent motion forecasting benchmark.
  arXiv  Detail & Related papers  (2023-06-18T09:40:40Z)
• Mixing predictions for online metric algorithms [34.849039387367455]
  We design algorithms that combine predictions and are competitive against such dynamic combinations. Our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the $k$-server problem.
  arXiv  Detail & Related papers  (2023-04-04T13:18:00Z)
• Bandit Social Learning: Exploration under Myopic Behavior [54.767961587919075]
  We study social learning dynamics motivated by reviews on online platforms.<n>Agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration.<n>We derive stark learning failures for any such behavior, and provide matching positive results.
  arXiv  Detail & Related papers  (2023-02-15T01:57:57Z)
• Collaborative Uncertainty Benefits Multi-Agent Multi-Modal Trajectory Forecasting [61.02295959343446]
  This work first proposes a novel concept, collaborative uncertainty (CU), which models the uncertainty resulting from interaction modules.<n>We build a general CU-aware regression framework with an original permutation-equivariant uncertainty estimator to do both tasks of regression and uncertainty estimation.<n>We apply the proposed framework to current SOTA multi-agent trajectory forecasting systems as a plugin module.
  arXiv  Detail & Related papers  (2022-07-11T21:17:41Z)
• What Should I Know? Using Meta-gradient Descent for Predictive Feature Discovery in a Single Stream of Experience [63.75363908696257]
  computational reinforcement learning seeks to construct an agent's perception of the world through predictions of future sensations. An open challenge in this line of work is determining from the infinitely many predictions that the agent could possibly make which predictions might best support decision-making. We introduce a meta-gradient descent process by which an agent learns what predictions to make, 2) the estimates for its chosen predictions, and 3) how to use those estimates to generate policies that maximize future reward.
  arXiv  Detail & Related papers  (2022-06-13T21:31:06Z)
• Test-time Collective Prediction [73.74982509510961]
  Multiple parties in machine learning want to jointly make predictions on future test points. Agents wish to benefit from the collective expertise of the full set of agents, but may not be willing to release their data or model parameters. We explore a decentralized mechanism to make collective predictions at test time, leveraging each agent's pre-trained model.
  arXiv  Detail & Related papers  (2021-06-22T18:29:58Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.