Welfare and Revenue Guarantees for Competitive Bundling Equilibrium

Abstract

Competitive equilibrium, the central equilibrium notion in markets with indivisible goods, is based on pricing each good such that the demand for goods equals their supply and the market clears. This equilibrium notion is not guaranteed to exist beyond the narrow case of substitute goods, might result in zero revenue even when consumers value the goods highly, and overlooks the widespread practice of pricing bundles rather than individual goods. Alternative equilibrium notions proposed to address these shortcomings have either made a strong assumption on the ability to withhold supply in equilibrium, or have allowed an exponential number of prices.

In this paper we study the notion of competitive bundling equilibrium – a competitive equilibrium over the market induced by partitioning the goods into bundles. Such an equilibrium is guaranteed to exist, is succinct, and satisfies the fundamental economic condition of market clearance. We establish positive welfare and revenue guarantees for this solution concept: For welfare we show that in markets with homogeneous goods, there always exists a competitive bundling equilibrium that achieves a logarithmic fraction of the optimal welfare. We also extend this result to establish nontrivial welfare guarantees for markets with heterogeneous goods. For revenue we show that in a natural class of markets for which competitive equilibrium does not guarantee positive revenue, there always exists a competitive bundling equilibrium that extracts as revenue a logarithmic fraction of the optimal welfare. Both results are tight.

S. Dobzinski—Incumbent of the Lilian and George Lyttle Career Development Chair. Supported in part by the I-CORE program of the planning and budgeting committee and the Israel Science Foundation 4/11 and by EU CIG grant 618128.

M. Feldman—partially supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ERC grant agreement number 337122.

1 Introduction

Competitive equilibria play a fundamental role in market theory and design – they capture the market’s steady states, in which each participant maximizes his profit at equilibrium prices, and supply equals demand such that the market clears [14, Parts III and IV].

This paper focuses on the well-known combinatorial markets model, which consists of a set M of m indivisible goods (or items), and a set N of n consumers. We consider both the extensively studied case of homogeneous goods, and its generalization to heterogeneous goods. Each consumer i has a valuation $v_i:2^M\rightarrow \mathbb R^+$ over bundles of goods. The standard assumptions are that each $v_i$ is normalized ($v_i(\emptyset )=0$) and monotone non-decreasing. A competitive equilibrium is an allocation of the goods to the consumers, denoted by $(S_1,\ldots , S_n)$, together with supporting item prices, denoted by $p_j$ for good j, such that the following two conditions hold:

• 1. Profit Maximization: The profit of every consumer i is maximized by his allocation $S_i$; i.e., for every alternative set of goods T, $v_i(S_i)-\sum _{j\in S_i}p_j \ge v_i(T)-\sum _{j\in T}{p_j}$.

• 2. Market Clearance: All items are allocated; i.e., $\bigcup _iS_i=M$.

Unfortunately, despite their fundamental role, competitive equilibria are only guaranteed to exist in limited classes of combinatorial markets, most notably those in which all valuations are gross substitutes [10, 16]. Intuitively this means that consumers do not view the goods as complementary, so that if the price of one good rises, the demand for other goods does not decline (see Sect. 2 for a formal definition of gross substitutes and other valuation classes).

The standard market model described above implicitly assumes that the goods on the market are exogenously determined, yet in many markets this is not true. For example, there is no inherent reason for beer to be sold in 6-packs rather than, say, 8-packs. This practice of bundling is ubiquitous in real-life markets: It is a well-known method for revenue extraction [13] – e.g., for this reason many airlines set the price of a one-way ticket to be equal to the price of a round-trip ticket. It is also a common mean for avoiding the “exposure” problem due to complementarities – e.g., in the online market for concert ticket resale StubHub.com, a seller holding two tickets may prohibit their separate resale so that if there is no demand for both, she may still enjoy the concert with a friend.

In this paper we study the role of bundling in steadying the market. We will see that bundling introduces new equilibria, and thus can recover stability in markets that lack a competitive equilibrium. The main challenge is whether “good” bundlings exist, i.e., those which result in nearly optimal social efficiency and/or revenue extraction.

1.1 Related Work and Definition of Our Equilibrium Concept

