CS Paper Radar

Representation Theorems for Actual Powers over Two-Agent General Concurrent Game Frames

Zixuan Chen, Fengkui Ju, Thomas Ågotnes

cs.LO cs.GTcs.MA ·submitted 2026-10-11 09:28 UTC · v1
publishedtheory

Abstract

One of the most well-known connections between logic and games is Pauly's representation theorem: the induced powers of individuals and coalitions in concurrent game frames correspond, in a precise sense, to a certain class of neighborhood frames. The precise sense here is what is called alpha effectivity (or alpha power): the power of a coalition is characterized by the sets of states in which it can ensure that the outcome lies by taking some joint action. This definition is inherently monotonic, and, as pointed out by van Benthem, Bezhanishvili, and Enqvist (2019), that fact can obscure relevant information about the power structure in the game: we do not know whether two sets that a coalition has the power to enforce correspond to the same joint action or to different joint actions. An alternative is to characterize the power of a coalition by its actual power (called basic power by van Benthem, Bezhanishvili, and Enqvist (2019)): the collection of sets of states, each of which corresponds to one joint action by the coalition and all possible joint actions by the other agents. It has recently been argued by Li and Ju (2025, 2026) that standard concurrent game frames rely on three assumptions that may, in some cases, be too strong: seriality, independence of agents, and determinism. This yields a total of eight different classes of general concurrent game frames. In this paper, assuming two agents, we prove that, in terms of actual powers, the eight classes of general concurrent game frames are represented by eight corresponding classes of neighborhood frames. This generalizes a result by van Benthem, Bezhanishvili, and Enqvist (2019).

Comment
In Proceedings GandALF 2026, arXiv:2610.08898. Corresponding author: Fengkui Ju
Journal ref
EPTCS 454, 2026, pp. 67-83
DOI
10.4204/EPTCS.454.6

Closest papers

Nearest neighbours by meaning across the whole index.

The Lattice of Coalition Logics between MCL and CL: Coatoms and Compact Meets

cs.LO math.LO ·2026-10-17 ·Shanxia Wang, Yuqiang Dou
similarity 0.63
Abstract · 19 pages, one table; supplementary finite-checking Python program in ancillary files

For a fixed finite set $N$ of at least two agents, we investigate the lattice $L_N$ of coalition logics between minimal coalition logic (MCL) and classical coalition logic (CL), with extensions required to be structural. This lattice is order-dual to an interval in the subvariety lattice of Boolean coalition algebras. The eight basic extensions obtained by imposing seriality, independence of agents, and determinism form a Boolean cube under inclusion, but not a sublattice of $L_N$. Our main results concern coatoms and compact meets. First, finite critical coalition algebras, realized as complex algebras of finite general concurrent games, yield three infinite families of pairwise distinct coatoms containing seriality, distinguished by failures of independence, determinism, or both. An explicit splitting characterizes the unique coatom omitting seriality. Second, the meet of two basic extensions is compact if and only if the extensions are comparable. For incomparable pairs, no axiomatization of the meet can use formulas of uniformly bounded modal depth, even with infinitely many axioms. Consequently, $L_N$ and three natural principal intervals are non-coherent algebraic lattices. These results reveal lattice-theoretic phenomena beyond the inclusion order of the eight basic extensions.

0.28

How Well Can Strategyproof Tournament Rules Resist Pairwise Manipulation?

cs.GT ·2026-09-07 ·Ke Ding, Bo Li, Fangxiao Wang
theory similarity 0.57
Abstract · 23 Pages

A tournament rule maps the outcomes of all pairwise matches among $n$ teams to a possibly randomized winner. Desirable rules should be Condorcet consistent and monotone, yet also resistant to manipulation among coalition. Prior work mostly measures such manipulation additively through $k$-strongly non-manipulable at $α$ ($k$-SNM-$α$), meaning that no coalition of size $k$ can fix the matches among themselves to increase their total winning probability by $α$. Very recently, two new notions of non-manipulability were introduced. Multiplicative non-manipulability ($k$-MNM-$δ$) is defined analogously, using the multiplicative factor instead. Non-manipulability for $λ$ ($k$-NM$_λ$) characterizes the selfishness of a team, which restricts a coalition's gain to be less than $λ$ times the winning probability sacrificed by its members. In this work, we begin with a strict hierarchy among these three notions: NM$_λ$ is stronger than MNM, which is then stronger than SNM. This motivates us to consider those two notions that are stronger but less studied: pairwise multiplicative non-manipulability and $2$-non-manipulability for $λ$. We show that Randomized Death Match is $2$-MNM-$3/2$ and optimally matches the lower bound. Then, we introduce the BlockBonusedWinStrengths rule, which is Condorcet consistent, monotone, and $2$-NM$_2$. This rule substantially improves the previous upper bound of $λ=11$ and comes within a factor of two of the lower bound $λ=1$.

