Random scheduling with deadlines under dichotomous preferences

A group of individuals share a deterministic server which is capable of serving one job per unit of time. Every individual has a job and a cut off time slot (deadline) where service beyond this slot is as worthless as not getting any service at all. Individuals are indifferent between slots which are not beyond their deadlines (compatible slots). A schedule (possibly random) assigns the set of slots to individuals by respecting their deadlines. We only consider the class of problems where for every set of relevant slots (compatible with at least one individual) there are at least as many individuals who have a compatible slot in that set: we ignore the case of underdemand. For this class, we characterize the random scheduling rule which attaches uniform probability to every efficient deterministic schedule (efficient uniform rule) by Pareto efficiency, equal treatment of equals, and probabilistic consistency (Chambers, 2004). We also show that a weaker version of the probabilistic consistency axiom is enough to achieve our result. Finally we show that efficient uniform rule is strategyproof.