Three Essays on Rationing, Matching and Scheduling

Abstract

This dissertation consists of three chapters. In the first chapter, we are considering the problem of rationing a disposable indivisible good under satiated preferences. A standard of gains rationing (s.g.r.) method allocates successive units of good by following a linear ordering of individuals and non-zero demand pairs. The dual of a s.g.r. method is a standard of losses rationing (s.l.r.) method, it follows the same linear ordering to successively allocate units of deficit. In our main result, Theorem 1, we provide three characterizations of s.l.r. methods. The first characterization is by resource monotonicity (RM), strategy-proofness (SP), non-bossiness (NB), and a property we introduce in this chapter, independence of fully satisfied demand (IFSD). IFSD is weaker than both the well known consistency (CSY) axiom and a generalized version of RM that we introduce in this chapter, strong resource monotonicity (SRM). We offer the other two characterizations by replacing RM and IFSD in the first characterization with SRM, and by replacing IFSD and NB in the first characterization with CSY. We obtain an analogue of Theorem 1 for s.g.r. methods by using the duals of the axioms in Theorem 1. By combining SP and its dual with IFSD and its dual or with SRM or with the dual of SRM we provide three characterizations of fixed order priority rationing methods in Theorem 2.

The second chapter is on roommate problems. We characterize Pareto efficient and group strategy-proof rules for roommate problems with an even number of individuals where individuals find all their potential partners acceptable. We define a priority rule (sequential dictatorship) as a recursive algorithm that matches individuals in successive rounds. Specifically in every round an individual with priority is matched to his top ranked partner among available individuals and the order of individuals with priority is a function of the prior matches. We then show that the class of Pareto efficient and group strategy-proof rules is equivalent to the family of priority rules.

In our final chapter we consider a scheduling problem with deadlines. 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 (uniform rule) by Pareto efficiency, equal treatment of equals, and probabilistic consistency (Chambers (2004)). We also provide an alternative description for the uniform rule by a ball drawing algorithm.