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

Ramit Das
R. Ramanujam
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).

In Lawrence S. Moss: Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2019), Toulouse, France, 17-19 July 2019, Electronic Proceedings in Theoretical Computer Science 297, pp. 106–120.
Published: 19th July 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.297.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org