by Stefan Schwarz, Ingo Althöfer, Thomas Fischer, Karsten Müller, Matthias Seise
Preprint series: 05-14, Reports on Optimization
Abstract: Team matches for two-person games / sports, e.g. chess are considered.
In a competition between two teams A and B each player of team A has to play against exactly one player of team B. To arrange this assignment each team chooses a line-up.
For the line-up the playing strength is the most common criterion. The best player of A should be 'the first' and so on.
Assuming that team A has lined up its players according to their strengths, which line-up should team B opt for? We characterize all potentially optimal line-ups for such a team match. It turns out that there are F_2n such line-ups for n players, where (F_1,F_2,F_3,F_4,F_5,...) = (0,1,1,2,3,...) are the Fibonacci numbers.
Keywords: Assignment, Fibonacci numbers, pattern avoiding permutations, Combinatorial Optimization, Gaming