On the complexity of exchanging

DOI10.1016/J.IPL.2016.01.004zbMATH Open1356.68106arXiv1503.06052OpenAlexW1729085596MaRDI QIDQ264207FDOQ264207

Authors: Xavier Molinero, Martin Olsen, Maria Serna 

Publication date: 6 April 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of $j$ given losing coalitions into a set of $j$ winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions.

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

Recommendations

• On the complexity of problems on simple games
• On the complexity of the decisive problem in simple and weighted games
• Dimension and codimension of simple games
• Forms of representation for simple games: sizes, conversions and equivalences
• NP-completeness of some problems concerning voting games

zbMATH Keywords

computational complexitysimple gamestradenessweighted games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12)

Cites Work

• Simple games and weighted games: A theoretical and computational viewpoint
• Complete simple games
• The dimension for the European Union Council under the Nice rules.
• Dimension of complete simple games with minimum
• Weighted voting, abstention, and multiple levels of approval
• On the dimension of simple monotonic games
• Cooperation through social influence
• Even faster algorithm for set splitting!
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of problems on simple games

Cited In (10)

• On the theoretical properties of the exchange algorithm
• Duration problem with multiple exchanges
• How to Exchange Half a Bit
• On the generalized dimension and codimension of simple games
• Analysis of the gift exchange problem
• Multivariate complexity analysis of Swap Bribery
• Exchange Design and Efficiency
• On Finite Dimension Exchange Algorithms
• Multidimension: a dimensionality extension of simple games
• Forms of representation for simple games: sizes, conversions and equivalences

This page was built for publication: On the complexity of exchanging

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