Characterizing Potentially Optimal Line-Up Orders in Team Competitions

by    Stefan Schwarz, Ingo Althöfer, Thomas Fischer, Karsten Müller, Matthias Seise

Preprint series: 05-14, Reports on Optimization

90B80 Discrete location and assignment [See also 90C10]
90C27 Combinatorial 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

Upload: 2005-09-27

Update: 2005

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.