DIMACS
DIMACS REU 2021

General Information

me
Student: Eric Xue
School: Yale University
E-mail: eric (dot) xue (@) yale (dot) edu
Project: Fair and Strategy-proof Tournament Design

Project Description

We are interested in the manipulability of fair tournament rules on round-robin tournaments in two previously unconsidered settings. In the first setting, participants place greater emphasis on winning the tournament themselves but are still willing to purposefully lose against another participant if the joint benefit from colluding is "great enough." In the second setting, tournament rules are allowed to choose more than one winner.

Prior work has focused on the setting in which tournament rules choose exactly one winner, and two participants are willing to collude as long as the joint benefit is positive (but possibly "small"). Unfortunately, in this setting, it is impossible to design a fair tournament rule that is non-manipulable even by two participants. We study how greater selfishness on the part of the participants and the option of choosing multiple winners allow us to confront this impossiblity result.


Weekly Log

Week 1:
The REU officially started this week. In the beginning of the week, I attended orientation, during which I got to meet the other participants, and a workshop to set up this website. I also met with my mentors to figure out the direction we want to take our project in. I proved some preliminary results, e.g., a lower bound on the manipulablility of tournament rules with our definition of fairness in terms of how much participants care about winning themselves, matching lower and upper bounds on the number of winners needed to deincentivize manipulation, and where a previously proposed tournament rule falls short in our setting, by the end of the week. Toward the end of the week, I attended a nice talk by Neil Sloane about the OEIS and met with Ariel to discuss what I've done this week and how to move forward. Also, the REU hosted a social event during which I got to talk with some of the other participants.
Week 2:
I continued to study the performance of some previously considered and well-known tournament rules in our new setting in which participants care more about winning the tournament themselves. It's interesting that some of the rules that performed well in prior work cannot escape the impossibility of simultaneous fairness and non-manipulability, while some simple rules can when participants are incredibly selfish. This work led to some conjectures regarding the role of monotonicity in tournament rules that perform well in our setting. I also attended a seminar by Saray Shai on multilayered road networks.
Week 3:
I investigated the compatibility of monotonicity, non-manipulability, and two previously considered notions of fairness--Condorcet consistence and cover consistence. Even with stronger notions of monotonicity, it is difficult to show that no fair and non-manipulable rule can satisfy these notions without high levels of selfishness. Currently, we can only show this incompatibility when gains from manipulation are maximal. The lack of information regarding how probabilities are assigned makes it difficult to obtain meaningful bounds on the gains and losses from manipulation, except in special cases of tournaments. I also considered whether the additional strength of cover consistence over Condorcet consistence would allow us to show a stronger lower bound on how selfish players need to be so that they don't collude. The same obstacles that arose earlier impeded progress in this direction as well.
Another direction that I looked into was whether there is a rule with manipulability decreasing with the number of players. When considering whether any natural rules satisfied this property, I realized many of them satisfied a certain property. This realization led to a notion of fairness which to the best of my knowledge has not been previously considered. For rules that satisfy this notion, I proved that the problem of finding non-manipulable rules is equivalent to the problem of finding rules with decreasing manipulability. Throughout the week, I attended a data science bootcamp hosted by TRIPODS.
Week 4:
I formally proved that a number of natural tournament rules satisfy the notion of fairness introduced last week, suggesting that it is quite natural. Using this notion, I showed some lower bounds on the tradeoff between selfishness and manipulability. I also looked into how a notion of fairness that is stronger than Condorcet consistency but weaker than our new notion fits into our model. Interestingly, the equivalence result proved for our new notion of fairness holds for this moderately strong notion as well. However, the weakness only allows us to demonstrate existence of non-manipulable rules given one with decreasing manipulability. In particular, we cannot determine what the rule is.
Week 5:
I spent most of the week tying up a loose end--that a well-known tournament rule is always manipulable for a fixed level of selfishness regardless of how many players there are. I had trouble proving a key lower bound, which I was confident was correct, needed for the approach I took, but I eventually figured out a way to prove a weaker yet still sufficient lower bound to get the result. I also discussed with Ariel what experiments might shed light on whether there is a Condorcet consistent and non-manipulable rule for a fixed level of selfishness. In general, an LP cannot capture the constraints of our model, but I realized that an LP could capture the constraints if we additionally enforced our rules to be monotone. The results of the experiments suggested that one of previous conjectures on the role of monotonicity is correct.
Week 6:
Following the direction suggested by last week's experiments, I attempted to show a lower bound on how selfish agents need to be for a rule to be monotone, Condorcet consistent, and non-manipulable. I hoped to use duality to show that the primal feasibility LP was infeasible for a certain collection of tournaments and for certain levels of selfishness, but experiments revealed that the LPs I was considering were indeed feasible. In fact, I found a tournament rule on tournaments of four players that satisfied our desired properties but provably violated our conjectured lower bound. After consulting with Ariel, we realized there were bugs in our previous experiments. Correcting these bugs and rerunning the experiments completely reversed our previous conjecture, suggesting that there are good rules that satisfy all three properties. It would be extremely exciting if we could demonstrate such a rule.
Week 7:
I wrote some code for additional experimentation, e.g., code for generating all non-isomorphic tournaments on n players and code for generating the linear constraints for the LP. Since many assignments of probabilities satisfied our constraints in prior experiments, we wanted to see if we could arrive at a unique assignment by enforcing different notions of fairness or by choosing different objective functions to optimize. Experiments showed that there are non-manipulable rules satisfying stronger notions of fairness for tournaments of size up to 6. For tournaments of larger size, our experiments become computationally intractable. I tried out some ideas for tournament rules that I had by implementing them in Python, but unfortunately, none of them have satisfied all the constraints for tournaments of size 5.
Week 8:
I continued trying out ideas for tournament rules. To get these ideas, I consulted early work on tournament choice rules. Tournament choice rules differ from the tournament rules we are interested in because they often choose multiple teams as winners (i.e., a subset of "best" teams) rather than break ties and choose a single winner. Nonetheless, the ideas and techniques behind these rules may shed some light on our problem. I found the idea behind the bipartisan set of treating a tournament as a zero sum game particularly interesting. Unfortunately, none of the rules I thought of this week satisfied the constraints for tournaments of size 6.
Week 9:
I focused on writing my final report and preparing for my presentation this week. I also attended EC 2021 this week, so this week was especially busy.

Additional Information


Acknowledgements

I am incredibly grateful to Ariel Schvartzman and Dave Pennock for their mentorship and useful discussions. This work was carried out while I was a participant in the 2021 DIMACS REU program at Rutgers University, supported by NSF grant CCF-1852215.