Author name cluster

Sunil Simon

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

JAIR Journal 2024 Journal Article

Boolean Observation Games

Hans van Ditmarsch
Sunil Simon

We introduce Boolean Observation Games, a subclass of multi-player finite strategic games with incomplete information and qualitative objectives. In Boolean observation games, each player is associated with a finite set of propositional variables of which only it can observe the value, and it controls whether and to whom it can reveal that value. It does not control the given, fixed, value of variables. Boolean observation games are a generalization of Boolean games, a well-studied subclass of strategic games but with complete information, and wherein each player controls the value of its variables. In Boolean observation games, player goals describe multi-agent knowledge of variables. As in classical strategic games, players choose their strategies simultaneously and therefore observation games capture aspects of both imperfect and incomplete information. They require reasoning about sets of outcomes given sets of indistinguishable valuations of variables. An outcome relation between such sets determines what the Nash equilibria are. We present various outcome relations, including a qualitative variant of ex-post equilibrium. We identify conditions under which, given an outcome relation, Nash equilibria are guaranteed to exist. We also study the complexity of checking for the existence of Nash equilibria and of verifying if a strategy profile is a Nash equilibrium. We further study the subclass of Boolean observation games with ‘knowing whether’ goal formulas, for which the satisfaction does not depend on the value of variables. We show that each such Boolean observation game corresponds to a Boolean game and vice versa, by a different correspondence, and that both correspondences are precise in terms of existence of Nash equilibria.

PDF Details DOI

LORI Conference 2023 Conference Paper

A Logical Description of Priority Separable Games

Ramit Das
R. Ramanujam 0001
Sunil Simon

Abstract When we reason about strategic games, implicitly we need to reason about arbitrary strategy profiles and how players can improve from each profile. This structure is exponential in the number of players. Hence it is natural to look for subclasses of succinct games for which we can reason directly by interpreting formulas on the (succinct) game description rather than on the associated improvement structure. Priority separable games are one of such subclasses: payoffs are specified for pairwise interactions, and from these, payoffs are computed for strategy profiles. We show that equilibria in such games can be described in Monadic Least Fixed Point Logic (MLFP). We then extend the description to games over arbitrarily many players, but using the monadic least fixed point extension of existential second order logic.

Details

TARK Conference 2023 Conference Paper

Iterated Elimination of Weakly Dominated Strategies in Well-Founded Games

Krzysztof R. Apt
Sunil Simon

Recently, in [K. R. Apt and S. Simon: Well-founded extensive games with perfect information, TARK21], we studied well-founded games, a natural extension of finite extensive games with perfect information in which all plays are finite. We extend here, to this class of games, two results concerned with iterated elimination of weakly dominated strategies, originally established for finite extensive games. The first one states that every finite extensive game with perfect information and injective payoff functions can be reduced by a specific iterated elimination of weakly dominated strategies to a trivial game containing the unique subgame perfect equilibrium. Our extension of this result to well-founded games admits transfinite iterated elimination of strategies. It applies to an infinite version of the centipede game. It also generalizes the original result to a class of finite games that may have several subgame perfect equilibria. The second one states that finite zero-sum games with 'n' outcomes can be solved by the maximal iterated elimination of weakly dominated strategies in 'n-1' steps. We generalize this result to a natural class of well-founded strictly competitive games.

Details DOI

TARK Conference 2021 Conference Paper

Well-Founded Extensive Games with Perfect Information

Krzysztof R. Apt
Sunil Simon

We consider extensive games with perfect information with well-founded game trees and study the problems of existence and of characterization of the sets of subgame perfect equilibria in these games. We also provide such characterizations for two classes of these games in which subgame perfect equilibria exist: two-player zero-sum games with, respectively, two and three outcomes.

Details DOI

IJCAI Conference 2019 Conference Paper

Graphical One-Sided Markets

Sagar Massand
Sunil Simon

We study the problem of allocating indivisible objects to a set of rational agents where each agent's final utility depends on the intrinsic valuation of the allocated item as well as the allocation within the agent's local neighbourhood. We specify agents' local neighbourhood in terms of a weighted graph. This extends the model of one-sided markets to incorporate neighbourhood externalities. We consider the solution concept of stability and show that, unlike in the case of one-sided markets, stable allocations may not always exist. When the underlying local neighbourhood graph is symmetric, a 2-stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational players agree to exchange objects terminates in such an allocation. We show that computing a 2-stable allocation is PLS-complete and further identify subclasses which are tractable. In the case of asymmetric neighbourhood structures, we show that it is NP-complete to check if a 2-stable allocation exists. We then identify structural restrictions where stable allocations always exist and can be computed efficiently. Finally, we study the notion of envy-freeness in this framework.

PDF Details

TARK Conference 2019 Conference Paper

Reasoning about Social Choice and Games in Monadic Fixed-Point Logic

Ramit Das
R. Ramanujam 0001
Sunil Simon

