Abstract
dc:description.abstractResource allocation is a central problem in theoretical computer science, operations research, and economics. In a resource allocation problem, a platform designs efficient algorithms to assign limited resources to participating agents under uncertainty, aiming to maximize either total social welfare or total revenue. Among various algorithmic approaches to resource allocation, pricing schemes are widely used due to their simplicity and practicality. The platform posts prices for the resources it offers, and arriving agents decide whether to purchase items based on these prices. Theoretically, posted-price mechanisms for resource allocation operate as systems where a platform sets resource prices and agents with private valuations drawn from underlying distributions make utility-maximizing decisions. However, these distributions are typically unknown to the platform and must be learned, either from limited offline data or through real-time interactions. Traditional approaches to learning in pricing mechanisms often assume access to numerous samples drawn from each agent's valuation distribution. In contrast, real-world markets frequently present information that is sparse, noisy, or indirect. This raises a fundamental question: how can a platform learn effective pricing mechanisms under severe information constraints? This thesis addresses this question by studying the learnability of resource allocation mechanisms under three highly restrictive information models: 1. Learning from a single sample: The platform receives only a single sample from each agent's valuation distribution. 2. Learning from pricing queries: The platform posts prices and observes only agents' purchasing decisions as feedback. 3. Online learning with limited feedback: The platform dynamically adjusts prices over time while receiving partial observational feedback. \end{enumerate} This thesis demonstrates that near-optimal pricing algorithms can be efficiently learned within these restrictive frameworks. Together, these results provide a unified perspective on mechanism design under limited information and show that strong performance guarantees are attainable even under severe informational constraints.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, PhD
- Department thesis:degree_department
- Computer Science
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wang, Yifan
- Advisor dc:contributor.advisor
-
- Singla, Sahil
- Committee member dc:contributor.committeemember
-
- Vempala, Santosh
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82190