Buy-many mechanisms are not much better than item pricing
Shuchi Chawla Yifeng Teng Christos Tzamos












 




0pt
-

 


 
 
 









 figures/ 



multiuser,layout=inline,index
colorsig
scascSC
ytaytYT
ctactCT




theoremTheorem[section]
propositionProposition[section]
lemma[theorem]Lemma
corollary[theorem]Corollary
fact[theorem]Fact
claimClaim

definition
definitionDefinition[section]
exampleExample[section]
mechanismMechanism



numberedtheorem[1]

theorem-1

numberedlemma[1]

theorem-1

numberedcorollary[1]

theorem-1










































 
                        
















































































































































Buy-many mechanisms are not much better than item pricingThis work was supported
      in part by NSF grants CCF-1617505 and CCF-1704117. A preliminary
      announcement of this work is to appear at the ACM EC'19 conference.
    Shuchi Chawla

    University of Wisconsin-Madison. {shuchi@cs.wisc.edu,
      yifengt@cs.wisc.edu, tzamos@wisc.edu}.
Yifeng Teng^†
Christos Tzamos^†

    
=================================================================================================================================================================================================================================

empty




Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations.

We challenge this conventional belief by showing that these large gaps can only happen in restricted situations. These are situations where the mechanism overcharges a buyer for a bundle while selling individual items at much lower prices. Arguably this is impractical in many settings because the buyer can break his order into smaller pieces paying a much lower price overall. Our main result is that if the buyer is allowed to purchase as many (randomized) bundles as he pleases, the revenue of any multi-item mechanism is at most O(log n) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations.

We also show that this result is tight in a very strong sense. Any family of mechanisms of subexponential description complexity cannot achieve better than logarithmic approximation even against the best deterministic mechanism and even for additive valuations. In contrast, item pricing that has linear description complexity matches this bound against randomized mechanisms.












§ INTRODUCTION


It is well known that revenue optimal mechanisms can be complicated:
when a seller has more than one item to sell to a buyer, the seller
may price bundles of items rather than just the individual items;
better still the seller may offer random subsets of items, also called
lotteries; even more surprisingly, the seller may offer an infinitely
large menu of such options. A primary line of enquiry within
algorithmic mechanism design aims to establish simplicity versus
optimality tradeoffs: is it possible to obtain some fraction of the
optimal revenue via simple mechanisms, i.e. mechanisms that can be
described easily, understood easily, and are prevalent in practice?

To quantify this tradeoff let us introduce some standard notation. Let
 denote the optimal revenue obtained by using the most general
kind of mechanism—a menu of lottery pricings. Let  denote the
optimal revenue achieved by a deterministic mechanism—a menu of
bundle pricings. Two “simple” mechanisms have been studied
extensively in literature: item pricings, where each item is assigned
a price and the buyer can buy any subset at the sum of the constituent
prices; and bundle pricings, where every bundle is sold at a
single constant price. The optimal revenues achievable by item
pricings and bundle pricings are denoted  and respectively. The goal then is to bound the ratios /, or
/max(,), etc.

Briest et al. <cit.> were the first to show that revenue optimal
mechanism design exhibits a particularly diabolical curse of
dimensionality: whereas / is equal to 1 when the seller has
only one item to sell, the ratio becomes infinite with three items
even if the buyer is unit demand. Hart and Nisan <cit.> improved this
to show that the ratio is infinite already with just two items. In
fact, if the buyer has additive values over two items, meaning that
the value of the bundle of two items is the sum over the individual
item values, the ratio of / can also be
infinite.[Note that for unit demand buyers =.] Even
focusing on just deterministic mechanisms, the situation is not much
better: the ratio of  to  can be as large as Ω(2^n/n)
with n items and additive values. Daskalakis in his 2014
survey <cit.> summarized the situation as such: 
“Multi-item auctions defy intuition.”

Further work along these lines suggested that the existence of a good
tradeoff depends on properties of the buyer's valuation – both the
structure of the value function as well as the distribution from which
it is drawn. For example, two parallel lines of work investigating
unit demand buyers <cit.> and additive valuation
buyers <cit.> respectively established
that when the buyer's values for different items are drawn
independently, the larger of  and  is within a constant
factor of . These results extend to more general settings with
subadditive valuations <cit.> as well as multiple
buyers <cit.>, but continue to require
some degree of independence across individual item
values.[<cit.>, <cit.>, and <cit.> allow
  item values to be correlated by being defined as linear functions
  over a common set of random variables, but the latter is required to
  be independent. There is one notable exception. 
  Psomas et al. <cit.> perform an investigation
  of smoothed complexity for revenue optimal mechanism design over
  correlated value distributions, where they studied the smoothed revenue 
  achievable after the value distribution is perturbed slightly in different ways.]

Our work presents an alternate view of the simplicity versus
optimality tradeoff. Our thesis is that the curse of dimensionality only
happens when buyers' actions are restricted. 
Let us illustrate through an example adapted from Hart and
Nisan <cit.>. Consider a seller with n items and a single
buyer with additive values. Order all of the 2^n-1 subsets of the
items in weakly increasing order of size, and let S_i denote the
ith set in this ordering. The buyer's value function is picked
randomly from a set of 2^n-1 different types. The ith type is
realized with probability proportional to n^-i and values every
item in the set S_i at n^i/|S_i| and every item not in S_i at
0. It is now straightforward to see that a mechanism  that
offers the set S_i at a price of n^i-1 extracts as revenue a
1/n fraction of the buyer's total expected value, or
Ω(2^n/n)—for every i, the type i buyer extracts the most
utility by purchasing the set S_i. On the other hand, the buyer's
expected value is distributed according to the equal revenue
distribution, and so any bundle pricing extracts at most O(1)
revenue and any item pricing extracts at most O(n). The implication
is that optimal deterministic mechanisms can obtain exponentially
larger revenue than simple ones.

We notice that  disallows buyer from purchasing more than one
set of items offered by the seller. The single-buyer
mechanism design problem is a convenient abstraction for settings with
unlimited supply and multiple i. i. d. buyers. Upon finding a
(near-)optimal mechanism for the single-buyer setting, we can apply
the mechanism as-is in the latter setting, once for each
buyer. However, in that context, mechanisms such as  offer
buyers opportunities for arbitrage. Consider, in particular, a set
S_i of size 2.  sells both of the items in S_i
individually at a price no more than a 1/n fraction of the price of
S_i. A buyer of type i can then participate in the mechanism
twice, purchasing the constituents of S_i individually and paying
far less to the mechanism than before. In effect,  is not
Sybil-proof.

