Two agent game powers linked to neighborhood frames in eight models
Representation Theorems for Actual Powers over Two-Agent General Concurrent Game Frames
Logic in Computer ScienceComputer Science and Game TheoryMultiagent Systems
Summary
Games where two players make choices simultaneously can be studied using mathematical structures that describe what each player can ensure happens. Earlier work focused on a simplified view that missed details about how specific joint choices affect outcomes. This paper extends the understanding by considering eight different models of such games, each relaxing some standard assumptions. The authors show that each model corresponds neatly to a certain class of mathematical structures called neighborhood frames when considering actual powers, giving a fuller picture of what players can do together.
What this means in practice
- •For multiagent system designers: Design verification tools that precisely capture what coalitions of two agents can enforce under various assumptions about their interaction.
- •For distributed control engineers: Model control scenarios with two interacting components more accurately by choosing the appropriate game model from the eight classes represented by neighborhood frames.
A theory result. No direct application yet.
Authors
Zixuan Chen, Fengkui Ju, Thomas Ågotnes
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).