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

DOI10.1016/J.JMATECO.2010.12.003zbMATH Open1222.91017arXiv1102.4037OpenAlexW2129074646WikidataQ56387528 ScholiaQ56387528MaRDI QIDQ553522FDOQ553522

H. Reiju Mihara, Masahiro Kumabe

Publication date: 27 July 2011

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

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.

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

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

zbMATH Keywords

computabilityvoting gamescomplete independence

Mathematics Subject Classification ID

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

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
• A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision
• Title not available (Why is that?)
• On the axiomatic method and its recent applications to game theory and resource allocation
• The computational difficulty of manipulating an election
• Arrow's theorem, countably many agents, and more visible invisible dictators
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Arrow's theorem and Turing computability
• Preference aggregation theory without acyclicity: the core without majority dissatisfaction
• Social choice and computational complexity
• An infinite version of Arrow's theorem in the effective setting
• Nonanonymity and sensitivity of computable simple games
• Undescribable Events
• Title not available (Why is that?)
• Computability of simple games: a complete investigation of the sixty-four possibilities
• A Note on the Complete Independence of the Conditions for Simple Majority Decision

Cited In (6)

• 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)