Archive

Posts Tagged ‘game theory’

Competitive Auctions

September 17th, 2009 No comments

This week I will present the Theory Discussion Group about Competitive Auctions. It is mainly a serie of results in papers from Jason Hartline, Andrew Goldberg, Anna Karlin, Amos Fiat, … The first paper is Competitive Auctions and Digital Goods and the second is Competitive Generalized Auctions. My objective is to begin with a short introduction about Mechanism Design, the concept of truthfulness and the characterization of Truthful Mechanisms for Single Parameter Agents. Then we describe the Random Sampling Auction for Digital Goods and in the end we discuss open questions. I thought writting a blog post was a good way of organizing my ideas to the talk.

1. Mechanism Design and Truthfulness

A mechanism is an algorithm augmented with economic incentives. They are usually applied in the following context: there is an algorithmic problem and the input is distributed among several agents that have some interest in the final outcome and therefore they may try manipulate the algorithm. Today we restrict our attention to a specific class of mechanisms called single parameter agents. In that setting, there is a set {N} consisting of {n} agents and a service. Each agent {i \in N} has a value {v_i} for receiving the service and {0} otherwise. We can think of {v_i} as the maximum player {i} is willing to pay for that service. We call an environment {\mathcal{X} \subseteq 2^N} the subsets of the bidders that can be simultaneously served. For example:

  1. Single item auction: {\mathcal{X} =\{S; \vert S \vert \leq 1\}}
  2. Multi item auction: {\mathcal{X} =\{S; \vert S \vert \leq k\}}
  3. Digital goods auction: {\mathcal{X} =2^N}
  4. Matroid auctions: {\mathcal{X}} is a matroid on {N}
  5. Path auctions: {N} is the set of edges in a graph and {\mathcal{X}} is the set of {s-t}-paths in the graph
  6. Knapsack auctions: there is a size {s_i} for each {i \in N} and {S \in \mathcal{X}} iff {\sum_{i \in S} s_i \leq C} for a fixed {C}

Most mechanism design problems focus in maximizing (or approximating) the social welfare, i.e., finding {S \in \mathcal{X}} maximizing {\sum_{i \in S} v_i}. Our focus here will be maximizing the revenue of the auctioneer. Before we start searching for such a mechanism, we should first see which properties it is supposed to have, and maybe even first that that, define what we mean by a mechanism. In the first moment, the agents report their valuations {v_i} (which can be their true valuations or lies), then the mechanism decides on an allocation {S \subseteq N} (in a possibly randomized way) and charges a payment {P_i} for each allocated agents. The profit of the auctioneer is {\sum_{i \in S} P_i} and the utility of a bidder is:

