CS Paper Radar

Incentive Design for Multi-Agent Systems: A Bilevel Optimization Framework for Coordinating Independent Agents and Convergence Analysis

Xinyi Wei, Shuo Han, Jie Fu

eess.SY ·submitted 2026-09-22 17:13 UTC · v1

Abstract

Incentive design aims to guide the performance of a system towards a human's intention or preference. We study this problem in a multi-agent system with one leader and multiple followers. Each follower independently solves a mdp to maximize its own expected total return with the same state space and action space. However, the leader's objective depends on the collective best-response policies of all followers. To influence these policies of followers, the leader provides side payments as incentives to individual followers at a cost, aiming to align the collective behaviors of followers with its own goal while minimizing this cost of incentive. Such a leader-followers interaction is formulated as a bilevel optimization problem: the lower level consists of followers individually optimizing their MDPs given the side payments, and the upper level involves the leader optimizing its objective function given the followers' best responses. The main challenge to solve the incentive design is that the leader's objective is generally non-concave and the lower level optimization problems can have multiple local optima. To this end, we employ a constrained optimization reformation of this bi-level optimization problem and develop an algorithm that provably converges to a stationary point of the original problem, by leveraging several smoothness properties of value functions in MDPs. We validate our algorithm in a stochastic gridworld by examining its convergence, verifying that the constraints are satisfied, and evaluating the improvement in the leader's performance.

Closest papers

Nearest neighbours by meaning across the whole index.

Forging Self-Funded Marketplaces among Strategic Agents

cs.GT ·2026-08-14 ·Yuan Deng, Vasilis Gkatzelis, Xizhi Tan, Grigoris Velegkas, Song Zuo
publishedbenchmark similarity 0.63
Abstract · Extended Abstract accepted 27th ACM Conference on Economics and Computation (ACM EC 2026)

We introduce the problem of designing mechanisms that incentivize strategic agents to form self-funded marketplaces. In our model, if agent $i$ exerts effort $x_i\in [0,1]$, they incur a cost of $x_i\cdot c_i$ (where $c_i$ is unknown to the mechanism designer) and they generate revenue $x_i\cdot r_i$; crucially, $c_i$ can be greater or smaller than $r_i$. Each effort profile $\mathbf{x}$ yields value $v(\mathbf{x})$ and the objective is to choose an effort vector that maximizes the value while ensuring that every agent $i$ receives a payment $p_i\geq x_i\cdot c_i$ and that $\mathbf{x}$ is budget-balanced, i.e., $\sum_{i} p_i \leq \sum_{i} x_i\cdot r_i$. This problem generalizes the well-studied budget-feasible mechanism design problem, where the requirement is that $\sum_{i} p_i \leq B$ for some predetermined budget $B$. To evaluate the performance of such mechanisms, we first consider the first-best benchmark (the optimal value achievable in the absence of any private information) and show that no truthful auction can achieve a bounded approximation of this benchmark. Also, even in restricted settings, no auction can achieve better than a logarithmic approximation. We complement these results by proposing a class of sequential auctions whose subgame perfect equilibria guarantee a logarithmic approximation of this benchmark. We then introduce an alternative benchmark, the maximin share (MMS), that better captures the thickness of the market and we provide an auction whose subgame perfect equilibria achieve a constant approximation of this benchmark.

0.20

Incentive Mechanisms for Welfare Maximization Under Individual Rationality in Noncooperative Dynamical Systems

eess.SY ·2026-10-22 ·Yuyue Yan, Maojiao Ye, Hideaki Ishii, Tomohisa Hayakawa
similarity 0.62
Abstract · 16 pages, 10 figures

Human societies are shaped by strategic interactions among self-interested decision-makers, where conflicts between individual and social interests naturally arise. This paper investigates the design of incentive mechanism for multi-agent game systems to reconcile social welfare maximization with individual benefits under economic constraints. We develop a linear-quadratic incentive framework to reshape Nash equilibria while reconciling the constraints of Pareto efficiency, individual rationality, and budget balance. The optimal target state is identified as the solution of a constrained optimization problem associated with the social welfare and aggregated payoff functions. Our theoretical analysis characterizes the conditions of incentive functions that steer self-interested agents towards the optimal target state as a Pareto-efficient Nash equilibrium for achieving the maximum attainable social welfare. We further characterize how the choice of social welfare function constrains achievable individual outcomes, revealing a structural paradox associated with priority weighting under individual rationality. Several numerical examples are presented to demonstrate the efficacy of our results.

0.17

Welfare in Envy-free Contracts: When Agents Have Sparse Interests

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.62
Abstract

We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

0.11

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

cs.GT ·2026-10-22 ·Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
benchmark similarity 0.61
Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

