Back to search

Cornell University

Efficiency Of Mechanisms In Complex Markets

Abstract

dc:description.abstract

We provide a unifying theory for the analysis and design of efficient simple mechanisms for allocating resources to strategic players, with guaranteed good properties even when players participate in many mechanisms simultaneously or sequentially and even when they use learning algorithms to identify how to play and have incomplete information about the parameters of the game. These properties are essential in large scale markets, such as electronic marketplaces, where mechanisms rarely run in isolation and the environment is too complex to assume that the market will always converge to the classic economic equilibrium or that the participants will have full knowledge of the competition. We propose the notion of a smooth mechanism, and show that smooth mechanisms possess all the aforementioned desiderata in large scale markets. We further give guarantees for smooth mechanisms even when players have budget constraints on their payments. We provide several examples of smooth mechanisms and show that many simple mechanisms used in practice are smooth (such as formats of position auctions, uniform price auctions, proportional bandwidth allocation mechanisms, greedy combinatorial auctions). We give algorithmic characterizations of which resource allocation algorithms lead to smooth mechanisms when accompanied by appropriate payment schemes and show a strong connection with greedy algorithms on matroids. Last we show how inefficiencies of mechanisms can be alleviated when the market grows large in a canonical manner.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Syrgkanis, Vasileios
Chair dc:contributor.chair
  • Tardos, Eva
Committee members dc:contributor.committeemember
  • Sirer, Emin G.
  • Blume, Lawrence Edward
  • Kleinberg, Robert David

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8793480

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Syrgkanis, Vasileios. Efficiency Of Mechanisms In Complex Markets. Doctor of Philosophy thesis, Cornell University, 2014. https://hdl.handle.net/1813/38938