Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
Embedding Cultural Diversity in Prototype-based Recommender Systems
Popularity bias in recommender systems can increase cultural overrepresentation by favoring norms from dominant cultures and marginalizing underrepresented groups. This issue is critical for platforms offering cultural p…
AttributeDiversityFairnessRecommendation SystemsFairSort: Learning to Fair Rank for Personalized Recommendations in Two-Sided Platforms
Traditional recommendation systems focus on maximizing user satisfaction by suggesting their favourite items. This user-centric approach may lead to unfair exposure distribution among the providers. On the contrary, a pr…
FairnessRecommendation SystemsRe-RankingOptimizing generalized Gini indices for fairness in rankings
There is growing interest in designing recommender systems that aim at being fair towards item producers or their least satisfied users. Inspired by the domain of inequality measurement in economics, this paper explores …
FairnessRecommendation SystemsTowards Robust Offline Evaluation: A Causal and Information Theoretic Framework for Debiasing Ranking Systems
Evaluating retrieval-ranking systems is crucial for developing high-performing models. While online A/B testing is the gold standard, its high cost and risks to user experience require effective offline methods. However,…
RetrievalEnhancing New-item Fairness in Dynamic Recommender Systems
New-items play a crucial role in recommender systems (RSs) for delivering fresh and engaging user experiences. However, traditional methods struggle to effectively recommend new-items due to their short exposure time and…
FairnessKnowledge DistillationRecommendation SystemsReinforcement Learning (RL)