There have been several suggestions in the literature as to how to extend competitive equilibria to accommodate bundling. One direction initiated in [3] is the study of competitive equilibria over bundles that are supported by $2^m$ non-linear bundle prices, possibly personalized per consumer.¹ Auctions that reach such equilibria with personalized prices are studied in [1, 20], while anonymous supporting prices and auctions that reach them for classes of valuations are studied in [11, 22] (see also [18, 19, 21, 24]).

In contrast to this direction, consider perhaps the simplest possible extension of competitive equilibria, in which supporting prices are linear and anonymous. We define a competitive bundling equilibrium to consist of a partition of the goods into bundles, denoted by $\mathcal {B}=(B_1,\ldots , B_{m'})$ and referred to as a bundling, in addition to an allocation $(S_1,\ldots , S_n)$ of the bundles to the consumers, and a price $p_{B_j}$ for each bundle $B_j$. Similar to competitive equilibria, two conditions must hold:

• 1. Profit Maximization: For every consumer i and alternative set of bundles T, $v_i(S_i)-\sum _{B_j\in S_i}p_{B_j} \ge v_i(T)-\sum _{B_j\in T}p_{B_j}$.

• 2. Market Clearance: $\bigcup _iS_i=M$.

An advantage of competitive bundling equilibria is that they always exist. This can be seen, e.g., by naively bundling all goods together and allocating the bundle to the highest-valuing consumer. The social efficiency, however, may reach only a $1\!\,/\!\,n$-fraction of that achieved by the optimal allocation. Hence we will mainly be occupied with seeking better competitive bundling equilibria than the naive one.

A previously studied notion that is closely related to, and inspires, our competitive bundling equilibrium notion is the solution concept known as combinatorial Walrasian equilibrium, introduced in [8]. In this solution concept, only the profit maximization condition must hold and not the market clearance one, and in this sense it is closer in spirit to an algorithmic pricing solution than to a classic market-stabilizing equilibrium.² The main result in [8] is that if one ignores the requirement to sell all the goods, then there is always a bundling together with anonymous and linear bundle prices that achieve at least half of the optimal welfare. The main open problem posed in [8] is whether their result can be extended under the market clearance requirement, and in this paper we address this open question, among others. The open question of [8] received partial treatment also in [9], but with respect to only two restricted classes of valuations. In this work we consider a much more general setting, and in passing generalize the results obtained in [9] for these two classes.³

Applicability. The notion of competitive bundling equilibrium is applicable when bundling is legally or effectively irrevocable. In the seminal paper of [3] this property is referred to as “crates cannot be opened”. Retail markets where bundles are explicitly marked as “not for individual sale” are one example of markets with this property, as is the market for air tickets mentioned above. Sterilized products are another case in which the physical packaging cannot be opened. As another example consider attraction passes – companies like Disney sell bundles of several day passes which are activated upon first entrance, when identification is required from the visitor; the rest of the passes can then only be used by the same visitor. It is even common practice for different producers to bundle together their goods; for example, a travel website can offer bundles of air tickets, hotel rooms and car rental.⁴

A second condition for the applicability of competitive bundling equilibrium is that the market clears. This condition is sometimes violated in markets dominated by a single monopolist, who may attempt to enforce an outcome in which goods are withheld despite positive demand (note this will only succeed if, despite the fact that such markets are often regulated, the monopolist can credibly commit not to sell the goods in the future – see the classic paper of [5] for failure of a monopolist to do so). In competitive markets, however, market clearance is necessary for stability. The standard argument is that in uncleared markets, competing producers have incentive to undercut prices, thus leaving the market unstable (for a thorough discussion see Sect. 10.B of [14]). In addition, markets for resources like spectrum or public land will necessarily clear, since the governmental seller cannot withhold supply arbitrarily.

1.2 Our Results

We establish the existence of competitive bundling equilibria that are approximately optimal with respect to social efficiency and also revenue, where the approximation factors depend on the size of the combinatorial market’s shorter side $\mu =\min \{n,m\}$. While our main focus is on existence of good equilibria, our results are constructive and often tractable.

(I) Welfare for Homogeneous Goods. We refer to combinatorial markets with homogeneous goods as multi-unit settings; in such settings the consumers’ values depend on the number of units they receive. Multi-unit settings have been studied extensively in the literature (e.g., [2, 4, 15, 23]), since this model captures important goods like Treasury bills, electricity and telecommunications spectrum, as well as online advertising. For a recent survey dedicated to multi-unit settings see [17].

The classic result of Vickrey [23] shows that if the consumers’ valuations exhibit decreasing marginal utilities (i.e., the added value from adding a single unit decreases in the size of the existing bundle), then there always exists a competitive equilibrium. This no longer holds in the more general case where valuations exhibit complements among units. We give a complete analysis for competitive bundling equilibria in multi-unit settings and establish the following theorem.

Theorem [Main] (Sect. 4): For every multi-unit market there exists a competitive bundling equilibrium that provides an $O(\log \mu )$-approximation to the optimal welfare. There exist such markets in which the approximation ratio of every competitive bundling equilibrium is $\varOmega (\log \mu )$.

The lower bound in this theorem applies even if all valuations but one exhibit decreasing marginal utilities, and all are subadditive (see Sect. 2 for a definition).⁵

(II) Welfare for Heterogeneous Goods. Our techniques developed for homogeneous goods apply to combinatorial markets with heterogeneous goods as well, yielding the following results.

Theorem [General Markets] (Sect. 5): For every combinatorial market there exists a competitive bundling equilibrium that provides an $\tilde{O}(\sqrt{\mu })$-approximation to the optimal welfare. There exist such markets in which the approximation ratio of every competitive bundling equilibrium is $\varOmega (\log \mu )$.

Theorem [Budget-Additive Consumers] (Sect. 6): For every combinatorial market with budget-additive valuations there exists a competitive bundling equilibrium that provides an $O(\log \mu )$-approximation to the optimal welfare. There exist such markets in which the approximation ratio of every competitive bundling equilibrium is no better than $\frac{5}{4}$.

The gap between the upper and lower bounds is one of two main open questions that arise from this paper.

Theorem [Two Consumers] (See the Full Version [6]): For every combinatorial market with $n=2$ consumers there exists a competitive bundling equilibrium that provides a $\frac{3}{2}$-approximation to the optimal welfare. There exist such markets in which the approximation ratio of every competitive bundling equilibrium is no better than $\frac{3}{2}$.

(III) Revenue. We use our techniques to show a positive result for revenue, in order to highlight the role of bundling in revenue extraction and to demonstrate how the competitive bundling equilibrium notion can be useful even in gross substitutes markets (for which standard equilibria are guaranteed to exist but may possibly extract zero revenue).

Theorem [Revenue] (See the Full Version [6]): For every combinatorial market with valuations belonging to a subclass of gross substitutes there exists a competitive bundling equilibrium that extracts as revenue an $\varOmega (1/\log \mu )$-fraction of the optimal welfare. There exist such markets in which the revenue of every competitive bundling equilibrium is an $O(1/\log \mu )$-fraction of the optimal welfare.

The second main open question that arises from this paper is whether the above result extends to the entire class of gross substitutes.

2 Preliminaries

We briefly address the standard issue of valuation representation and review certain classes of valuations. The expert reader can safely skip this section.

A naïve representation of a valuation is exponential; the standard assumption is thus that valuations are accessed by a succinct oracle. One standard kind of oracle is a demand oracle: Given a consumer valuation v and item prices ${{\varvec{p}}}$, an item set T is in the consumer’s demand set if it maximizes his profit, i.e., $v(T)-\sum _{j\in T}p_j= \max _{U\subseteq M}\{v(U)-\sum _{j\in U}p_j\}$. A demand query returns a member of the demand set under the given prices. The other standard kind of oracle is a value oracle: For a given valuation and bundle, a value query returns the value of the bundle. Even in multi-unit settings, demand queries are known to be strictly stronger than value queries.

An important class of valuations is gross substitutes valuations. A valuation v is a gross substitutes valuation if for every pair of price vectors ${{\varvec{q}}}\ge {{\varvec{p}}}$, for every item set T in the demand set of ${{\varvec{p}}}$, there exists an item set U in the demand set of ${{\varvec{q}}}$ such that U includes every item $j\in T$ whose price did not increase. A unit-demand valuation v is a kind of gross substitutes valuation for which the value of every bundle T is the maximum value of some item in T. A superclass of gross substitutes valuations is subadditive valuations. A valuation v is subadditive if for every two bundles T, U it holds that $v(T)+v(U)\ge v(T\cup U)$. A class of subadditive valuations that are not gross substitutes is budget-additive valuations. A valuation v is budget-additive if there exists b such that for every bundle T we have that $v(T) = \min \{\sum _{j\in T} v(\{j\}), b\}$.

3 Technical Tools

In this section we prepare our main workhorses: Lemmas 1 and 2. These lemmas identify structures – described in Definitions 1 and 2 – from which a competitive bundling equilibrium with certain welfare guarantees can be found in polynomial time utilizing a result of [8]. Subsequent sections of the paper devise and analyze algorithms to construct these structures. We first present the lemmas and then prove them in Sect. 3.1.

Definition 1

A high-demand priced bundling consists of a bundling $\mathcal {B}$ and bundle prices ${{\varvec{p}}}$, such that for every bundle $B\in \mathcal {B}$, there is a set $N_B$ of at least $|\mathcal {B}|$ consumers for whom $v_i(B)-p_B > 0$, i.e., B is strictly profitable.

Lemma 1

For every high-demand priced bundling $(\mathcal {B},{{\varvec{p}}})$, there exists a competitive bundling equilibrium with allocation $S'=(S'_1,\ldots , S'_n)$, whose welfare $\sum _{i\in N} v_i(S'_i)$ is at least the sum of prices $\sum _{B\in \mathcal {B}}p_B$. Moreover, it can be found in ${\text {poly}}(m,n)$ time using demand queries given $(\mathcal {B},{{\varvec{p}}})$.

Definition 2

A bundling $\mathcal B$, bundle prices ${{\varvec{p}}}$ and allocation S over $\mathcal B$ form a partial competitive bundling equilibrium if they constitute a competitive bundling equilibrium for a consumer subset $N'\subseteq N$.

Lemma 2

For every partial competitive bundling equilibrium with bundling $\mathcal B$ and prices ${{\varvec{p}}}$, there exists a competitive bundling equilibrium with allocation $S'=(S'_1,\ldots , S'_n)$, whose welfare $\sum _{i\in N} v_i(S'_i)$ is at least the revenue $\sum _{B\in \mathcal {B}} p_B$. Moreover, it can be found in ${\text {poly}}(m,n)$ time using demand queries given the partial competitive bundling equilibrium.

