Algorithmic Mechanism Design in Dynamic Environments

Christos-Alexandros Psomas

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2017-89
May 12, 2017

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-89.pdf

Over the past two decades, a new field has emerged between Computer Science and Game Theory: Algorithmic Mechanism Design. Despite tremendous growth and success in tackling a wide variety of problems, the vast majority of this literature to date focuses on static, one-time decisions. In many situations of interest, however, this simplification is quite unrealistic. For example, a search engine must choose how to allocate its advertising inventory in the face of changing search queries and advertiser budgets. In a cloud computing center resources need to be dynamically reallocated in response to the arrival of new computational tasks of varying priority. This thesis explores the interplay between incentives and the dynamic nature of decision-making in the design of efficient mechanisms.

In the first part of this thesis we study Dynamic Auction Design. We introduce a novel class of dynamic auction problems in which a monopolist is selling $m$ items to $n$ buyers in $m$ consecutive stages. We study this problem from several different perspectives: {\em Computational Complexity}, i.e. how hard is it to compute the optimal auction; {\em Competition Complexity}, i.e. how much additional competition is necessary for a standard Vickrey (second-price) auction at every stage to extract more revenue than the optimal auction; {\em Power of Adaptivity}, i.e. what is the revenue gap between adaptive and non-adaptive auctions; and {\em Power of Commitment}, i.e. what happens if the seller cannot commit to her future behavior - for example when contracts are not possible.

In the second part we study Dynamic Fair Division. We introduce a novel class of resource allocation problems in which resources are shared between agents dynamically arriving and departing over time. For a single resource, when $n$ agents are present, there is only one truly ``fair'' allocation: each agent receives $1/n$ of the resource. However, implementing this static solution over time is impractical: there are too many disruptions to existing allocations, since, for a new agent to get her fair share, all other agents must give up a small piece. What if, at every $c$ arrivals we could only reclaim resources from a fixed number of agents $d$? We provide algorithms that are non wasteful (they do not leave resources unallocated) and yet are almost optimal with respect to fairness, even for multiple, heterogeneous resources.

Advisor: Christos Papadimitriou


BibTeX citation:

@phdthesis{Psomas:EECS-2017-89,
    Author = {Psomas, Christos-Alexandros},
    Title = {Algorithmic Mechanism Design in Dynamic Environments},
    School = {EECS Department, University of California, Berkeley},
    Year = {2017},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-89.html},
    Number = {UCB/EECS-2017-89},
    Abstract = {Over the past two decades, a new field has emerged between Computer Science and Game Theory: Algorithmic Mechanism Design. Despite tremendous growth and success in tackling a wide variety of problems, the vast majority of this literature to date focuses on static, one-time decisions. In many situations of interest, however, this simplification is quite unrealistic. For example, a search engine must choose how to allocate its advertising inventory in the face of changing search queries and advertiser budgets. In a cloud computing center resources need to be dynamically reallocated in response to the arrival of new computational tasks of varying priority. This thesis explores the interplay between incentives and the dynamic nature of decision-making in the design of efficient mechanisms.

In the first part of this thesis we study Dynamic Auction Design. We introduce a novel class of dynamic auction problems in which a monopolist is selling $m$ items to $n$ buyers in $m$ consecutive stages. We study this problem from several different perspectives: {\em Computational Complexity}, i.e. how hard is it to compute the optimal auction; {\em Competition Complexity}, i.e. how much additional competition is necessary for a standard Vickrey (second-price) auction at every stage to extract more revenue than the optimal auction; {\em Power of Adaptivity}, i.e. what is the revenue gap between adaptive and non-adaptive auctions; and
{\em Power of Commitment}, i.e. what happens if the seller cannot commit to her future behavior - for example when contracts are not possible.

In the second part we study Dynamic Fair Division. We introduce a novel class of resource allocation problems in which resources are shared between agents dynamically arriving and departing over time.  For a single resource, when $n$ agents are present, there is only one truly ``fair'' allocation: each agent receives $1/n$ of the resource. However, implementing this static solution over time is impractical: there are too many disruptions to existing allocations, since, for a new agent to get her fair share, all other agents must give up a small piece. What if, at every $c$ arrivals we could only reclaim  resources from a fixed number of agents $d$? We provide algorithms that are non wasteful (they do not leave resources unallocated) and yet are almost optimal with respect to fairness, even for multiple, heterogeneous resources.}
}

EndNote citation:

%0 Thesis
%A Psomas, Christos-Alexandros
%T Algorithmic Mechanism Design in Dynamic Environments
%I EECS Department, University of California, Berkeley
%D 2017
%8 May 12
%@ UCB/EECS-2017-89
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-89.html
%F Psomas:EECS-2017-89