Single-buyer mechanisms can without loss of generality be described as
menus of options where each option is a random allocation
(a.k.a. lottery) paired with a price. In this paper we study Sybil-proof or buy-many mechanisms where the buyer is allowed
to purchase any multi-set of menu options (of arbitrary
size).[When the menu contains lotteries, there is a slight
  distinction between whether the buyer can select a multi-set of
  options adaptively depending on outcomes of previous lotteries, or
  non-adaptively. Our results apply to both settings.] For
deterministic menus, Sybil-proofness simply means that the prices
assigned to different menu options are subadditive over subsets of
items. As a corollary, item pricing and bundle pricing are already
Sybil-proof. For general mechanisms, in fact, imposing the constraint
of Sybil-proofness greatly limits the extent to which mechanisms can
price discriminate between buyers of different types and, in
particular, disallows the gap examples of Briest et al. and Hart and
Nisan.[Babaioff et al. <cit.> previously
  observed that there can be a “small positive constant” revenue gap
  between Sybil-proof and optimal mechanisms, without bounding such a
  constant from below. Our results imply that this gap is unbounded.]

We can now again ask whether arbitrary, complicated Sybil-proof
mechanisms can obtain unboundedly larger revenue (or, even
exponentially or polynomially larger revenue, with respect to the
dimension n) relative to simple mechanisms. Our main result is that
they cannot:

  For any arbitrary distribution over arbitrary valuation functions, 

    / = O(log n).



Here  denotes the optimal revenue achievable through
(potentially randomized) Sybil-proof mechanisms. Briest et
al. <cit.> previously studied the gap between Sybil-proof
mechanisms[Briest et al. used the term “buy-many setting”
  for what we call Sybil-proof mechanisms.] and item pricings for the
special case of unit-demand buyers and proved the same upper
bound. Our main contribution is to extend this result to arbitrary
valuation functions and distributions over valuations. Indeed we make
no assumptions whatsoever on the buyer's valuations other than that
they are monotone non-decreasing in the set of items
allocated—allocating extra items to the buyer never lowers his
value.

Can we do even better? We show that the above result is tight in a
very strong sense:

  
  There exists a distribution over additive values for which no
  mechanism with description complexity at most 2^o(n^1/6) can obtain a
  o(log n) fraction of the optimal deterministic Sybil-proof revenue.

  Observe that item pricings can be described using O(nlog R) bits
  when values lie in the range [1,R]. We construct a distribution
  over additive values with R<n and a deterministic subadditive
  pricing such that no mechanism that can be represented using
  2^o(n^1/6) bits can obtain a o(log n) fraction of the
  revenue of the subadditive pricing. We further show that for
  single-minded buyers, the gap cannot be improved in general even if
  the pricing we are comparing against is a submodular
  function. Briest et al. previously showed a similar result for
  unit-demand buyers, namely that the ratio /
  can be Ω(log n).

  

  
Menu size. Our results also have implications for the
  menu size complexity of optimal auctions. The menu size of an
  auction, defined as the number of different outcomes the seller
  offers to the buyer, has been studied extensively in literature as a
  measure of complexity for single-buyer mechanisms (see, e.g.,
  <cit.>). One criticism of this
  notion of menu size is that some mechanisms can be described much
  more succinctly than indicated by their menu size, as is the case
  for item pricing. Hart and Nisan <cit.> introduced the
  alternate concept of “additive menu size”, namely the number of
  “basic” options a buy-many mechanism offers, and showed that even
  mechanisms with small additive menu size cannot capture a good
  fraction of the optimal revenue.  Our results show that allowing the
  buyer to purchase multiple options doesn't just allow a more
  succinct description of the mechanism, it also fundamentally changes
  the set of mechanisms available to the seller. In particular,
  buy-many mechanisms with even infinite additive menu size cannot
  capture any finite fraction of the overall optimal revenue , as
  their revenue is bounded by .

  Our work calls for a new investigation of additive menu-size
  complexity of Sybil-proof mechanisms.  A natural question, for
  example, is whether one can always obtain a constant fraction of the
  optimal Sybil-proof revenue via mechanisms with finite additive menu
  size. If so, what menu size is necessary to obtain a 1-ϵ
  fraction of the optimal Sybil-proof revenue? Does it matter whether
  the buyer can select multiple options adaptively or non-adaptively?
  We leave these questions to future work.

  

  
Our techniques. Henceforth we will represent
  single-buyer mechanisms as pricing functions that assign a price to
  every possible (random) allocation. For Sybil-proof mechanisms, this
  price corresponds to the cheapest manner in which the buyer can
  acquire a (collection of) lottery(ies) that dominates the desired
  random allocation. For a pricing function p and value function
  v, let _v(p) denote the 
  
  
  revenue the mechanism p obtains from a buyer with value v. When v is drawn
  from a distribution , the mechanism's expected revenue is
  [v∼] _v(p). Our goal is to find for any given
  Sybil-proof pricing p and distribution , a “simple”
  pricing q, such that [v∼] _v(q) is comparable to
  [v∼] _v(p). 

  As a first attempt towards this goal, we ask whether p can be
  “point-wise” approximated by q. That is, does there exist a
  small c>1 such that for all random allocations λ,
  q(λ)/c ≤ p(λ)≤ q(λ)? It turns out that for
  adaptively Sybil-proof pricings p,[Non-adaptive
    Sybil-proofness requires some extra work in dealing with lotteries
    that have valuable items at very very low probabilities of
    allocation.] with q being an additive function, taking c=n
  suffices. Since our eventual goal is to obtain an approximation to
  revenue in expectation over a given value distribution, rather than
  point-wise over each possible lottery purchased, it is reasonable to
  expect that a scaling-type argument would provide an O(log c)
  approximation. In particular, let α be a random power of 2
  between 1/c and 1, and let α q denote the pricing where
  every price in q is scaled by the factor α. Then it holds
  that for any λ, with probability 1/log(c),
  α q(λ) is within [1/2,1] times p(λ). The
  implication is that a buyer purchasing λ under p would
  still be interested in purchasing λ at the cheaper price
  offered by α q, while paying at least half of what he was
  paying under p. However, there is a fallacy in this argument: a
  buyer that purchases λ under p may switch to purchasing a
  much cheaper allocation when offered the pricing α q. Our
  main technical contribution is in dealing with the buyer's incentives
  to argue that even if the buyer switches allocations, the resulting
  revenue is still significant large. 

  Formally we prove the following theorem, that may be of independent
  interest. The theorem states that if a pricing function q point-wise c-approximates a pricing function p, then a
  particular (random) scaling of q obtains an O(log c)-approximation in revenue to p with respect to any arbitrary distribution over valuation functions.

  
  
    For any c>1, let p and q be any two pricing functions
    satisfying q(λ)/c ≤ p(λ) ≤ q(λ) for all
    random allocations λ∈Δ(2^[n]). Then there exists a
    distribution over “scaling factors” α∈ [1/2c,1] such that
    for any valuation function v, E_α[_v(α
    q)]≥1/2log(2c)_v(p).
  












































  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Theorem <ref> shows that approximating a pricing function pointwise
  suffices to obtain a good approximation to the revenue.
  
  Our lower bounds are obtained by considering a weaker notion of approximation
  of a pricing function p using another function q that exactly captures the revenue
  tradeoff over many natural valuation classes. It only requires 
  the approximation be accurate in expectation over the “demand distribution”,
  i.e. the distribution over sets that are
  bought when the function p is offered as a price menu to the
  buyer. We say that a pricing function q, c-approximates from below the pricing function p  over the demand distribution Π if, 
  
    [S∼Π]q(S) 1_q(S)≤ p(S)≥1/c[S∼Π]p(S)


  
























