TRUTH · Algorithmic Foundations of Large Markets
FP7 — People (Marie Curie Actions)
- Duration
- 2013-09-01 → 2017-08-31
- EU contribution
- €100,000
- Participants
- 1
- Scheme
- MC-CIG
Lines connect the coordinator with its partners.
Results in brief
Algorithmic Foundations of Large Markets
Large markets have recently emerged everywhere: auctions for selling licenses for electromagnetic spectrum have raised revenue of billions of dollars, Amazon and eBay have created markets that allow trade between individuals and companies, sponsored search have become an important source of revenue for Internet companies. Markets have been extensively studied in economics. Yet, technological developments enable interaction between large numbers of users, each might be collecting and storing huge amounts of data. This creates numerous exciting challenges. For example, many market construction tools considered in economics work well in small environments, but do not scale to large ones since they cannot be implemented in a computationally efficient way. Consequently, computational and informational bottlenecks receive an ad-hoc treatment in practice. The goal of this research program is establish strong foundations for Efficient Large Markets. More specifically, this research is about understanding the possibility of constructing computationally efficient truthful mechanisms. A truthful mechanism is one in which each bidder always has a dominant strategy: a strategy that is always maximizes his profit no matter what the other are doing. It belongs to the subfield of Algorithmic Mechanism Design, which lies on the intersection of computer science and game theory. The proposal has considered two specific avenues of research: 1) Proving limits on the power of computationally-efficient truthful mechanisms. Specifically, the community lacks the tools to prove impossibility results on the power of computationally efficient truthful mechanisms for the paradigmatic problem of combinatorial auctions. The only such bounds known are for mechanisms in which the access to the valuations is restricted to “value queries”. These bounds are obtained by using the Direct Hardness approach introduced in [Dobzinski, STOC’11]. The proposal suggested to develop tools and techniques for proving impossibility results for richer settings. 2) Developing new types of mechanisms and characterizing truthfulness. Our understanding of truthful mechanisms is lacking: for many important domains we do not know what is the set of truthful mechanisms and we only know about relatively simple families. The proposal suggested characterizing important domains and hopefully exposing new types of mechanisms. During this project, we have made progress on both fronts. In particular, we have presented some state of the art mechanisms for well-studied settings and provided several characterizations of truthful mechanisms. Other achievements of the proposal include (among others) research on non-interactive markets, the study of the bilateral trading problem and the introduction of mechanisms for combinatorial cost sharing. The latter work has won the EC’17 best paper award. The PI has invested many efforts into the establishment of a new research group at the Weizmann institute of Science. The group has become an integral part of the institute: several students have already graduated and the PI has recently received tenured from the institute.
Data: CORDIS, © European Union
Project objective
The goal of this proposal is to study the theoretical foundations of computationally efficient large markets. Market Design is a task that is traditionally carried out by economists and game theorists. However, as markets are becoming larger one must take into account computational considerations as well. The field that integrates methodologies from classic mechanism design and computer science is called Algorithmic Mechanism Design.Specifically, Game Theory and Mechanism Design study how selfish players interact. A traditional example is an auction for a single item, where mechanism design studies how to achieve a certain goal, e.g., social welfare or revenue maximization. However, when there are multiple heterogeneous items that may exhibit complementarities and substitutabilities, designing mechanisms becomes much more challenging. While classic mechanism design does offer some solutions, these solutions usually do not scale well, as they are not computationally efficient. The goal of this proposal is to understand whether this gap can be bridged.Most research in Algorithmic Mechanism Design focuses on dominant-strategy auctions, where every bidder always has a bid that is at least as good as any other possible bid. This proposal has two related objectives: (1) prove that in some settings there are no computationally efficient dominant-strategy mechanisms, and (2) develop techniques that will allow characterizing the set of dominant-strategy mechanisms in important auction domains, and design new families of dominant-strategy mechanisms.The proposal is expected to advance the state of the art in problems that are at the heart of Algorithmic Mechanism Design (and, more generally, at the heart of Algorithmic Game Theory).""
Original text from CORDIS.
Participants
- WEIZMANN INSTITUTE OF SCIENCE · RehovotCoordinatorIsrael
Links
Data: CORDIS, © European Union