#### Termes les plus recherchés

# [PDF](+29👁️) Télécharger Approximate Revenue Maximization with Multiple Items pdf

#### Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood. In this paper we obtain approximate revenue optimization results using two simple auctions: that of selling the items separately, and that of selling them as a single bundle. Our main results (which are of a "direct sum" variety, and apply to any distributions) are as follows. Selling the items separately guarantees at least half the revenue of the optimal auction; for Télécharger gratuit Approximate Revenue Maximization with Multiple Items pdf

Approximate Revenue Maximization with Multiple

Items*

Sergiu Hart t Noam Nisan *

March 2, 2013

CN ;

o

^ . Abstract

Pi

. Myerson's classic result provides a full description of how a seller can maximize

. revenue when selling a single item. We address the question of revenue maximiza-

__■ tion in the simplest possible multi-item setting: two items and a sinqle buyer who

B has % -1*— value, for the items, aud au additive valuation. lu

general, the revenue achievable from selling two independent items may be strictly

higher than the sum of the revenues obtainable by selling each of them separately.

In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two

| items even in this simple setting is not understood.

In this paper we obtain approximate revenue optimization results using two

simple auctions: that of selling the items separately, and that of selling them as a

single bundle. Our main results (which are of a "direct sum" variety, and apply

'xT .

to any distributions) are as follows. Selling the items separately guarantees at

least half the revenue of the optimal auction; for identically distributed items, this

j> ■ becomes at least 73% of the optimal revenue.

For the case of k > 2 items, we show that selling separately guarantees at least

a c/ log 2 k fraction of the optimal revenue; for identically distributed items, the

bundling auction yields at least a c/log k fraction of the optimal revenue.

*First version: February 2012.

'Institute of Mathematics, Department of Economics, and Center for the Study of Rationality, He-

brew University of Jerusalem. Research partially supported by a European Research Council Advanced

Investigator grant.

* School of Computer Science and Engineering, and Center for the Study of Rationality, Hebrew

University of Jerusalem. Research partially supported by a grant from the Israeli Science Foundation

and by a Google grant on Electronic Markets and Auctions.

1

1 Introduction

Suppose that you have one item to sell to a single buyer whose willingness to pay is

unknown to you but is distributed according to a known prior (given by a cumulative

distribution F). If you offer to sell it for a price p then the probability that the buyer

will buy is j 1 — F(p), and your revenue will be p - (1 — F(p)). The seller will choose a

price p* that maximizes this expression.

This problem is exactly the classical monopolist pricing problem, but looking at it

from an auction point of view, one may ask whether there are mechanisms for selling

the item that yield a higher revenue. Such mechanisms could be indirect, could offer

different prices for different probabilities of get ting the i tem, and perhaps others. Yet,

concludes that the take-

|l98l| )

Myerson's characterization of optimal auctions flMyerson

it-or-leave-it offer at the above price p* yields the optimal revenue among all mechanisms.

Even more, Myerson's result also applies when there are multiple buyers, in which case

p* would be the reserve price in a second price auction.

Now suppose that you have two (different) items that you want to sell to a single

buyer. Furthermore, let us consider the simplest case where the buyer's values for the

items are independently and identically distributed according to F ("i.i.d.-F" for short),

and furthermore that his valuation is additive: if the value for the first item is x and for

the second is y, then the value for the bundle - i.e., getting both items - is^| x + y. It

would seem that since the two items are completely independent from each other, then

the best we should be able to do is to sell each of them separately in the optimal way,

and thus extract exactly twice the revenue we would make from a single item. Yet this

turns out to be false.

Example: Consider the distribution taking values 1 and 2, each with probability 1/2.

Let us first look at selling a single item optimally: the seller can either choose to price it

at 1, selling always^] and getting a revenue of 1, or choose to price the item at 2, selling it

with probability 1/2, still obtaining an expected revenue of 1, and so the optimal revenue

for a single item is 1. Now consider the following mechanism for selling both items:

bundle them together, and sell the bundle for price 3. The probability that the sum of

the buyer's values for the two items is at least 3 is 3/4, and so the revenue is 3-3/4 = 2.25

- larger than 2, which is obtained by selling them separately.

However, that is not always so: bundling may sometimes be worse than selling the

1 Assume for simplicity that the distribution is continuous.

2 Our buyer's demand is not limited to one item (which is the case in some of the existing literature;

see below).

3 Since we want to maximize revenue we can always assume without loss of generality that ties are

broken in a way that maximizes revenue; this can always be achieved by appropriate small perturbations.

2

items separately. For the distribution taking values and 1, each with probability 1/2,

selling the bundle can yield at most a revenue of 3/4, and this is less than twice the

single- item revenue of 1/2. In some other cases neither selling separately nor bundling

is optimal. For the distribution that takes values 0, 1 and 2, each with probability 1/3,

the unique optimal auction turns out to offer to the buyer the choice between any single

item at price 2, and the bundle of both items at a "discount" price of 3. This auction

gets revenue of 13/9 revenue, which is larger than the revenue of 4/3 obtained from

either selling the two items separately, or from selling them as a single bundle. A similar