\displaystyle u_i = \left\{ \begin{aligned} v_i - P_i &, i \in S \\ 0 &, i \notin S \end{aligned} \right.

The agents will report valuations so to maximize their final utility. We could either consider a general mechanism e calculate the profit/social welfare in the game induced by this mechanism or we could design an algorithm that gives incentives for the bidders to report their true valuation. The revelation principle says there is no loss of generality to consider only mechanisms of the second type. The intuition is: the mechanisms of the first type can be simulated by mechanisms of the second type. So, we restrict our attention to mechanisms of the second type, which we call truthful mechanisms. This definnition is clear for deterministic mechanisms but not so clear for randomized mechanisms. There are two such definitions:

  • Universal Truthful mechanisms: distribution over deterministic truthful mechanisms, i.e., some coins are tossed and based on those coins, we choose a deterministic mechanism and run it. Even if the players knew the random coins, the mechanism would still be truthful.
  • Truthful in Expectation mechanisms: Let {u_i(b_i)} be the utility of agent {i} if he bids {b_i}. Since it is a randomized mechanism, then it is random variable. Truthful in expectation means that {\mathop{\mathbb E}[u_i(v_i)] \geq \mathop{\mathbb E}[u_i(b_i)], \forall b_i}.

Clearly all Universal Truthful mechanisms are Truthful in Expectation but the converse is not true. Now, before we proceed, we will redefine a mechanism in a more formal way so that it will be easier to reason about:

Definition 1 A mechanism {\mathcal{M}} is a function that associated for each {v \in {\mathbb R}^N} a distribution over elements of {\mathcal{X}}.

Theorem 2 Let {x_i(v) = \sum_{i \in S \in \mathcal{X}} Pr_{\mathcal{M}(v)}[S]} be the probability that {i} is allocated by the mechanism given {v} is reported. The mechanism is truthful iff {x_i(v)} is monotone and each allocated bidder is charged payment:

\displaystyle P_i = v_i - \frac{1}{x_i(v_i, v_{-i})} \int_0^{v_i} x_i(w, v_{-i}) dw

This is a classical theorem by Myerson about the characterization of truthful auctions. It is not hard to see that the auction define above is truthful. We just need to check that {x_i(v_i, v_{-i}) (v_i - P(v_i, v_{-i})) \geq x_i(v'_i, v_{-i}) (v_i - P(v'_i, v_{-i}))} for all {v'_i}. The opposite is trickier but is also not hard to see.

Note that this characterization implies the following characterization of deterministic truthful auctions, i.e., auctions that map each {v \in {\mathbb R}^N} to a set {S \in \mathcal{X}}, i.e., the probability distribution is concentrated in one set.

Theorem 3 A mechanism is a truthful deterministic auction iff there is a functions {f_i(b_{-i})} such that for each we allocate to bidder {i} iff {b_i \geq f_i(b_{-i})} and in case it is allocated, we charge payment {f_i(b_{-i})}.

It is actually easy to generate this function. Given a mechanism, {b_i \mapsto x_i(b_i, b_{-i})} is a monotone and is a {\{0,1\}}-function. Let {f_i(b_{-i})} the point where it transitions from {0} to {1}. Now, we can give a similar characterization for Universal Truthful Mechanism:

Theorem 4 A mechanism is a universal truthful randomized auction if there are functions {f_i(r,b_{-i})} such that for each we allocate to bidder {i} iff {b_i \geq f_i(r,b_{-i})} and in case it is allocated, we charge payment {f_i(r,b_{-i})}, where {r} are random bits.

2. Profit benchmarks

Let’s consider a Digital Goods auction, where {\mathcal{X} = 2^N}. Two natural goals for profit extraction would be {\mathcal{T}(v) = \sum_i v_i} and {\mathcal{F}(v) = \max_i i v_i} where we can think of {v_1 \geq v_2 \geq \hdots \geq v_n}, the first is the best profit you can extract charging different prices and the second is the best profit you can hope to extract by charging a fixed price. Unfortunately it is impossible to design a mechanism that even {O(1)}-approximates both benchmarks on every input. The intuition is that {v_1} can be much larger then the rest, so there is no way of setting {f_1(b_{-1})} in a proper way. Under the assumption that the first value is not much larger than the second, we can do a good profit approximation, though. This motivates us to find an universal truthful mechanism that approximates the following profit benchmark:

\displaystyle \mathcal{F}^{(2)}(v) = \max_{i \geq 2} i v_i

which is the highest single-price profit we can get selling to at least {2} agents. We will show a truthful mechanism that {4}-approximates this benchmark.

3. Profit Extractors

Profit extractor are building blocks of many mechanisms. The goal of a profit extractor is, given a constant target profit {C}, extract that profit from a set of agents if that is possible. In this first moment, let’s see {C} as an exogenous constant. Consider the following mechanism called CostShare{_C (v)}: find the largest {k} s.t. {k \cdot v_k \geq C}. Then allocate to

Lemma 5 CostShare{_C} is a truthful profit-extractor that can extract profit {C} whenever {\mathcal{F}(v) = \max_i i v_i \geq C}.

Proof: It is clear that it can extract profit at most {C} if {\mathcal{F}(v) \geq C}. We just need to prove it is a truthful mechanism and this can be done by checking the characterization of truthful mechanisms. Suppose that under CostShare{_C (v)} exacly {k} bidders are getting the item, then let’s look at a bidder {i}. If bidder {i} is not getting the item, then his value is smaller than {C/k}, otherwise we could incluse all bidders up to {i} and sell for a price {C/k_1} for some {k_1 > k}. It is easy to see that bidder {i} will get the item just if he changes his value {v_i} to some value greater or equal than {C/k}.

On the other hand, it {i} is currently getting the item under {v}, then increasing his value won’t make it change. It is also clear that for any value {v_i \geq C/k}, he will still get the item. For {v_i < C/k} he doesn’t get it. Suppose it got, then at least {k+1} people get the item, because the price they sell it to {i} must be less than {v_i < C/k}. Thefore, increasing {v_i} back to its original value, we could still sell it to {k+1} players, what is a contradiction, since we assumed we were selling to {k} players.

We checked monotonicity and we also need to check the payments, but it is straightforward to check they satisfy the second condition, since {x_i(v_i) = 1} for {v_i \geq C/k} and zero instead. \Box

4. Random Sampling Auctions

Now, using that profit extractor as a building block, the main idea is to estimate {C} smaller than {\mathcal{F}(v)} for one subset of the agents and extract that profit from them using a profit extractor. First we partition {N} is two sets {N'} and {N''} tossing a coin for each agent to decide in which set we will place it, then we calculate {\mathcal{F}' = \mathcal{F}(v_{N'})} and {\mathcal{F}'' = \mathcal{F}(v_{N''})}. Now, we run CostShare{_{\mathcal{F}'} (v'')} and CostShare{_{\mathcal{F}''} (v')}. This is called Random Cost Sharing Auction.

Theorem 6 The Random Cost Sharing Auction is a truthful auction whose revenue {4}-approximates the benchmark {\mathcal{F}^{(2)}(v)}.

Proof: Let {\mathcal{R}} be a random variable associated with the revenue of the Sampling Auction mechanism. It is clear that {\mathcal{R} = \min \{ \mathcal{F}', \mathcal{F}'' \}}. Let’s write {\mathcal{F}^{(2)}(v) = kp} meaning that we sell {k} items at price {p}. Let {k = k' + k''} where {k'} and {k''} are the items among those {k} items that went to {N'} and {N''} respectively. Then, clearly {\mathcal{F}' \geq p k'} and {\mathcal{F}'' \geq p k''}, what gives us:

\displaystyle \frac{\mathcal{R}}{\mathcal{F}^{(2)}} = \frac{\min\{\mathcal{F}', \mathcal{F}''\}}{\mathcal{F}^{(2)}} \geq \frac{\min\{k'p, k''p\}}{kp} = \frac{\min\{k', k''\}}{k}

and from there, it is a straighforward probability exercise:

\displaystyle \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} = \mathop{\mathbb E}\left[{ \frac{\min\{k', k''\}}{k} }\right] = \frac{1}{k} \sum_{i=1}^{k-1} \min\{ i, k-i \} \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}

since:

\displaystyle \frac{k}{2} = \sum_{i = 0}^k i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k} \leq \frac{k}{4} + 2 \sum_{i = 0}^{k/2} i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}

and therefore:

\displaystyle  \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} \geq \frac{1}{4} \Box

This similar approximations can be extended to more general environments with very little change. For example, for multi-unit auctions, where {\mathcal{X} = \{ S; \vert S \vert \leq k \}} we use the benchmark {\mathcal{F}^{(2,k)} = \max_{2 \leq i \leq k} i v_i} and we can be {O(1)}-competitive against it, by random-sampling, evaluating {\mathcal{F}^{(1,k)} = \max_{\leq i \leq k} i v_i} on both sets and running a profit extractor on both. The profit extractor is a simple generalization of the previous one.

Mechanism Design

August 5th, 2009 No comments

In the early stage of algorithm design, the goal was to solve exacly and efficiently the combinatorial problems. Cook’s Theorem and the NP-completeness theory showed us that some problems are inehently hard. How can we solve this problem? By trying to find approximated solutions or by trying to look at restricted instances of those problems that are tractable. It turns out that the lack of computational power (NP-hardness in some sense) is not the only obstracle to solving problems optimally. Online algorithms propose a model where the difficulty is due to lack of information. The algorithm must take some decisions before seeing the entire input. Again, in most of the cases it is hopeless to get an optimal solution (the solution we could get if we knew the input ahead of time) and our goal is not to be far from it. Other example of natural limitation are streaming algorithms, where you should solve a certain problem with limited memory. Imagine for example one algorithm that runs in a router, that received gigabits each second. It is impossible to store all the information, and yet, we want to process this very very large input and give an anwer at some point.

An additional model is inspired in economy: there are a bunch of agents which have part of the input to the algorithm and they are interested in the solution, say, they have a certain value for each final outcome. Now, they will release their part of the input. The may lie about it to manipulate the final result according to their own interest. How to prevent that? We need to augment the algorithm with some economic incentives to make sure they don’t harm the final solution too much. We need to care about two things now: we still want a solution not to far from the optimal, but we also need to provide incentives. Such algorithm with incentives is called a mechanism and this represents one important field in Algorithmic Game Theory called Mechanism Design.

The simplest setting where this can occur is in a matching problem. Suppose there are {n} people and one item. I want to decide which person will get the item. Person {i} has a value of {v_i} of the item. Then I ask people their values and give the item to the person that has a higher value and this way I maximize the total cost of the matching. But wait, this is a not a mechanism yet. People don’t have incentives to play truthfully in this game. They may want to report higher valuations to get the item. The natural solution is to charge some payment {p} from whoever gets the item. But how much to charge? The solution is the Vickrey auction, where we charge the second highest bid to the winner. More about Vickrey auction and some other examples of truthful mechanisms can be found in the Algorithmic Game Theory book, which can be found in Tim Roughgarden’s website.

One of the most famous early papers in this are is the “Optimal Design Auction” by Myerson where he discusses auctions mechanisms that maximize the profit for the seller. After reading some papers in this area, I thought I should return and read the original paper by Myerson, and it was indeed a good idea, since the paper formalizes (or makes very explicit) a lot of central concept in this area. I wanted to blog about the two main tools in mechanism design discussed in the paper: the revelation principle and the revenue equivalence theorem.

Revelation Principle

We could imagine thousands of possible ways of providing economic incentives. It seems a difficult task to look at all possible mechanisms and choose the best one. The good thing is: we don’t need to look at all kinds of mechanisms: we can look only at truthful revelation mechanisms. Let’s formalize that: consider {n} bidders and each has value {v_i} for getting what they want (suppose they are single parameter agents, i.e., they get {v_i} if they get what they want or {0} if they don’t). We can represent the final outcome as a vector {x \in [0,1]^n}. Here we consider also randomizes mechanisms, where the final outcome can be, for example, allocate the item to bidder {i} with probability {x_i}. This vector has some restrictions imposed by the structure of the problem, i.e., if there is only one item, then we must have {\sum_i x_i \leq 1}. In the end of the mechanism, each player will pay some amount to the mechanism, say {p_i}. Then at the end, player {i} has utility: {u_i(x,p) = x_i v_i - p_i} and the total profit of the auctioneer is {\sum_i p_i}.

Let’s describe a general mechanism: in this mechanism each player has a set of strategies, say {\Theta_i}. Each player chooses one strategy {\theta_i \in \Theta_i} and the mechanism chooses one allocation and one payment function based on the strategies of the players. {x = x(\theta_1, \hdots,\theta_n)} and {p = p(\theta_1, \hdots,\theta_n)}. Notice it includes even complicated multi-round strategies: in this case, the strategy space {\Theta_i} would be a very complicated description of what a player would do for each outcome of each round.

Let {V_i} be the set of the possible valuations a player would have. So, given the mechanism, each player would pick a function {\theta_i: V_i \rightarrow \Theta_i}, i.e., {\theta_i(v_i)} is the strategy he would pick if he observed his value was {v_i}. This mechanism has an equilibrium if there is a set of such functions that are in an equilibrium, i.e., no one would change his function and be better off. If those exist, we can implement a this as a direct revelation mechanism. A direct revelation mechanism is a mechanism where the strategies are simply to reveal a value in {V_i}. So, I just ask each player his valuation.

Given a complicated mechanism {x: \Theta \rightarrow [0,1]^n}, {x: \Theta \rightarrow {\mathbb R}_+^n} and equilibrium strategies {\theta_i: V_i \rightarrow \Theta_i }, I can implement this as a direct revelation mechanism just by taking:

\displaystyle x'(v_1, \hdots, v_n) = x(\theta_1(v_1), \hdots, \theta_n(v_n))

\displaystyle p'(v_1, \hdots, v_n) = p(\theta_1(v_1), \hdots, \theta_n(v_n))

It is not hard to see that if the mechanism is {(x', v')}, for the players the best thing to do is to reveal directly their true valuation, eliminating all the complicated steps in between. One practical example of a direct revelation mechanism is the Vickrey auction. Consider the English auction, which is the famous auction that happens in most of movied depicting auctions (or Sotheby’s for a clear example): there is one item and people keep raising their bids untill everyone else drops and the last person still biddings gets the item. The clear strategy in those auctions is to raise your bid as long as the current value is below your valuation {v_i} and there still other bidders that haven’t dropped the auction. Clearly the person with highest value {v_i} will get the item. Let {v_j} be the second highest value. It is not hard to see that all but one will drop the auction after {v_j}, so the highest bidders is likely to pay {v_j + \epsilon}. This is exacly the Vickrey auction, where we just emulate the English as a direct revelation mechanism. There are of course other issues. The following quote I got from this paper:

“God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.” (A. Alfred Taubman, Chairman, Sotheby’s Galleries)

So, we can restrict our attention to mechanims in the form {x : V \rightarrow [0,1]^n} and {p : V \rightarrow {\mathbb R}_+^n} that are truthful, i.e., where the players have no incentives not to report their true valuation. We can characterize truthful auctions using the next theorem. Just a bit of notation before: let {v_{-i} = (v_1, \hdots, v_{i-1}, v_{i+1}, \hdots, v_n)}, {x_{-i} = (x_1, \hdots, x_{i-1}, x_{i+1}, \hdots, x_n)}, … and for {f}, let {f} be the joint probability distribution and {f_{-i}} be the joint probability distribution over {v_{-i}}:

Theorem 1 An auction is truthful if and only if, for all possible probability distributions over values given by {f_1}, …, {f_n} we have

  1. {x_i(v_i) = \int x_i(v_i, v_{-1}) f_{-i}(v_{-i}) dv_{-i}} is monotone non-decreasing
  2. {p_i(v_i) = v_i x_i(v_i) - \int_0^{v_i} x_i(z) dz} where {p_i(v_i) = \int p_i(v_i, v_{-1}) f_{-i}(v_{-i}) dv_{-i}}

Revenue Equivalence

The second main tool to reason about mechanisms concerns the revenue of the mechanism: it is Myerson’s Revnue Equivalence Principle, which roughly says that the revenue under a truthful mechanism depends only on the allocation and not on the payment function. This is somehow expected by the last theorem, since we showed that when a mechanism is truthtful, the payments are totally dependent on {(x,f)}.

The profit of the auctioneer is given by {\int \sum_{i=0}^n p_i(v) f(v) dv}. We can substitute {p_i(v)} by the payment formula in last theorem obtaining:

\displaystyle \begin{aligned} \text{profit} &= \sum_{i=0}^n \int_{V_i} p_i(v_i) f_i(v_i) dv_i = \\&= \sum_{i=0}^n \int_{V_i} \left( v_i x_i(v_i) - \int_0^{v_i} x_i(z) dz \right) f_i(v_i) dv_i \end{aligned}

We can invert the order of the integration in the second part, getting:

\displaystyle \begin{aligned} \int_{V_i} \int_0^{v_i} x_i(z) f_i(v_i) dz dv_i &= \int_{V_i} \int_{v_i}^{\infty} x_i(z) f_i(v_i) dv_i dz = \\ &= \int_{V_i} x_i(z) (1 - F_i(z)) dz \\ \end{aligned}

So, we can rewrite profit as:

\displaystyle  \text{profit} = \sum_{i=0}^n \int_V \left[ 1 - \frac{1 - F_i(v_i)}{f_i(v_i)} \right] x_i(v_i) f(v) dv

And that proves the following result:

Theorem 2 The seller’s expected utility from a truthful direct revelation mechanism depends only on the assignment function {x(v)}.

Now, to implement a revenue-maximizing mechanism we just need to find {x(v)} that optimize the profit functional above still meeting the truthfulness constraints in the first theorem. This is discussed by Myerson in his paper. There is just one issue here: our analysis is dependent on the probabilities {f_i}. There are various approaches to that:

  • Assume that the values of the bidders are drawn from distribution and {f_i} and given to them. The distributions are public knowledge but the realization of {f_i} is just known to bidder {i}.
  • Bidders have fixed values {v_i} (i.e., {f_i} are the Dirac distribution concentrated on {v_i}) and in this case, the revenue maximizing problem becomes trivial. It is still an interesting problem in the point of view of truthfulness. But in this case, we should assume that {v_i} is fixed but just player {i} knows its value.
  • The distributions exist but they are unknown by the mechanism designer. In this case, he wants to design a mechanism that provided good profit guaranteed against all possible distributions. The profit guarantees need to be established accourding to some benchmark. This is called prior-free mechanism design.

More references about Mechanism Design can be found in these lectures by Jason Harline, in the original Myerson paper or in the Algorithmic Game Theory book.