Algorithmics, Social choice, Market Design, and Other Topics

Our new working paper.  Strategyproof and Proportionally Fair Facility Location Haris Aziz, Alexander Lam, Barton E. Lee, and Toby Walsh, October 2021 http://www.cse.unsw.edu.au/~haziz/fairFLP.pdf Abstract: We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportional fairness. We present several characterization results for mechanisms that satisfy strategyproofness and varying levels of proportional fairness. We also characterize one of the mechanisms as  the  unique  equilibrium outcome for any mechanisms that satisfies natural fairness and monotonicity properties. Finally, we identify strategyproof and proportionally fair mechanisms that provide the best welfare-optimal approximation among all mechanisms that satisfy the corresponding fairness axiom.

  Our work on a bounded envy-free fair division algorithm has been covered in the book "Landscape of 21st Century Mathematics - Selected Advances, 2001–2020" (author: Bogdan Grechuk, publisher: Springer, link: https://www.springer.com/gp/book/9783030806262). The book covers a list of "great recent theorems from all areas of mathematics."