0.31

Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

cs.LG cs.MA ·2026-11-02 ·Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Wierman
similarity 0.60
Abstract

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

0.18

Single-level reformulations for network pricing under Wardrop equilibrium with separable affine costs

cs.GT math.OC ·2026-10-19 ·Miguel F. Anjos, José Neto
benchmarktheory similarity 0.60
Abstract

We consider the problem of setting tolls on a subset of the arcs of a congested network so as to maximize the revenue of a network authority, anticipating that users route according to a Wardrop equilibrium. This problem is naturally cast as a bilevel program in which the leader sets tolls while the followers respond by choosing an equilibrium routing. We focus on the important special case of separable affine arc cost functions. Under this assumption, Wardrop equilibria admit Beckmann's convex characterization, from which we derive three new single-level reformulations of the bilevel problem, exploiting both Beckmann's formulation and its dual: an arc-based formulation, which we solve exactly, and two path-based formulations, solved by column-and-constraint generation. Beyond the reformulations, we further derive from Beckmann's potential an upper bound on the optimal revenue that can be used to certify optimality gaps across all formulations. An extensive computational study on instances derived from the Sioux Falls and Eastern Massachusetts networks compares our formulations with the recent mixed-integer nonlinear formulation of Beck, Labbé and Schmidt. The arc-based formulation solves substantially more instances to proven optimality (within a time limit of 1800 s) than this formulation and, unlike it, returns a feasible solution on every instance. It remains effective on the largest, 74-node network, on which the formulation of Beck et al. solves none. The magnitude of the upper bounds on the tolls proves to be a major driver of tractability: the genuinely hard core of the benchmark emerges once the regulatory cap on tolls is removed. The two path-based formulations, used as heuristics, return a solution within one percent of the optimum on every instance whose optimal value is known, often in seconds where exact formulations reach the time limit.

0.24

Scaling Chance-Constrained Correlated Equilibrium Computation for Exclusive Resource-Assignment Games

cs.GT ·2026-09-11 ·Jaehan Im, Ufuk Topcu, David Fridovich-Keil
similarity 0.60
Abstract

The chance-constrained correlated equilibrium concept provides a robust coordination technique for self-interested agents whose costs are uncertain to a central coordinator, but the number of joint actions considered in its computation grows exponentially with the number of agents. We propose an exact-one resource-assignment restriction for games in which agents compete for shared resources and simultaneous use of a resource is undesirable or unsafe. The restriction allows each resource to be assigned to exactly one agent, reducing the number of joint actions considered from O(2^(nr)) to O(n^r) for n agents and r resources. The resulting problem is solved over the restricted joint action set while retaining all incentive constraints associated with unilateral deviations. We show that the feasible set of the restricted problem is exactly the convex hull of the chance-constrained pure Nash equilibria contained in the exact-one assignment set, yielding a necessary and sufficient condition for nonemptiness. We further derive a sufficient condition under which all chance-constrained pure Nash equilibria of the unrestricted game are retained by the restriction. Numerical experiments in a vertiport departure-corridor coordination scenario demonstrate a 99.81% reduction in median computation time relative to the unrestricted formulation while achieving equivalent coordination performance.

0.31

Adaptive Incentive Design for Linear-Quadratic Dynamic Games: No-Regret Social Coordination

eess.SY ·2026-10-09 ·Lantian Zhang, Yibei Li, Georgios Vasileiou, Lihua Xie, Silun Zhang
theoryhot direction similarity 0.59
Abstract · 16 pages

Incentives can align private interests with collective goals, but their design becomes intertwined with learning when agents' preferences are unknown. This paper develops an adaptive incentive-design framework for multi-agent linear-quadratic dynamic games, where a system planner can simultaneously learn agents' private preferences and steer their strategic behavior towards the social optimum. To this end, we first characterize the complete family of affine incentives that implement the social optimum as the unique open-loop Nash equilibrium while ensuring exact budget balance. When agents' preferences are unknown, we develop an online algorithm to estimate their preference parameters and establish strong consistency of the estimates under a weak trajectory-dependent excitation condition, without requiring persistent excitation or i.i.d. trajectories. We then integrate this estimator into an active-learning incentive mechanism that combines certainty-equivalent coordination with decaying random probing. We prove that the probing generates sufficient information through the agents' equilibrium responses and the system dynamics, ensuring consistent preference learning from the resulting closed-loop trajectories. We show that the induced trajectories converge almost surely to their socially optimal counterparts, while cumulative social-cost regret relative to the full-information oracle and cumulative net-budget imbalance grow sublinearly. Simulations of a transboundary pollution game demonstrate the effectiveness of the proposed framework.

0.32