Multi-Agent Coordination and Allocation Under Externalities

45 concepts38 papers2 proposals

In classical multi-agent systems, economic models, and game theory, we often rely on a convenient simplifying assumption: independence of payoffs. In an auction, your utility depends entirely on the item you win. In a team-formation scenario, a group's productivity depends solely on its internal members. In a resource allocation problem, your satisfaction is determined entirely by your own bundle.

While mathematically elegant, this assumption falls apart in the real world. When a factory pollutes, it creates negative side effects for everyone nearby (Vincent Conitzer et al., Expressive Negotiation in Settings with Externalities). When a wireless device transmits data, its signal generates cross-tier interference that degrades the performance of neighboring networks (Francesco Pantisano et al., Spectrum Leasing as an Incentive Towards Uplink Macrocell and Femtocell Cooperation).

These interconnected effects are known as externalities. When externalities are present, an agent's utility is inherently bound to the global state of the system. Over the last few decades, researchers have worked to redesign fundamental game-theoretic frameworks—such as coalition formation, information disclosure, and fair division—to account for these complex, real-world interdependencies.

From Characteristic Functions to Partition Functions

In cooperative game theory, the central challenge is determining how autonomous agents should organize into disjoint teams, a problem known as Coalition Structure Generation (CSG). Traditional models assume a characteristic function form, where a coalition's value is fixed regardless of how the remaining agents group themselves.

As Tuomas Sandholm et al. observed in their foundational work, this assumption completely fails when groups compete or interact (Coalition Structure Generation with Worst Case Guarantees). To capture these real-world dynamics, researchers turn to Partition Function Games (PFGs). In a PFG, the value of a coalition is determined by the entire partition of the system (Oskar Skibski et al., A Graphical Representation for Games in Partition Function Form). For example, in smart grids, the financial value of a consumer energy collective depends heavily on how all other market competitors choose to aggregate (Tiago Pinto et al., Consumer Flexibility Aggregation Using Partition Function Games With Non-Transferable Utility).

Accounting for these externalities introduces an "exponential wall" of computational complexity. Instead of merely evaluating $2^n$ subsets of agents, algorithms must navigate the vastly larger space of all possible partitions. To make this tractable, researchers look for structural shortcuts:

Even when an optimal structure is found, distributing the rewards fairly remains a bottleneck. Oskar Skibski demonstrated that computing the classic Shapley value—the gold standard for fair payoff distribution—becomes #P-complete when inter-group externalities are introduced (Complexity of Computing the Shapley Value in Games with Externalities).

Strategic Information Disclosure and Persuasion

Externalities also fundamentally reshape how information flows through strategic environments. In Bayesian persuasion, a well-informed "sender" attempts to influence the choices of "receivers" by selectively disclosing information.

When receivers' payoffs are independent, the sender can optimize their signaling strategy relatively easily. However, in competitive environments like financial markets, traffic routing, or spectrum allocation, a receiver's payoff is heavily influenced by what other receivers decide to do (Matteo Castiglioni et al., Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive). This creates an intricate layer of strategic dependency: receivers can no longer evaluate a message in isolation; they must form beliefs about what others know and how they will act, transforming the receiver response into a simultaneous Nash equilibrium (Gerson Personnat et al., Learning to Play Multi-Follower Bayesian Stackelberg Games).

This interdependence drastically increases computational complexity:

To bypass these intractability barriers, researchers have begun blending persuasion with mechanism design. For instance, Matteo Castiglioni et al. demonstrated that by introducing a "type reporting" step—asking receivers to reveal their preferences from a menu—an otherwise intractable persuasion problem can be solved efficiently in polynomial time (Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting).

Redefining Fairness in Resource Allocation

The challenge of externalities extends directly into computational social choice and fair division. When dividing indivisible items among agents, classic fairness concepts like Envy-Freeness up to One Item (EF1) assume that an agent's utility depends strictly on their own allocated bundle.

In reality, individuals frequently compare their outcomes to those of others (Šimon Schierreich, Multivariate Analysis and Structural Restrictions in Computational Social Choice). If an item assigned to your neighbor causes you distress or provides you a passive benefit, standard fairness definitions break down. Argyrios Deligkas et al. proved that finding an envy-free allocation under these conditions is NP-complete even in highly restricted cases (The Complexity of Fair Division of Indivisible Items with Externalities).

To resolve this, Haris Aziz et al. extended classic fairness concepts to accommodate global allocation states, introducing a robust criterion called General Fair Share (GFS) that is guaranteed to exist even in the presence of severe negative externalities (Fairness Concepts for Indivisible Items with Externalities).

Summary

Whether agents are forming teams, consuming information, or dividing resources, the presence of externalities shifts the problem from local optimization to global coordination. By moving from characteristic functions to partition functions, and from isolated decisions to simultaneous equilibria, modern multi-agent research provides the mathematical and algorithmic tools needed to navigate inherently interdependent systems.

Key Foundational Work

Coalition Structure Generation with Worst Case Guarantees (1999) — contributed 2 concept elements to this direction.
Expressive Negotiation in Settings with Externalities (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_inter_agent_externalities_4292c1b5,
  title = {inter-agent externalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inter-agent-externalities/rdr_4292c1b59e114d07a1d158beaa8dceaf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_inter_agent_externalities_4292c1b5_v1,
  title = {inter-agent externalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inter-agent-externalities/rdr_4292c1b59e114d07a1d158beaa8dceaf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake