Computability of simple games: A characterization and application to the core

DOI10.1016/J.JMATECO.2007.05.012zbMATH Open1133.91314arXiv0705.3227OpenAlexW3104439138WikidataQ56060514 ScholiaQ56060514MaRDI QIDQ2482640FDOQ2482640

Authors: Masahiro Kumabe, H. Reiju Mihara 

Publication date: 23 April 2008

Published in: Journal of Mathematical Economics (Search for Journal in Brave)

Abstract: The class of algorithmically computable simple games (i) includes the class of games that have finite carriers and (ii) is included in the class of games that have finite winning coalitions. This paper characterizes computable games, strengthens the earlier result that computable games violate anonymity, and gives examples showing that the above inclusions are strict. It also extends Nakamura's theorem about the nonemptyness of the core and shows that computable games have a finite Nakamura number, implying that the number of alternatives that the players can deal with rationally is restricted.

Full work available at URL: https://arxiv.org/abs/0705.3227

Recommendations

• Computability of simple games: a complete investigation of the sixty-four possibilities
• Nonanonymity and sensitivity of computable simple games
• A characterization of social choice correspondences that implement the core of simple games
• The Nakamura numbers for computable simple games
• scientific article; zbMATH DE number 1842054

zbMATH Keywords

Turing computabilityrecursion theoryvoting gamesinfinitely many playerscomputable manuals and contracts

Mathematics Subject Classification ID

Games with infinitely many players (91A07)

Cites Work

• Social choice and individual values
• Voting schemes for which it can be difficult to tell who won the election
• The Nakamura numbers for computable simple games
• Computability of simple games: A characterization and application to the core
• Computational complexity in the design of voting rules
• Incomplete Written Contracts: Undescribable States of Nature
• The vetoers in a simple game with ordinal preferences
• Minimally generated Boolean algebras
• Title not available (Why is that?)
• Cooperation and Effective Computability
• On the Complexity of Cooperative Solution Concepts
• The computational difficulty of manipulating an election
• Acyclic social choice from finite sets
• A New Solution Concept for Coalitional Games in Open Anonymous Environments
• Rationality, Computability, and Nash Equilibrium
• Arrow's theorem, countably many agents, and more visible invisible dictators
• Cooperation and Punishment
• Computable preference and utility
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Non-computability of competitive equilibrium
• May's theorem with an infinite population
• Voting games and acyclic collective choice rules
• Title not available (Why is that?)
• Arrow's theorem and Turing computability
• A note on the core of voting games
• Social choice and electoral competition in the general spatial model
• Social choice and computational complexity
• An infinite version of Arrow's theorem in the effective setting
• Nonanonymity and sensitivity of computable simple games
• Title not available (Why is that?)
• Computability of simple games: a complete investigation of the sixty-four possibilities
• Precisely dictatorial social welfare functions
• Arrow's theorem with restricted coalition algebras
• Title not available (Why is that?)
• On computational complexity of membership test in flow games and linear production games
• Learning Rational Expectations Under Computability Constraints
• Anonymity and neutrality in Arrow's Theorem with restricted coalition algebras
• On the computability of Nash equilibria
• Anonymity in large societies
• Existence of a coalitionally strategyproof social choice function: a constructive proof

Cited In (15)

• The reciprocity set
• Computational complexity in the design of voting rules
• Preference aggregation theory without acyclicity: the core without majority dissatisfaction
• On the complexity of problems on simple games
• The Nakamura numbers for computable simple games
• Computability of simple games: a complete investigation of the sixty-four possibilities
• Cores and capacities of compound simple games
• Nonanonymity and sensitivity of computable simple games
• Computability of simple games: A characterization and application to the core
• Title not available (Why is that?)
• Answers set programs for non-transferable utility games: expressiveness, complexity and applications
• Expository notes on computability and complexity in (arithmetical) games
• Computing the cores of strategic games with punishment-dominance relations
• A relation-algebraic approach to simple games
• On Dedekind's problem for complete simple games

This page was built for publication: Computability of simple games: A characterization and application to the core

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482640)