3.1 Proofs

The proofs of Lemmas 1 and 2 use the following result that is a reinterpretation of [8].

Theorem 1

([8]). In a combinatorial market with general, possibly non-monotone valuations, let $\mathcal B$ be a bundling with bundle prices ${{\varvec{p}}}$. There exist a further bundling $\mathcal B'$ over bundles in $\mathcal B$⁶, and prices ${{\varvec{p'}}}$ and an allocation $S=(S_1,\ldots , S_n)$ over bundling $\mathcal B'$, such that:

• 1. For every i, let $T_i\subseteq \mathcal B$ be the set of original bundles $S_i$ is combined from, and let $U_i\subseteq \mathcal B'$ be the set of new bundles $S_i$ is combined from. Then $\Sigma _{B\in U_i}p'_B\ge \Sigma _{B\in T_i}p_B$.

• 2. $S_i$ is in consumer i’s demand set given prices $p'$, i.e., $v_i(S_i)-\Sigma _{B\in U_i}p'_B$ maximizes i’s profit among all subsets of $\mathcal B'$.

• 3. For every bundle $B\in \mathcal B'$ unallocated in S, $B\in \mathcal B$ and $p'_B=p_B$.

The bundling, prices and allocation can be found in ${\text {poly}}(m,n)$ time using demand queries given $\mathcal B$ and ${{\varvec{p}}}$.

