PaperlayerView exact revision on arXiv

Source-linked AI summary

Deriving the Pure Price of Anarchy for Networked Resource Allocation Games

Vartika Singh, Philip N. Brown

arXiv:2609.12077v1cs.GTcs.MAcs.SYeess.SYmath.OC

TL;DR

The paper addresses the lack of a general method for designing utilities across arbitrary information networks and system objectives. It uses linear programs to derive optimal pPoA and utility designs, establishing network-independent results for supermodular objectives and results for other networked settings.

  • Problem

    Prior work provides bounds for information-network settings but lacks a general method to optimize utility functions across arbitrary objectives and networks.

    Source: §I · p. 1

  • Method

    The paper develops a linear program to derive optimal pPoA and utility designs for general system objectives and arbitrary information networks.

    Source: §I · p. 1, §VI · p. 11

  • Results

    For supermodular objectives, fully communication-denied marginal-contribution utility is optimal regardless of the network; the paper also proves pPoA of 1/2 for specified set cover networks.

    Source: §I · p. 2

  • Takeaways & Limitations

    The results provide exact optimal-performance guarantees for several networked settings, including supermodular games independently of the information network.

    Source: §I · p. 2, §VI · p. 11

    The paper focuses on pure Nash equilibria; when these may not exist in nontrivial networks, the authors identify learning dynamics and limiting behavior as an important direction for comparison.

    Source: §VI · p. 11

Abstract

from arXiv · show

This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.

I. INTRODUCTION

The paper extends utility design for pure Nash equilibria to arbitrary information networks, addressing a gap in methods for general objectives and networks. It develops an LP-based approach and studies utility designs and performance guarantees across several objective classes.

II. PROBLEM DESCRIPTION

  • The designer chooses local utilities so that the induced game’s equilibria achieve favorable system-objective values, evaluated by the worst-equilibrium-to-optimum ratio.The coordination setting includes cases where centralized control is expensive or infeasible and agents have limited access to others’ actions.Source: §I · p. 1

I. INTRODUCTION

  • The LP derives optimal pPoA for arbitrary system objectives and information networks, extending earlier general-objective work limited to full-information networks.The authors also identify specific optimal utility designs and guarantees for supermodular and set cover games.Source: §I · p. 1
  • For supermodular objectives, fully communication-denied marginal contribution utility is optimal regardless of the information network.For set cover games, the paper also establishes an optimal price of anarchy of 1/2 for a blind, isolated, and two-normal-agent network.Source: §I · p. 2
  • Full-information-optimal utilities remain near-optimal for submodular games after communication failures, while numerical examples suggest optimal pPoA increases with network connectedness.The connectedness relationship is presented as a numerical indication, not a proof.Source: §I · p. 2

A. Local Utilities and Utility Generating Mechanism

  • The model represents information through an observation network and lets the designer choose distinct utility-generating mechanisms for different agents.The resource-allocation framework combines anonymous separable games with network parameterization and is described as applicable to settings such as facility location and sensor coverage.Source: A. Local Utilities and Utility… · pp. 2–3, §I · p. 2

1) Marginal Contribution Utility:

  • Marginal contribution utility assigns an agent the marginal gain in the system objective when that agent participates.The passage identifies this rule as generated by the mechanism f_mc.Source: 1) Marginal Contribution Utility · p. 3

2) Equal Share Utility:

The paper introduces equal-share and communication-denied utility designs, then formalizes the resulting games and evaluates their pure Nash equilibria. Its analysis is restricted to games with at least one such equilibrium, and the designer’s guarantee is considered over possible games under a given basis function and information graph.

2) Equal Share Utility:

  • Equal-share utility is presented as a local utility design with a corresponding utility-generating mechanism.The supplied passage also gives a count-based expression associated with this design.Source: 2) Equal Share Utility · p. 3

3) Communication-Denied Utility:

  • Communication-denied utility is a named local utility design, also called “blind” in prior work.The design is associated with the utility-generating mechanism f_cd.Source: 3) Communication-Denied Utility · p. 3

B. Resulting Class of Games and Solution

  • A pure Nash equilibrium is an action profile where no agent can improve its utility through a unilateral deviation.The analysis restricts attention to games with at least one pure Nash equilibrium; the designer seeks guarantees across possible games given the basis function and information graph.Source: B. Resulting Class of Games and Solution · p. 3
  • The information graph can partition agents into classes with matching observation and observer sets, allowing similar agents to receive the same local utilities.Figure 1 illustrates classes formed from agents’ observation relationships.Source: Figure 1 · p. 4

C. Information Graph and Classes

