Reasoning about Social Choice and Games in Monadic Fixed-Point Logic
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2019-07-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1907.09100v1 |
| _version_ | 1818300590335197184 |
|---|---|
| author | Ramit Das R. Ramanujam Sunil Simon |
| author_facet | Ramit Das R. Ramanujam Sunil Simon |
| author_sort | Ramit Das |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-12-13T05:09:32Z |
| format | Article |
| id | doaj.art-3a1843931c9c4a8194b347ff7f66b015 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-13T05:09:32Z |
| publishDate | 2019-07-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-3a1843931c9c4a8194b347ff7f66b0152022-12-21T23:58:34ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802019-07-01297Proc. TARK 201910612010.4204/EPTCS.297.8:23Reasoning about Social Choice and Games in Monadic Fixed-Point LogicRamit DasR. RamanujamSunil SimonWhether 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).http://arxiv.org/pdf/1907.09100v1 |
| spellingShingle | Ramit Das R. Ramanujam Sunil Simon Reasoning about Social Choice and Games in Monadic Fixed-Point Logic Electronic Proceedings in Theoretical Computer Science |
| title | Reasoning about Social Choice and Games in Monadic Fixed-Point Logic |
| title_full | Reasoning about Social Choice and Games in Monadic Fixed-Point Logic |
| title_fullStr | Reasoning about Social Choice and Games in Monadic Fixed-Point Logic |
| title_full_unstemmed | Reasoning about Social Choice and Games in Monadic Fixed-Point Logic |
| title_short | Reasoning about Social Choice and Games in Monadic Fixed-Point Logic |
| title_sort | reasoning about social choice and games in monadic fixed point logic |
| url | http://arxiv.org/pdf/1907.09100v1 |
| work_keys_str_mv | AT ramitdas reasoningaboutsocialchoiceandgamesinmonadicfixedpointlogic AT rramanujam reasoningaboutsocialchoiceandgamesinmonadicfixedpointlogic AT sunilsimon reasoningaboutsocialchoiceandgamesinmonadicfixedpointlogic |