Note that the expectation in the right hand side of (<ref>) is
exactly the revenue of p, while the expectation in the left hand side is a proxy
for the revenue of q. It assumes that the demand distribution over sets remains the same
but a set is bought only if its price under q is not higher than its price under p.

In fact, there is a distribution over single-minded
buyers[Single-minded buyers are interested in buying a specific
  subset S of items at some value.] for
which the expected revenues of p and q are exactly equal to the
expressions above: we pick a set S from the distribution Π and
assign a value of p(S) to every superset of S, including itself,
and a value of 0 everywhere else.

Our lower bounds show that under this weaker notion of approximation,
functions q with subexponential description complexity cannot
obtain better than O(log n) approximation, even for submodular pricing functions
p. This directly implies that no simple
mechanism can get better than logarithmic approximation to the optimal revenue 
for single minded-buyers (Theorem <ref>) and also extends
to the case of additive buyers (Theorem <ref>).











While in general better-than-logarithmic approximation with simple mechanisms
is not possible even for simple valuations, in Appendix <ref> 
we offer improved upper bounds
in special cases where the demand distribution has additional structure.






























§ NOTATION AND DEFINITIONS



We study the following single-buyer mechanism design problem. A seller has n heterogeneous items to sell to a single buyer. The buyer's type is given by a valuation function v that assigns non-negative values to every set of items: v:2^[n]→ℛ_0^+. Values are monotone, meaning that for any S and T with S⊂ T⊆ [n], v(S)≤ v(T). The buyer's type is drawn from an arbitrary known distribution  over the set of all possible valuation functions.

Any selling mechanism can be described as a menu of options, each of which assigns a price to a random allocation or lottery. Let Δ=Δ(2^[n]) denote the set of all probability distributions over sets of items and ∈Δ denote a “lottery” or random allocation. We describe a mechanism using a pricing function p:Δ→ℛ_0^+; The price assigned to a lottery ∈Δ is then given by p().[Since we are not investigating menu size, we will assume that the pricing assigns a price to every lottery. It is easy to extend a partial pricing to a complete one: we assign to every lottery the price of the cheapest option that dominates it, or a price of infinity if no such option exists. For Sybil-proof pricings, we define the price for some lottery λ as being the cheapest way to assemble a random allocation λ' that first-order stochastically dominates λ. See below for a formal definition of dominance among lotteries.]

If a buyer with valuation v buys a lottery ∈Δ at price p(), her utility from the purchase is given by

    u(v,p,):=[S∼]v(S)-p().

If a buyer with valuation v purchases a multiset ={_1, _2, ⋯, _k} of lotteries with price function p, her utility from the purchase is given by

    u(v,p,):=[S_i∼_i ∀ i∈[k]]v(⋃_i S_i)-∑_i∈ [k]p(_i).

We sometimes use v() as shorthand for [S∼]v(S) and v() likewise for the value assigned to the union of sets drawn from a multiset  of lotteries. 



  
Sybil-proofness and optimal revenue. We say that a lottery  dominates another lottery (or a multiset of lotteries) ' if there exists a coupling between a random draw S from  and a random draw (or union of draws) S' from ' such that S is a superset of S'. We are now ready to define Sybil-proofness.


A mechanism or pricing p:Δ→ℛ_0^+ is Sybil-proof if for every multiset  of lotteries there exists a single lottery  dominating it that is no more expensive: p()≤∑_'∈ p(').  


Observe that if a lottery  dominates another lottery (or a multiset of lotteries) ', then any buyer with a monotone valuation function obtains higher expected value from  than from '. We therefore get the following observation:


  Given any Sybil-proof pricing p, for any buyer type v it is optimal for the buyer to purchase a single lottery = _∈Δ (v()-p()).


Given a Sybil-proof pricing p, we use _p(v) := _∈Δ (v()-p()) to denote the lottery purchased by a buyer with value function v, and u(v,p) as the corresponding utility achieved. For convenience, we overload notation and use p(v) := p(_p(v)) to denote the price paid by the buyer. Given a distribution  over buyer types, we write _(p) := [v∼] p(v) as the revenue of the pricing p. The optimal Sybil-proof revenue for distribution  is given as follows; we drop the subscript  when it is clear from the context.

    _ := max_Sybil-proof pricings  p_(p).




  
Adaptive Sybil-proofness. Our definition of Sybil-proofness guards against buyers that purchase multiple options from the given menu and receive a random allocation for each. The buyer can perform even better if these menu options are selected sequentially and adaptively—that is, if the buyer observes the instantiation of each random allocation before deciding whether and what to purchase next. Guarding against such an adaptive buyer places a further restriction on the prices the mechanism can charge. Let 𝒜 denote a buying strategy, that is, an adaptive sequence of lotteries. Let _𝒜 denote the (random) sequence of lotteries bought in 𝒜. As before, we say that 𝒜 is dominated by a lottery  if there exists a coupling between a random draw S from  and a random union of draws S' from _𝒜 such that S is a superset of S'. We can now define a more restrictive definition of Sybil-proofness:


A mechanism or pricing p:Δ→ℛ_0^+ is Adaptively Sybil-proof if for every adaptive buying strategy 𝒜 there exists a single lottery  dominating it that is cheaper: p()≤[_𝒜]∑_'∈_𝒜 p(').  


