On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions

Brandt, Felix; Brill, Markus; Seedig, Hans Georg

doi:10.5591/978-1-57735-516-8/IJCAI11-026

On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions

Felix Brandt, Markus Brill, Hans Georg Seedig

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 85-89.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-026

Abstract

Tournament solutions, i.e., functions that associate with each complete and asymmetric relation on a set of alternatives a non-empty subset of the alternatives, play an important role within social choice theory and the mathematical social sciences at large. Laffond et al. have shown that various tournament solutions satisfy composition-consistency, a structural invariance property based on the similarity of alternatives. We define the decomposition degree of a tournament as a parameter that reflects its decomposability and show that computing any composition-consistent tournament solution is fixed-parameter tractable with respect to the decomposition degree. Furthermore, we experimentally investigate the decomposition degree of two natural distributions of tournaments and its impact on the running time of computing the tournament equilibrium set.

Felix Brandt, Markus Brill, and Hans Georg Seedig. 2011. On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 85–89. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-026

@inproceedings{ijcai2011p26,
  title     = {On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions},
  author    = {Brandt, Felix and Brill, Markus and Seedig, Hans Georg},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {85--89},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-026},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-026},
}

TY  - CPAPER
TI  - On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions
AU  - Brandt, Felix
AU  - Brill, Markus
AU  - Seedig, Hans Georg
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 85
EP  - 89
DO  - 10.5591/978-1-57735-516-8/IJCAI11-026
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-026
ER  -