TY - GEN
T1 - On the fixed-parameter tractability of composition-consistent tournament solutions
AU - Brandt, Felix
AU - Brill, Markus
AU - Seedig, Hans Georg
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84856487309&partnerID=8YFLogxK
U2 - 10.5591/978-1-57735-516-8/IJCAI11-026
DO - 10.5591/978-1-57735-516-8/IJCAI11-026
M3 - Conference contribution
AN - SCOPUS:84856487309
SN - 9781577355120
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 85
EP - 90
BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Y2 - 16 July 2011 through 22 July 2011
ER -