The paper represents information networks through classes of agents with matching observation patterns and develops an LP for deriving pPoA in general information networks. For supermodular games, the optimal pPoA bound is independent of the network and is attained by communication-denied utilities.

C. Information Graph and Classes

D. Pure Price of Anarchy for Network (C, N)

III. SUPERMODULAR GAMES

  • For supermodular games, Theorem 1 extends to arbitrary information networks; the network-independent optimal pPoA bound is attained by communication-denied utilities, which guarantee a PNE.Source: §III · p. 5

IV. SUBMODULAR GAMES

Submodular games can have pPoA that depends on both the information network and the basis function, so the paper gives results for commonly studied network classes and set cover games. With any communication failure, set cover pPoA is at most 1/2, compared with the full-information optimum of about 0.63.

IV. SUBMODULAR GAMES

  • For submodular games, pPoA can depend on the information network and basis function, so Section IV treats common network classes while arbitrary cases are deferred to Section V.The section’s theorems cover broad classes of networks rather than only fixed examples.Source: §IV · p. 6

A. Set Cover Games

  • In set cover games, the basis function gives a resource no additional objective value once at least one agent selects it.The set cover basis is w(j)=1 for j≥1 and w(0)=0.Source: A. Set Cover Games · p. 6

1) A General Upper Bound on Networked Set Cover Games:

  • With any communication failure, set cover pPoA is at most 1/2, while the known full-information optimum is 1−1/e ≈ 0.63.The bound applies irrespective of network size, agent count, or utility-generating mechanism.Source: 1) A General Upper Bound on Networked… · p. 6

2) Set Cover Games with Blind and Isolated Agents:

For set cover games, marginal contribution is optimal in the stated blind-agent setting and achieves pPoA 1/2 for a broader, partially connected class of networks. Results for more general blind, isolated, and normal classes give bounds tied to the number of classes, while the full-information utility design is reported as robust to communication failures in numerical examples.

2) Set Cover Games with Blind and Isolated Agents:

  • With at least one blind agent, marginal contribution is optimal for networks of blind, isolated, and normal agents; pure Nash equilibria exist for any utility mechanism in this setting.The theorem completes the characterization by ruling out mechanisms that outperform marginal contribution in these networks.Source: 2) Set Cover Games with Blind and… · pp. 6–7

3) Set Cover Games with General Networks:

  • When each pair of classes has at least one observation direction but the network is not full-information, marginal contribution achieves pPoA 1/2.The bound does not depend on the number of agents in the classes.Source: 3) Set Cover Games with General Networks · p. 7
  • For the stated general-network case, marginal contribution satisfies pPoA(f_mc, w, C, N) ≥ 1/(1+k).Here k is the number of classes in the information network.Source: 3) Set Cover Games with General Networks · p. 7
  • For networks with blind, isolated, and normal classes, Theorem 5 gives pPoA bounds whose dependence is on the number of classes, not the number of agents in each class.The theorem applies when not all classes are normal.Source: 3) Set Cover Games with General Networks · p. 7
  • Numerical examples indicate that the full-information optimal utility design is nearly optimal after communication failures, with the better mechanism depending on submodularity.At d=0.25 marginal contribution performs better, whereas at d=0.75 the full-information design outperforms it.Source: Figure 3 · p. 8

B. General Submodular Games

In general submodular games, the full-information utility mechanism remains close to optimal under communication failures, while numerical results associate better optimal PoA with more connected information networks. The section also introduces the LP framework for arbitrary games and its action-configuration notation.

B. General Submodular Games

  • For general submodular games, an LP computes pure PoA for a given basis function, utility mechanism, and information network, enabling numerical analysis when closed forms are difficult.The examined basis functions use w(j) = j^d, where d ranges from 0 to 1; d = 0 corresponds to set cover games.Source: B. General Submodular Games · p. 8

1) Robustness:

  • With more blind agents, marginal contribution and f* converge to optimal PoA; at high submodularity, its PoA remains above half even when all agents are blind.At low submodularity, marginal contribution performs very close to the optimal mechanism; its performance degrades as the parameter rises.Source: Figure IV · p. 8
  • As more agents become compromised, the gap between the PoA at f* and the optimal PoA becomes negligible, and f* remains robust across submodularity parameters.The authors conclude that f* remains almost optimal even under unanticipated communication failure.Source: 1) Robustness · p. 8

2) Monotonicity:

  • Optimal PoA decreases as more agents become blind or isolated, and blind-agent networks outperform isolated-agent networks; the connectivity relationship remains unproved.The comparison varies the submodularity parameter with three compromised agents out of 15, as well as the number of compromised agents at d = 0.5.Source: 2) Monotonicity · p. 9, Figure 5 · p. 9