situation happens for the un iform distribution on [0, 11 , for which neither bundling nor

selling separately is optimal ( jManelli and Vincentl 20061 ). In yet other cases the optimal

mechanism is not even deterministic and must offer

2011

otteries for the items. This happens

Let F be the distribution which

in the following example from lHart and Reny

takes values 1, 2 and 4, with probabilities 1/6, 1/2, 1/3, respectively. It turns out that

the unique optimal mechanism offers the buyer the choice between buying any one good

with probability 1/2 for a price of 1, and buying the bundle of both goods (surely) for a

price of 4; any deterministic mechanism has a strictly lower revenue.

So, it is not clear what optimal mechanisms for selling two items look like, and indeed

characterizations of optimal auctions even for this simple c ase are not known. We shorty

describe some of the previous work on these type of issues.

McAfee and McMillan

identi fy ca ses where the optim a l mec hanism is deterministic. However,

1988]

Thanassoulis

2004j and

Manelli and Vincent

2006] found a technical error in the paper and exhibit

counter-examples. These last two papers contain good surveys of the work with i n eco -

nomic theory, with m o re recent analys i s bv iFang and Norman

Hart and Renyl 20101 ] , lHart and Renyl 2011| , iLevi 20111 ] . In the last few ye ars algorith

200

6],

Jehiel et al.

2007|,

mic w ork o n these types of topics was carried out. One line of work (e.g.

Briest et al

201(1 ] and

Cai et al

20121 ]) shows that for discrete distributions the optimal auction

can be found by linear programming in rather general settings. This is certainly true in

our simple setting where the direct representation of the auction constraints provides a

polynomial size linear program. Thus we emphasize that the difficulty in our case is not

computational, but is rather that of characterization and understanding the results of the

explicit computations: this is certainly so for contin uous distributions, b u t also for dis-

crete onesj^l Another line of work in computer science ( Chawla et al. 2007 ]. lc"hawla et al.

4 Previous examples wher e randomiza t ion helps appear in iManelli and Vincentl 2006],

Manelli and Vincent 2007 and Thanassoulis! 2004 1. but these require interdependent distributions of

values, rather than independent and identically distributed values.

If we limit ourselves to deterministic auctions (and discrete distributions), finding the optimal one

is easy computationally in the case of one buyer (just enumerate), in contrast to the general case of

m ultiple buyers with correlated yalues f or which computational complexity difficulty has been established

bv IPapadimitriou and Pierrakosl 2011 1.

3

2010 j . IChawla et al.l |2010bj | . iDaskalakis and Weinberg |20JjJ) attempts approximating

the optimal revenue by simple mechanisms. This was done for various settings, especially

unit-demand settings and some generalizations. One conclusion from this line of work

is that for many subclasses of distributions (such as those with monotone hazard rate)

various simple mechanisms can extract a constant fraction of the expected value of the

itemsj. This is true in our simple setting, where for such distributions selling the items

separately provides a constant fraction of the expected value and thus of the optimal

revenue.

The current paper may be viewed as continuing this tradition of approximating the

optimal revenue with simple auctions. It may also be viewed as studying the extent

to which auctions can gain revenue by doing things that appear less "natural" (such as

pricing lotteries whose outcomes are the items; of course, the better our understanding

becomes, the more things we may consider as natural.) We study two very simple and

natural auctions that we show do give good approximations: the first simple auction is

to sell the items separately and independently, and the second simple auction is to sell all

items together as a bundle. We emphasize that our results hold for arbitrary distributions

and we do not make any assumptions (such as monotone hazard rate) El In particular, our

approximations to the optimal revenue also hold when the expected value of the items is

arbitrarily (even infinitely) larger than the optimal revenue.

