Constrained Serial Dictatorships can be Fair
When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Justified Fairness in House Allocation Problems: two Characterizations of Strategy-proof Mechanisms
We consider the house allocation problems with strict preferences, where monetary transfers are not allowed. We propose two properties in the spirit of justified fairness. Interestingly, together with other well-studied …
FairnessStrategy-proof Popular Mechanisms
We consider the allocation of indivisible objects when agents have preferences over their own allocations, but share the ownership of the resources to be distributed. Examples might include seats in public schools, facul…
Allocating Indivisible Items in Categorized Domains
We formulate a general class of allocation problems called categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent…
Constrained Serial Rule on the Full Preference Domain
We study the problem of assigning objects to agents in the presence of arbitrary linear constraints when agents are allowed to be indifferent between objects. Our main contribution is the generalization of the (Extended)…
FairnessAccept or Deny? Evaluating LLM Fairness and Performance in Loan Approval across Table-to-Text Serialization Approaches
Large Language Models (LLMs) are increasingly employed in high-stakes decision-making tasks, such as loan approvals. While their applications expand across domains, LLMs struggle to process tabular data, ensuring fairnes…