Improving Performance Guarantees for Decentralized Control Systems

How does selfish behavior affect social welfare in a multi-agent system?

What are decentralized systems and why do they matter?

A decentralized system is one that lacks a single point of control or authority. Instead, multiple autonomous agents act according to local information. The importance of these systems lies in their ability to handle complexity, scalability, and robustness in environments where central control is either impractical or undesirable. Examples of such systems include smart grids, swarm robotics, blockchain technology, and traffic routing problems.

Worst-case performance guarantees for decentralized systems

Decentralized systems designers need to know how poorly their system can perform under the worst circumstances. How long does it take a smart grid to come back online during an outage and how sharply can energy prices rise during peak demand? How far off can a robot swarm's performance be from its objective? How low can transactions per second fall when a blockchain technology becomes congested? What are the longest delays that could occur under a given traffic routing scheme?

A common tool for analyzing such questions is the Price-of-Anarchy (PoA), which is defined as the ratio of the maximum possible social welfare to the welfare arising in the worst-case equilibrium. Much work has been done to explore what guarantees we can make about PoA given information on the social welfare function, the agents' private utility functions, and the relationships between these functions. Here, I highlight a few of the key findings in this area.

Information Sharing Constraints in Greedy Submodular Maximization

Consider the class of problems where the social welfare function is submodular. A submodular function is a set function that satisfies the diminishing returns property. If A is a subset of B, then adding some element z to A (where z was not already in A) increases the function value at least as much as adding z to B. See here (page 2) for a formal definition.

Although maximizing submodular functions can be an NP-Hard problem in certain cases, a greedy algorithm can approximate the optimal solution within a factor of 2. This guarantee, however, relies on the strong assumption that the agents have full access to the decisions of all preceding agents. Grimsman et al. explore situations where this in costly or infeasible and find that performance deteriorates roughly in proportion to the size of the largest group of agents making decisions independently [1]. Motivated by this degradation in performance, further work explores how to optimally decide which agents ought to be able to communicate with others to minimize the damage resulting from these information sharing constraints [3].

Valid Utility Games

Valid utility games are a class of multi-agent games defined by three criteria:

1. The social welfare function is submodular.

2. Each agent’s utility is at least its marginal contribution to the social welfare.

3. The total utility is at most the total value of social welfare.

Given these criteria, we can guarantee that any Nash equilibrium outcome of the game attains at least half the optimal social welfare [4]. Note that such Nash equilibria can be computed synchronously, differing from from the greedy algorithm mentioned in the previous subsection.

Valid Utility Games with Information Sharing Constraints

In [2], Grimsman et al. explore a combination of the above two scenarios: the agents participate in a valid utility game and there exist information sharing constraints. The authors quantify how performance degrades as agents are only aware of a subset of the decisions of other agents and introduce a subset of valid utility games that offer a higher performance guarantee.

Current Work

My current efforts with BYU IDeA Labs focuses on exploring other classes of games for which the Price of Anarchy is greater than 1/2 (which are likely but not necessarily subsets of valid utility games). In particular, we are interested in how various private utility functions affect Price of Anarchy. Common utility functions include marginal contribution to social welfare and Shapley value. What other derivatives of the social welfare function can we use as the private utility functions? Can some convex combination of marginal utility and Shapley value yield interesting results? Does the private utility function need to derive from the social welfare function in the first place?

[1] Grimsman, D., Ali, M. S., Hespanha, J. P., & Marden, J. R. (2018). The impact of information in distributed submodular maximization. IEEE Transactions on Control of Network Systems, 6(4), 1334-1343.

[2] Grimsman, D., Brown, P. N., & Marden, J. R. (2022, December). Valid utility games with information sharing constraints. In 2022 IEEE 61st Conference on Decision and Control (CDC) (pp. 5739-5744). IEEE.

[3] Grimsman, D., Hespanha, J. P., & Marden, J. R. (2018, December). Strategic information sharing in greedy submodular maximization. In 2018 IEEE Conference on Decision and Control (CDC) (pp. 2722-2727). IEEE.

[4] A. Vetta, "Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions," The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., Vancouver, BC, Canada, 2002, pp. 416-425