Title: On the Kidney Exchange Problem and Online Minimum Energy Scheduling
Description: The allocation and management of scarce resources are of central importance in the design of policies to improve social well-being. This dissertation consists of three essays; the first two deals with the problem of allocating kidneys and the third one on power management in computing devices. Kidney exchange programs are an attractive alternative for patients who need a kidney transplant and who have a willing, but medically incompatible, donor. A registry that keeps track of such patient-donor pairs can nd matches through exchanges amongst such pairs. This results in a quicker transplant for the patients involved, and equally importantly, keeps such patients from the long wait list of patients without an intended donor. As of March 2014, there were at least 99,000 candidates waiting for a kidney transplant in the U.S. However, in 2013 only 16,893 transplants were conducted. This imbalance between supply and demand among other factors, has driven the development of multiple kidney exchange programs in the U.S. and the subsequent development of matching mechanisms to run the programs.

In the first essay we consider a matching problem arising in kidney exchanges between hospitals. Focusing on the case of two hospitals, we construct a strategy-proof matching mechanism that is guaranteed to return a matching that is at least 3/4 the size of a maximum cardinality matching. It is known that no better performance is possible if one focuses on mechanisms that return a maximal matching, and so our mechanism is best possible within this natural class of mechanisms. For path-cycle graphs we construct a mechanism that returns a matching that is at least 4/5 the size of max-cardinality matching. This mechanism does not necessarily return a maximal matching. Finally, we construct a mechanism that is universally truthful on path-cycle graphs and whose performance is within 2/3 of optimal. Again, it is known that no better ratio is possible. In most of the existing literature, mechanisms are typically evaluated by their overall performance on a large exchange pool, based on which conclusions and recommendations are drawn.

In our second essay, we consider a dynamic framework to evaluate extensively used kidney exchange mechanisms. We conduct a simulation-based study of a dynamically evolving exchange pool during 9 years. Our results suggest that some of the features that are critical in a mechanism in the static setting have only a minor impact in its longrun performance when viewed in the dynamic setting. More importantly, features that are generally underestimated in the static setting turn to be relevant when we look at dynamically evolving exchange pool. For example, the pairs' arrival rates. In particular we provide insights into the eect on the waiting times and the probability to receive an oer of controllable features such as the frequency at which matching are run, the structures through which pairs could be matched (cycles or chains) as well as inherent features such as the pairs ABO-PRA characteristics, the availability of altruistic donors, and wether or not compatible pairs join the exchange etc.

We evaluate the odds to receive an oer and the expected time to receive an oer for each ABO-PRA type of pairs in the model. Power management in computing devices aims to minimize energy consumption to perform tasks, meanwhile keeping acceptable performance levels. A widely used power management strategy for devices, is to transit the devices and/or components to lower power consumption states during inactivity periods. Transitions between power states consume energy, thus, depending on such costs, it may be advantageous to stay in high power state during some inactivity periods. In our third essay we consider the problem of minimizing the total energy consumed by a 2-power state device, to process jobs that are sent over time by a constrained adversary. Jobs can be preempted, but deadlines need to be met. In this problem, an algorithm must decide when to schedule the jobs, as well as a sequence of power states, and the discrete time thresholds at which these states will be reached. We provide an online algorithm to minimize the energy consumption when the cost of a transition to the low power state is small enough.

In this case, the problem of minimizing the energy consumption is equivalent to minimizing the total number of inactivity periods. We also provide an algorithm to minimize the energy consumption when it may be advantageous to stay in high power state during some inactivity periods. In both cases we provide upper bounds on the competitive ratio of our algorithms, and lower bounds on the competitive ratio of all online algorithms.