PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomization to Balance Performance under Nominal and Compromised Communication

Colton Hill, Brandon Collins, Philip N. Brown

arXiv:2610.31957v1cs.GT

TL;DR

Communication-dependent game-theoretic guarantees may weaken when communication is compromised, while randomized strategies may not improve performance once communication is restored. The paper studies temperature selection in log-linear learning and finds a per-game balance between near-optimal nominal efficiency and strictly positive compromised efficiency, with guarantees that can weaken as resource choices grow.

  • Problem

    The paper asks whether one approach can provide near-optimal nominal performance and avoid arbitrarily poor performance under compromised communication, where information-dependent game-theoretic guarantees may worsen.

    Source: §1 · pp. 1–2

  • Method

    The paper studies temperature selection in log-linear learning for submodular maximization games with marginal-contribution utilities to control agents’ randomization.

    Source: §1 · p. 2

  • Results

    For every game, some temperature yields near-optimal nominal efficiency and strictly positive compromised efficiency, but every temperature-selection scheme admits games with arbitrarily poor compromised efficiency.

    Source: §5 · p. 6

  • Takeaways & Limitations

    The compromised-efficiency guarantee is game-dependent, motivating work on game-dependent randomization rules and conditions for stronger guarantees.

    Source: §5 · p. 6

    No universal lower bound on compromised efficiency applies across games, and the guarantee can become arbitrarily small when agents have too many resources to consider.

    Source: §4 · p. 5

Abstract

from arXiv · show

It is well-known that under nominal communication, where agents are able to share information with one another, game-theoretic methods provide system-level performance guarantees in multiagent cyber-physical human systems such as distributed resource allocation. However, approaches that depend on communication are frequently not robust when communication is compromised. While randomized decision-making can prevent arbitrarily poor outcomes under compromised communication, these performance guarantees often do not improve when communication abilities are restored. Thus, it remains unclear whether a single approach can perform well under nominal communication and remain robust under compromised communication. In this paper, we study whether a system operator can inform agents about how much they should randomize their choice when selecting actions in order to balance performance across both settings. We show that for any scenario (e.g., a multiagent resource allocation instance), there exists a level of randomization where nominal efficiency is near-optimal while compromised efficiency is strictly positive. We then show that this guarantee weakens as agents must choose between increasingly many resources. These results provide an initial step toward understanding randomization as a tool for robust performance across communication settings.

1. INTRODUCTION

The introduction frames a tradeoff: game-theoretic guarantees rely on communication, while randomized methods can protect performance when communication is compromised but may not improve nominal performance. It asks whether temperature selection within one learning framework can balance both settings.

1. INTRODUCTION

  • Under nominal communication the price of anarchy is 1/2, but under compromised communication it worsens to 1/n, where n is the number of agents.The nominal guarantee assumes agents can observe one another’s actions; under compromised communication they observe only their own.Source: §1 · p. 1
  • Randomized strategies can drive expected system-level objective to approximately 63% of optimal, but this guarantee does not improve when agents are not compromised.The cited algorithms depend on resource values rather than agents’ utility functions.Source: §1 · pp. 1–2
  • The operator faces a choice between nominally effective utility-and-learning approaches that risk compromised performance and randomized approaches that accept moderate nominal performance.The tradeoff matters when communication status changes unexpectedly and the operator cannot switch approaches in real time.Source: §1 · p. 2
  • The paper asks whether one randomization guideline can make nominal performance near-optimal while avoiding arbitrarily poor performance under compromised communication.It studies this question within a submodular maximization game using marginal-contribution utilities and log-linear learning, with temperature controlling randomization.Source: §1 · p. 2
  • The authors report that a temperature can balance nominal efficiency and compromised robustness for a fixed game, but the guarantee can weaken as agents face more resources.The result applies to marginal-contribution utilities optimized via log-linear learning; for any fixed temperature, some game can have arbitrarily poor asymptotic compromised efficiency.Source: §1 · p. 2

2. MODEL

The model represents resource allocation as a game in which agents choose resources and receive utilities tied to the system objective. It compares informed and blind agents under log-linear learning, and uses a star-graph game to analyze expected efficiency.

2.1 Multiagent Singleton Set Cover

  • Agents choose one admissible resource, and the system objective sums the values of selected resources under the model’s positivity assumptions.At least one action profile has positive objective value, while the empty profile has value zero.Source: §2.1 · p. 2

2.2 Marginal-Contribution Utility Function

  • Marginal-contribution utility assigns each agent the change in system objective due to that agent’s presence.The utility is the objective at the agent’s action minus the objective when that agent is absent.Source: §2.2 · p. 2
  • Informed agents observe others’ actions, whereas blind agents act as if others are absent; the nominal and compromised games represent all-informed and all-blind cases.Blind agents’ utilities are evaluated with other agents’ actions set to the empty profile.Source: Blind Agents · pp. 2–3

