Resource allocation and decision making for groups
Abstract/Contents
- Abstract
- Social choice theory concerns the design and analysis of methods for aggregating possibly conflicting individual preferences to reach a collective decision in a satisfactory manner. The discipline dates from Condorcet's voting paradox in the 18th century, and its paradigm was significantly influenced by Arrow's seminal work in the 1950s. While classical social choice theory focuses on the existence and non-existence of aggregation methods that satisfy certain axioms, over the past two decades computer scientists have studied the discipline from a computational perspective, leading to an active research area of computational social choice. This dissertation presents results of the classical flavor as well as those applying complexity concepts and algorithmic techniques. In the first part, we consider resource allocation settings. We depart from the usual framework in which each recipient of a bundle of items is represented by a single preference, and assume instead that each interested party consists of agents who may have different preferences on the items. We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, and derive bounds on the size of such a set under various informational and computational assumptions. We also investigate fairness guarantees in the allocation of indivisible items among groups. While the problem is more challenging than in the traditional setting with individual agents, we show that it is nevertheless possible to obtain positive results using asymptotic analysis and approximation. In the second part, we study decision making problems, where our goal is to choose the "best" alternatives from a given set of alternatives. We demonstrate that the bipartisan set, a method for selecting the best alternatives from a tournament proposed in the 1990s, is the unique method that satisfies a number of desirable properties. In addition, we consider issues related to choosing winners in sports competitions. We show that if tournament organizers have the freedom to determine the bracket of a single-elimination tournament, they can often make their favorite player win the tournament. We also tackle the problem of scheduling asynchronous round-robin tournaments, in which all games take place at different times, and propose schedules that perform well with respect to measures concerning the quality and fairness of the tournament.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2018; ©2018 |
| Publication date | 2018; 2018 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Suksompong, Warut |
|---|---|
| Degree supervisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Procaccia, Ariel D |
| Thesis advisor | Valiant, Gregory |
| Degree committee member | Procaccia, Ariel D |
| Degree committee member | Valiant, Gregory |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Warut Suksompong. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2018. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2018 by Warut Suksompong
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...