Fairness in the Multi-Secretary Problem
This addresses fairness in online resource allocation, bridging social choice and algorithmic decision-making, though it is incremental in combining existing techniques.
The paper tackles the problem of applying fairness constraints to the multi-secretary online decision-making problem, proposing mechanisms that combine online algorithms with social choice rules like the Method of Equal Shares and Nash Rule, and shows they achieve strong theoretical guarantees and perform well in experiments.
This paper bridges two perspectives: it studies the multi-secretary problem through the fairness lens of social choice, and examines multi-winner elections from the viewpoint of online decision making. After identifying the limitations of the prominent proportionality notion of Extended Justified Representation (EJR) in the online domain, the work proposes a set of mechanisms that merge techniques from online algorithms with rules from social choice -- such as the Method of Equal Shares and the Nash Rule -- and supports them through both theoretical analysis and extensive experimental evaluation.