2.3 Log-Linear Learning

  • In log-linear learning, one randomly selected agent updates each timestep, with temperature controlling the likelihood of choosing a suboptimal action.As temperature approaches zero, the agent selects a best response with arbitrarily high probability; as it grows, available actions become equally likely.Source: §2.3 · p. 3

2.4 Expected System-Level Objective Relative to Optimal

  • The model evaluates expected system objective under the stationary distribution of learning relative to an optimal action profile.At positive temperature, the finite-action learning process admits a stationary distribution.Source: Figure 2 · p. 3, §2.4 · p. 3

2.5 Star-Graph Game

  • The constructed game models a central high-value resource and several remote alternatives, with all agents able to access the central resource to help ensure coverage.It has one resource of value 1, n − 1 medium-valued resources of value 1 − α, n − 1 low-valued resources of value α, and m(n − 1) negligible-value resources.Source: §2.5 · p. 3

3. ROBUST TEMPERATURE SELECTION

For each fixed game, the system operator can choose a positive temperature that makes nominal efficiency near-optimal while keeping compromised efficiency strictly positive. A numerical example illustrates this tradeoff: a small amount of randomization costs little nominal efficiency while improving compromised efficiency.

3. ROBUST TEMPERATURE SELECTION

  • For any game, a positive temperature can make nominal efficiency at least 1 − η while keeping compromised efficiency strictly positive.The guarantee applies to singleton set-cover games with marginal-contribution utilities and log-linear learning.Source: §3 · p. 4
  • Under nominal communication, log-linear learning’s stationary distribution concentrates on system-optimal action profiles as temperature approaches zero.This follows because the nominal game is a finite exact potential game with system objective W as its potential.Source: §3 · p. 4
  • At τ = 0.107, nominal efficiency is 3% below optimal while compromised efficiency rises 10% from its worst.In the illustrated game, n = 100, m = 25, α = 0.25, and ε = 0.01.Source: §3 · p. 4, Figure 3 · p. 4

4. COMPROMISED EFFICIENCY BREAKS DOWN WITH LARGE ACTION SETS

Theorem 4.1 shows that no temperature-selection scheme guarantees a uniform positive lower bound on compromised efficiency across all games. The numerical experiments illustrate how fixed and cardinality-based temperature schemes can both lose efficiency as the number of negligible-value resources grows, for different reasons.

4. COMPROMISED EFFICIENCY BREAKS DOWN WITH LARGE ACTION SETS

  • For any temperature-selection scheme and any δ > 0, some game has compromised efficiency below δ.The theorem’s construction establishes that no universal positive lower bound applies across games.Source: §4 · pp. 4–5

4.1 Numerical Experiments

  • The analysis identifies too many resources as the source of both schemes’ compromised-efficiency problems, though through distinct probability shifts.Fixed temperature accumulates probability on negligible resources; cardinality-based cooling can instead concentrate it on a covered resource.Source: §4.1 · pp. 5–6
  • With fixed temperature, adding ε-valued resources increases their combined selection probability, allowing compromised efficiency to become arbitrarily poor.Each ε-valued resource individually has low selection probability, but the probability of choosing some such resource grows with their number.Source: §4.1 · p. 5, Figure 4 · p. 5
  • The cardinality-based scheme lowers temperature logarithmically as resources increase, but blind agents can then concentrate probability on a covered, 1-valued resource and lose efficiency.The numerical experiment uses n = 100, ε = 0.01, and α values 0.4, 0.45, and 0.5.Source: §4.1 · p. 6, Figure 5 · p. 6

5. CONCLUSION

The paper studies log-linear learning as a way to balance nominal performance and robustness to compromised communication in submodular maximization games. For every game, some temperature yields near-optimal nominal efficiency and strictly positive compromised efficiency, but no temperature-selection scheme prevents arbitrarily poor compromised efficiency across games.

5. CONCLUSION

  • For every game, some temperature makes nominal efficiency near-optimal while compromised efficiency remains strictly positive.The result concerns randomization under log-linear learning in multiagent submodular maximization games.Source: §5 · p. 6
  • For every temperature-selection scheme, there are games with arbitrarily poor compromised efficiency.Source: §5 · p. 6
  • The paper studies whether randomization under log-linear learning can balance nominal performance with robustness to compromised communication.The setting is multiagent submodular maximization games.Source: §5 · p. 6
  • Future work should develop game-dependent randomization rules, identify conditions for stronger guarantees, and explore efficiency under partial communication failures.The paper also proposes studying whether efficiency improves monotonically as agents regain information.Source: §5 · p. 6
Loading 2610.31957v1…