0.23

On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems

cs.MA cs.AI ·2026-10-13 ·Jianhong Wang, Jonathan Lawry
theory similarity 0.55
Abstract · 25 pages

Understanding agent heterogeneity can inform the design of shared and agent-specific policy representations, however existing criteria provide no unified structural test. We study finite-horizon POSGs and define a type-compatible transformation as a policy-evaluation symmetry when complete policy evaluation commutes with it for every decentralized behavioral policy. Policy-evaluation symmetries form a group for which agent orbits define structural agent types. This classification does not depend on the particular policy chosen or the distribution of initial states. We prove that every componentwise environment automorphism is a policy-evaluation symmetry, but that the converse does not hold. Applying the framework to cooperative Dec-POMDPs shows that agents can belong to different structural types even when they share a common reward. For prescribed weighted reward aggregation, we derive an exact value identity and sufficient conditions for the resulting Dec-POMDP to inherit the policy-evaluation symmetries of the source POSG. Finally, we give sufficient conditions under which repeated model factorizations induce policy-evaluation symmetry, and show that preserving an optimal Boltzmann policy set neither implies nor follows from this symmetry in general.

0.25

Goal Revelation as a Bridge Between Information-Theoretic Empowerment and Capability-Based Human Power

cs.AI cs.ITcs.LG ·2026-11-04 ·Jaime Ruiz-Serra, Tomáš Gavenčiak, Jobst Heitzig
theorycode/data similarity 0.55
Abstract · 19 pages, 3 tables. Code: https://github.com/RuizSerra/revealing-goals

Power matters for AI safety. Optimal agents tend to acquire power across a wide range of objectives (instrumental convergence). As we embed AI agents into socio-technical systems, humans risk gradual disempowerment. Both concerns call for a formal, quantitative measure of power. Two such measures in the context of Markov games are information-theoretic empowerment, the capacity of the channel from an agent's actions to future states, and capability-based individual power, a measure of goal attainment built from the probabilities that a human would attain each goal in a family of candidates were they pursuing it. We show where the two meet. From individual power, Fano's inequality yields a floor $B(s)$. This floor is a lower bound on what we term goal revelation, the mutual information $\mathbb{I}(G;ξ\mid s)$ between the human's latent goal and the realised trajectory. Empowerment caps revelation from above, so that $B(s) \le \mathbb{I}(G;ξ\mid s) \le \mathbb{I}(\mathbf{A}_h \to ξ\mid s) \le \mathfrak{E}_h(s)$. Each quantity can be large while the one below it stays at zero, highlighting the following failure modes. An assistant maximising empowerment can prefer an interface offering broad influence over goal-irrelevant degrees of freedom to one that lets the human attain every goal they might hold. An assistant maximising revelation cannot tell a working interface from one rewired so that every goal yields the wrong outcome, since relabelling goals leaves mutual information unchanged while zeroing every attainment probability. Positive guarantees therefore come only from the attainment end of the chain. A satisfaction floor, computable from two statistics of interaction logs, offers a way to monitor the power users retain in a deployed system, and simulations in random environments show the three quantities are correlated but far from interchangeable.

0.35

Concurrent Strategies as Street Fibrations

cs.LO math.CT ·2026-09-29 ·Hugo Paquet, Glynn Winskel
published similarity 0.55
Abstract · MFPS 2026 post-proceedings

Concurrent games and strategies based on event structures are an established and expressive model of interactive computation. In this paper we revisit the problem of equipping this model with symmetry. Symmetry is essential for many applications, but it is also a source of mathematical complexity, not least because strategies with symmetry can be compared up to several distinct notions of equivalence. Our first contribution is a complete characterization of two classes of strategies for which composition admits an identity. For these two classes the identity laws hold, respectively, up to a "weak" and a "strong" notion of equivalence. The main result is that the weak class of strategies corresponds precisely to those inducing Street fibrations over the game. We also show how the established "thin" approach to symmetry also fits in this general framework. A second contribution is a formal connection between games and setoid-valued profunctors. This follows a long tradition of relating games and relational models, but here additionally includes a very general model of symmetries. Our characterization of strategies as Street fibrations makes the connection to profunctors significantly easier to establish.

