Research map / Multi-agent systems and games / Games and equilibria
Online Information Acquisition: Hiring Multiple Agents
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies a principal hiring multiple agents to acquire costly information via scoring rules and action recommendations, giving a polynomial-time LP for optimal correlated mechanisms and a no-regret online algorithm with Õ(T^{2/3}) regret.
Problem
Mechanism design for a principal who hires multiple agents to take costly actions that generate private signals about an unknown state, when the game parameters are unknown and must be learned online.
Approach
Formulates optimal correlated scoring-rule mechanisms for multi-agent information acquisition as a linear program solvable in polynomial time, then learns the unknown parameters online via exploration (probability, posterior and cost-difference estimation with binary search over scoring rules) and commits to a modified mechanism that is strictly IC under uncertainty by convex combination with ad-h
Key results
- Polynomial-time LP computes an optimal correlated mechanism for multi-agent information acquisition.
- No-regret online algorithm with Õ(T^{2/3}) regret w.r.t. an optimal mechanism, matching single-agent state of the art.
- Uncorrelated mechanisms can be suboptimal in general, but are optimal under conditionally independent signals.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the online learning algorithm with probability and cost estimation followed by an incentive-compatible commit phase | Multi-agent information acquisition with unknown game parameters · Online multi-agent information acquisition | regret: \widetilde{\mathcal{O}}(T^{2/3}) | Helped |
Surprising findings
- Optimal mechanisms must correlate agents' efforts, creating externalities and equilibrium selection issues.
- There exists a game in which no uncorrelated mechanism is optimal.
Limitations
- Number of agents assumed constant; exponential dependence on instance size otherwise.
- Regret bound depends on instance parameters (minimum posterior distance and minimum signal probability) through a term κ.
- Requires assumption of known scoring rules satisfying strict incentive properties.
Experimental setup
Metrics: cumulative regret
Baselines: single-agent online information acquisition algorithm
Builds on: scoring rules for information acquisition single-agent online information acquisition (Õ(T^{2/3}))
Closest papers by meaning
- Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition (ICML 2025 · similarity 0.88)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.87)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.86)
- Contracting with a Learning Agent (NeurIPS 2024 · similarity 0.86)
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.86)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.