Big Red Bits

MHR, Regular Distributions and Myerson’s Lemma

May 30th, 2011 renatoppl No comments

Monotone Hazard Rate (MHR) distributions and its superclass regular distributions keep appearing in the Mechanism Design literature and this is due to a very good reason: they are the class of distributions for which Myerson’s Optimal Auction is simple and natural. Let’s brief discuss some properties of those distributions. First, two definitions:

Hazard rate of a distribution $f$ : $h(z) = \frac{f(z)}{1-F(z)}$
Myerson virtual value of a distribution $f$ : $\phi(z) = z - \frac{1-F(z)}{f(z)}$

We can interpret the hazard rate in the following way: think of $T \sim f$ as a random variable that indicates the time that a light bulb will take to extinguish. If we are in time $t$ and the light bulb hasn’t extinguished so far, what is the probability it will extinguish in the next $\delta$ time:

$\mathbb{P}[T \leq t+\delta \vert T > t] \approx \frac{f(t) \delta}{1-F(t)}$

We say that a distribution is monotone hazard rate, if $h(z)$ is non-decreasing. This is very natural for light bulbs, for example. Many of the distributions that we are used to are MHR, for example, uniform, exponential and normal. The way that I like to think about MHR distributions is the following: if some distribution has hazard rate $h(z)$ , then it means that $F'(z) = (1-F(z)) h(z)$ . If we define $G(z) = 1-F(z)$ , then $(log G(z))' = \frac{G'(z)}{G(z)} = -h(z)$ , so:

$F(z) = 1-\text{exp}(-\int_0^z h(u) du)$

From this characterization, it is simple to see that the extremal distributions for this class, i.e. the distributions that are in the edge of being MHR and non-MHR are constant hazard rate, which correspond to the exponential distribution $F(z) = 1-e^{-\lambda z}$ for $z \in [0,\infty)$ . They way I like to think about those distributions is that whenever you are able to prove something about the exponential distribution, then you can prove a similar statement about MHR distributions. Consider those three examples:

Example 1: $\mathbb{P}[\phi(z) \geq 0] \geq \frac{1}{e}$ for MHR distributions. This fact is straightforward for the exponential distribution. For the exponential distribution $\phi(z) = z-\lambda^{-1}$ and therefore

$\mathbb{P}[\phi(z) \geq 0] \geq \mathbb{P}[z > \lambda^{-1}] = 1-F(\lambda^{-1}) = e^{-1}$

but the proof for MHR is equally simple: Let $r = \inf \{z; \phi(z) \geq 0\}$ , therefore $r h(r) \leq 1$ .
$P\{ \phi(v) \geq 0\} = P\{ v \geq r \} = 1 - F(r) = e^{-\int_0^r h(u) du} \geq e^{-r h(r)} \geq e^{-1}$

Example 2: Given $z_1, z_2 \sim f$ iid where $f$ is MHR and $v_1 = \max \{z_1, z_2\}$ and $v_2 = \min \{z_1, z_2\}$ , then $\mathbb{E}[v_2] \geq \frac{1}{3} \mathbb{E}[v_1]$ . The proof for the exponential distribution is trivial, and in fact, this is tight for the exponential, the trick is to use the convexity of $z \mapsto \int_0^z h(u) du$ . We use that $\int_0^{2z} h \geq 2 \int_0^z h$ in the following way:

$\mathbb{E} [v_2] = \int_0^\infty (1 - F(z))^2 dz = \int_0^\infty e^{-2 \int_0^z h} dz$

$\geq \int_0^\infty e^{-\int_0^{2z} h} dz= \frac{1}{2} \int_0^\infty 1 - F(z) dz = \frac{1}{2} \mathbb{E} [z]$

Since $\mathbb{E} [v_1 + v_2] = \mathbb{E} [z_1 + z_2] = 2 \mathbb{E} [z]$ , we have that $\mathbb{E}[v_1] = 2 \mathbb{E}[z] - \mathbb{E}[v_2] \leq \frac{3}{2} \mathbb{E}[z]$ . This way, we get: $\mathbb{E}[v_2] \geq \frac{1}{2}\mathbb{E}[z] \geq \frac{1}{2} \cdot \frac{2}{3} \mathbb{E}[v_1] = \frac{1}{3} \mathbb{E}[v_1]$

Example 3: For MHR distributions, there is a simple lemma that relates the virtual value and the real value and this lemma is quite useful in various settings: let $r = \inf \{z; \phi(z) > 0 \}$ , then for $z \geq r$ , $\phi(z) \geq z - r$ . Again, this is tight for exponential distribution. The proof is quite trivial:

$x - \phi(x) = \frac{1-F(x)}{f(x)} \leq \frac{1-F(r)}{f(r)} = r$

Now, MHR distributions are a subclass of regular distributions, which are the distributions for which Myerson’s virtual value $\phi(z)$ is a monotone function. I usually find harder to think about regular distributions than to think about MHR (in fact, I don’t know so many examples that are regular, but not MHR. Here is one, though, called the equal-revenue-distribution. Consider $z \in [1, \infty)$ distributed according to $f(z) = 1/z^2$ . The cumulative distribution is given by $F(z) = 1-1/z$ . The interesting thing of this distribution is that posted prices get the same revenue regardless of the price. For example, if we post any price $r \in [1,\infty)$ , then a customer with valuations $z \sim f$ buys the item if $z > r$ by price $r$ , gettingÂ revenue is $r (1-F(r)) = 1$ . This can be expressed by the fact that $\phi(z) = 0$ . I was a bit puzzled by this fact, because of Myerson’s Lemma:

Myerson Lemma: If a mechanism sells to some player that has valuation $v \sim f$ with probability $x(v)$ when he has value $v$ , then the revenue is $\mathbb{E} [x(v) \phi(v)]$ .

And it seemed that the auctioneers was doomed to get zero revenue, since $\phi(z) = 0$ . For example, suppose we fix some price $r$ and we sell the item if $v \geq r$ by price $r$ . Then it seems that Myerson’s Lemma should go through by a derivation like that (for this special case, although the general proof is quite similar):

$\mathbb{E} [x(v) \phi(v)] = \int_r^\infty \phi(z) f(z) dz = \int_r^\infty z f(z) - (1-F(z)) dz =$

$= \int_r^\infty [ z f(z) - \int_z^\infty f(u) du ] dz = \int_r^\infty z f(z) dz - \int_r^\infty \int_r^u f(u) dz du$

$= r (1-F(r))$

but those don’t seem to match, since one side is zero and the other is 1. The mistake we did above is classic, which is to calculate $\infty - \infty$ . We wrote:

$\mathbb{E}[\phi(v)] = \int_r^\infty z f(z) dz - \int_r^\infty 1-F(z) dz$

but both are infinity! This made me realize that Myerson’s Lemma needs the condition that $\mathbb{E}[z] < \infty$ , which is quite a natural a distribution over valuations of a good. So, one of the bugs of the the equal-revenue-distribution is that $\mathbb{E}[z] = \infty$ . A family that is close to this, but doesn’t suffer this bug is: $f(z) = \frac{\alpha-1}{z^\alpha}$ for $z \in [1,\infty)$ , then $F(z) = 1 - z^{1-\alpha}$ . For $\alpha > 2$ we have $\mathbb{E}[v] < \infty$ , then we get $\phi(z) = \frac{\alpha-2}{\alpha-1} z$ .

Categories: theory Tags: probability, profit maximization

More about hats and auctions

October 29th, 2009 renatoppl No comments

In my last post about hats, I told I’ll soon post another version with some more problems, which I ended up not doing and would talk a bit more about those kind of problems. I ended up not doing, but here are a few nice problems:

Those ${n}$ people are again a room, each with a hat which is either black or white (picked with probability ${\frac{1}{2}}$ at random) and they can see the color of the other people’s hats but they can’t see their own color. They write in a piece of paper either “BLACK” or “WHITE”. The whole team wins if all of them get their colors right. The whole team loses, if at least one writes the wrong color. Before entering the room and getting the hats, they can strategyze. What is a strategy that makes them win with ${\frac{1}{2}}$ probability?

If they all choose their colors at random, the probability of winning is very small: ${\frac{1}{2^n}}$ . So we should try to correlate them somehow. The solution is again related with error correcting codes. We can think of the hats as a string of bits. How to correct one bit if it is lost? The simple engineering solution is to add a parity check. We append to the string ${x_0, x_1, \hdots, x_n}$ a bit ${y = \sum_i x_i \mod 2}$ . So, if bit ${i}$ is lost, we know it is ${x_i = (y + \sum_{j \neq i} x_j) \mod 2}$ . We can use this idea to solve the puzzle above: if hats are places with ${\frac{1}{2}}$ probability, the parity check will be ${0}$ with probability ${\frac{1}{2}}$ and ${1}$ with probability ${\frac{1}{2}}$ . They can decide before hand that everyone will use ${y = 0}$ and with probability ${\frac{1}{2}}$ they are right and everyone gets his hat color right. Now, let’s extend this problem in some ways:

The same problem, but there are ${k}$ hat colors, they are choosen independently with probability ${\frac{1}{k}}$ and they win if everyone gets his color right. Find a strategy that wins with probability ${\frac{1}{k}}$ .

There are again ${k}$ hat colors, they are choosen independently with probability ${\frac{1}{k}}$ and they win if at least a fraction ${f}$ ( ${0 < f < 1}$ ) of the people guesses the right color. Find a strategy that wins with probability ${\frac{1}{fk}}$ .

Again to the problem where we just have BLACK and WHITE colors, they are chosen with probability ${\frac{1}{2}}$ and everyone needs to find the right color to win, can you prove that ${\frac{1}{2}}$ is the best one can do? And what about the two other problems above?

The first two use variations of the parity check idea in the solution. For the second case, given any strategy of the players, for each string ${x \in \{0,1\}^n}$ they have probability ${p_x}$ . Therefore the total probability of winning is ${\frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x}$ . Let ${x' = (1-x_1, x_2, \hdots, x_n)}$ , i.e., the same input but with the bit ${1}$ flipped. Notice that the answer of player ${1}$ is the same (or at least has the same probabilities) in both ${x}$ and ${x'}$ , since he can’t distinguish between ${x}$ and ${x'}$ . Therefore, ${p_{x} + p_{x'} \leq 1}$ . So,

$\displaystyle 2 \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x = \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x + \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x' \leq 1$

. This way, no strategy can have more than ${\frac{1}{2}}$ probability of winning.

Another variation of it:

Suppose now we have two colors BLACK and WHITE and the hats are drawn from one distribution ${D}$ , i.e., we have a probability distribution over ${x \in \{0,1\}^n}$ and we draw the colors from that distribution. Notice that now the hats are not uncorrelated. How to win again with probability ${\frac{1}{2}}$ (to win, everyone needs the right answer).

I like a lot those hat problems. A friend of mine just pointed out to me that there is a very nice paper by Bobby Kleinberg generalizing several aspects of hat problems, for example, when players have limited visibility of other players hats.

hats1

I began being interested by this sort of problem after reading the Derandomization of Auctions paper. Hat guessing games are not just a good model for error correcting codes, but they are also a good model for truthful auctions. Consider an auction with a set ${N}$ single parameter agents, i.e., an auction where each player gives one bid ${b_i}$ indicating how much he is willing to pay to win. We have a set of constraints: ${\mathcal{X} \subseteq 2^N}$ of all feasible allocations. Based on the bids ${(b_i)_{i \in N}}$ we choose an allocation ${S \in \mathcal{X}}$ and we charge payments to the bidders. An example of a problem like this is the Digital Goods Auction, where ${\mathcal{X} = 2^N}$ .

In this blog post, I discussed the concept of truthful auction. If an auction is randomized, an universal truthful auction is an auction that is truthful even if all the random bits in the mechanism are revealed to the bidders. Consider the Digital Goods Auction. We can characterize universal truthful digital goods auction as bid-independent auctions. A bid-independent auction is given by function ${f_i(b_{-i})}$ , which associated for each ${b_{-i}}$ a random variable ${f_i(b_{-i})}$ . In that auction, we offer the service to player ${i}$ at price ${f_i(b_{-i})}$ . If ${b_i \geq f_i(b_{-i})}$ we allocate to ${i}$ and charge him ${f_i(b_{-i})}$ . Otherwise, we don’t allocate and we charge nothing.

It is not hard to see that all universal truthful mechanisms are like that: if ${x_i(b_i)}$ is the probability that player ${i}$ gets the item bidding ${b_i}$ let ${U}$ be an uniform random variable on ${[0,1]}$ and define ${f_i(b_{-i}) = x_i^{-1}(U)}$ . Notice that here ${x_i(.) = x_i(., b_{-i})}$ , but we are inverting with respect to ${b_i}$ . It is a simple exercise to prove that.

With this characterization, universal truthful auctions suddenly look very much like hat guessing games: we need to design a function that looks at everyone else’s bid but not on our own and in some sense, “guesses” what we probably have and with that calculated the price we offer. It would be great to be able to design a function that returns ${f(b_{-i}) = b_i}$ . That is unfortunately impossible. But how to approximate ${b_i}$ nicely? Some papers, like the Derandomization of Auctions and Competitiveness via Consensus use this idea.

Categories: puzzles, theory Tags: coding theory, mechanism design, profit maximization, puzzles, theory

Competitive Auctions

September 17th, 2009 renatoppl 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:

Single item auction: ${\mathcal{X} =\{S; \vert S \vert \leq 1\}}$
Multi item auction: ${\mathcal{X} =\{S; \vert S \vert \leq k\}}$
Digital goods auction: ${\mathcal{X} =2^N}$
Matroid auctions: ${\mathcal{X}}$ is a matroid on ${N}$
Path auctions: ${N}$ is the set of edges in a graph and ${\mathcal{X}}$ is the set of ${s-t}$ -paths in the graph
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.