On the complexity of exchanging

•We analyse the computational complexity of the trade robustness problem.•We look at the problem of turning winning coalitions into losing coalitions.•We consider the trade robustness problem for different representations.•We give remaining problems related with trade robustness. We analyze the comp...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2016-06, Vol.116 (6), p.437-441
Main Authors: Molinero, Xavier, Olsen, Martin, Serna, Maria
Format: Article
Language:English
Subjects:
68 Computer science
68Q Theory of computing
91 Game theory, economics, social and behavioral sciences
91A Game theory
Associations
Classificació AMS
Complexitat computacional
Complexity
Complexity theory
Computation
Computational complexity
Data processing
Exchanging
Game theory
Games
Investigació operativa
Jocs, Teoria de
Lists
Matemàtiques i estadística
Mathematical analysis
Mathematical problems
Simple games
Studies
Teoria de jocs
Tradeness
Turning
Weighted games
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We analyse the computational complexity of the trade robustness problem.•We look at the problem of turning winning coalitions into losing coalitions.•We consider the trade robustness problem for different representations.•We give remaining problems related with trade robustness. 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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2016.01.004