0.35

Core nonemptiness for $2/3$-convex games

cs.GT econ.TH ·2026-11-12 ·Keisuke Bando, Toshiyuki Hirai, Kenzo Imamura, Ryuhei Mizutani
similarity 0.54
Abstract

We study the core of $2/3$-convex games, a class of transferable-utility (TU) games that generalizes convex games, which requires at least two of any three distinct coalitions satisfy the supermodular inequality. We show that every $2/3$-convex game admits a marginal worth vector in the core, and hence has a nonempty core. Our proof is constructive and yields a linear-time algorithm for finding such a core allocation. We also show that $2/3$-convexity does not imply permutational convexity in general, while the implication holds under an additional superadditivity condition on pairs of singletons. As an application, we introduce a TU model motivated by the OSCE's consensus-minus-two procedure and show that the resulting game is $2/3$-convex but need not be convex.

0.06

Stability and Perfection in Constrained Weighted Network Games

cs.GT econ.TH ·2026-11-04 ·Julien Fixary, Rémi Castera, Rida Laraki
similarity 0.53
Abstract

We introduce a general framework of constrained weighted network formation in which agents allocate resources across coalitional interactions while facing feasibility constraints. More precisely, we allow arbitrary coalitions of agents to be assigned a continuous weight, and we incorporate both coalitional capacity constraints and individual budget constraints into the model. This framework extends the weighted network formation model of Bich and Morhaim by combining continuous interaction intensities with endogenous feasibility restrictions. Within this setting, we introduce a new notion of stability -- called coalitionwise stability -- extending pairwise stability to constrained network games. Under standard continuity and componentwise quasiconcavity assumptions on payoff functions, we establish the existence of coalitionwise stable networks. We then investigate refinements of stability inspired by the notion of perfect equilibrium introduced by Selten, and by the notion of perfect pairwise stability developed by Bich and Teteryatnikova for network games. The presence of feasibility constraints fundamentally alters the geometry of the feasible set, which no longer possesses a product structure. As a consequence, trembling-hand type refinements become substantially more delicate, since perturbations of some interactions may render other interactions infeasible. Nevertheless, we introduce constrained analogues of both the trembling-hand and perturbative notions of perfect stability considered by Bich and Teteryatnikova, and study their existence and their relationship. In particular, we show the equivalence between these trembling-hand and perturbative formulations under some componentwise monotonicity assumption.

0.21

Does the grand coalition form? Persistence, arrival, and the role of the sharing rule in a dynamic process of nested binding agreements

cs.GT econ.THmath.OC ·2026-08-18 ·Jobst Heitzig
theory similarity 0.53
Abstract · Revised version, slightly changed definition of profitability, additional implementation results. 70 pages, 4 figures

We study a dynamic coalition-formation process in the tradition of Konishi and Ray (2003): players repeatedly form and dissolve binding agreements, evaluate states by discounted long-term expected payoffs, and hold self-confirming beliefs about the process. States and payoff sharing follow Heitzig and Kornek (2018): a state is a hierarchy of nested agreements, and the members of a new agreement share the surplus it generates, measured against the state without that agreement. All payoff assumptions are structural. We prove that every grand state ever reached is absorbing, and that every absorbing state is grand, for every discount factor. A grand state is actually reached, almost surely, for small discount factors, for three players, and, at every discount factor, whenever distributional stakes are smaller than each player s share of the efficiency gain. Otherwise the process can fail only by cycling for ever among non-grand states. We give exact necessary conditions on such a cycle, decidable for a fixed candidate cycle by linear programming, and exhibit, under an earlier and weaker notion of profitability, a four-player payoff structure whose only closed class is a cycle of two pairs forming and dissolving alternately. Under the present definition, and under either termination rule, no equilibrium traverses a cycle on a fixed schedule: somebody always reaches a state they would rather not leave, and the axioms give them the floor. Whether arrival can fail by cycling at random is open. The axioms are not merely postulated: we exhibit a bargaining game proposal, amendment by substitutes voted on by their own signatories, final unanimity, and an arbitrarily small delay on failure whose equilibria satisfy them as the delay vanishes, and which settles each period in its first round.

0.17