Browsing by Subject "Resource allocation"
- Results Per Page
- Sort Options
Item Open Access Algorithms for Public Decision Making(2019) Fain, Brandon ThomasIn public decision making, we are confronted with the problem of aggregating the conflicting preferences of many individuals about outcomes that affect the group. Examples of public decision making include allocating shared public resources and social choice or voting. We study these problems from the perspective of an algorithm designer who takes the preferences of the individuals and the constraints of the decision making problem as input and efficiently computes a solution with provable guarantees with respect to fairness and welfare, as defined on individual preferences.
Concerning fairness, we develop the theory of group fairness as core or proportionality in the allocation of public goods. The core is a stability based notion adapted from cooperative game theory, and we show extensive algorithmic connections between the core solution concept and optimizing the Nash social welfare, the geometric mean of utilities. We explore applications in public budgeting, multi-issue voting, memory sharing, and fair clustering in unsupervised machine learning.
Regarding welfare, we extend recent work in implicit utilitarian social choice to choose approximately optimal public outcomes with respect to underlying cardinal valuations using limited ordinal information. We propose simple randomized algorithms with strong utilitarian social cost guarantees when the space of outcomes is metric. We also study many other desirable properties of our algorithms, including approximating the second moment of utilitarian social cost. We explore applications in voting for public projects, preference elicitation, and deliberation.
Item Open Access Eliciting and Aggregating Information for Better Decision Making(2018) Freeman, RupertIn this thesis, we consider two classes of problems where algorithms are increasingly used to make, or assist in making, a wide range of decisions. The first class of problems we consider is the allocation of jointly owned resources among a group of agents, and the second is the elicitation and aggregation of probabilistic forecasts from agents regarding future events. Solutions to these problems must trade off between many competing objectives including economic efficiency, fairness between participants, and strategic concerns.
In the first part of the thesis, we consider shared resource allocation, where we relax two common assumptions in the fair divison literature. Firstly, we relax the assumption that goods are private, meaning that they must be allocated to only a single agent, and introduce a more general public decision making model. This allows us to incorporate ideas and techniques from fair division to define novel fairness notions in the public decisions setting. Second, we relax the assumption that decisions are made offline, and instead consider online decisions. In this setting, we are forced to make decisions based on limited information, while seeking to retain fairness and game-theoretic desiderata.
In the second part of the thesis, we consider the design of mechanisms for forecasting. We first consider a tradeoff between several desirable properties for wagering mechanisms, showing that the properties of Pareto efficiency, incentive compatibility, budget balance, and individual rationality are incompatible with one another. We propose two compromise solutions by relaxing either Pareto efficiency or incentive compatibility. Next, we consider the design of decentralized prediction markets, which are defined by the lack of any single trusted authority. As a consequence, markets must be closed by popular vote amongst a group of anonymous, untrusted arbiters. We design a mechanism that incentivizes arbiters to truthfully report their information even when they have a (possibly conflicting) stake in the market themselves.
Item Open Access Microeconomic Models for Managing Shared Datacenters(2017) Llull, QiuyunAs demands for users’ applications’ data increase, the world’s computing platforms are moving towards more capable machines – servers and warehouse-scale datacenters. Diverse users share datacenters for complex computation and compete for shared resources. In some systems, such as public clouds where users pay for reserved hardware, management policies pursue performance goals. In contrast, private systems consist of users who voluntarily combine their resources and subscribe to a common management policy. These users reserve the right to opt-out from shared systems if resources are managed poorly. The system management framework needs to ensure fairness among strategic users, encouraging users to participate while guaranteeing individual performance and preserving the system’s performance. Microeconomic models are well suited for studying individual behavior and the allocation of scarce resources. In this thesis, we present three pieces of work on task colocation, resource allocation, and task scheduling problems to demonstrate the effectiveness of a microeconomic approach.
Colocating applications on shared hardware (i.e., chip-multiprocessors) improves server utilization but introduces resource contention into the memory subsystem. In the first work, we design a colocation framework based on cooperative game theory to manage shared resource contention. Our framework uses a recommendation system to predict individual applications preferences for colocated tasks. It then uses these predictions to drive novel colocation mechanisms to guarantee user fairness and preserve system performance. Attractive system outcomes encourage strategic users to participate in the datacenter.
Processor allocations are inefficient when they are based on static reservations because reservations are often conservative; users rarely know their application’s needs across time, especially when applications have complex phase behavior. In the second work, we propose a fast, lightweight performance prediction framework to help users capture their phase behaviors in parallel applications. We design a dynamic and distributed core allocation framework so that users can trade resources for better efficiency based on predicted performance. Our management framework provides efficient allocations and game-theoretic fairness guarantees. In the last work, we characterize applications’ sensitivity to non-uniform memory access (NUMA) in big memory servers. We develop performance and energy models for communication costs in a blade server. We use this model to perform case studies on NUMA-aware scheduling policies and task queue management. Our parameterized models lay the foundation for the coordinated design of scheduling policies and hardware configurations. This method can be further used to design locality-aware schedulers with microeconomic models, e.g., dynamic pricing strategies for city parking.
Item Open Access The Ethics of the Rule of Rescue: Guidelines for Use in the Medical Setting(2019-04-16) Flynn, SpencerThe “rule of rescue” (RR) is the human impulse to rescue an identifiable person facing imminent threat, regardless of associated costs. For example, no price is spared to save trapped miners, even though instituting improved mine safety protocols may be more cost-effective by preventing mine disasters in the first place. In healthcare institutions, the rule of rescue is controversial primarily because of the frequent conflict between the impulse to rescue versus cost-effective healthcare allocation, and secondarily because of the occasional conflict between the impulse to rescue versus fairness and equity concerns. Consider the issue of allocating ventilators in a flu pandemic—in the face of scarcity, should we attempt to rescue each victim as they come, or adhere to a cost-effectiveness scheme in distributing resources? Further, should we attempt to rescue each victim as they come if wealthy, insured patients disproportionately present for help, or should we enact more generalized policies to ensure fair outcomes at a population level? Here, I present the first full ethical treatment of the RR, including an analysis of the moral psychology of rescue and the RR as considered from both consequentialist and deontological lenses. Regarding psychology at the individual level, I conclude that the impulse to rescue does not track morally salient considerations, but instead is influenced primarily by heuristics and errors in processing statistics. At a societal level, I conclude that following the RR plays an important role in building social trust and motivating altruism. Further, I show that the RR is compatible with each major ethical theory, albeit only insofar as it is necessary for social cohesion and wellbeing. I end by presenting a summary checklist of the relevant considerations around employing the RR in healthcare institutional decision-making, as well as a few suggestions for future research programs.Item Open Access Young children, but not chimpanzees, are averse to disadvantageous and advantageous inequities.(J Exp Child Psychol, 2017-03) Ulber, Julia; Hamann, Katharina; Tomasello, MichaelThe age at which young children show an aversion to inequitable resource distributions, especially those favoring themselves, is unclear. It is also unclear whether great apes, as humans' nearest evolutionary relatives, have an aversion to inequitable resource distributions at all. Using a common methodology across species and child ages, the current two studies found that 3- and 4-year-old children (N=64) not only objected when they received less than a collaborative partner but also sacrificed to equalize when they received more. They did neither of these things in a nonsocial situation, demonstrating the fundamental role of social comparison. In contrast, chimpanzees (N=9) showed no aversion to inequitable distributions, only a concern for maximizing their own resources, with no differences between social and nonsocial conditions. These results underscore the unique importance for humans, even early in ontogeny, for treating others fairly, presumably as a way of becoming a cooperative member of one's cultural group.