V. ARBITRARY GAMES

  • Theorem 6 provides an LP for any basis function, utility mechanism, and information network, including objectives not restricted to submodular or supermodular functions.This LP is the analytical machinery underlying the technical results in Sections III and IV.Source: §V · p. 9

A. Notations for LP

  • The LP notation indexes action configurations by agent class and encodes resource values so that equilibrium and optimal behavior are realized.The primal LP's decision variables represent resource values in underlying game instances.Source: A. Notations for LP · p. 10

B. LP deriving PoA for any Utility Generating Mechanism

The section extends price-of-anarchy characterization to arbitrary information networks with an LP, then explains how the formulation can optimize utility design when pure Nash equilibria are guaranteed. It also identifies equilibrium existence and dynamic learning behavior as open concerns.

B. LP deriving PoA for any Utility Generating Mechanism

  • Theorem 6 characterizes pure PoA by an LP for any information network, basis function, and utility mechanism when each class's utility at one is positive; otherwise pPoA is zero if any is nonpositive.This extends prior full-information LP characterization to general information networks.Source: B. LP deriving PoA for any Utility… · pp. 10–11
  • For networks of blind, isolated, and normal agents, guaranteed pure Nash equilibrium permits optimizing over utility mechanisms to derive optimal utility and PoA.Scaling each class's utility by a positive coefficient preserves PoA, allowing the nonlinear terms to be replaced and the optimization made linear.Source: B. LP deriving PoA for any Utility… · p. 11

VI. CONCLUSIONS

  • The paper provides one LP for exact PoA under a chosen utility design and another for optimal utility design and optimal PoA across arbitrary objectives and networks.It reports settling open questions including optimal PoA for networked supermodular problems.Source: §VI · p. 11
  • When nontrivial networks may lack pure-strategy Nash equilibria, the relevance of static PNE guarantees weakens, motivating comparison with learning-rule limiting behavior.The conclusions also identify closed-form bounds for other submodular functions and comparisons between fixed and optimal mechanisms across networks as future work.Source: §VI · p. 11

APPENDIX I PROOFS OF SECTION V

The appendix proves the LP characterization by reducing candidate games, encoding them with action configurations and resource values, and establishing equivalence through a tight relaxation and duality.

APPENDIX I PROOFS OF SECTION V

  • Action configurations track agents' equilibrium and optimal choices, while θ(t) aggregates the values of resources associated with each configuration as primal LP variables.The LP's finite-value formulation uses θ(t) for each configuration t.Source: Appendix I · pp. 11–12
  • The proof shows the relaxation is tight and equivalent to the primal LP by constructing a game instance from any feasible LP solution.Boundedness of the configuration values supports equivalence.Source: Appendix I · pp. 12–14
  • The proof restricts attention to games retaining only each agent's worst-equilibrium and optimal actions, then normalizes the worst-equilibrium objective to one without changing PoA.The reduction and normalization establish a tractable form for the PoA optimization.Source: Appendix I · pp. 12–13
  • Strong duality equates the dual LP optimum with the primal LP value, completing the LP characterization of PoA.The proof matches constraints indexed by its reduced configuration set to those in the stated dual.Source: Appendix I · p. 15
  • Multiplying each class's utility mechanism by any positive constant leaves PoA unchanged.This invariance supports the utility-rescaling step used when optimizing over mechanisms.Source: Appendix I · p. 16

APPENDIX II

The appendix uses the linear program to prove pPoA bounds for utility designs across information networks, including cases distinguished by blind, isolated, and normal-agent classes.

APPENDIX II

  • For supermodular objectives, the LP gives pPoA(f, w, C, N) ≤ n/w(n) for every utility mechanism.The proof sets λ_j = w(n)/n at the optimum and obtains μ = w(n)/n.Source: APPENDIX II · pp. 16–17
  • With κ blind or isolated classes, the marginal contribution design attains pPoA 1/(1+κ) when κ < n, and 1/n when κ = n.The proof identifies the corresponding optimal μ values as 1+κ and n.Source: APPENDIX II · p. 18
  • When κ ≥ n−1, marginal contribution attains pPoA 1/n; for the other case considered, its pPoA is 1/(2+κ).The latter bound comes from the most binding LP constraint with κ+1 active a_j terms and one active b_j term.Source: APPENDIX II · pp. 18–19
  • For networks with blind and normal classes, the marginal-contribution LP term is at most k because a blind class and its observing class cannot both contribute.This yields μ* ≤ k in the proof.Source: APPENDIX II · p. 19
  • When there are no normal classes, the appendix derives μ* = 1+k for marginal contribution, yielding pPoA at least 1/(1+k).Here all classes are blind or isolated.Source: APPENDIX II · p. 19
Loading 2609.12077v1…