We will denote by REv(J r ) = REVfc(J-") the optimal revenue obtainable from selling,

to a single buyer (with an additive valuation), k items whose valuation is distributed

according to a (/c-dimensional joint) distribution F . This revenue is well understood only

for the special case of one item (k = 1), i.e., for a one-dimensional F, in which case it is

obtained by selling at the Myerson price (i.e., REVi(F) = sup p >op ■ (1 — F(p)). The first

three theorems below relate the revenue obtainable from selling multiple independent

items optimally (which is not well understood) to the revenue obtainable by selling each

of them separately (which is well understood).

Our first and main result shows that while selling two independent items separately

need not be optimal, it is not far from optimal and always yields at least half of the optimal

revenue. We do not know of any easier proof that provides any constant approximation

boundj^l

6 In our setting ths is true even more generally, for instance whenever the ratio between the median

and the expectation is bounded, which happens in particular when the tail of the distribution is "thinner"

than x~ a for a > 1.

One may argue that there is no need for uniform approximation results on the ground that the seller

knows the distribution of the buyer's valuation. However, as we have shown above, that does not help

finding the optimal auction (even for simple distributions) - whereas the approximations are always easy

and simple (as they use only optimal prices for one-dimensional distributions).

8 There is an easy proof for the special case of deterministic auctions, which we leave as an exercise

to the reader. It does not seem that this type of easy proof can be extended to general auctions since

4

The joint distribution of two items distributed independently according to F\ and F 2 ,

respectively, is denoted by F 1 x F 2 .

Theorem 1 For every one-dimensional distributions F\ and F2,

Revi(Fi) + Revi(F 2 ) > - ■ Rev 2 (F! x F 2 ).

This result is quite robust and generalizes to auctions with multiple buyers, using

either the Dominant- Strategy or the Bayes-Nash notions of implementation. It also gen-

eralizes to multi-dimensional distributions, i.e., to cases of selling two collections of items,

and even to more general mechanism design settings

ever, as we show in a companion paper

see Theorems [20] and EDD@ How-

Hart and Nisan

20121 ] , such a result does not hold

when the values for the items are allowed to be correlated: there exists a joint distribution

of item values such that the revenue obtainable from each item separately is finite, but

selling the items optimally yields infinite revenue.

For the special case of two identically distributed items (one-dimensional and single

buyer), i.e., F\ = F 2 , we get a tighter result.

Theorem 2 For every one- dimensional distribution F,

REVi(F) + REVi(F) > — — • Rev 2 (F x F).

Thus, for two independent items, each distributed according to F, taking the optimal

Myerson price for a single item distributed according to F and offering the buyer to choose

which items to buy at that price per item (none, either one, or both), is guaranteed to

yield at least 73% of the optimal revenue for the two items. This holds for any distribution

F (and recall that, in general, we do not know what that optimal revenue is; in contrast,

the Myerson price is well-defined and immediate to determine).

There is a small gap between this bound of e/(e+ 1) = 0.73... and the best separation

that we have with a gap of of 0.78... (see Corollary |2"9|) . We conjecture that the latter is

in fact the tight bound.

We next consider the case of more than two items. It turns out that, as the number

of items grows, the ratio between the revenue obtainable from selling them optimally to

that obtainable by selling them separately is unbounded. In fact, we present an example

showing that the ratio may be as large as 0(\ogk) (see Lemma [8]). Our main positive

it would apply also t o interdependent item values in which case, as we show in a companion paper

lHart and Nisan 2012 . there is no finite bound relating the two- item revenue to that of selling them

separately.

9 However, we have not been able to generalize these decomposition results to multiple buyers and

multiple items simultaneously.

5

result for the case of multiple items is a bound on this gap in terms of the number of

items. When the k items are independent and distributed according to Fx,...,F k , we

write F± x • • • x Fk for their product joint distribution.

Theorem 3 There exists a constant c > such that for every integer k > 2 and every

one- dimensional distributions Fx, ...,F k ,

Revi(Fi) + • • • + REVi(Ffc) > -4t • REV fc (Fx x ■ • • x F k ).

log k

We then consider the other simple single-dimensional auction, the bundling auction,

which offers a single price for the bundle of all items, We ask how well it can approx-

imate the optimal revenue. We first observe that, in general, the bundling auction may

do much worse and only yield a revenue that is a factor of almost k times lower than that

of the optimal auction (see Example [E2 moreover, we show in Lemma that this is

tight up to a constant factor). However, when the items are independent an d identically

distributed, then the bundling auctio n does much better. It is well known ([Armstrong

19991 ]. iBakos and Brynjolfssonl |1999l |) that for every fixed distribution F, as the number

of items distributed independently according to F approaches infinity, the bundling auc-

tion approaches the optimal one (for completeness we provide a short proof in Appendix

5.) This, however, requires k to grow as F remains fixed. On the other hand, we show

that this is not true uniformly over F: for every large enough k, there are distributions

where the bundling auction on k items extracts less than 57% of the optimal revenue

(Example fT9|) . Our main result for the bundling auction is that in this case it extracts

a logarithmic (in the number of items k) fraction of the optimal revenue. We do not

know whether the loss is in fact bounded by a constant fraction. Since the distribution of

the sum of k independent and identically distributed according to F items is the fc-times

convolution F * ■ ■ ■ * F, our result is:

Theorem 4 There exists a constant c > such that for every integer k > 2 and every

one- dimensional distribution F ,

RevUF * • • • * F) > ■ RevJF x • ■ • x F).

Vv v - log k K v

k k

Many problems are left open. From the general point of view, the characterization

of the optimal auction is still mostly open, despite the many partial results in the cited

papers. In particular, it is open to fully characterize when selling separately is optimal;

10

By Myerson's result, this is indeed the optimal mechanism for selling the bundle.

6

when the bundling auction is optimal I; or when are deterministic auctions optimal. More

specifically, regarding our approximation results, gaps remain between our lower bounds

and upper bounds.

The structure of the paper is as follows. In Section 2 we present our notations and

the preliminary setup. Section 3 studies the relations between the bundling auction and

selling separately; these relations are not only interesting in their own right, but are then

also used as part of the general analysis and provide us with most of the examples that

we have for gaps in revenue. Section 4 studies the case of two items, gives the main

decomposition theorem together with a few extensions; Section 5 gives our results for

more than two items. Several proofs are postponed to appendices. Finally, Appendix

5 provides a table summarizing our bounds on the revenue gaps between the separate

auction and the optimal auction, and between the bundling auction and the optimal

auction.

2 Notation and Preliminaries

2.1 Mechanisms

A mechanism for selling k items specifies a (possibly randomized) protocol for interaction

between a seller (who has no private information and commits to the mechanism) and a

buyer who has a private valuation for the items. The outcome of the mechanism is an

allocation specifying the probability of getting each of the k items and an (expectedll^l

payment that the buyer gives to the seller. We will use the following notations:

• Buyer valuation: x = (x±, . . . ,Xk) where X{ > denotes the value of the buyer

for getting item i.

• Allocation: q = (<Zi, . . . , <&) G [0, l] k , where qi = qi(x) denotes the probability

that item i is allocated to the buyer when his valuation is x (alternatively, one may

interpret t& as the fractional quantity of item i that the buyer gets).

• Seller revenue: s = s(x) denotes the expected payment that the seller receives

from the buyer when the buyer's valuation is x.

11 We do show that this is the case for a class of distributions that decrease not too slowly; see Theorem

m\

12 We only consider risk-neutral agents.

13 In the literature this is also called transfer, cost, price, revenue, and denoted by p, t, c, etc. We

hope that using the mnemonic s for the teller's final payoff and b for the Buyer's final payoff will avoid

confusion.

7

• Buyer utility: b = b(x) denotes the utility of the buyer when his valuation is x,

i.e., b(x) = Y.i x i ( li( x ) ~ s ( x ) = x ■ <l( x ) ~ s ( x )-

We will be discussing mechanisms that are:

• IR - (Ex-post) Individually Rational: b(x) > for all x.

• IC - Incentive Compatible: For all x, x'\ J2 i x i q i (x) — s(x) > Yli x i < ii( x ')~ s(x').

The IC requirement simply captures the notion that the buyer acts strategically in the

mechanism. Since we are discussing a single buyer, this is in a simple decision-theoretic

sense and in particular there is no distinction between the domainant strategy and the

Bayes-Nash implementation notions.

The following lemma gives well known and easily proven equivalent conditions for

incentive compatibility.

Lemma 5 The following three definitions are equivalent for a mechanism with b(x) =

x ■ q(x) - s(x) = J2i x iQi( x ) ~ s ( x ) :

1. The mechanism is IC.

2. The allocation q is weakly monotone, in the sense that for all x, x' we have (x —

x') ■ (q(x) — q(x')) > 0, and the payment to the seller satisfies x' • (q(x) — q(x')) <

