Randomized Serial Dictatorship and Envy Bounds
This project deals with the Random Serial Dictatorship mechanism (RSD), answering an open problem from this article.
We have found tight bounds on the worst envy ratio possible and are currently generalizing our results to RSD with multiple rounds and non-additive valuation functions.
Elections in Metric Spaces
We are currently working on finding guarantees on the minimum number of voters we are certain that some candidate gets in any pairwise election. We are interested
in the special case of instances where the voters' preferences are induced by a metric space. This generalizes the notion of a Condorcet winner and builds directly on this article.
NP-hardness of a Toothpick Rotation Problem
This research project deals with a decision problem in which toothpicks are placed horizontally on the 2D plane and we seek to determine if there is a way to rotate
each of them exactly once so that none of them ever touch each other and they all end up vertically placed. We have obtained complexity results and plan to publish an article in the coming months.
Reinforcement Learning on Multi-Agent Systems
We established tight bounds on the number of agents needed in the Cooperative Guard Art Gallery Problem. We also ran simulations trained with RL to compare the
theoretical and empirical results. A publication is incoming in the next few months.
Those projects do not contain any significant result, but I made them public because they still reflect all the progress I have made since!