Of course there is no way for the seller to enforce whether buyers can make purchasing decisions adaptively or non-adaptively, so it is natural to study mechanisms satisfying adaptive Sybil-proofness. Competing against optimal adaptively Sybil-proof mechanisms makes some of our arguments easier. However, all of our positive results also apply to the less restrictive notion of (non-adaptive) Sybil-proofness.






  
Deterministic mechanisms. Deterministic mechanisms price only deterministic sets (a.k.a. bundles) of items—p:2^[n]→ℛ_0^+. A deterministic pricing p is Sybil-proof if and only if it is monotone and subadditive, that is, for any S_1⊂ S_2⊆ [n], p(S_1)≤ p(S_2), and for any set of bundles, 𝒯⊆ 2^[n], the prices of the union of bundles is no more than the sum of individual bundle prices: ∑_S∈𝒯 p(S) ≥ p(∪_S∈𝒯  S). The optimal deterministic Sybil-proof revenue for distribution  is given as follows.

    _ := max_Deterministic monotone
    subadditive pricings  p_(p).




  
Simple pricings. An item pricing is a deterministic additive pricing: p(S) = ∑_i∈ S p({i}) for all S⊆ [n]. A bundle pricing is a constant pricing that assigns the same price to every set: p(S)=p([n]) for all S⊆ [n]. Observe that item pricings and bundle pricings are always Sybil-proof. We use  and  to denote the optimal revenue achievable using item pricings and bundle pricings respectively (over an implicit distribution ).














§ APPROXIMATION VIA ITEM PRICING



In this section we present our main upper bound, namely that the ratio between _ and _ is bounded by O(log n) for any value distribution . This result is based on ideas that are present implicitly in the work of Briest et al. <cit.> for unit-demand buyers. We formalize and extend these ideas to arbitrary valuations. 

Our argument proceeds in two parts. First, we show that in order to approximate the expected revenue of a pricing p with a pricing q within some factor β, it suffices to obtain a point-wise 2^O(β)-approximation of p via q. Then we show that adaptively Sybil-proof pricings p can be point-wise n-approximated by additive pricings. This provides a bound on the gap between adaptive _ and _. In the last part of this section, we extend our result to non-adaptively Sybil-proof pricings. 



 §.§ Point-wise approximation implies revenue approximation


Suppose that we have two pricing functions p and q that are close on every possible (random) allocation. In particular, for some c>1, we have q(λ)/c≤ p(λ)≤ q(λ) for every random allocation λ∈Δ. We say that q point-wise c-approximates p. We will now prove Theorem <ref>, namely that a point-wise c-approximation implies an O(log c)-approximation in revenue. 

 <ref>
    For any c>1, let p and q be any two pricing functions
    satisfying q(λ)/c ≤ p(λ) ≤ q(λ) for all
    random allocations λ∈Δ(2^[n]). Then there exists a
    distribution over “scaling factors” α∈ [1/2c,1] such that
    for any valuation function v, E_α[_v(α
    q)]≥1/2log(2c)_v(p).
  



Our argument considers a suite of pricings {α q} defined over a range of scale factors α∈ [1/2c,1]. We want to argue that this suite of pricings collectively obtains good revenue from every buyer type. At the heart of our argument is the following observation: for any buyer type, if the buyer obtains much larger utility at low prices (1/2c q) than at high prices (q), we can capture a good fraction of this difference in utilities as revenue by picking a scaling factor α from an appropriate distribution independent of the buyer's type. We formalize this observation as Lemma <ref> below. We then argue that if q point-wise approximates p, then this difference of utilities is proportional to the revenue obtained by p from the buyer.



  
  For any pricing q and any 0<ℓ≤ h, let α be drawn from [ℓ,h] with density function 1/αlog(h/ℓ). Then, for any valuation function v,

    E_α[_v(α q)]≥u(v,ℓ q)-u(v,h q)/log(h/ℓ).


To understand the lemma, consider starting at α=ℓ and gradually increasing the scaling factor and, correspondingly, prices. As the prices increases, the buyer's utility from purchasing his favorite bundle weakly decreases. As long as the buyer continues to buy the same lottery, this decrease in utility is captured as revenue. At certain price points the buyer switches to buying a different lottery, causing the revenue to drop discontinuously. Other than these discontinuities, however, the buyer's loss in utility is captured exactly as increase in revenue (see Figure <ref>). This observation allows us to relate the gradient of the revenue as a function of the scaling factor α to the gradient of the utility. Our next observation is that because revenue depends linearly on the scaling factor α (except at the break points), the revenue is proportional to its gradient. Then by picking an appropriate distribution on α, we can capture exactly this gradient as expected revenue. We now present this argument formally.

	


Consider a buyer with value function v. Let (α) denote the utility the buyer derives when offered the pricing α q, and λ_α denote the corresponding lottery purchased:

    (α)     = max_λ∈Δ  (v(λ)-α q(λ))
    λ_α    = _λ∈Δ  (v(λ)-α q(λ)).

By the envelope theorem it holds that '(α) = d/dα(v(λ_α)-α q(λ_α))=-q(λ_α). Therefore, the seller's revenue from this buyer is given by 

    α q(λ_α) = -α'(α).


Now, consider picking α from the equal revenue distribution over [ℓ,h] with density function 1/(αlog (h/ℓ)), and offering the buyer the pricing α q. Then, the expected revenue from this buyer is:

    ∫_ℓ^h  α q(λ_α) ·1/αlog (h/ℓ) dα    =  -1/log (h/ℓ)∫_ℓ^h '(α) dα 
     = (ℓ)-(h)/log (h/ℓ).
  


We are now ready to complete the proof of Theorem <ref>.

Theorem <ref>
  Fix a buyer valuation v, and let h=1 and ℓ=1/2c. We will bound the utility the buyer derives under pricings ℓ q and hq in terms of his utility under p.
 
    u(v,ℓ q) = max_∈Δ(v()-1/2c q()) ≥max_∈Δ(v()-1/2 p()) ≥ u(v,p) + 1/2 p(v).

On the other hand, 

    u(v,hq) = max_∈Δ(v()-q())≤max_∈Δ(v()-p()) = u(v,p).

We can now apply Lemma <ref> to obtain a revenue of at least 1/2log (2c) p(v) from the buyer.

















































 §.§ Upper bound for adaptively Sybil-proof pricings


