AF: Small: Algorithm and Incentive Design for Modern Resource Allocation Platforms

The last decade has witnessed the rapid development of large-scale online platforms and marketplaces for effective allocation of resources, whether it be cloud-computing systems for allocating CPU, disk, and network bandwidth among competing jobs; online marketplaces for the sharing economy that match sellers of services such as rides, lodging, and skills with buyers of these services; or large-scale advertising platforms that match advertisers with publishers of content. This project will address the key challenges in algorithm and incentive design for these platforms, in particular those arising from three fundamental sources.

The first is uncertainty in the characteristics of the set of participants interacting with the platform, whether it be job durations in a cloud-computing system, or buyer and seller valuations and the asymmetric knowledge of these in an online marketplace. The second is the dynamic nature of the set of participants, where jobs in a cloud system, as well as buyers and sellers in an online marketplace, dynamically arrive and depart.

The third is multi-dimensionality of the resource-allocation problems, where jobs or buyers derive utility from several types of resources simultaneously. This project will develop holistic algorithmic approaches to address these challenges, while ensuring the resulting formulations remain computationally tractable. The resulting algorithmic techniques will provide guiding principles for obtaining practical improvements in the performance of these platforms.

The project has an integrated education and outreach plan, whereby the next generation of students will be equipped with the relevant algorithmic skills via effective teaching and mentorship. Results from the project will also be broadly disseminated via publications in major conferences and journals; via organizing workshops that bring together researchers with diverse backgrounds; and finally, via developing course materials and tutorials.

At a more technical level, the project is developing approaches that go beyond the worst-case via novel stochastic models of uncertainty and dynamics that will circumvent the computational hardness and existential impossibility results in worst-case models. The project is first developing new stochastic models for scheduling in data centers based on the multi-armed bandit framework, where jobs with multidimensional resource requirements dynamically arrive and have dependencies between them.

The project is then developing an algorithmic theory for the strategic aspects of two-sided marketplaces arising from sharing economy applications. This involves developing Bayesian models for how the platform can use asymmetric information about the marketplace to influence the outcome of mechanisms run by sellers. It also involves developing techniques to address the dynamic aspect of matching and pricing buyers and sellers, when both sides arrive and depart over time according to stochastic processes.

The project is borrowing modeling tools from and contributing tools to the topics of optimal control theory, Bayesian auctions and persuasion, dynamic pricing, and stochastic matchings. The key novelty of the project is in developing techniques at the intersection of well-studied and classic disciplines, such as at the intersection of stochastic optimization, learning theory, and scheduling theory; or optimal control, approximation algorithms, and computational economics.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.