Whether it be in normal form games, or in fair allocations, or in voter preferences in voting systems, a certain pattern of reasoning is common. From a particular profile, an agent or a group of agents may have an incentive to shift to a new one. This induces a natural graph structure that we call the improvement graph on the strategy space of these systems. We suggest that the monadic fixed-point logic with counting, an extension of monadic first-order logic on graphs with fixed-point and counting quantifiers, is a natural specification language on improvement graphs, and thus for a class of properties that can be interpreted across these domains. The logic has an efficient model checking algorithm (in the size of the improvement graph).

Details DOI

AAAI Conference 2017 Conference Paper

Constrained Pure Nash Equilibria in Polymatrix Games

Sunil Simon
Dominik Wojtczak

We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games deﬁned on weighted directed graphs. The payoff of a player is deﬁned as the sum of nonnegative rational weights on incoming edges from players who picked the same strategy augmented by a ﬁxed integer bonus for picking a given strategy. These games capture the idea of coordination within a local neighbourhood in the absence of globally common strategies. We study the decision problem of checking whether a given set of strategy choices for a subset of the players is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We identify the most natural tractable cases and show NP or coNP-completness of these problems already for unweighted DAGs.

PDF Details

IJCAI Conference 2017 Conference Paper

Synchronisation Games on Hypergraphs

Sunil Simon
Dominik Wojtczak

We study a strategic game model on hypergraphs where players, modelled by nodes, try to coordinate or anti-coordinate their choices within certain groups of players, modelled by hyperedges. We show this model to be a strict generalisation of symmetric additively separable hedonic games to the hypergraph setting and that such games always have a pure Nash equilibrium, which can be computed in pseudo-polynomial time. Moreover, in the pure coordination setting, we show that a strong equilibrium exists and can be computed in polynomial time when the game possesses a certain acyclic structure.

PDF Details

IJCAI Conference 2016 Conference Paper

Efficient Local Search in Coordination Games on Graphs

Sunil Simon
Dominik Wojtczak

We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmented by a fixed non-negative bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. Prior work shows that the problem of determining the existence of a pure Nash equilibrium for these games is NP-complete already for graphs with all weights equal to one and no bonuses. However, for several classes of graphs (e. g. DAGs and cliques) pure Nash equilibria or even strong equilibria always exist and can be found by simply following a particular improvement or coalition-improvement path, respectively. In this paper we identify several natural classes of graphs for which a finite improvement or coalition-improvement path of polynomial length always exists, and, as a consequence, a Nash equilibrium or strong equilibrium in them can be found in polynomial time. We also argue that these results are optimal in the sense that in natural generalisations of these classes of graphs, a pure Nash equilibrium may not even exist.

PDF Details

TARK Conference 2015 Conference Paper

Coordination Games on Directed Graphs

Krzysztof R. Apt
Sunil Simon
Dominik Wojtczak

We study natural strategic games on directed graphs, which capture the idea of coordination in the absence of globally common strategies. We show that these games do not need to have a pure Nash equilibrium and that the problem of determining their existence is NP-complete. The same holds for strong equilibria. We also exhibit some classes of games for which strong equilibria exist and prove that a strong equilibrium can then be found in linear time.

Details DOI

GandALF Workshop 2013 Workshop Paper

Social Network Games with Obligatory Product Selection

Krzysztof R. Apt
Sunil Simon

Recently, Apt and Markakis introduced a model for product adoption in social networks with multiple products, where the agents, influenced by their neighbours, can adopt one out of several alternatives (products). To analyze these networks we introduce social network games in which product adoption is obligatory. We show that when the underlying graph is a simple cycle, there is a polynomial time algorithm allowing us to determine whether the game has a Nash equilibrium. In contrast, in the arbitrary case this problem is NP-complete. We also show that the problem of determining whether the game is weakly acyclic is co-NP hard. Using these games we analyze various types of paradoxes that can arise in the considered networks. One of them corresponds to the well-known Braess paradox in congestion games. In particular, we show that social networks exist with the property that by adding an additional product to a specific node, the choices of the nodes will unavoidably evolve in such a way that everybody is strictly worse off.

PDF Details DOI

LORI Conference 2011 Conference Paper

Reflections on Vote Manipulation

Jan van Eijck
Floor Sietsma
Sunil Simon

Abstract The notion of non-manipulability (or: strategy-proofness) used in the famous Gibbard-Satterthwaite theorem is too strong to make useful distinctions between voting rules. We explore alternative definitions and suggest how these can be used to classify voting rules.

Details

TARK Conference 2009 Conference Paper

Dynamic restriction of choices: a preliminary logical report

Soumya Paul
R. Ramanujam 0001
Sunil Simon

We study games in which the choices available to players are not fixed, and may change during the course of play. Specifically, we consider a model in which players may switch strategies, and a global (social) decision may remove some choices, based on the strategies being adopted by players. We propose a logical formalism in which such choices are specified, and a model of bounded memory strategies in which the eventual implications of such choices can be computed, and present preliminary results.

Details