English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The past few years have seen a surge of work on fairness in allocationproblems where items must be fairly divided among agents having individualpreferences. In comparison, fairness in settings with preferences on bothsides, that is, where agents have to be matched to other agents, has receivedmuch less attention. Moreover, two-sided matching literature has largelyfocused on ordinal preferences. This paper initiates the study of fairness instable many-to-one matchings under cardinal valuations. Motivated by real-worldsettings, we study leximin optimality over stable many-to-one matchings. Wefirst investigate matching problems with ranked valuations where all agents oneach side have the same preference orders or rankings over the agents on theother side (but not necessarily the same valuations). Here, we provide acomplete characterisation of the space of stable matchings. This leads to FaSt,a novel and efficient algorithm to compute a leximin optimal stable matchingunder ranked isometric valuations (where, for each pair of agents, thevaluation of one agent for the other is the same). Building upon FaSt, wepresent an efficient algorithm, FaSt-Gen, that finds the leximin optimal stablematching for a more general ranked setting. When there are exactly two agentson one side who may be matched to many agents on the other, strict preferencesare enough to guarantee an efficient algorithm. We next establish that, in theabsence of rankings and under strict preferences (with no restriction on thenumber of agents on either side), finding a leximin optimal stable matching isNP-Hard. Further, with weak rankings, the problem is strongly NP-Hard, evenunder isometric valuations. In fact, when additivity and non-negativity are theonly assumptions, we show that, unless P=NP, no efficient polynomial factorapproximation is possible.

On Achieving Leximin Fairness and Stability in Many-to-One Matchings