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.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/D8125QSX |
| Date | January 2014 |
| Creators | Herrera Humphries, Tulia |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.002 seconds