Note that the bundling, prices and allocation guaranteed to exist by the above theorem do not form a competitive bundling equilibrium, as they do not satisfy the market clearance condition.

We will also need the following lemma, which formulates a standard argument and is proven for completeness in the full version of this paper [6].

Lemma 3

(Bucketing – folklore). For every allocation $S=(S_1,\dots , S_n)$ of items M, there exists a value v and an allocation $S'=(S'_1,\dots , S'_n)$ of $M'\subseteq M$, such that $v_i(S'_i)\in [v,2v)$ for every $S'_i\ne \emptyset$, and a logarithmic fraction of the welfare is maintained, i.e., $\sum _{i\in N}{v_i(S'_i)} \ge \frac{1}{2(\log \mu +2)} \sum _{i\in N}{v_i(S_i)}$ where $\mu =\min \{m,n\}$. The value v and allocation $S'$ can be found in ${\text {poly}}(m,n)$ time using value queries given S.

Proof

(Lemma 1). We will show that after applying Theorem 1 to the high-demand priced bundling, all bundles in $\mathcal B$ are allocated. Assume towards contradiction there is a bundle $B\in \mathcal B$ that is not allocated. Then its price remains unchanged by property (3) of Theorem 1. But there are at least $|\mathcal {B}|$ consumers for which B is profitable at this price, hence for property (2) to hold, each of these consumers must be allocated an alternative bundle (otherwise their profit would be 0). However, there are only $|\mathcal B|-1$ bundles except for B, a contradiction.    $\square$

Proof

(Lemma 2). Fix some $\epsilon >0$. Consider the partial competitive bundling equilibrium and denote its consumer subset by $N'$. For every consumer $i\in N'$ for which $S_i$ is not empty, define a new valuation $v^\epsilon _i$ that is identical to $v_i$ except for a shift of $\epsilon$ in the value of $S_i$, i.e., $v^\epsilon _i(S_i)=v_i(S_i)+\epsilon$ (the new valuation may no longer be monotone). For every other consumer i simply set $v^{\epsilon }_i=v_i$. Observe that the partial competitive bundling equilibrium is still a partial competitive bundling equilibrium with respect to the $v^\epsilon _i$’s. Now apply Theorem 1 to get a bundling $\mathcal B'$, allocation $(S'_1,\dots ,S'_n)$ and prices ${{\varvec{p'}}}$. We show that since we started with a partial competitive bundling equilibrium, these bundling, allocation and prices form a competitive bundling equilibrium with respect to the $v^\epsilon _i$’s, that is, all bundles in $\mathcal B$ are allocated. By the latter fact and by properties (1) and (2) of Theorem 1, $\sum _{i\in N} v_i(S'_i)\ge \sum _{B\in \mathcal {B}} p_B$.

To show that we get a competitive bundling equilibrium, since property (2) of Theorem 1 is guaranteed, the only missing component is to show market clearance, i.e., that $\cup _i S_i=M$. Suppose towards a contradiction that there is a bundle $B\in \mathcal B$ that was not allocated. Let i be the consumer that was allocated that bundle in the partial competitive bundling equilibrium. Observe that under the prices of the partial competitive bundling equilibrium, B is the most profitable bundle of i. Now since B is unallocated, its price remaines the same by property (3) of Theorem 1, while the prices of the other bundles can only increase by properties (1) and (3). Thus B is the most preferred bundle for i (with valuation $v_i$ it is only a most preferred bundle), and by property (2) consumer i must be allocated this bundle.

We would now like to show the existence of a competitive bundling equilibrium with respect to the $v_i$’s and not just with respect to the $v_i^{\epsilon }$’s. When taking $\epsilon$ to 0, we get an infinite sequence of allocations and prices. Since the number of allocations is finite and since all prices are bounded between 0 and $\max \{\max _iv_i(M), \max _B(p_B)\}$, there exists a subsequence in which one allocation $\tilde{S}$ repeats and the prices converge to a price vector $\tilde{p}$. Note that it still holds that $\sum _{i\in N} v_i(\tilde{S}_i)\ge \sum _{B\in \mathcal {B}} p_B$.

To finish the proof we now claim that this allocation $\tilde{S}$ and prices $\tilde{p}$ are a competitive bundling equilibrium with respect to the $v_i$’s. Observe that for every $\epsilon$ in the converging subsequence, if consumer i receives $\tilde{S}_i$, then $\tilde{S}_i$ is the unique bundle that maximizes his profit; otherwise, for smaller values of $\epsilon$, $\tilde{S}_i$ is no longer the most profitable bundle for i in contradiction to the assumption that we have a competitive bundling equilibrium for the $v_i^{\epsilon }$’s. Since this is true for every $\epsilon >0$, for $\epsilon =0$ we get that $\tilde{S}_i$ is one of the most profitable bundles for i, which is enough to prove that $\tilde{S}$ and $\tilde{p}$ form a competitive bundling equilibrium with respect to the bundling $\mathcal B$.    $\square$

4 Welfare for Homogeneous Goods

This section focuses on multi-unit markets, where units of a single good may be treated by different consumers as both substitutes and complements. We show existence of a competitive bundling equilibrium that logarithmically approximates the optimal social welfare; this result is tight even when all valuations are subadditive.

Theorem 2

For every multi-unit market with n consumers and m items, there exists a competitive bundling equilibrium that provides an $O(\log \mu )$-approximation to the optimal welfare ${\text {OPT}}$, where $\mu =\min \{m,n\}$. Moreover, it can be found in ${\text {poly}}(\log m,n)$ time using value queries.⁷

Proof

Our goal is to show there exists a high-demand priced bundling whose aggregate price is an $O(\log \mu )$-approximation to ${\text {OPT}}$; the proof of existence then follows by applying Lemma 1.

Consider a welfare-optimal allocation $(O_1,\ldots , O_n)$. We begin by applying Lemma 3, by which there exist a value v and an allocation $(O'_1,\ldots , O'_n)$ of an item subset $M'$, such that (1) for every consumer i with non-empty allocation, $v_i(O'_i)\in [v,2v)$; (2) a logarithmic fraction of the welfare is preserved, i.e., $\sum _{i\le n}{v_i(O'_i)} \ge {\text {OPT}}/\varTheta (\log \mu )$.

Without loss of generality assume $|O'_1| \ge \dots \ge |O'_n|$, and let $n'$ be the largest index such that $O'_{n'}\ne \emptyset$. If $n'=1$, the proof is complete by allocating the grand bundle to consumer 1 for price $v_1(M)$. Assuming from now on $n'>1$, we show how allocation $O'$ can be used to construct a high-demand priced bundling.

Let $\mathcal {B}$ be a partition of all m items into $k:=\lfloor n'/2\rfloor \ge 1$ bundles of roughly equal size – if k does not divide m, place leftover items in one of the bundles arbitrarily. Observe that every bundle $B\in \mathcal {B}$ has size at least $|O'_{k+1}|$. Set the price of every such bundle to $p_B=v-\epsilon$ for some small $\epsilon =\epsilon (v)$. Then all k bundles are strictly profitable for consumers $k+1,\dots ,n'$, and since there are at least k such consumers we have a high-demand priced bundling.

It remains to show that the aggregate price, $k(v-\epsilon )$, is a logarithmic fraction of ${\text {OPT}}$: By choosing $\epsilon \le v/5$, we have that $k(v-\epsilon ) \ge v(2k+2)/5$. Plugging in $2k+2\ge n'$ we get $k(v-\epsilon ) \ge 2vn'/10$, which by the fact that $v_i(O'_i)<2v$ is at least $\frac{1}{10} \sum _{i\le n}{v_i(O'_i)} \ge {\text {OPT}}/ \varTheta (\log \mu )$, completing the existence proof.

We now sketch the proof of the computational result. Assuming $m\gg n$ (the case of interest), we add a preprocessing stage in which units are partitioned into equal-sized bundles of size $m/n^2$ (ignoring leftovers for simplicity). [7] show that the welfare-optimal allocation of such bundles achieves a 2-approximation to the welfare of an optimal unconstrained allocation. Further recall that in any multi-unit setting, there is a computationally efficient constant-approximation to ${\text {OPT}}$. Together with the computational guarantees of Lemmas 1 and 3, this implies that a competitive bundling equilibrium which provides an $O(\log \mu )$-approximation to the optimal welfare can be found in ${\text {poly}}(\log m,n)$ time using demand queries. It is left to show that a demand query in the new setting can be simulated by ${\text {poly}}(\log m,n)$ value queries. Since the total number of original units in any bundle is now a multiple of $m/n^2$, one can use dynamic programming to simulate a demand query as required.    $\square$

Theorem 3

There exists a multi-unit market where $m=n$ and valuations are subadditive, such that every competitive bundling equilibrium has welfare that is a $1/\varOmega (\log m)$-fraction of the optimal.

Table 1. A lower bound for multi-unit markets with subadditive consumers

Proof

Consider the multi-unit market in which $m=n$ and consumer valuations are as described in Table 1. Note that all consumers are subadditive (in fact consumers 2 to n are unit-demand). The optimal allocation in this market allocates each of the consumers a single unit, achieving welfare $\varOmega (\log m)$. We will show that in every competitive bundling equilibrium, consumer 1 is allocated all units, and thus the welfare is only $2+2\epsilon$.

Consider a competitive bundling equilibrium with allocation S over bundling $\mathcal B$, and bundle prices ${{\varvec{p}}}$. Let $i'$ be the smallest index of a consumer whose allocation is non-empty. Observe that all bundles $B\in \mathcal {B}$ must have a common price $p\le 1/ i'$: Clearly consumer $i'$ cannot be charged more than $1/ i'$, and if the price of any bundle $> 1/ i'$, then some consumer’s profit is not being maximized. Now assume towards contradiction that $i'>1$. By the market clearance property, $|\mathcal {B}|\le i'$, and so the total price for all bundles in $\mathcal {B}$ is at most 1. Consumer 1 will thus strictly increase his profit by buying all bundles in $\mathcal {B}$, in contradiction to the profit maximization property of a competitive bundling equilibrium. This completes the proof.    $\square$

In the full version we strengthen Theorem 3 by showing it holds even when lotteries are allowed.

5 Welfare for Heterogeneous Goods

In this section we consider general combinatorial markets, and show that for every such market there exists a competitive bundling equilibrium whose allocation achieves a $\tilde{O}(\sqrt{\mu })$-approximation to the optimal welfare. In the full version of this paper, we also address computational aspects (see [6]).

Theorem 4

For every combinatorial market with n consumers and m goods, there exists a competitive bundling equilibrium with welfare that is a $\tilde{O}(\sqrt{\mu })$-approximation to the optimal welfare ${\text {OPT}}$, where $\mu =\min \{m,n\}$.

Proof

Apply Lemma 3 to the welfare-optimal allocation $(O_1,\dots ,O_n)$ to get a value v and an allocation $S=(S_1,\dots ,S_n)$ of items $M'\subseteq M$. Without loss of generality, assume that exactly the first r allocated parts in S are non-empty (r must be $\le \mu$), so that (1) for every consumer $i\in [r]$, $v_i(S_i)\in [v,2v)$; (2) a logarithmic fraction of the welfare is preserved, i.e., $\sum _{i\in [r]}{v_i(S_i)} \ge \frac{1}{O(\log \mu )}\sum _{i}v_i(O_i)$. By applying Lemma 4 below to the value v and allocation S, we get an $O(\sqrt{r})=O(\sqrt{\mu })$-approximation to the welfare of S, which is an $\tilde{O}(\sqrt{\mu })$-approximation to ${\text {OPT}}$.    $\square$

The proof of Theorem 4 relies on the following lemma.

Lemma 4

Let v be a value and $S=(S_1,S_2,\ldots ,S_r)$ an allocation of items $M'\subseteq M$ to the first r consumers, such that $\forall i\in [r]$, $S_i\ne \emptyset$ and $v_i(S_i)\in [v,2v)$. Then there is a competitive bundling equilibrium that achieves an $O(\sqrt{r})$-approximation to the welfare of S.

Proof

We show how to construct a high-demand priced bundling whose aggregate price is an $O(\sqrt{r})$-approximation to the welfare of S. The proof is then established by invoking Lemma 1.

Beginning with $S_1,\dots ,S_r$, we create new bundles by joining sets of $\lceil \sqrt{r}\rceil$ $S_i$s, adding leftovers to the last bundle (which contains between $\lceil \sqrt{r}\rceil$ and $2\lceil \sqrt{r}\rceil$) $S_i$s). Items in $M\setminus M'$ are also added to the last bundle. Let $\mathcal {B}$ denote the resulting bundling, and set a price $p_B=v$ for every $B\in \mathcal {B}$. The pair $(\mathcal {B},{{\varvec{p}}})$ is a high-demand priced bundling: By construction, $|\mathcal {B}| \le \sqrt{r}$, and every bundle $B\in \mathcal B$ is profitable for at least $\sqrt{r}$ consumers (those who were originally allocated the $S_i$s it contains).

Now, recall that $\sum _{i\in [r]}{v_i(S_i)} \le 2vr$. Since no bundle $B\in \mathcal {B}$ contains more than $2\lceil \sqrt{r}\rceil \le 2\sqrt{r}+2$ $S_i$s, then $|\mathcal {B}|\ge r/(2\sqrt{r}+2)$, and so the proof is complete:

$$\begin{aligned} \sum _{B\in \mathcal {B}} p_B = |\mathcal {B}|v \ge \frac{rv}{2\sqrt{r} + 2} \ge \frac{1}{4\sqrt{r}+4} \sum _{i\in [r]}{v_i(S_i)}. \end{aligned}$$

   $\square$

6 Welfare for Budget-Additive

In Sect. 5 we showed that every combinatorial market admits a competitive bundling equilibrium that provides an approximation ratio of $\tilde{O}(\sqrt{m})$ to the social welfare. A natural next step is to understand whether we can get better approximation ratios for specific subclasses. We make progress towards this goal by showing that if the valuations are all budget-additive then we can get a logarithmic approximation. The best lower bound we currently know shows that no market with budget-additive valuations can achieve an approximation ratio better than $\frac{5}{4}$ (for the proof, see the full version of this paper [6]).

Theorem 5

In every combinatorial market with budget-additive valuations, there is a competitive bundling equilibrium with welfare that is an $O(\log m)$-approximation to the optimal welfare.

We henceforth describe a high-level proof of Theorem 5 (see the full version of this paper [6] for details). Our proof is constructive and proceeds as follows: We first compute an allocation $A=(A_1,\ldots ,A_n)$ by running (a slight variation of) the greedy algorithm of [12] for submodular valuations. This algorithm considers the items one by one in an arbitrary order, and allocates each item to a consumer that maximizes the marginal value for it given the items he received until now. This allocation is known to achieve a constant approximation to ${\text {OPT}}$ for submodular valuations.

Next, our goal is to identify a subset of the bundles ($A_i$’s) that can be converted into a partial equilibrium on the one hand, and give (at least) a logarithmic approximation to ${\text {OPT}}$ on the other hand. Given such a subset, we can then apply Lemma 2 to complete the proof. The non-trivial challenges are: (1) how to allocate the items that do not belong to the identified subset of bundles, and (2) how to price the bundles to ensure profit maximization for the corresponding consumers.

To address these challenges, we distinguish between two cases: If most of the welfare of A comes from consumers who have exhausted their budgets (i.e., $v_i(A_i)=b_i$), we identify a subset of the buyers $S_b$ with budgets $b_i\in (b,2b]$ for some b, who contribute a logarithmic fraction of the welfare of A. Then, for every consumer $i \in S_b$, we bundle up the items in $A_i$ into a bundle, and add the remaining items (i.e., those not belonging to any of the consumers in $S_b$) to an arbitrary consumer in $S_b$. We then price each bundle at a uniform price of b. It is not too difficult to verify that this is a partial competitive bundling equilibrium with respect to the consumers in $S_b$.

If most of the welfare of A comes from consumers who have not exhausted their budgets (i.e., $v_i(A_i) < b_i$), for every non-exhaustive consumer i, we bundle up the items in $A_i$ into a bundle, and add the remaining items, T, to the non-exhaustive consumer $i^*$ who maximizes the value $v_i(A_i \cup T)$. We charge every consumer exactly his valuation for the allocated bundle (so each one gains zero utility). The greediness of the initial algorithm ensures that every non-exhaustive consumer maximizes his profit over all allocations $A_i$ given to other non-exhaustive consumers. It remains to show that this holds also with respect to the consumer $i^*$. But this is clear by the definition of $i^*$ as the consumer who maximizes the valuation for this bundle. It follows that this is a partial competitive bundling equilibrium with respect to the non-exhaustive consumers.