Papers for

distributed optimization engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Distributed methods find best potential approximations in multiplayer games

Distributed Algorithms for $α$-Potential Functions in General-Sum Games

Abstract: We study the problem of computing the tightest \(α\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(α\)-potential constructions.

Sun 4 OctMultiagent SystemsComputer Science and Game Theory
The gist
In games where many players pick actions and their outcomes depend on everyone’s choices, it’s hard to find simple functions that capture how players influence each other. This paper studies how to compute the best simple approximation from each player’s perspective, even when players only know their own benefits. The authors develop methods that split the problem into parts players can solve locally and parts that search globally for the best overall solution. Their techniques balance accuracy with computational effort, helping to improve models used to study strategic behavior.
Open → 2610.05516v1