Group scheduling and assignment : complexity and algorithms
Abstract/Contents
- Abstract
- Scheduling an event for a group of agents is a challenging problem. It tends to be tedious and time-consuming for everyone involved. In practice, procrastination and strategic behavior of agents are often a problem, but even if we assume that agents are truthful, prompt, and indifferent among the possible outcomes, the group scheduling problem exhibits an interesting algorithmic problem. Assuming truthful and prompt behavior of agents, we consider settings where the event organizer has probabilistic estimates on availability of agents and is allowed to query agents for their actual availability. Naturally, it is desirable to minimize the (expected) number of queries so as to optimize the time and inconvenience caused by the scheduling process. We consider two models that are motivated by an existing tool that is widely used in practice today, and offer intuitive and computationally efficient algorithms that are applicable to group scheduling settings. Furthermore, we also discuss how our algorithms can be used in different domains than group scheduling. Another set of issues arise in group assignment problems. Imagine that an event organizer wishes to assign agents to social activities. Agents may have preferences over activities as well as the number of participants in the activity they are assigned to. The organizer would like to assign as many agents to activities as possible, but not at the cost of upsetting some agents by disregarding their preferences. Finding a Nash stable solution is an interesting algorithmic question of its own in this setting, and it has been studied in the literature that many variants of the problem are computationally difficult (i.e., NP-hard). In this thesis, we take an extra step to investigate some of these problems by analyzing their parameterized complexity when the size of a solution is parameterized. Parameterized complexity offers a finer scale than classical complexity, and we classify many variants of the group assignment problem into different complexity classes in the W-hierarchy. Motivated by this problem, we also consider another class of group assignment problems in which agents have friends and enemies. Friend and enemy relationships introduce combinatoric complications into the setting, and we show that the number of friends and/or enemies each agent has plays an important role in complexity of these problems. In addition, we also show that symmetric relationship reduces the complexity of these problems to a great extent. Lastly, we consider strategic agents in the group assignment problems. We show that in general it is impossible to obtain a strategy-proof mechanism that can also find a Nash stable solution in these settings, even if we restrict the preferences of agents. The only positive result we show is when there is only one activity and all agents prefer more participants than fewer participants -- in this case, there exists a strategy-proof mechanism that is socially optimal and computationally efficient.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2016 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Lee, Hooyeon |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Goel, Ashish |
| Primary advisor | Williams Vassilevska, Virginia, 1980- |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Williams Vassilevska, Virginia, 1980- |
| Thesis advisor | Shoham, Yoav |
| Advisor | Shoham, Yoav |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Hooyeon Lee. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2016. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2016 by Hooyeon Lee
- 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...