Random tournaments: who plays with whom
            and how many times?

           Adil Paul, Róbert Busa-Fekete, and and Eyke Hüllermeier

Department of Computer Science, University of Paderborn, Warburger Str. 100, 33098
                             Paderborn, Germany
                     {adil.paul,busarobi,eyke}@upb.de


      Abstract. The weighted feedback arc set problem on tournaments
      (WFAS-T) is defined by a weighted tournament graph whose nodes
      represents the teams/items, and the goal is to find a ranking over the
      teams that minimizes the sum of the weights of the feedback arcs. We
      consider the probabilistic version of WFAS-T, in which the weights of the
      directed edges between every pair of teams sum up to one. A WFAS-T
      with this probabilistic constraint naturally determines a distribution over
      the tournament graphs. In this study, we investigate an online learning
      problem where the learner can observe tournament graphs drawn from
      this distribution. The goal of the learner is to approximate the solu-
      tion ranking of the underlying probabilistic WFAS-T problem. We also
      investigate the partial information case, known from the multi-armed
      bandit problem, where the learner is allowed to select single edges and
      observe the corresponding value. Since the probabilistic WFAS-T prob-
      lem is in general NP-hard [1], our learning algorithm relies on some
      recent approximation results for WFAS-T [2, 3]. We also consider some
      interesting special cases where the learner is able to estimate the exact
      solution, for example where the weights of the tournament graph satisfy
      the Bradley-Terry assumption [4].

       Keywords: weighted feedback arc set problem, tournaments, online
       learning, bandit feedback
References
1. Noga Alon. Ranking tournaments. SIAM J. Discrete Math., 20(1):137–142, 2006.
2. Don Coppersmith, Lisa K. Fleischer, and Atri Rurda. Ordering by weighted number
   of wins gives a good ranking for weighted tournaments. ACM Trans. Algorithms,
   6(3):55:1–55:13, 2010.
3. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent infor-
   mation: Ranking and clustering. In Proceedings of the Thirty-seventh Annual ACM
   Symposium on Theory of Computing, pages 684–693, 2005.
4. Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs:
   I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.

  Copyright c 2015 by the paper’s authors. Copying permitted only for private and
  academic purposes. In: R. Bergmann, S. Görg, G. Müller (Eds.): Proceedings of
  the LWA 2015 Workshops: KDML, FGWM, IR, and FGDB. Trier, Germany, 7.-9.
  October 2015, published at http://ceur-ws.org




                                       79