Tootfinder

The Cost and Complexity of Minimizing Envy in House Allocation
Jayakrishnan Madathil, Neeldhara Misra, Aditi Sethia
https://arxiv.org/abs/2406.09744 https:…

The Cost and Complexity of Minimizing Envy in House Allocation
We study almost-envy-freeness in house allocation, where $m$ houses are to be allocated among $n$ agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations of envy-freeness. But typical relaxations such as envy-free up to one good do not make sense for house allocation, as every agent is required to receive exactly one house. Hence we turn to different aggregate measures of envy as markers of fairness. In p…

A Little Aggression Goes a Long Way
Jyothi Krishnan, Neeldhara Misra, Saraswati Girish Nanoti
https://arxiv.org/abs/2406.05742 https://

A Little Aggression Goes a Long Way
Aggression is a two-player game of troop placement and attack played on a map (modeled as a graph). Players take turns deploying troops on a territory (a vertex on the graph) until they run out. Once all troops are placed, players take turns attacking enemy territories. A territory can be attacked if it has $k$ troops and there are more than $k$ enemy troops on adjacent territories. At the end of the game, the player who controls the most territories wins. In the case of a tie, the player with …