  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.