As a warm-up to our main theorem, we show how Theorem <ref> can be directly applied to get an upper bound on _/_ for adaptively Sybil-proof pricings. We first briefly sketch the proof for deterministic Sybil-proof pricings. Recall that deterministic Sybil-proof pricings are monotone subadditive functions. Let p be any such pricing. Then, by defining q to be identical to p over singletons (q({i})=p({i}) for all i∈ [n]) and extending it additively to bundles (q(S)=∑_i∈ S q({i})), we observe on the one hand that q is no smaller than p on any set S. On the other hand, p(S) is at least as large as the price of the most expensive singleton item in S, which is at least as large as the average price of an item in S, or q(S)/n. Therefore, q point-wise n-approximates p. We can therefore apply Theorem <ref> to obtain an O(log n) approximation to the expected revenue of p under any value distribution. We now formalize this argument for randomized adaptively Sybil-proof pricings.
















For any distribution , we have _≤ O(log n)_.


  Let p be the adaptive Sybil-proof pricing that achieves revenue _. We again begin by defining base prices for each of the items. Informally, these are the minimum prices the buyer needs to pay in expectation to obtain item i with certainty:

    q({i}) = min_∈Δ p()/[i∈]

where we write [i∈] as shorthand for _S∼[i∈ S]. Let _i denote the lottery that defines the price for item i: _i = _∈Δ p()/[i∈]. For every ∈Δ, q()=∑_S⊆[n]λ(S)∑_i∈ Sq({i}).

Observe that for any lottery ∈Δ, the adaptive buyer can draw a set T from  and purchase this set by purchasing for every i∈ T the lottery _i repeatedly until he obtains the item. The expected price paid by the buyer in this strategy is precisely [T∼]q(T) = ∑_i∈ [n] (q({i})[i∈])=q(). Since p is adaptively Sybil-proof, we have p()≤ q().

On the other hand, by the definition of q, p()≥ q({i}) [i∈] and therefore, summing over all i∈ [n] and dividing by n, we have p()≥1/n q(). Taking c=n in Theorem <ref> finishes the proof.




 §.§ Upper bound for general randomized Sybil-proof pricings



We will now prove our main theorem:
<ref>
  For any arbitrary distribution over arbitrary valuation functions, 

    / = O(log n).







As in our argument for the adaptive setting, consider any Sybil-proof pricing p and let us define the pricing q as: 

    q({i}) = min_∈Δ p()/[i∈]  ∀ i∈ [n]      and      q(S) = ∑_i∈ S q({i})  ∀ S⊆ [n].

Our goal, as before, is to argue that q point-wise approximates p. It is straightforward to argue that p() ≥1/n q() for all ∈Δ. However, it is no longer necessarily true that p(S)≤ q(S) for all sets S of items. This is because acquiring the set S non-adaptively with certainty under p may cost much more than q(S). This in turn implies that the buyer's utility under q may be larger than his utility under p. Indeed no matter how large of a scaling factor h we pick, it is tricky to directly argue that u(v,hq)≤ u(v,p). Instead, we will argue that if the set S the buyer wants to purchase under hq is too expensive to purchase under p, this happens because some high value item in S can only be bought with very low probability in p. We will use such items as the basis to construct a different additive pricing that obtains a good fraction of the revenue of p. We now formalize this argument.


  Let p be the Sybil-proof pricing that achieves revenue _. Let ℓ=1/2n, h=4n, and define the pricing q as above. Let α be picked from the range [ℓ,h] with density function 1/(αlog (h/ℓ)). Then for any valuation function v, it is straightforward to observe that u(v,ℓ q)≥ u(v,p)+p(v)/2. We will now focus on bounding u(v,hq).


















Let T_h be the set purchased by the buyer when offered the pricing hq. Then u(v,hq)=v(T_h)-hq(T_h). We want to bound this utility in terms of the utility the buyer gets under the pricing p, so let us consider how much it would cost the buyer to acquire T_h under p. In particular, fix some number m and suppose that the buyer purchases a multiset _m that contains m_i=⌈m/[i∈_i]⌉ copies of _i for all i∈ T_h. Then, the probability that some i∈ T_h does not belong to the random allocation drawn from this multiset is at most (1-[i∈_i])^m_i< 2^-m. Accordingly, the probability that T_h is not a subset of the random allocation drawn from _m is at most n 2^-m. The total price of _m is ∑_i∈ T_h⌈m/[i∈_i]⌉  p(_i) ≤ (m+1)∑_i∈ T_h q({i}) = (m+1)q(T_h). We therefore have:

    u(v,p) ≥ u(v,p,_m) ≥ (1-n 2^-m) v(T_h) - (m+1)q(T_h)   for all  m.


Now, let k be defined such that n 2^-kv(T_h) = q(T_h), that is, k = log(nv(T_h)/q(T_h)). Then we get:

    u(v,p)    ≥ v(T_h) - (k+2)q(T_h)    and,
     u(v,hq)    ≤ u(v,p) + (k+2-h) q(T_h).

Now, if k+2≤ h, then we already have the bound we desire. So, for the remainder of the proof, assume that k>h-2≥ 3n. We will construct a different item pricing to recover the quantity (k+2-h)q(T_h)<kq(T_h) as revenue from the buyer with value v.

For any T⊆ [n] and positive integer a, the (uniform) item pricing  is defined as follows: (S) = 2^a+n q(T) |S| for all S⊆ [n]. Now consider a buyer with value function v and with k = log(nv(T_h)/q(T_h)). When offered the pricing [T_h] with a< k-n-2log n, this buyer obtains a utility of at least v(T_h)-[T_h](T_h) ≥ v(T_h) - 2^a+nnq(T_h)> v(T_h)-1/n2^kq(T_h)= 0. Therefore, the buyer buys at least one item under this pricing and pays at least 2^a+nq(T_h). In other words,

    [T_h](v) ≥ 2^a+nq(T_h)   for  a< k-n-2log n.
 
Let T be drawn from the uniform distribution over 2^[n] and a be drawn from the geometric distribution with mean 2, that is, [a=x]=2^-x-1 for every x∈ℕ. Then, we get:

    [T,a]_v()   ≥1/2^n∑_a=0^k-n-2log n-11/2^a+12^a+nq(T_h) 
        = 1/2 (k-n-2log n-1) q(T_h)
       ≥1/4 kq(T_h)   for  k≥ h-2.


Finally we apply Lemma <ref> with h=4n and ℓ=1/2n:

    log(8n^2) [α]α q(v)    = u(v,ℓ q)-u(v,hq) = u(v,p)-u(v,hq) + 1/2 p(v)


