Advances in Multi-Agent Contracts and Allocation Problems

The field of multi-agent systems is witnessing significant developments in the design of contracts and allocation problems. Recent research focuses on extending the analysis of multi-agent contracts beyond pure Nash equilibria to encompass more general equilibrium notions, such as mixed Nash equilibria and correlated equilibria. This shift is driven by the recognition that pure Nash equilibria may not capture the full range of possible outcomes in multi-agent interactions. Furthermore, researchers are exploring new approaches to allocation problems, including the use of cycle-canceling algorithms for submodular valuations and the study of tatonnement dynamics in markets with chores. These advances have important implications for the design of efficient allocation mechanisms and the analysis of strategic behavior in multi-agent systems. Noteworthy papers in this area include: One Action Too Many, which establishes strong impossibility results for combinatorial contracts with budget constraints; Utilitarian Guarantees for the Method of Equal Shares, which derives minimum utilitarian welfare guarantees for a prominent Participatory Budgeting rule; and Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs, which unifies two foundational constructs from economics and algorithmic game theory to address the efficient allocation of differentiated goods in complex markets.

Sources

Black-Box Lifting and Robustness Theorems for Multi-Agent Contracts

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Utilitarian Guarantees for the Method of Equal Shares

Cycle Cancellation for Submodular Fractional Allocations and Applications

T\^atonnement Dynamics for Fisher Markets with Chores

Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures

Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs

Built with on top of