General Information

---

Project Description

1. A tournament on n teams is a complete, directed graph. We aim to study tournament rules, that is functions that take as input a tournament and output a distribution over winners, that are most consistent and least manipulable as possible.

   ---

   Weekly Log

   Week 1:

   We meet our supervisor twice this week to go over the suggested problems and better understand the topic. He gave us some advice about the possible direction to focus our research and suggested several papers to read. We also prepared our initial presentation.

   Week 2:

   On Monday we gave our initial presentation and described our research plan. During the week we finished reading relevant papers and started to analyze rules that could work be resistant to manipulation by three teams. We shoved that in one of these rules three teams cannot increase their joint probability of winning by more than 23/27. During that time we also tried to explore dependence of possible manipulability of rules by k teams on the precise number of all teams since this question was so far mostly unexplored.

   Week 3:

   We came up with several ideas this week. Firstly, we formalized our analysis of the rule from last week. That is, a rule that randomly forms a ternary tree from the available teams, and from each node advances either a team that beats the other two or, if there is no such team, a random team advances. We show that a group of three teams cannot increase their probability of winning by more than 23/27. We also started the analysis of this rule for a case when just two teams want to increase their probability of winning.

   Our next idea was to look at the rules more broadly. A rule assigns distribution to all possible tournaments and non-manipulability conditions impose restrictions on some pairs of tournaments. Thus, we can form a "meta-graph" having tournaments as nodes and some edges between them representing pairs of tournaments with restrictions. Using this general approach we designed several rules that seem promising.

   Lastly, we looked at the possibility of extending rules applicable to n teams to n+1 teams. We design and analyzed one such extension. While thinking about it, we solved the case when k teams are trying to manipulate a tournament with k+1 teams.

   Week 4:

   We continued exploring the ideas from the previous week. To get a better idea about the precise manipulability of our rule using a ternary tree, we decided to find the precise value of manipulability by checking it on a computer for nine teams. Since there are many tournaments on 9 vertices, we used a graph library that can solve the graph isomorphism problem in a reasonable time. We manage to compute the precise amount for nine teams.

   We also tried to explore the meta-graph structure more. Either to find some concrete rule assigning probabilities, that would show an upper bound on manipulability, or to find some inner structure yielding a natural lower bound. We haven't managed to find anything significant yet.

   Lastly, we continued with the approach of extending the rule applicable to n teams to a rule applicable to more teams. We managed to find a reasonable extension going from n to n*n.

   Week 5:

   This week we still focused on our three approaches. In the ternary tree we have shown equivalence with a certain rule on a specific binary tree, and we tried to use it to find a better bound on manipulability.

   In the metagraph approach we found a rule achieving promising manipulability. But it still seems that a rule with lower manipulability should exist. Thus, we will continue with this approach next week.

   Lastly we mostly finished with the idea of extending rules. The main takeaway from it is that if a rule for some specific number of teams exits and satisfies some reasonable assumptions, then there is a rule for any number of teams that is only slightly more manipulable.

   Week 6:

   This week we focused on finalizing our research and started writing our final paper. From a research perspective, we tried to finish the analysis of our rule for the ternary tree. It seemed promising, but at the end of the week, we noticed that our analysis was flawed, so we will try to correct it next week.

   In the metagraph approach, we weren't able to prove that a better rule that we found last week exists, so we wrote the initial part of the proof down.

   Week 7:

   Unfortunately, we weren't able to correct the flaw in our analysis, and we mainly focused on writing all our results down. We meet with our supervisor twice, and we will aim to publish it at some conference. We also attended a trip to Bell Labs, where we visited the anechoic chamber, which was, in the past, the quietest place on our planet.

   Week 8:

   This week we presented our results to the rest of the REU participants. Before that, we mostly worked on our presentation.

   ---

   Presentations

   • First Presentation
   • Final Presentation

   ---

   Additional Information

   • My Coworker
     • David Miksanik
   • My Mentor
     • Ariel Schvartzman
   • Members of the Czech group
     • Jan Bronec,
     • Guillermo Gaboa,
     • Svetlana Ivanova,
     • Gaurav Kucheriya,
     • Jáchym Mierva,
     • David Miksanik,
     • David Sychrovsky,
     • Tung Anh Vu,
     • Ilia Zavidnyi.