Putting together Equations (<ref>), (<ref>), and (<ref>), we get that for any buyer valuation v:

    log(8n^2)[α]_v(α q) + 4[T,a]_v()   ≥1/2 p(v).


The theorem now follows by taking expectations over the valuation function v and recalling that {α q} and {} are all additive pricing functions.































































§ LOWER BOUND



In this section we present our main lower bound, namely that the O(log n) approximation achieved in the previous section is tight in a very strong sense. We show that there exists a distribution over additive buyer types such that no mechanism with sub-exponential description complexity can o(log n)-approximate the revenue from optimal deterministic Sybil-proof pricing. This implies in particular that no simple mechanism can achieve better than logarithmic approximation, including popular mechanisms studied in previous work such as selling separately, selling the grand-bundle, partition mechanisms or any combination of these mechanisms.

Before presenting our results for additive buyers, we first consider the simpler case where buyers are single-minded, i.e. they are only interested in purchasing a single set.

Our construction proceeds by identifying a large class of subadditive functions that assign independently arbitrary values in [n^1/6,n^1/3] to exponentially many sets S_1,S_2,⋯,S_N. For any function p in this class, pricing according to p extracts full surplus from a distribution over single minded buyers where a buyer wanting set S_i has value p(S_i). Getting an O(log n) approximation for such a distribution as in the previous section is easy by setting the same price for every subset since there are only O(log n) different scales of prices to choose from. However, to obtain a better approximation one would need to charge high or low prices at different sets which requires at least one bit per set to describe. As there are exponentially many sets, mechanisms with subexponential description complexity cannot obtain better than logarithmic approximation.










 §.§ The basic construction and a lower bound for single-minded buyers


Let p and q be any two functions defined over the subsets of [n]. Let  be a demand distribution over sets, ∈Δ(2^[n]). We will say that q c-approximates p from below over  if the following holds:

    [S∼]q(S) 1_q(S)≤ p(S)≥1/c[S∼]p(S).

Our argument will proceed in two parts. First, we will show that for any “small” class of functions q, there exists a subadditive (in fact, submodular) p and a distribution  such that no q in the class can o(log n)-approximate p from below over . Then we will show that for any p and  of the form constructed in the first step, there exists a distribution over valuation functions such that the optimal subadditive revenue is a constant fraction of [S∼]p(S), while the revenue of any other function q is exactly [S∼]q(S) 1_q(S)≤ p(S) for single-minded buyers. Together this will imply the following theorem.



  For any large enough n, there exists a distribution  over single-minded valuation functions over n items and a deterministic submodular pricing function p such that _(p) is a factor of Ω(log n) larger than the revenue of any pricing that can be described using 2^o(n^1/6) bits.


Let us begin by describing the class of subadditive functions p that we will use in our argument. Let 𝒮 = {S_1, S_2, ⋯, S_N} be a collection of N subsets of [n]. Let β = (b_1, ⋯, b_N) be a vector of integers of size N, where each coordinate is picked from the range [,]. We define a partial function  as follows: for all S_i∈𝒮, set (S_i)=b_i. The following lemma follows from the work of Balcan and Harvey <cit.> and shows that we can pick both N and / to be sufficiently large while ensuring that p is submodular.[Matroid rank functions are a subclass of monotone submodular functions, which in turn are a subclass of all monotone subadditive functions.] See the appendix for a proof.


Let N=2^n^1/6/8, =n^1/6, and =n^1/3. Then, there exists a collection of sets 𝒮 = {S_1, S_2, ⋯, S_N}, such that for each i |S_i|=n^1/3; for each i≠ j, |S_i∩ S_j|≤ n^1/6; and for any integral vector β∈ [,]^N, the partial function  can be completed to a matroid rank function.


Let  be the uniform distribution over the collection 𝒮. Our next lemma argues that for any small class of functions 𝒬, there exists a vector β, such that no function in 𝒬 can c-approximate  from below over . Observe that because  only places non-zero mass over sets in 𝒮, we do not need to specify a completion of  for this lemma.


Let m=log(/), c≤ m/8, and 𝒬 be an arbitrary class of functions defined over the subsets of [n] with |𝒬|≤ 2^o(N/4^m). Then there exists an integral vector β∈ [,]^N such that no function q∈𝒬 can c-approximate  from below over .




  Fix a function q∈𝒬. We will pick β from a distribution and show that the probability that q c-approximates the corresponding function  is small. For each i∈ [N], draw b_i independently according to the following truncated geometric distribution: [b_i=2^k]=2^-k/1-2^-m for 1≤ k≤ m. Let h_i = q(S_i)1_q(S_i)≤(S_i) be a random variable that depends on β. Then the statement that q c-approximates  from below over  is equivalent to the statement that 

    ∑_i∈ [N] h_i ≥1/c∑_i∈ [N](S_i).


Observe that over the randomness in β, the variables h_i are independent and bounded. For all i, h_i≤(S_i)≤ 2^m. Furthermore,  

    h_i=q(S_i)[(S_i)≥ q(S_i)]≤ q(S_i) 2/q(S_i) = 2.

On the other hand,

    (S_i)=b_i=m/1-2^-m.
 
We can now bound the probability that (<ref>) holds by applying concentration to the sums of h_i and (S_i) respectively.







    _β[∑_i h_i .    ≥   . 1/c∑_i (S_i)]
       ≤   [∑_i h_i≥1/2c∑_i (S_i)]+[∑_i (S_i)<1/2∑_i (S_i)]
       =   [∑_i h_i≥m/2c(1-2^-m)N]+[∑_i (S_i)<m/2(1-2^-m)N]
       ≤   exp(-2(m/2c(1-2^-m)N-2N)^2/N(2^m)^2)+exp(-2(m/2(1-2^-m)N)^2/N(2^m)^2)
       =   
    O(2^-N4^-m).

Here the third line uses Hoeffding's inequality by observing that 0≤ h_i,(S_i)≤ 2^m; the last line follows using c≤ m/8. The lemma now follows by taking the union bound over all q∈𝒬.



We are now ready to prove Theorem <ref>.

Theorem <ref>
  Let , , N, and 𝒮 be as given in Lemma <ref>. Let  be the uniform distribution over 𝒮. Let m=log(/), c=m/8=Ω(log n), and observe that the class 𝒬 of all pricings that can be described using 2^o(n^1/6) bits has size 2^o(N/4^m). So we can apply Lemma <ref> to obtain a vector β.

