DIMACS

General Information

me
Name: David Mikšaník
School: Charles University, Prague
E-mail: dav(dot)miksanik(at)gmail(dot)com
Office: 409

Project Description

A tournament is a complete directed graph on n teams (an edge is oriented from x to y if and only if x defeated y). A (tournament) rule assigns to each tournament T and each team x a probability that x is the winner of T.

Not every rule is "good". It is reasonable to assume that every "good" rule has at least these properties:

The ultimate goal is, for every k>=3, to find the largest possible p_k such that there is no rule that is (CC) and (k-SNM-p) for p<p_k. (This problem for k=2 is solved in [2] or [3].) Even the case k=3 seems to be challenging. Hence solving this case would be still great. Other than that, we try to come up with other properties that a "good" rule should have.

Weekly Log

Week #1

On the first day, we (me and Jan Soukup) met our mentor Ariel Schvartzman. He reviewed the most important notion and results from [1] and [2]. These papers are the starting point for us. On the following day, we had another meeting with Ariel Schvartzman, where he suggested a possible direction of our research: mainly how to extend/improve known results in [2] and [3].

We prepared our initial presentation for Monday (see Week 2 and Additional information below). Moreover, I started reading the papers [2] and [3] more carefully.

Meantime, On Thursday, I attended the seminar on how to create and maintain this webpage you look at. (Note: this week started on Wednesday.)

Week #2

We started this week by giving the initial presentation in which we described our project and research goals to other participants. During the week, we developed a new rule, called RTT, and showed that this rule is CC and 3-SNM-23/27 (probably the bound is not tight). In the next week, we will try to analyze this rule in more detail. I also read the papers [2], [3].

Without success, we tried to improve the lower bounds of some known rules for the groups of k=2 or k=3 teams. We also tried to understand how the manipulability of rules depends on the number of teams in the tournament. The latter problem has not been discussed in the literature yet.

Week #3

We observed that it is possible to generalize RTT rule to a rule that is CC and 4-SNM-61/64 (using the same idea as we proved that RTT is 3-SNM-23/27). We hope that understanding how RTT behaves for groups of k=2 teams colluding helps us improve the proof that RTT is 3-SNM/23/27. I proved that RTT is 2-SNM-17/36 and conjectured that RTT is 3-SNM-0.77 (note that 23/27=0.8519).

At this time, Jan had been trying to look at tournaments differently. For given k and n, build the following "metagraph": the vertices are the tournaments on n vertices and edges are between the vertices that are S-adjacent, for some set S of teams of size at most k. Then a k-SNM-p rule assigns to each vertex a distribution over winners in the way that the probability that the winner is in S changes by at most p. Using this view, Jan designed the rules that seem less manipulable than other known rules for k=3.

On Friday, we returned to the question of how the manipulability of rules depends on the number of teams in tournaments. Specifically, given any rule R (for n teams), we constructed a rule R' (for n+1 teams) that has similar properties as R.

Week #4

On Monday, I finished writing proof that the construction of rule R' (for n+1 teams) using a rule R (for n teams) has a little worse properties than R. Using this construction iteratively, we can obtain a rule for an arbitrarily large tournament. However, the rule has bad properties (the manipulability goes to 1). We also had a meeting with our mentor, where we briefly analyzed our idea of constructing a rule R' (for n^2 teams) using a rule R (for n teams) with a little worse properties than R. After the meeting we analyzed the construction more carefully. Using this construction iteratively we can obtain a rule for an arbitrarily large tournament. However, unlike in the previous construction, the rule R' has similar properties as R in the sense that the manipulability R' increases by at most a constant (depending on k and n). In fact, the constant is of order (k-1)^2/n.

In the following days, I formally proved that the rule R' has the desired properties. We also discussed the consequences of this construction.

On Friday, we try to understand the connection between RTT and a variation of RTT (it is sligtly less randomized than RTT). We call this rule DRTT. We show that for n=3 and n=9 both rules are equivalent.

Week #5

We started this week by showing that the rules RTT and DRTT are equivalent. This has two important consequences. First, it takes less time to evaluate DRTT than RTT on a computer. Second, DRTT can be viewed as an evaluation of some binary tree. The rest of the week suggested that the equivalence of RTT and DRTT gives us additional power to improve the manipulability bounds on RTT (for k=2 and k=3).

Using a computer, Jan found that DRTT is 2-SNM-1/3 for n=9. However, I am not able to prove that DRTT is 2-SNM-1/3, for any n, at this moment (but I am probably able to prove that DRTT is 2-SNM-2/5). We know that RTT is 3-SNM-p for p ≤ 23/27. By the initial analysis, I prove that DRTT (and hence RTT) is 3-SNM-p for p < 2/3. I will check the analysis next week more carefully.

Jan found a "weird" rule that is 3-SNM-1/2. He believies that there exists a rule that is 3-SNM-2/5, which is the best possible we can get (see his wepage for more information).

Week #6

On Monday, after the meeting with our mentor, Jan found a flaw in my analysis of DRTT rule. Hence destroying the proof that DRTT is 3-SNM-p for p < 2/3. For the rest of the week, without a success, I was trying to fix it or find a new approach.

Jan was writing up the proof that the "weird" rule is 3-SNM-1/2.

Week #7

The end of the program is coming and hence we decided to not continue with trying the fix the proof that DRTT is 3-SNM-p for p < 2/3. We fully committed ourselves to write up all our results. To be specific, I was writing up the analysis of RkT rule, where k>=2 is a natural number (RkT is a generalization of RTT=R3T).

On Thursday, we visited Nokia Bell Labs and we learned something about this place where a lot of important things were discovered.

Week #8

Although the REU program ends in the next week, we left the USA on Friday. For this reason, on Thursday, we gave a presentation summarizing our achievements (see Additional information below). Hence most of the time this week we spent preparing the presentation.

Other than that, we were writing up our results. I was still writing the analysis of RkT rule.

Week #9

Writting and attending Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications at Charles University.

Additional information

References

  1. Altman, A. & Klienberg, R.. (2010). Nonmanipulable randomized tournament selections. Proceedings of the National Conference on Artificial Intelligence. 2. 686-690.
  2. Schneider, Jon & Schvartzman, Ariel & Weinberg, S.. (2016). Condorcet-Consistent and Approximately Strategyproof Tournament Rules.
  3. Schvartzman, Ariel & Weinberg, S. & Zlatin, Eitan & Zuo, Albert. (2019). Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence.

Acknowledgements

This work was carried out while the author David Mikšaník was a participant in the 2022 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.

Proud member of Charles University group consisting of Jan Soukup (Our coordinator), Jan Bronec, Guillermo Gaboa, Svetlana Ivanova, Gaurav Kucheriya, Jáchym Mierva, David Miksanik, David Sychrovsky, Tung Anh Vu, Ilia Zavidnyi.