View PDF HTML (experimental)

Abstract:We consider cardinality-constrained optimization of set functions over the nodes of a graph. The standard greedy algorithm selects each node according to its immediate marginal contribution, a local criterion that may fail to anticipate the synergies within the final set. We introduce past-aware game-theoretic centrality (PAGTC), which evaluates a candidate node through its expected marginal contribution over the possible completions of the current partial solution to the prescribed target size. This yields a sequential selection strategy that explicitly accounts for the final budget. For nonnegative monotone submodular objectives and a budget $r$, we prove an approximation guarantee of $r/(2r-1)$ and derive computable a posteriori bounds. Since direct PAGTC evaluation involves averaging over a large number of coalitions, we extend an exact computation framework for game-theoretic centrality and derive efficiently computable expressions for two classes of graph-optimization problems, namely facility location and influence in complex contagion, covering both submodular and non-submodular cases. The numerical results show that the benefits depend on the objective and are most pronounced for complex contagion, where submodularity does not hold.

Submission history

From: Francesco Zigliotto [view email]
[v1] Mon, 10 Nov 2025 14:48:40 UTC (272 KB)
[v2] Mon, 1 Dec 2025 15:04:49 UTC (272 KB)
[v3] Tue, 8 Sep 2026 10:36:51 UTC (370 KB)