Now we will define a distribution  over valuation functions as follows. For i∈ [N], let v_i be the function that takes on value b_i over any superset of S_i and value 0 otherwise. Function v_i is instantiated with probability 1/N. Let p be the completion of  as given by Lemma <ref>. Consider a pricing function that assigns a price of 1/2 p(S) to any set S⊆ [n]. Since this function is subadditive and a buyer with value v_i is single-minded and can afford to buy the set S_i, the mechanism obtains a revenue of 1/2 p(S_i) from this buyer. The mechanism's expected revenue over the distribution  is then 1/2[S∼](S).

On the other hand, for any monotone pricing function q, a buyer with value function v_i purchases the set S_i if and only if q(S_i)≤ v_i(S_i)=b_i=(S_i). Therefore, the revenue of such a function q over  is at most
[S∼]q(S) 1_q(S)≤ p(S).

The theorem now follows by applying Lemma <ref>.





 §.§ A lower bound for additive buyers

We now extend our lower bound to additive value buyers. Our construction is similar to that for Theorem <ref> but there are some subtle differences. As before, let 𝒮 = {S_1, S_2, ⋯, S_N} and β = (b_1, ⋯, b_N)∈ [,]^N. 





We now state and prove our lower bound for additive buyers.


  For any large enough n, there exists a distribution  over additive valuation functions over n items and a deterministic monotone subadditive pricing function p such that _(p) is a factor of Ω(log n) larger than the revenue of any mechanism that can be described using 2^o(n^1/6) bits.


  Let N and 𝒮 be as defined in Lemma <ref>. Let =2n^1/6, =n^1/3, and fix an integral vector β∈ [,]^N. Consider the following distribution _β over value functions. For i∈ [N], v_i,β is an additive function that takes on the value b_i/|S_i| over all items in S_i, and 0 on items not in S_i. Observe that v_i,β is a uniform additive valuation and v_i,β(S_i) = b_i. Function v_i,β is instantiated with probability 1/N. 

Now consider the pricing function  defined over the sets in 𝒮 as (S_i)=1/2 b_i for all S_i∈𝒮, and extended to arbitrary sets in the natural way: (S) = min_A⊆ [N]: ∪_i∈ AS_i⊇ S∑_i∈ A(S_i). Observe that (S_i)<v_i,β(S_i). We claim that  is subadditive and therefore extracts revenue 1/2 b_i from the buyer with type v_i,β. To see this, recall that the buyer obtains positive utility from the set S_i. Suppose the buyer instead decides to buy the collection S_i_1,S_i_2,⋯,S_i_k. Since |S_i_j∩ S_i|≤ n^1/6, v_i,β(S_i_1∪ S_i_2∪⋯∪ S_i_k)≤ kn^-1/6b_i. Thus his utility from buying these sets is at most 

    kn^-1/6b_i-∑_j=1^k1/2b_i_j≤ kn^-1/6-1/2 k  =0.
 
Therefore, we have (v_i,β) = (S_i).

Now let 𝒬 be the class of mechanisms/pricings in the statement of the theorem and fix any q∈𝒬. We will again define a distribution over instances by defining a distribution over the vectors β, as in the proof of Lemma <ref>. Let m=log(/). For all i∈ [N], draw b_i independently from the following truncated geometric distribution: [b_i=2^k]=2^-k/1-2^-m for 1≤ k≤ m.

Let h_i = q(v_i,β) be the revenue q obtained from the buyer with value function v_i,β. Observe that h_i is a random variable that depends on b_i. As before, the variables h_i are independent and bounded by 2^m. Furthermore, we can bound the expectation of h_i by observing that a buyer with valuation v_i,β is an additive buyer with uniform values over items in S_i. Selling a subset of items to this buyer is equivalent to selling fractional amounts of a single item to a single-parameter buyer. The optimal revenue from this buyer, over the randomness in b_i, is bounded by the revenue of single posted price. Therefore, h_i≤ 2. We now apply the same concentration argument as in the proof of Lemma <ref> to obtain

    _β[∑_i h_i≥1/c∑_i (S_i)] ≤ O(2^-N4^-m).

The theorem now follows by taking the union bound over q∈𝒬.































































plainnat






§ DEFERRED PROOFS





















 §.§ Proof of Lemma <ref>

<ref>
Let N=2^n^1/6/8, =n^1/6, and =n^1/3. Then, there exists a collection of sets 𝒮 = {S_1, S_2, ⋯, S_N}, such that for each i |S_i|=n^1/3; for each i≠ j, |S_i∩ S_j|≤ n^1/6; and for any integral vector β∈ [,]^N, the partial function  can be completed to a matroid rank function.


We need the following lemmas from <cit.>.

(Theorem 9 of <cit.>) Let μ and τ be non-negative integers. f:2^[N]→ℝ is called (μ,τ)-large if f(J)≥ 0, ∀ |J|<τ; f(J)≥μ, ∀τ≤ |J|≤ 2τ-2. Then for any sets S_1,⋯,S_N⊆[n], ℐ={I:|I|≤μ∧|I∩ S(J)|≤ f(J),∀ J⊆[N],|J|<τ} is the family of independent sets of a matroid, here S(J)=⋃_j∈ JS_j.



(Theorem 13 of <cit.>) Let G(U∪ V,E) be bipartite graph. G is called a d,L,ϵ-lossless expander if Γ(u)=d, ∀ u∈ U; Γ(J)≥ (1-ϵ)d|J|, ∀ J⊆ U, |J|≤ L. Then if |U|=N, |V|=n, d≥ 2log N/ϵ, n≥ 6Ld/ϵ, a (d,L,ϵ)-lossless expander exists.


We prove that for N=2^n^1/6/8, d=b_max=μ=n^1/3, b_min=n^1/6, ϵ=b_min/4μ=1/4n^1/6, τ=2μ/b_min=2n^1/6, L=2τ=4n^1/6, there exists S_1,⋯,S_N such that for any b_1,⋯,b_N∈[b_min,b_max], f(S_i)=b_i is a matroid rank function.

Let S_j=Γ({j}) in the lossless expander (can check feasible under parameters above). Then |S_j|=d=n^1/3, |S_i∩ S_j|=|S_i|+|S_j|-|Γ({i,j})|≤ 2d-(1-ϵ)2d<n^1/6. Let h(J)=∑_j∈ Jb_j-(μ|J|-|S(J)|).


h is (μ,τ)-large.


Notice that h(J)≥ b_min|J|-ϵ|J|μ=3ϵμ|J|. When |J|≤τ, h(J)≥ 0; when |J|>τ, h(J)≥3ϵμτ=1.5μ>μ.