s(x) — s(x') < x ■ (q(x) — q(x')) for all x, x' .

3. The buyer's utility b is a convex function of x and for all x the allocation q(x) is

a subgradient of b at x, i.e., for all x' we have b(x') — b(x) > q(x) ■ (x' — x). In

particular b is differentiate almost everywhere and there qi(x) = db(x)/dxi.

Proof. • 1 implies 2: The RHS of the second part is the IC constraint for x, the LHS is

the IC constraint for x', and the whole second part directly implies the first part.

• 2 implies 1: Conversely, the RHS of the second part is exactly the IC constraint for

x.

• 1 implies 3: By IC, b(x) = sup^/ x ■ q(x') — s(x') is a supremum of linear functions

of x and is thus convex. For the second part, b(x') — b(x) — q(x) ■ (x' — x) — x' ■ q(x') +

s(x) — s(x') — x' • q(x) > 0, where the inequality is exactly the IC constraint for x' .

• 3 implies 1: Conversely, as in the previous line, the subgradient property at x is

exactly equivalent to the IC constraint for x' . ■

Note that this in particular implies that any convex function b with < db(x)/dxi < 1

for all % defines an incentive compatible mechanism by setting qi(x) = db(x)/dxi (at non-

differentiability points take q to be an arbitrary subgradient of b) and s(x) = x-q(x) —b(x).

8

When distributed according to the joint cumulative distribution function

J^o

, the expected revenue of the mechanism given by b is

i?(6;^)=E^( S (x)) = | •■• J fc Xi ?M- b (x) \ dF( Xl ,...,x k ).

Thus we want to maximize this expression over all convex functions b with <

db(x)/dxi < 1 for all i. We can also assume

• NPT — No Positive Transfers: s(x) > for all x.

This is without loss of generalit y a s any mechanism can be converted to an NPT one,

with the revenue only increasing! 1 ^ This in particular implies that 6(0) = without loss

of generality (as it follows from IR+NPT).

2.2 Revenue

For a cumulative distribution T on (for k > 1), we consider the optimal revenue

obtainable from selling k items to a (single, additive) buyer whose valuation for the k

items is jointly distributed according to T:

• Rev(J-") = Rev^J 7 ) is the maximal revenue obtainable by any incentive compatible

and individually rational mechanism.

• SRev(J-") is the maximal revenue obtainable by selling each item separately.

• BRev(J-") is the maximal revenue obtainable by bundling all items together.

Thus, Rev(J-") = supt)R(b; T) where b ranges over all convex functions with <

db(x)/dxi < 1 for all i and 6(0) = 0. It will be often convenient to use random variables

rather than distributions, and thus we use Rev(X) and Rev(J-") interchangeably when

the buyer's valuation is a random variable X = (Xi, . . . , X)~) with values in distributed

according to T . In this case we have SRev(X) = Rev(Xi) + ■ ■ • + REv(X fc ) and

BRev(X) = REv(Xi + ... + X k ).

This paper will only deal with independently distributed item values, that is, T =

F x x • • • x F k , where F { is the distribution of itenfjf i. We hava^ll SRev(J 7 ) = Rev(Fi) +

14 We write this as x = (x±, ...,Xk) ~ J~. We use J- for multi-dimensional distributions and F for

one-dimensional distributions.

15 For each x with s(x) < redefine q(x) and s(x) as q(x') and s(x') for x' that maximizes Xiqi(x') —

s(x') over those x' with s(x') > 0.

16 As these are cumulative distribution functions, we have T(xi, . . . , Xk) — F\(xi) ■ . . . ■ Fk(xk)-

17 The formula for SRev holds without independence, with Fj the i-th marginal distribution of J ' .

9

+REV(F fc ) and BRevCT) = REV fFi

Hart and Nisan

■*Fk), where * denotes convolution. Our com-

2012H studies general distributions F, i.e., interdependent

panion paper

values.

For k = 1 we have Myerson's characterization of the optimal revenue:

REVipf) = SRev(X) = BRev(X)

supp-P(X >p)

p>0

(which also equals sup p>0 p • F(X > p) = sup p>0 p • (1 — F(p))).

Note that for any k, both the separate revenue SRev and the bundling revenue BRev

require solving only one- dimensional problems; by Myerson's characterization, the former

is given by k item prices Pi, ■ ■ ■ ,Pk, arid the latter by one price p for all items together.

3 Warm up: Selling Separately vs. Bundling

In this section we analyze the gaps between the two simple auctions: bundling and selling

the items separately. Not only are these comparisons interesting in their own right, but

they will be used as part of our general analysis, and will also provide the largest lower

bounds we have on the approximation ratios of these two auctions relative to the optimal

revenue.

We start with a particular distribution which will turn out to be key to our analysis.

We then prove upper bounds on the bundling revenue in terms of the separate revenue,

and finally we prove upper bounds on the separate revenue in terms of the bundling

revenue.

3.1 The Equal- Revenue Distribution

We introduce the distribution which we will show is extremal in the sense of maximizing

the ratio between the bundling auction revenue and the separate auction revenue.

Let us denote by ER - the equal-revenue distribution - the distribution with density

function f(x) = x~ 2 for x > 1; its cumulative distribution function is thus F(x) = 1 — x^ 1

for x > 1 (and for x < 1 we have f(x) = and F(x) = 0). (This is also called the Pareto

distribution with parameter a = 1.) It is easy to see that, on one hand, Rev - ! (ER) = 1

and, moreover, this revenue is obtained by choosing any price p > 1. On the other hand

its expected value is infinite: K(ER) = x ■ x~ 2 dx = 00. We start with a computation

of the distribution of the weighted sum of two ER distributions.

10

Lemma 6 LetX 1 ,X 2 i.i.d.-ER and a, (3 > 0. Then^t

P ali + /3X 2 > s) = -flog 1 + 1 a 1 } +

z z \ ap J z

forz>a + (3, and F(aXi + BX 2 > z) = 1 for z < a + B .

Proof. Let Z = aX x + f3X 2 . For z < a + (3 we have P(Z > z) = 1 since X* > 1. For

z > a + (3 we get

>z) = jm fi- F (^p\y x

(z-P)/a \ R f°° 1

(z-P)/a

dt + / — ldt

! X 2 Z-aX J( x -ff)/a X

a a ( z \ 1

— log x log a; I

z z \a / x\ 1

a

+

z-(3

^ 6og (- a -l)+ log (--A)- "' 1 "

z 2 \ \B J \a J J z(z — (3) z z — (3

aB ( z 2 -(a + B)z\ a + 8

^■°H 1+ ^ ] +

We can now calculate the revenue obtainable from bundling several independent ER

items.

Lemma 7 BRev(ER x ER) = 2.5569... ; where 2.5569... = 2(u? + l) with w the solution

o/0 we w = 1/e.

Remark. We will see below ( Corollary 129]) that bundling is optimal here, and so 2.5569...

is in fact the optimal revenue for two i.i.d.-ER items.

Proof. Using Lemma [6] with a = B = 1 yields p ■ P(Xi + X 2 > p) — p~ l log(l + p 2 —

2p) + 2 = 2p~ 1 \og(p — 1) + 2, which attains its maximum of 2w + 2 at p = 1 + 1/w. ■

Lemma 8 There exist constants Ci,c 2 > such that for all k > 2,

dklogk < BREv(ER xk ) < c 2 k\ogk.

18 For a one-dimensional distribution F, "i.i.d.-f ' refers to a collection of independent random variables

each distributed according to F.

19 log denotes natural logarithm.

20 Thus w — W(l/e) where W is the so-called "Lambert- W" function.

11

In particular, this shows that selling separately may yield, as k increases, an arbitrarily

small proportion of the optimal revenue: HEv(ER xk ) > BREv(-Ei? xfe ) > Ciklogk =

d log A; - SRev(ER xIs ).

Proof. Let X be a random variable with distribution ER; for M > 1 let X M :=

min{X, M} be X truncated at M. It is immediate to compute E(X M ) = logM + 1 and

Var(X M ) < 2M.

• Lower bound: Let X±, . . . , Xk be i.i.d.-ER; for every p, M > we have Rev(^V Xj) >

p- P(Ei^< >p) >p- p (E**f > p)-

When M = fclogfc and p = (fclogfc)/2 we get (£;E(X M ) - p)/ v /fc¥ar(X M ) >

A/log so p is at least ^/log fc/8 standard deviations below the mean of Ei=i^ M -

Therefore, by Chebyshev's inequality, P(Ei=i^« M — p) — 1 — 8/ log A; > 1/2 for all k

large enough, and then Rev(X)* =1 > p • 1/2 = fclogfc/4.

• Upper bound: We need to bound sup p>0 p • P(Ei=i^« — P)- ^ P — 6/clogfc then

P ■ F (E?=i x i > P) < P < Qk lo S

If p > 6k log then (take M = p)

p ■ P ^2 X t>P^j < P ■ P > P j + P • P (X > p for some 1 < i < k) . (1)

The second term is at most p • k ■ (1 — F(p)) = k (since F(p) — 1 — 1/p). To estimate

the first term, we again use Chebyshev's inequality. When k is large enough we have

p/(k(\ogp + 1)) < 2 (recall that p > 6/clogA;), and so p is at least y/pf (8k) standard

deviations above the mean

o f EjLi X f- Thus P ■ F (Eti > p) < P • (8A0/P = 8fc, and

so p • P(Ef=i X * > P) < 9A; ( reca11 ©)•

Altogether, Rev( J^ =1 Xj) < max{6£; log k, 9k} = 6k log k for all large enough. ■

Remark. A more precise analysis, based on the "Generalized Central Limit Theorem,"^]

shows that T5~R,Ev(ER xk )/(k log k) converges to 1 as k — > oo. Indeed, when Xj are i.i.d.-

ER, the sequence (Ei=i^ ~~ ^k)/ a k with = kn/2 and bk = klogk + Q(k) converges

in distribution to the Cauchy distribution as k — > oo. Since REVi(Cauchy) can be shown

to be bounded (by 1/tt), it follows that Rev(J]*Li^) = klogk + Q(k).

3.2 Upper Bounds on the Bundling Revenue

It turns out that the equal revenue distribution exhibits the largest possible ratio between

the bundling auction and selling separately. This is a simple corollary from the fact that

the equal revenue distribution has the heaviest possible tail.

21 See, e.g.. IZaliapin et al.l 12005].

12

Let X and Y be one- dimensional random variables. We say that X is (first- order)

stochastically dominated by Y if for every real p we have ¥(X > p) < P(Y > p). Thus,

Y gets higher values than X.

Lemma 9 If a one-dimensional X is stochastically dominated by a one-dimensional Y

then REVi(X) < Rev^F).

Proof. Rev(X) = sup p p • F(X > p) < sup p p • P(Y > p) = Rev(F) (by Myerson's

characterization) . ■

It should be noted that this monotonicity of the revenu e with respect to stoc hastic

dominance does not hold when there are two or more items

Hart and Renvi [2011 ] .

Lemma 10 For every one- dimensional X and every r > 0: ReVi(X) < r if and only if

X is stochastically dominated bt

r ■ ER.

Proof. By Myerson's characterization, Rev(X) < r if and only if for every p we have

F(X > p) < r/p; but r/p is precisely the probability that r ■ ER is at least p. m

We will thus need to consider sums of "scaled" versions of ER, i.e., linear combinations

of independent ER random variables. What we will see next is that equalizing the scaling

factors yields stochastic domination.

Lemma 11 Let Xi,X 2 be i.i.d.-ER and let a, (3, a', j3' > satisfy a + [3 = a' + f3'. If~^

a(3 < a'(3' then aXi + (3X 2 is stochastically dominated by a'Xi + (3'X 2 .

Proof. Let Z = aX\ + (3X 2 and Z' = a'X\ + (3'X 2 , and put 7 = a + = a' + /3'. Using

Lemma El for z < 7 we have F(Z > z) — F(Z' > z) — 1, and for z > 7 we get

m /„ \ ctB , ( z 2 — •yz\ 7

nz>z) = i^^—^yi

z 2 V ) :

since t log(l + l/t) is increasing in t for t > 0, and a(3/ [z 2 — jz) < a'f3' / [z 2 — jz) by our

assumption that a (3 < a' (3' together with z > 7. ■

We note the following useful fact: if for every L Xj is stochastically dominated by Y { ,

then X\ + h Xk is stochastically dominated b\l 24 l Y\ + h Y^.

22 We slightly abuse the notation and write r ■ ER for a random variable r ■ Y when Y is distributed

according to ER.

23 Equivalently, \a-/3\> \a' - /3'\.

24 Think of all the random variables being defined on the same probability space and satisfying Xi < i$

pointwise (which can be obtained by the so-called "coupling" construction), and then ~^Xi < is

immediate.

13

Corollary 12 Let be i.i.d.-ER and ol; l > 0. Then Y2i=i a iXi is stochastically domi-

nated by Yli=i olX^ where a = (X^=i a i)/k-

Proof. If, say, ct\ < a < a 2 , then the previous lemma implies that a\X\ + a 2 X 2 is

stochastically dominated by aX\ + a' 2 X 2 ,where a 2 = at + a 2 — at, and so Yli=i a -iXi is

stochastically dominated by aXi + a' 2 X 2 + X]i=3 a j^i- Continue in the same way until

all coefficients become a. ■

We can now provide our upper bounds on the bundling revenues.

Lemma 13 (i) For every one- dimensional distributions Fi,F 2 ,

BRev(Fi x F 2 ) < 1.278... • (Rev(Fi) + Rev(F 2 )) = 1.278... • SRev(Fi x F 2 ),

where 1.278... = w + 1 with w the solution of we w = 1/e.

(ii) There exists a constant c > such that for every k > 2 and every one- dimensional

distributions F±, . . . , Fk,

k

BRev(Fi x • • • x F k ) < clog k ■ REv(Fi) = clogk ■ SRev(Fi x ■■■ x F k ).

Proof. Let Xi be distributed according to Fi, and denote = REv(Fj), so X{ is

stochastically dominated by r^ where Yi is distributed according to ER (see Lemma

[TO]) . Assume that the Xi are independent, and also that the Yi are independent. Then

X±-\ — ■ + X k is stochastically dominated by r{Y\ H — • + r k Y k . By Corollary [T2l the latter

is stochastically dominated by fYi + • • • + fY k where f = (X]j r «)A = R EV (-^i))A-

Therefore BRev(Fi x • ■ ■ x F k ) < fBREv(£'i? xfc ), and the results (i) and (ii) follow from

Lemmas [7] and [8] respectively. ■

3.3 Lower Bounds on the Bundling Revenue

In general, the bundling revenue obtainable from items that are independently distributed

according to different distributions may be significantly smaller than the separate revenue.

Lemma 14 For every integer k > 1 and every one-dimensional distributions . . . , F k ,

k

BRev(F! x ■ • ■ x F k ) > - ■ V REv(F i ) = - • SRev(Fx x ■ • • x F k ).

1=1

Proof. For every i we have Rev(F,) < BRev(Fi x • ■ ■ x F k ), and so J2i R EV (-^j) <

k ■ BRev(Fx x ••• xF fc ). ■

14

This is tight:

Example 15 BRev(Fx x • • • x F k ) = (1/k + e) • SRev(Fi x • • - x F k ) :

Take a large M and let F< have support {0, AP} with P(M i ) = M"\ Then REv(F i ) = 1

and so SRev(F 1 x • • ■ x F k ) = h, while BRev(F x x ■ • • x F k ) is easily seen to be at most

maxi M i ■ (M~* + ■■■ + M~ k ) < 1 + 1/(M - 1).

However, when the items are distributed according to identical distributions, the

bundling revenue cannot be much smaller than the separate revenue, and this is the case

that the rest of this section deals with.

Lemma 16 For every one- dimensional distribution F,

BRev(F x F) > - ■ Rev(F) = - ■ SRev(F x F).

3 3

Proof. Let X be distributed according to F; let p be the optimal Myerson price for X and

q = F(X > p), so Rev(-F) = pq. If q < 2/3 then the bundling auction can offer a price of

p and the probability that the bundle will be sold is at least the probability that one of

the items by itself has value p, which happens with probability 2q — q 2 = q(2 — q)> 4g/3,

so the revenue will be at least 4g/3 • p = (4/3)Rev(F). On the other hand, if q > 2/3

then the bundling auction can offer price 2p, and the probability that it will be accepted

is at least the probability that both items will get value of at least p, i.e. q 2 . The revenue

will be 2q 2 p > {A/3)qp = (4/3)Rev(F). ■

This bound is tight:

Example 17 BRev(F x F) = (2/3) • SRev(F x F) :

Let F have support {0, 1} with P(l) = 2/3, then Rev(F) = 2/3 while BRev(F x F) =

8/9 (which is obtained both at price 1 and at price 2)|^f

We write F* k for the /c-times convolution of F; this is the distribution of the sum of

k i.i.d. random variables each distributed according to F.

Lemma 18 For every integer k > 1 and every one- dimensional distribution F ,

BRev(F xA; ) = REv(F* k ) > ^k ■ Rev(F) = - • SREv(F xfe ).

25 It can be checked that the optimal revenue is attained here by the separate auction, i.e., Rev(_FxF) =

SRev(F xF) = 4/3.

15

Proof. Let X be distributed according to F; let p be the optimal Myerson price for X

and q = ¥(X > p), so Rev(F) = pq. We separate between two cases. If qk < 1 then the

bundling auction can offer price p and, using inclusion-exclusion, the probability that it

will be taken is bounded from below by kq — i^)q 2 > kq/2 so the revenue will be at least

kqp/2 > k ■ Rev(F)/2. If qk > 1 then we can offer price p\_qk\. Since the median in a

Binomial(/c, q) distribution is known to be at least \_qk\ , the probability that the buyer

will buy is at least 1/2. The revenue will be at least p\_qk\/2 > kqp/4 = k ■ Rev(F)/4.

■

We have not attempted optimizing this constant 1/4, which can be easily improved.

The largest gap that we know of is the following example where the bundling revenue is

less than 57% than that of selling the items separately, and applies to all large enough k.

We suspect that this is in fact the maximal possible gap.

Example 19 For every k large enough, a one- dimensional distribution F such that

BREv(F xfc )/SREv(F xfe ) < 0.57 :

Take a large k and consider the distribution F on {0,1} with P(l) = c/k where c =

1.256... is the solution of 1 — e~ c = 2(1 — (c + l)e _c ), so the revenue from selling a

single item is c/k. The bundling auction should clearly offer an integral price. If it

offers price 1 then the probability of selling is 1 — (1 — c/k) k « 1 — e~ c = 0.715...,

which is also the expected revenue. If it offers price 2 then the probability of selling is

1 — (1 — c/k) k — k(c/k)(l — c/k) k ^ 1 « 1 — (c + l)e _c and the revenue is twice that, again

0.715.... If it offers price 3 then the probability of selling is 1 — (1 — c/k) k — k(c/k)(l —

c/k) k ~ x - ( k 2 )(c/k) 2 (l - c/kf- 2 w 1 - (1 + c + c 2 /2)e~ c « 0.13..., and the revenue is

three times higher, which is less than 0.715. For higher integral prices t the probability

of selling is bounded from above by c*/t!, the revenue is t times that, and is even smaller.

Thus BREv(F xfc )/SREv(F xfc ) « 0.715/1.256 < 0.57 for all k large enough.

4 Two Items

Our main result is an "approximate direct sum" theorem. While the main interest, as

stated in Theorem [TJ is for selling two independent items, we will state and prove in the

next section a more general result that applies to two independent sets of items.

4.1 The Main Decomposition Result

In this section X is a fcj-dimensional nonnegative random variable and Y is a /^-dimensional

nonnegative random variable (with k%, ki > 1). While we will assume that the vectors X

16

and Y are independent, we allow for arbitrary interdependence among the coordinates of

X, and the same for the coordinates of Y .

Theorem 20 (Generalization of Theorem [TJ) Let X andY be multi- dimensional ran-

dom variables. If X and Y are independent then

Rev(X, Y) < 2 • (Rev(X) + Rev(Y)).

The proof of this theorem is divided into a series of lemmas. The main insights are

the "Marginal Mechanism" (Lemma |2"T|) and the "Smaller Value" (Lemma [2^]) .

The first attempt in bounding the revenue from two items, is to fix one of them

and look at the induced marginal mechanism on the second. Let us use the notation

Val(X) = E(£\ Xi) = ^ E(Xj), the expected total sum of values, for multi-dimensional

X's (for one-dimensional X this is Val(X) = E(X).)

Lemma 21 (Marginal Mechanism) Let X and Y be multi- dimensional random vari-

ables (here X and Y may be dependent) . Then

Rev(X,F) < Val(Y) +E y [REv(X|y)],

where (X\Y) denotes the conditional distribution of X given Y.

Proof. Take a mechanism that obtains the optimal revenue from (X, Y), and fix some

value of y = (y\, . . . , yk 2 )- The induced mechanism on the X- items, which are distributed

according to (X\Y — y), is IC and IR, but also hands out quantities of the Y items. If we

modify it so that instead of allocating yj with probability qj = qj(x,y), it pays back to

the buyer an additional money amount of qjVj, we are left with an IC and IR mechanism

for the X items. The revenue of this mechanism is that of the original mechanism

conditioned on Y = y minus the expected value of qjVj, which is bounded from above

by Y^jVj- New take expectation over the values y of Y to get E y ^y [Rev(X|F = y)] >

Rev(X,F) - Val(Y). ■

Remark. When X and Y are independent then (X|Y = y) = X for every y and thus

Rev(X, Y") < Val(F) + Rev(X).

Unfortunately this does not suffice to get good bounds since it is entirely possible

for Val(Y) to be infinite even when Rev(Y) is finite (as happens, e.g., for the equal-

revenue distribution ER.) To effectively use the marginal mechanism lemma we will have

to carefully cut up the domain of (X,Y), bound the value of one of the items in each

of these sub-domains, and then stitch the results together. We will use Z to denote an

17

arbitrary mult i- dimensional nonnegative random variable, but the reader may want to

think of it as (X, Y).

Lemma 22 (Sub-Domain Restriction) Let Z be a multi-dimensional random vari-

able and let S be a set of values o/l 26 l Z . Then

REV(l Ze5 Z) < Rev(Z).

Proof. The optimal mechanism for tz^sZ will extract at least as much from Z. This

follows directly from an optimal mechanism having No Positive Transfers (see the end of

Section EU). ■

Lemma 23 (Sub-Domain Stitching) Let Z be a multi- dimensional random variable

and let S, T be two sets of values of Z such that S U T contains the support of Z . Then

REv(l ZeS Z) + Rw(l zeT Z) > Rev(Z).

Proof. Take the optimal mechanism for Z. Rev(Z) is the revenue extracted by this

mechanism, which is at most the sum of what is extracted on S and on T. If you

take the same mechanism and run it on the random variable tz^sZ, it will extract the

same amount on S as it extracted from Z on S, and similarly for T which contains the

complement of S. ■

Our trick will be to choose S so that we are able to bound VAL(l(x,y)eS^)- This will

suffice since the marginal mechanism lemma actually implies:

Lemma 24 (Marginal Mechanism on Sub-Domain) Let X and Y be multi- dimensional

random variables, and let S be a set of values of (X,Y). If X and Y are independent

then

REv(l (x , y)e5 • {X,Y)) < VAL(l (Xi y )e5 F) + Rev(X).

Proof. For every y let S y = {x\(x,y) e S}. Note that REv(l (x> y )e5 • (X,Y)) =

REv(l (Xj y )eS X, l( X ,Y)esY), and REv(l (x ,y) G s^|^ = y) = Rw(txes y X). The Marginal

Mechanism Lemma[2I]then yields REv(l (X5 y )e5 -(X, Y)) < VAL(l (Xi y )e5 F)+Ej / [REv(l Xe5!/ X)],

and by the Sub-Domain Restriction Lemma [221 Re v ( 1 y c <? X ) < Rev(X) for every y. ■

We first deal with the case of two items, i.e. one- dimensional X and Y . The set of

values S for which we bound Val(1( X ,y)<=sY) will be the set {Y < X}.

26 If Z is a /c-dimensional random variable, then S is a (measurable) subset of R5_. We use the notation

Izgs for the indicator random variable which takes the value 1 when Z 6 S and otherwise.

18

Lemma 25 (Smaller Value) Let X andY be one- dimensional random variables. If X

and Y are independent then

E(1 Y < X Y) < Rev(X).

Proof. A possible mechanism for X that yields revenue of VAL(ly<xV) is the following:

choose a random y according to Y and offer this as the price. The expected revenue of

this mechanism is E y ^ Y {y • P(X > y)) = E y ^ Y (E(Yl Y < x \Y = y)) = E(Yt Y <x), so this

is a lower bound on Rev(X). ■

We can now conclude the proof of Theorem [TJ which is the special case of Theorem

[20] when X and Y are one-dimensional.

Proof of Theorem 1201 — one-dimensional case. Using the Sub-Domain Stitch-

ing Lemma we will cut the space as follows: Rev(X, Y) < Rev(1 y <x(X,Y)) +

REV(ljf<y(-X", Y)). By the Marginal Mechanism on Sub-Domain Lemma EU the first

term is bounded by K(t Y <xY) + Rev(X) < 2Rev(X), where the inequality uses the

Smaller Value Lemma [23 The second term is bounded similarly. ■

The multi-dimensional case is almost identical. The Smaller Value Lemma [25] be-

comes:

Lemma 26 Let X and Y be multi- dimensional random variables. If X and Y are ind

Lire la suite

- 333.69 KB
- 15

##### Vous recherchez le terme ""

29

108