Algorithms and hardness results for resource allocation and facility location problems

Simple item page
dc.contributor.advisorPlaxton, C. Greg
dc.creatorSinha, Vaibhav Birendrakumar
dc.creator.orcid0000-0003-3499-6136
dc.date.accessioned2021-09-07T19:25:48Z
dc.date.available2021-09-07T19:25:48Z
dc.date.created2021-05
dc.date.issued2021-05-12
dc.date.submittedMay 2021
dc.date.updated2021-09-07T19:25:49Z
dc.description.abstractMany real-life scenarios involve making decisions based on agent preferences, for example, electing leaders, developing public facilities, and allocating resources in market. In this thesis, we consider two such problems where we want to make decisions based on agent preferences. In our first problem, we study a variant of the classic housing markets model. Each agent is initially assigned a unique house, and the houses form a graph. Each agent has strict preferences over the houses. Two agents can swap houses if the swap is Pareto-improving and the houses are adjacent. We study three reachability questions in the context of various graph structures. In our second problem, we study a variant of the facility location game. In this setting, a central planner has to build a set of heterogeneous facilities. Every agent reports the set of facilities that they consider "obnoxious". The goal is to design strategyproof and group-strategyproof mechanisms that maximize either the total utility of agents or the minimum utility of agents.
dc.description.departmentComputer Sciences
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/87491
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/14435
dc.language.isoen
dc.subjectResource allocation
dc.subjectFacility location
dc.subjectMechanism design
dc.subjectGame theory
dc.titleAlgorithms and hardness results for resource allocation and facility location problems
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Sciences
thesis.degree.disciplineComputer Science
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelMasters
thesis.degree.nameMaster of Science in Computer Sciences

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
SINHA-THESIS-2021.pdf
Size:
406.76 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UT Electronic Theses and Dissertations