By Theorem <ref>, ℐ={|I|≤μ∧ |I∩ S(J)|≤ h(J), ∀ |J|< τ} is the family of independent sets of a matroid. For any S_i, pick B_i⊆ S_i such that |B_i|=b_i. Now we show that B_i is a maximum independent subset of S_i. We need to verify the following properties:

	
  * rank(S_i)≤ b_i. This is true since for any S⊆ S_i, if S is independent, then |S∩ S_i|≤ h({i})=b_i.
	
  * B_i is independent. Only need to show that for any J, |B_i∩ S(J)|≤ h(J). When i∈ J, |J|≥ 2, h(J)=b_i+∑_j≠ i,j∈ Jb_j-ϵμ|J|≥ b_i+(|J-1|)b_min-|J|ϵμ≥ b_i since ϵμ=1/4b_min. When i∉J, |B_i∩ S(J)|≤∑_j∈ J|B_i∩ S_j|≤∑_j∈ J|S_i∩ S_j|≤ |J|·2ϵμ<3ϵμ|J|≤ h(J). Thus B_i∈ℐ, then B_i is independent.


Thus for any 𝐛∈[b_min,b_max]^N, f(S_i)=b_i can be extended to a feasible matroid rank function.




§ A CONSTANT UPPER BOUND FOR SPECIAL DEMAND DISTRIBUTIONS



In Section <ref> we proved that we cannot obtain an o(log n)-approximation to deterministic subadditive pricing via simple mechanisms for arbitrary distributions over valuation functions. However, when the distributions satisfy a certain property simple mechanisms, in particular item or bundle pricings, are able to do better.


  Given a deterministic Sybil-proof pricing p and a distribution  over valuations, the demand distribution Π_p, is the distribution over sets of items that specifies the random set of items bought by a buyer with value drawn from  under pricing p: for all S⊆ [n], Π_p,(S) = _v∼[S = _T⊆ [n] (v(T)-p(T))].[Generally speaking, specifying the demand distribution requires specifying a tie-breaking rule between multiple sets of equal utility. We will focus here on single-minded buyers, so the possibility of tie-breaking will not arise.]


Observe that for any pricing p and value distribution , the revenue of the pricing is precisely [v∼]p(v) = [S∼Π_p,]p(S). We will now show that if the buyer is single-minded and the demand distribution is a product distribution over items, then the revenue of p can be approximated by a simple pricing.



Given a deterministic monotone subadditive pricing function p and value distribution  over single-minded values, suppose that the demand distribution Π_p, is a product distribution over items, then _(p)< 22.67max(_,_).


As in the work of <cit.>, we will break up set of items and correspondingly the revenue obtained by p into two components: over one of these components, a.k.a. the core, the price will concentrate around its expectation and can be approximated using a bundle pricing; over the other, a.k.a. the tail, a significant fraction of the revenue will be contributed by singleton items and can be recovered using an item pricing.

We write Π as shorthand for Π_p,. Number the items in decreasing order of their individual prices: p({1})≥ p({2})≥⋯≥ p({n}). For items i∈ [n] let π_i denote the marginal probability that i is purchased, that is, π_i = _S∼Π[i∈ S]. Find the index k∈[n] such that π_1+π_2+⋯+π_k<1/2 and π_1+π_2+⋯+π_k+1≥1/2. The high value, low probability items {1, 2, ⋯, k} will form the tail, and the remaining items will form the core.

For any subset S⊆ [n], define S_=S∩{1,2,⋯,k} and S_=S∩{k+1,⋯,n}. By the subadditivity of p we have p(S)≤ p(S_)+p(S_). Therefore, [S∼Π]p(S_)+[S∼Π]p(S_) is an upper bound of the revenue of p.

We will first bound the contribution of the core, [S∼Π]p(S_) using the following concentration lemma for subadditive functions from <cit.>. To apply the lemma, we observe that p(S_) is Lipschitz with a Lipschitz constant of max_i>k p({i}) = p({k+1}) because S_ contains only items with index larger than k.  


(Corollary 12 from <cit.>) Suppose that f(X) is a non-negative c-Lipschitz subadditive function, where X∈{0,1}^n is drawn from a product distribution D. If a is the median of f, then for any k>0, _X∼ D[f(X)≥ 3a+k]≤ 2^2-k/c.

Setting a = median_S∼Π(p(S_)) and c=p({k+1}), we obtain


    [S∼Π]p(S_)=∫_t≥ 0[p(S_)>t]dt≤ 3a+∫_k≥02^2-k/cdk=3a+4/ln 2c.

We now observe that we can recover both of the terms above using a bundle pricing. In particular, by setting a constant bundle price of a, we obtain a revenue of  a_v∼ [v([n])>a] ≥ a_S∼Π [p(S)>a] ≥ a_S∼Π [p(S_)>a] = a/2. On the other hand, by setting a constant bundle price of c, we obtain a revenue of c_v∼ [v([n])>c] ≥ c_S∼Π [p(S)>c] ≥ c_S∼Π[∃ i≤ k+1: i∈ S]. The latter probability can be bounded from below as:


    _S∼Π[∃ i≤ k+1, i∈ S]=1-(1-π_1)(1-π_2)⋯(1-π_k+1)≥ 1-(1-∑_i≤ k+1π_i/k+1)^k+1≥1-e^-1/2,

where the first inequality follows by applying Jensen's inequality, and the second follows by using ∑_i≤ k+1π_i≥1/2. 


Thus we can bound p(S_) as follows:

    p(S_)≤3a+4/ln 2c≤ 6 +4/(1-e^-1/2)ln 2< 20.67 .


Now we bound p(S_). By subadditivity, 

    p(S_)≤∑_i≤ kp(S_∩{i})=∑_i≤ kπ_ip({i}).
 
Recall that π_1+π_2+⋯+π_k≤1/2. Consider the additive pricing that sells items in {1,2,⋯,k} at item prices q_i=p({i}), and allocates items i>k for free.

Consider a buyer that purchases a set S under pricing p with S_={i}. In the pricing q, the buyer continues to afford the set S at a lower price of q_i=p({i})<p(S). Therefore, the revenue of the pricing q from this buyer is at least q_i=p({i}). Since this buyer is instantiated with probability at least [S_={i}] ≥1/2π_i, we get that p(S_)≤ 2 _(q)≤ 2. Then combining the above cases we get _(p)≤ 22.67max(_,_).






