Computability of simple games: a complete investigation of the sixty-four possibilities

DOI10.1016/J.JMATECO.2010.12.003MaRDI QIDQ553522zbMATH OpenOpenAlexWikidataFDO

Authors Masahiro Kumabe, H. Reiju Mihara

Publication date 27 July 2011

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

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

zbMATH Keywords

computabilityvoting gamescomplete independence

Mathematics Subject Classification ID

Decision theory (91B06) Other game-theoretic models (91A40) Voting theory (91B12)

Abstract: Classify simple games into sixteen "types" in terms of the four conventional axioms: monotonicity, properness, strongness, and nonweakness. Further classify them into sixty-four classes in terms of finiteness (existence of a finite carrier) and algorithmic computability. For each such class, we either show that it is empty or give an example of a game belonging to it. We observe that if a type contains an infinite game, then it contains both computable ones and noncomputable ones. This strongly suggests that computability is logically, as well as conceptually, unrelated to the conventional axioms.

Recommendations

• Nonanonymity and sensitivity of computable simple games
• Computability of simple games: A characterization and application to the core
• On the complexity of problems on simple games
• Computational complexity in the design of voting rules
• Social choice and computational complexity

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 1226099 (Why is no real title available?)
• A Note on the Complete Independence of the Conditions for Simple Majority Decision
• A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision
• An infinite version of Arrow's theorem in the effective setting
• Arrow's theorem and Turing computability
• Arrow's theorem, countably many agents, and more visible invisible dictators
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Computability of simple games: A characterization and application to the core
• Computability of simple games: a complete investigation of the sixty-four possibilities
• Nonanonymity and sensitivity of computable simple games
• On the axiomatic method and its recent applications to game theory and resource allocation
• Preference aggregation theory without acyclicity: the core without majority dissatisfaction
• Social choice and computational complexity
• Social choice and individual values
• The Nakamura numbers for computable simple games
• The computational difficulty of manipulating an election
• Undescribable Events
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(7)

• Computational complexity in the design of voting rules
• The Nakamura numbers for computable simple games
• Computability of simple games: a complete investigation of the sixty-four possibilities
• NP-completeness of some problems concerning voting games
• Nonanonymity and sensitivity of computable simple games
• Computability of simple games: A characterization and application to the core
• Expository notes on computability and complexity in (arithmetical) games

This page was built for publication: Computability of simple games: a complete investigation of the sixty-four possibilities

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