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 consisting of agents and a service. Each agent has a value for receiving the service and otherwise. We can think of as the maximum player is willing to pay for that service. We call an environment the subsets of the bidders that can be simultaneously served. For example:
- Single item auction:
- Multi item auction:
- Digital goods auction:
- Matroid auctions: is a matroid on
- Path auctions: is the set of edges in a graph and is the set of -paths in the graph
- Knapsack auctions: there is a size for each and iff for a fixed
Most mechanism design problems focus in maximizing (or approximating) the social welfare, i.e., finding maximizing . 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 (which can be their true valuations or lies), then the mechanism decides on an allocation (in a possibly randomized way) and charges a payment for each allocated agents. The profit of the auctioneer is and the utility of a bidder is:
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 be the utility of agent if he bids . Since it is a randomized mechanism, then it is random variable. Truthful in expectation means that .
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 is a function that associated for each a distribution over elements of .
Theorem 2 Let be the probability that is allocated by the mechanism given is reported. The mechanism is truthful iff is monotone and each allocated bidder is charged payment:
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 for all . 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 to a set , i.e., the probability distribution is concentrated in one set.
Theorem 3 A mechanism is a truthful deterministic auction iff there is a functions such that for each we allocate to bidder iff and in case it is allocated, we charge payment .
It is actually easy to generate this function. Given a mechanism, is a monotone and is a -function. Let the point where it transitions from to . 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 such that for each we allocate to bidder iff and in case it is allocated, we charge payment , where are random bits.
2. Profit benchmarks
Let’s consider a Digital Goods auction, where . Two natural goals for profit extraction would be and where we can think of , 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 -approximates both benchmarks on every input. The intuition is that can be much larger then the rest, so there is no way of setting 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:
which is the highest single-price profit we can get selling to at least agents. We will show a truthful mechanism that -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 , extract that profit from a set of agents if that is possible. In this first moment, let’s see as an exogenous constant. Consider the following mechanism called CostShare: find the largest s.t. . Then allocate to
Lemma 5 CostShare is a truthful profit-extractor that can extract profit whenever .
Proof: It is clear that it can extract profit at most if . 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 exacly bidders are getting the item, then let’s look at a bidder . If bidder is not getting the item, then his value is smaller than , otherwise we could incluse all bidders up to and sell for a price for some . It is easy to see that bidder will get the item just if he changes his value to some value greater or equal than .
On the other hand, it is currently getting the item under , then increasing his value won’t make it change. It is also clear that for any value , he will still get the item. For he doesn’t get it. Suppose it got, then at least people get the item, because the price they sell it to must be less than . Thefore, increasing back to its original value, we could still sell it to players, what is a contradiction, since we assumed we were selling to players.
We checked monotonicity and we also need to check the payments, but it is straightforward to check they satisfy the second condition, since for and zero instead.
4. Random Sampling Auctions
Now, using that profit extractor as a building block, the main idea is to estimate smaller than for one subset of the agents and extract that profit from them using a profit extractor. First we partition is two sets and tossing a coin for each agent to decide in which set we will place it, then we calculate and . Now, we run CostShare and CostShare. This is called Random Cost Sharing Auction.
Theorem 6 The Random Cost Sharing Auction is a truthful auction whose revenue -approximates the benchmark .
Proof: Let be a random variable associated with the revenue of the Sampling Auction mechanism. It is clear that . Let’s write meaning that we sell items at price . Let where and are the items among those items that went to and respectively. Then, clearly and , what gives us:
and from there, it is a straighforward probability exercise:
This similar approximations can be extended to more general environments with very little change. For example, for multi-unit auctions, where we use the benchmark and we can be -competitive against it, by random-sampling, evaluating on both sets and running a profit extractor on both. The profit extractor is a simple generalization of the previous one.