In the assignment problem, a set of items must be allocated to unit-demand agents who express ordinal preferences (rankings) over the items. In the assignment problem with priorities, agents with higher priority are entitled to their preferred goods with respect to lower priority agents. A priority can be naturally represented as a ranking and an uncertain priority as a distribution over rankings. For example, this models the problem of assigning student applicants to university seats or job applicants to job openings when the admitting body is uncertain about the true priority over applicants. This uncertainty can express the possibility of bias in the generation of the priority ranking. We believe we are the first to explicitly formulate and study the assignment problem with uncertain priorities. We introduce two natural notions of fairness in this problem: stochastic envy-freeness (SEF) and likelihood envy-freeness (LEF). We show that SEF and LEF are incompatible and that LEF is incompatible with ordinal efficiency. We describe two algorithms, Cycle Elimination (CE) and Unit-Time Eating (UTE) that satisfy ordinal efficiency (a form of ex-ante Pareto optimality) and SEF; the well known random serial dictatorship algorithm satisfies LEF and the weaker efficiency guarantee of ex-post Pareto optimality. We also show that CE satisfies a relaxation of LEF that we term 1-LEF which applies only to certain comparisons of priority, while UTE satisfies a version of proportional allocations with ranks. We conclude by demonstrating how a mediator can model a problem of school admission in the face of bias as an assignment problem with uncertain priority.
翻译:在派任问题中,必须将一组物品分配给那些对项目表示优先偏好(级别)的单位-需求代理商。在派任问题中,优先级别较高的代理商有权享有其优先商品,而优先级别较低。优先级别可以自然地作为排名和不确定的优先级别,作为排位的分布。例如,在招生机构不确定是否真正优于申请人时,将学生申请人分配到大学席位或求职者职位空缺的问题就属于这种模式。这种不确定性可以表明在产生优先级别时存在偏差的可能性。我们认为,我们是第一个明确拟订和研究派任问题并具有不确定优先事项的单位。我们在此问题上引入了两种自然的公平概念:不端嫉妒(SEF)和可能无嫉妒(LEF)的优先级别。我们表明,SEF和LEF不相容,而LEF的升分级比比比,我们所熟知的SLEF的比级比级比,我们更能以最优的SLEFA级比。