The project studies the computational complexity of finding stable and desirable outcomes in economic environments. Examples of such environments are:
- auctions of goods, for example "traditional" goods such as cars, paintings etc, or other goods such as assets or spectrum.
- markets involving several buyers and sellers, for example markets for consumption goods, assets or advertising space.
- settings where a set of resources are to be divided fairly among a set of participants, who have different preferences for those resources. For instance, one might be interested in distributing tasks between employees of an enterprise or assigning credit for their work on a project, splitting rent or fare between members of a household, or splitting inheritance between members of a family.
Stable outcomes are outcomes that all the participants of these environments find acceptable or desirable in some sense.
- In auctions, such outcomes are the Nash equilibria of the strategic interaction between the buyers. These are sets of monetary bids that the buyers are satisfied with, given the bids of the other bidders.
- For markets, these outcomes are competitive equilibria, where at the chosen price for each good, its supply equals its demand, and the participants acquire the best possible bundles of goods at the given prices.
- For division of resources, stable outcomes are partitions of the resources that each participant considers to be fair, according to their own preferences over the possible ways that the resources could be partitioned.
These economic environments have been studied extensively by a large interdisciplinary community spread across economics, mathematics and computer science, over the better part of the last century. Classic works in economics and mathematics have proven that for very general environments, such stable outcomes always exist, i.e., it is possible to satisfy all the participants of the environment at the same time.
The research in computer science has been instrumental in formulating and studying the main follow up question: "How can we find those stable outcomes?". In simple words, we are concerned with whether it is possible to design efficient algorithms for finding these outcomes, that is, algorithms that complete the task in a reasonable amount of time when run on a computer. Still, despite significant efforts from the community, we do not have efficient algorithms for finding stable outcomes in many of the major economic environments like the ones highlighted above, and we do not know if it is even possible to design them or not.
This project aims to provide concrete answers to this very question, for the four major economic environments of interest, namely
1) auctions
2) markets
3) fair division of divisible resources
4) fair division of indivisible resources
Specifically, we will design efficient algorithms for finding the corresponding stable outcomes for these environments, or we will prove that such algorithms are unlikely to exist, via so-called computational hardness results.
Our results will inform the research community on which of these problems are "easy" and which are "hard" to solve by a computer. They will aid researchers and practitioners in (a) understanding the inherent challenges of trying to come up with good solutions for those environments, (b) formulating the appropriate follow-up questions for these environments, and (c) identifying the special cases of interest for which such efficient algorithms are actually possible.
|