On the complexity of exchanging

DOI10.1016/J.IPL.2016.01.004MaRDI QIDQ264207zbMATH OpenOpenAlexFDO

Authors Xavier Molinero, Martin Olsen, Maria Serna

Publication date 6 April 2016

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

Full work available at URL https://arxiv.org/abs/1503.06052, http://hdl.handle.net/2117/86068

zbMATH Keywords

computational complexitysimple gamestradenessweighted games

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(10)

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

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)