The Assignment Game: New Mechanisms for Equitable Core Imputations
<|reference_start|>The Assignment Game: New Mechanisms for Equitable Core Imputations: The set of core imputations of the assignment game forms a (non-finite) distributive lattice. So far, efficient algorithms were known for computing only its two extreme imputations; however, each of them maximally favors one side and disfavors the other side of the bipartition, leading to inequitable profit sharing. Another issue is that a sub-coalition consisting of one player (or a set of players from the same side of the bipartition) can make zero profit, therefore a core imputation is not obliged to give them any profit. Hence core imputations make no fairness guarantee at the level of individual agents. This raises the question of computing {\em more equitable core imputations}.   In this paper, we give combinatorial (i.e., the mechanism does not invoke an LP-solver) polynomial time mechanisms for computing the leximin and leximax core imputations for the assignment game. These imputations achieve ``fairness'' in different ways: whereas leximin tries to make poor agents more rich, leximax tries to make rich agents less rich. In general, the two imputations are different.   Our mechanisms were derived by a suitable adaptation of the classical primal-dual paradigm from combinatorial optimization. The ``engine'' driving them involves recent insights, obtained via complementarity, into core imputations \cite{Va.New-characterizations} and the pristine combinatorial structure of matching. We have identified other natural games which could benefit from our approach.<|reference_end|>
@article{vazirani2024the,
    title={The Assignment Game: New Mechanisms for Equitable Core Imputations},
    author={Vijay V. Vazirani},
    journal={arXiv preprint arXiv:2402.11437},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11437},
    primaryClass={cs.GT econ.TH}
}