Revenue Maximization Envy-Free Pricing for Homogeneous Resources

1 Introduction

Pricing-based mechanisms become a key approach to allocate resources in multi-agent systems. For example, in sponsored search ad-slots are sold in online auctions [Nisan et al., 2009]. Main objectives in designing such mechanisms could include social welfare maximization, revenue maximization, strategy-proofness and/or fairness. In this paper, we consider the problem of assigning m homogeneous items or resources among n buyers without budgets, where agents valuations depend only on the number of items they get. This multi-unit settings allows us to highlight and concentrate on the simplest case where allocating different number of items to different agents plays a crucial role, i.e., it is arguably the most basic variant of combinatorial auctions. Somewhat astonishingly, this very simple settings generates a rich set of problems to study. Still, this limited setting seems to be of practical importance as these items could be homogeneous server grids or supercomputers in computer networks, power supply in manufacture systems, cargo space in transportation industry and etc. Our goal is to design polynomial pricing mechanisms that maximize the seller's revenue and assign items to buyers in a fair manner. One of

Qiang Zhang

University of Warsaw, Poland qzhang@mimuw.edu.pl

the common notions used to model fair division is envyfreeness, where each agent believes that he is treated the best. Envy-freeness dates back to twenty century [Foley, 1967; Varian, 1974] and is still an intense research topic in mathematics, computer science and economics. Different notions of envy-freeness have been proposed and studied in the literature. For example, envy-freeness was defined to denote the outcomes where all buyers receive the allocations they prefer the most at given prices [Bil`o et al., 2014; Briest, 2008; Chen and Deng, 2010; Guruswami et al., 2005; Hartline and Koltun, 2005]. As the prices for unsold items are not necessarily zero, this is a relatively weaker notion than Walrasian equilibrium (WE) [Walras, 1954]. On the other hand, following suggestions from classical papers [Foley, 1967; Varian, 1974], envy-freeness has also been defined in outcomes where buyers prefer their allocations to the allocations received by other agents [Colini-Baldeschi et al., 2014; Feldman et al., 2012; Fiat and Wingarten, 2009]. Throughout this paper, we will call the latter notion pair envy-freeness. It is easy to see that WE ⊂ envy-freeness ⊂ pair envy-freeness.

With respect to pricing mechanisms, Guruswami et al. [2005] showed that the Vickrey-Clarke-Groves (VCG) mechanism could return envy-free outcomes in polynomial time when buyers can buy only single items, i.e., unit-demand valuations. However, VCG not only fails to deliver envyfree outcomes in our setting, but also could result in poor revenues. Hence, we need to propose different mechanisms for the case studied here. First of all, we observe that for both our notions of envy-freeness we can restrict our attention to bundle pricing schemes, where the seller sets up a price for each bundle size and the payment of buyer i is the price of the bundle assigned. If a price for a given bundle size is infinite it can be seen as not selling items at this quantity at all, e.g., in many cases we are offered to buy a single item, or a fixed multi-pack of items at a discounted price. In other words, envy-freeness implies that we have to avoid price discrimination [Carlton and Perloff, 1990], i.e., sell the same bundles to different agents at different prices. In some cases we might want to be even less discriminatory and apply item pricing [Feldman et al., 2012; Colini-Baldeschi et al., 2014], where the seller sets up an uniform price p ∈ R for each item and the payment of buyer i is proportional to the number of items he receives.

Bundle pricing is more general and powerful and so allows to extract more revenue than item pricing. However, as we will present, envy-free or pair envy-free bundle pricing is more difficult to compute. Since revenue maximizing envy-free or pair envy-free pricing is trivial for unit-demand valuations in multi-unit settings, we consider the following common types of valuations: single-minded valuations with free disposal - each buyer wants a particular number of items and when he receives more items his valuation remains the same; non-decreasing valuations - the valuation depends on the number of items, but cannot decrease with increasing number of items; general valuations - there is no restriction on how the valuation depends on the number of items.

Our results We provide upper and lower bounds for item and bundle pricing for the two notions of envy-freeness. The results are summarized in Table 1. Although, the problems studied here are rather basic, some of them are quite challenging. Our paper should be seen as opening this research direction and naturally it leaves a few open problems for further research as exemplified by empty cells in Table 1.

Related Work Revenue maximizing envy-free pricing has drawn a lot of attention recently. The differences between our study and previous work are summarized as follows. First, most of the existing work studies the case of heterogeneous items (aka, multi-good settings) [Briest, 2008; Chen and Deng, 2010; Cheung and Swamy, 2008; Guruswami et al., 2005; Hartline and Koltun, 2005], or the case that buyers have budgets [Colini-Baldeschi et al., 2014; Feldman et al., 2012]. There are also some studies of unlimited supply, e.g., [Balcan and Blum, 2007; Chalermsook et al., 2012; Fiat and Wingarten, 2009; Briest and Krysta, 2006]. This is the first paper to consider the problem in multiunit setting without budgets. Second, compared to existing works that usually have assumptions on the valuations of buyers such as single-minded or non-decreasing valuations, we consider general valuations as well. Third, our study is related to combinatorial walrasian equilibrium, a generalization of Walrasian equilibrium, as given in [Feldman et al., 2013] where authors consider revenue maximization problems in which buyers have non-decreasing valuations and the seller could package the items into indivisible bundles, but in contrast to the classical notion of Walrasian equilibrium they allow unsold bundles to have nonzero prices and do not require market clearance. This notion is very similar to the envy-free bundle pricing in our paper. In comparison to [Feldman et al., 2013] we give a simpler O(logn) approximation mechanism that is especially tailored to our case. The O(logn) approximation mechanism could also apply to their settings. In addition, recently Dobzinski et al. [2014] studied welfare and revenue guarantees on competitive bundling equilibrium that is a similar notion of combinatorial walrasian equilibrium but requires market clearance.

2 Preliminaries

A multi-unit pricing problem A = 〈n,m,V〉 consists of n buyers, m homogeneous items and a valuation profile V = 〈v1, . . . , vn〉, where vi = 〈vi(0), vi(1), . . . , vi(m)〉 and vi(j) ∈ R+ is the value buyer i has for j items. We assume that for any i ∈ {1, . . . , n}, vi(0) = 0. We assume that vi(j) is also the maximum payment buyer i is willing to pay for j items.

In this paper, we consider single-minded valuations with free disposal, non-decreasing valuations and general valuations. We say buyers have single-minded valuations with free disposal if each buyer i has a fixed value wi for receiving at least ki items, and has value 0 for receiving less than ki items. Formally, the valuations of any buyer i for different numbers of items are represented as vi(k′ ) = 0 for all 0 ≤ k′ < ki and vi(k′ ) = wi for all ki ≤ k′ ≤ m. We say buyers have non-decreasing valuations if for any i ∈ {1, . . . , n} and j ∈ {1, . . . ,m- 1}, it holds that vi(j) ≤ vi(j + 1). Finally, we say buyers have general valuations if there is no assumption on the valuations of buyers.

We consider both item pricing and bundle pricing schemes. In item pricing scheme, a fixed price p ∈ R for each additional item is to be determined and the payment of buyer i is proportional to the number of items he receives, that is, pi = xip. W.l.o.g., we write outcomes in item pricing scheme as 〈X, p〉, where buyer i gets xi ∈ X items and the price per item is p. An item pricing outcome 〈X, p〉 is feasible if and only if all the following conditions hold:

1. supply constraint: it holds xi ∈ {1, . . . ,m} for every i ∈ {1, . . . , n} and ∑ni=1 xi ≤ m;
2. individual rationality: for every i ∈ {1, . . . , n}, it holds vi(xi) ≥ p · xi;
3. non-negative payments: p ≥ 0.

Given an item pricing outcome 〈X, p〉, the utility ui(xi, p) of buyer i is given by vi(xi) - xi · p. The revenue r(X, p) of the outcome is the total payment of buyers, i.e., r(X, p) = ∑ni=1 xip. Given an item pricing outcome, we say buyer i envies the allocation if the utility of buyer i is not maximized, that is, xi /∈ argmaxy vi(y)-p · y. An item pricing outcome 〈X, p〉 is envy-free if no buyer envies the allocation. Given an item pricing outcome, we also say buyer i envies buyer i′ if buyer i prefers buyer i′ 's assignment, that is, ui(xi, p) < ui(xi′ , p). An item pricing outcome 〈X, p〉 is pair envy-free if no buyer envies other buyers.

In bundle pricing scheme, prices for different sizes of bundles are to be determined and the payment of buyer i is equal to the price of the bundle he gets. W.l.o.g., we write outcomes in bundle pricing scheme as 〈X,P〉, where buyer i gets xi ∈ X items and the price for the bundle of j items is pj ∈ P. From now on, we will use p(j) instead of pj . W.l.o.g, we assume p(0) = 0. A bundle pricing outcome 〈X,P〉 is feasible if and only if the following conditions hold:

1. supply constraint: it holds xi ∈ {1, . . . ,m} for every i ∈ {1, . . . , n} and ∑ni=1 xi ≤ m;
2. individual rationality: for every i ∈ {1, . . . , n}, it holds vi(xi) ≥ p(xi);
3. non-negative payment: ∀j ∈ {0, 1, . . . ,m}, p(j) ≥ 0.

Given a bundle pricing outcome 〈X,P〉, the utility ui(xi, p(xi)) of buyer i is given by vi(xi) - p(xi). The revenue r(X,P) for the outcome is the total payment of buyers, i.e., r(X,P) = ∑ni=1 p(xi). Similar to item pricing scheme, given a bundle pricing outcome 〈X,P〉, we say buyer i envies the allocation if the utility of buyer i is not maximized, that is, xi /∈ argmaxy vi(y) - p(y). A bundle pricing outcome 〈X,P〉 is envy-free if no buyer envies the allocation. Given a bundle pricing outcome, we also say buyer i envies buyer i′ if buyer i prefers buyer i′ 's assignment, that is, ui(xi, p(xi)) < ui(xi′ , p(xi′)). A bundle pricing outcome 〈X, P〉 is pair envy-free if no buyer envies other buyers.

In this paper we study the following problems of revenue maximizing item pricing and bundle pricing outcomes in multi-unit settings under these two notions of envy-freeness.

Definition 1. The envy-free item pricing multi-unit (EFIPMUL) problem: Given 〈n,m,V〉, compute a feasible and envy-free item pricing outcome 〈X, p〉 that maximizes the revenue r(X, p).

Definition 2. The pair envy-free item pricing multi-unit (PEFIP-MUL) problem: Given 〈n,m,V〉, compute a feasible and pair envy-free item pricing outcome 〈X, p〉 that maximizes the revenue r(X, p).

Definition 3. The envy-free bundle pricing multi-unit (EFBPMUL) problem: Given 〈n,m,V〉, compute a feasible and envy-free bundle pricing outcome 〈X,P〉 that maximizes the revenue r(X, P).

Definition 4. The pair envy-free bundle pricing multi-unit (PEFBP-MUL) problem: Given 〈n,m,V〉, compute a feasible and pair envy-free bundle pricing outcome 〈X,P〉 that maximizes the revenue r(X,P).

We call the outcomes that maximize the revenue the optimal outcomes. Optimal outcomes are denoted by OPT = 〈XOPT, pOPT〉 in item pricing schemes and OPT = 〈XOPT,POPT〉 in bundle pricing schemes, respectively.

2.1 AKey Lemma

In this section, we present a key lemma that will be heavily used when we study the revenue for pair envy-freeness. Let us first define a weaker notion of feasibility.

Definition 5. An outcome is nearly-feasible if it satisfies only individual rationality and non-negative payment (i.e., it does not satisfy supply constraint).

The following key lemma transforms a nearly-feasible and pair envy-free outcome selling at item pricing y to a feasible and pair envy-free outcome selling at least m2 items at item pricing p ≥ y.

Lemma 1. Consider the PEFIP-MUL problem, given a nearly-feasible and pair envy-free outcome 〈O, y〉, there exists a feasible and pair envy-free outcome 〈X, p〉 such that 2 · r(X, p) ≥ m · y.

Proof. Let nj be the number of buyers who receive j items in O. We give a constructive proof where two cases are considered as follows.

First, suppose there exists a j ∈ {1, . . . ,m} such that j · nj ≥ m2 . In this case, the first step is to construct an outcome where only bundles of size j are sold at price y per item. Hence, by the property of pair envy-freeness, if any buyer receives j items, all buyers with positive ui(j, y) would also demand j items. In addition, buyers with ui(j, y) = 0 are indifferent between receiving j items and nothing, and buyers with negative ui(j, y) demand nothing. Now let m′ be the number of items demanded by buyers with positive ui(j, y). If m′ ≤ m, we sell j items to all buyers with positive ui(j, y) and as many buyers with ui(j, y) = 0 as possible under the supply constraint. In this way, we get a feasible outcome that extracts a revenue of at least m2 y. If m′ > m, we increase the price from y to p which is the minimum price that we have enough items to satisfy the demands of buyers with positive ui(j, p). Similarly at price p, we get a feasible outcome that extracts a revenue of at least m2 p by selling j items to all buyers with positive ui(j, p) and as many buyers with ui(j, p) = 0 as possible.

Otherwise, we repeat the following process until there are enough items to satisfy the demand of all buyers or the first case is reached. Arbitrarily pick a bundle size j that is sold, remove j from the bundles sold in the outcome and then recompute the best bundles for all buyers given the fact that bundles of size j are not available. Since we are not in the first case, it implies that at most half of the revenue is lost when we remove bundle j. Considering the first time that the total demand for the best bundles of all buyers is smaller than m/2. In such case in the previous round there is a bundle such that the total demand for it is more than m/2 items. We reach a contradiction since the process would end before. It concludes that by this process we will obtain a feasible outcome that extracts a revenue of at least m2 y.

3 Envy-free ItemPricing

In this section, we consider the EFIP-MUL problem. The envy-freeness requires that, given an uniform price per item, each buyer gets the number of items that maximizes his utility. The main result is to solve the EFIP-MUL problem optimally via a dynamic programming for general valuations. The technique also applies to non-decreasing valuations since the input size is the same. Additionally, we also consider the EFIP-MUL problem when buyers are single-minded.

3.1 General Valuations

In this section we assume that the input size of the EFIP-MUL problem is Θ(nm). Note that it is also essential to know all vi(j) in order to check if an outcome is envy-free or not. First, we introduce some notations. Given a buyer i and a price p, let Di(p) be the set of bundles that maximize the utility of buyer i, i.e., Di(p) = argmaxj ′∈{0,1,...,m} ui(j ′ , p). We call Di(p) the demand set of buyer i given p. Let si be the size of the demand set of Di(p). It is clear that there are at most O(m) elements in Di(p), i.e., si ≤ m + 1. We denote Di(p) = {D1 i (p), . . . ,Dsi i (p)}. Let Pi include the set of prices such that Di(p) ̸= Di(p + ϵ) where ϵ is a small quantity. An easy way to get Pi is to take any two valuations vi(j) and vi(j ′ ), where j ̸= j ′ , compute the price p such that vi(j)-p · j = vi(j ′ )-p · j ′ and include p in Pi if p ≥ 0. For example, when j = 0 we have all the prices p such that there exists a bundle j such that vi(j) - p · j = 0. Hence, the size of Pi is polynomial in m. The following lemma gives us the set of possible optimal prices:

Lemma 2. Consider the EFIP-MUL problem, given an optimal outcome, the price pOPT is in ⋃i∈{1,...,n} Pi.

For each p ∈ ⋃i∈{1,...,n} Pi, the maximum revenue given price p is computed through a dynamic programming. Let z(i, d) be the maximum revenue that at most d copies of the items are sold to the first i buyers. Initially z(0, d) = 0 for all d = 1, . . . ,m. To compute z(i, d) for i = 1, . . . , n, d = 1, . . . ,m, we use the recursion as follows: 1

where [si] = {1, . . . , si}. The maximum revenue at price p is given as z(n,m). The memory required in the dynamic programing is O(nm), and the number of operations is O(nm2 ). By Lemma 2, we can compute the maximum revenue for every candidate price and then output the optimal revenue.

Theorem 1. The envy-free item pricing multi-unit (EFIPMUL) problem is solvable in polynomial time.

3.2 Single-minded Valuations with Free Disposal

Let us now discuss the EFIP-MUL problem when buyers have single-minded valuations with free disposal. It is necessary to have a different algorithm for this case due to the fact that the input size is much smaller than for general valuations. As single-minded buyers could be described by two parameters, wi and ki, the input of this problem has size Θ(n logm) only. Hence, we are interested in revenue maximizing item pricing schemes with the running time polynomial in n and logm, but not in n and m as it was the case in the previous section.

One can show that the EFIP-MUL problem cannot be solved efficiently unless P = NP by the reduction from the Subset Sum problem. For the upper bound, we argue that there exists an FPTAS for the EFIP-MUL problem. The idea of the FPTAS is similar to the optimal envy-free item pricing for general valuations. First, there still exists a polynomial number O(n) of possible optimal prices. We need the following arguments to prove this. Given any price p > 0, the demand set of buyer i contains either 0 items, or ki items or both. By the similar arguments as Lemma 2, the set of possible optimal price is ⋃ni=1 wi ki . Second, given any possible price, if there are not enough items to satisfy the buyers whose demand sets do not contain 0, then the price is not feasible. Otherwise, besides satisfying the demand of such Algorithm 1: A logarithmic approximation algorithm for general valuations in PEFIP-MUL.

1 For a number a ∈ R, [a]+ returns 1 if a ≥ 0, and 0 otherwise.

1 for p ∈ P do 2 For any j ∈ {1, . . . ,m}, let nj be the number of buyers such that the bundle of j items is the largest one they have non-negative utilities for at price p; 3 Sell bundles with sizes at least z where z = argmaxj j ∑mk=j nk; 4 Let ¯nj be the number of buyers who demand j items at price p if only bundles of at least z items are sold; 5 if ∑mj≥z j · ¯nj ≤ m then 6 Assign j ≥ z items to the buyers who demand j items and charge each of them p · j; 7 else 8 Apply Lemma 1 to obtain a feasible outcome;

9 Output the outcome with the maximum revenue.

buyers, one could simply use the FPTAS for knapsack problem to assign the remaining items. This process would give (1 - ϵ)-approximation to the optimal revenue at the given price. Together with the fact the number of choices for the optimal price is polynomial in n, this gives an FPTAS for the EFIP-MUL problem in the case of single-minded buyers with free disposal.

Theorem 2. When buyers have single-minded valuations with free disposal, envy-free item pricing multi-unit (EFIPMUL) problem is NP-hard but there exists an FPTAS.

4 Pair Envy-free ItemPricing

In this section, we start our study of pair envy-freeness in the item pricing scheme. An immediate thought is that the optimal revenue in pair envy-free outcomes could be higher than the optimal revenue in envy-free outcomes. One could actually show that the gap could unbounded. 2

4.1 General Valuations

Our main result in PEFIP-MUL problem is a O(logn)- approximation algorithm. Let P contain all prices p such that there exists a buyer i, two different sizes of bundles j and j ′ ̸= j such that vi(j) - p · j = vi(j ′ ) - p · j ′ . Similar to Lemma 2 we have the following.

Lemma 3. Consider the PEFIP-MUL problem, given an optimal outcome, the price pOPT is in P.

Algorithm 1 approximates the revenue for every possible price and outputs the best one. For each price, Algorithm 1 figures out the best way to sell all bundles larger than a fixed size. When total demand is greater than m, it uses the technique from Lemma 1.

Theorem 3. Algorithm 1 always returns a feasible and pair envy-free item pricing outcome that O(logn)-approximates the optimal revenue in the PEFIP-MUL problem.

2 Consider two buyers with v1(1) = 1 + ϵ and v2(1) = 1 + ϵ, vi(j) = j for any i ∈ {1, 2} and j ∈ {2, . . . ,m}.

Proof. Given a price p, the maximum revenue of any (unconstrained) allocation is at most p ∑mj=1 nj · j. Algorithm 1 picks bundles with at least z items to sell, where z maximizes z ∑mj=z nj. In this case, buyers, whose largest bundles with positive utilities at price p are at least z, will demand at least z items. Since ∑mj=z j¯nj ≥ z ∑mj=z nj, ∑mj=z j¯nj lognapproximates ∑mj=1 nj · j. Hence, if there are enough items to satisfy the demand of all buyers (lines 5-6 in Algorithm 1), it gives a logn-approximation to the maximum revenue at price p. Otherwise, Algorithm 1 performs the operations in Lemma 1 and we lose at most another half of the revenue. In this case, Algorithm 1 gives a 2 logn-approximation of the maximum revenue at price p. Finally, by Lemma 3, the best revenue from all possible prices in Algorithm 1 gives a O(logn)-approximation to the optimal revenue.

4.2 Other Valuations

It is trivial to see that Algorithm 1 also works when buyers have non-decreasing valuations. On the other hand, similarly as for item pricing when buyers have single-minded valuations it can be shown that the problem is NP-hard. Since there are n candidates for z, with a little tweak, it can also give an O(logn) approximation in polynomial time in n and logm when buyers have single-minded valuations.

5 Envy-free or Pair Envy-free Bundle Pricing

In Section 4, we have seen that pair envy-freeness could extract more revenue in the item pricing scheme. However, it is not true for the bundle pricing scheme. Indeed the two different notions of envy-freeness produce exactly the same optimal revenues. In fact there exist a transformation between optimal allocation in the two notions of envy-freeness in the bundle pricing scheme. On one hand, in an envy-free outcome the utilities of buyers are maximized, which directly implies that the outcome is also pair envy-free. On the other hand, in a pair envy-free outcome it is possible that some sizes of bundles are not assigned to any buyer, and the envy-free outcome producing the same revenue could be achieved by the following. To transform the solution we just need to price these unassigned bundles extremely high, so that no one buys them. Under this transformation, buyers purchase the same bundles of items and the payments remain unchanged. This observation is summarized by the following theorem.

Theorem 4. The envy-free bundle pricing multi-unit (EFBPMUL) problem is equivalent to the pair envy-free bundle pricing multi-unit (PEFBP-MUL) problem.

By this result, in bundle pricing schemes, we could only consider envy-freeness or pair envy-freeness for different valuations. Before we proceed, we would like to start by showing some gaps between item pricing and bundle pricing. First, it is possible to show that a (pair) envy-free bundle pricing is able to extract nearly m times the revenue obtained in EFIPMUL. Second, we also observe that a (pair) envy-free bundle pricing could extract at least Ω(logn) times of the optimal revenue of PEFIP-MUL, where n ≈ √m. Let us consider the instance with n buyers and m = ∑nj=1 j items where the valuation of buyer i, for any i = 1, . . . , n, is vi(i) = 1i and vi(j) = 0 for any j ̸= i. In the PEFBP-MUL the optimal revenue is Hn (Hn = 1 + 12 + · · · + 1n is the harmonic number and it is well known to be about as large as the natural logarithm of n) that we can get by selling the bundle of size j at buyer j at price 1j , for any j = 1, . . . , n. Let us now prove that the optimal revenue for the PEFIP-MUL is a constant and this finishes the proof. From Lemma 3 we get that the optimal item price belongs to the set P = {1, 14 , 19 , . . . , 1 i2 , . . . , 1 n2 }. W.l.o.g., let us consider the price p = 1 i2 for some i = 1, . . . , n. It is easy to see that at price p only buyers j : j ≤ i have interest on buying (i.e., have non negative utility) a bundle of size j. Therefore the total revenue would be ∑ik=1 1 i2 ·k = 1 i2 ·(1+2+. . . , i) = O(i2 ) i2 = O(1).

We first provide a hardness result for general valuations in the EFBP-MUL and PEFBP-MUL problems, followed by a O(logn logm) approximation algorithm. Then, we present a FPTAS when buyers have single-minded valuations, and a O(log n) algorithm when buyers have increasing valuations.

5.1 Hardness

Theorem 5. The EFBP-MUL or PEFBP-MUL problem cannot be approximated within O(logϵ n) unless UDP-MIN can be approximated within O(logϵ |C|), for some ϵ > 0.

The technique is to show a reduction from uniform-budget unit-demand min-buying pricing problem (UDP-MIN) to EFBP-MUL or PEFBP-MUL problem. Briest [Briest, 2008] showed that UDP-MIN is R3SAT∗ (poly(n))-hard to be approximated within O(logϵ |C|) for some ϵ > 0.

5.2 General Valuations

In this section, we consider EFBP-MUL and PEFBP-MUL problems for general valuations. The main result is the proof that the optimal revenue in PEFBP-MUL is at most O(logm) times of the optimal revenue in PEFIP-MUL. Given the results in PEFIP-MUL, we could obtain an O(log n logm) approximation algorithm for EFBP-MUL and PEFBP-MUL.

Lemma 4. Given a feasible and pair envy-free bundle pricing outcome, there exists a feasible and pair envy-free item pricing outcome in which the revenue is at least O(logm)- fraction of the revenue of the feasible and pair envy-free bundle pricing outcome.

Proof. We give a constructive proof as follows. Suppose the feasible and pair envy-free bundle pricing outcome sells the bundles with sizes S = {s1, . . . , sl}. For each sj ∈ S, let pj be the price of the bundle and ¯nj be the number of buyers who are assigned to the bundles of size sj . Hence, there are s1 · ¯n1 items sold at price p1/s1, s2 · ¯n2 items sold at price p2/s2, and so on. W.l.o.g., we assume that p1/s1 ≥ . . . ≥ pl/sl.

Let z be the index that maximizes pj/sj ∑k≤j ¯nksk. Now consider the outcome that uses a price pz/sz and sells the bundles S′ = {s1, . . . , sz}. There are two cases. The first case is that given price p′ and bundles S′ , there are enough items to satisfy all the demand of buyers. Then we can bound the optimal revenue as follows.

The last inequality holds because all buyers who purchase bundles in S′ = {s1, . . . , sz} in the feasible and pair envyfree bundle pricing outcome would demand at least as much when the unit price is pz/sz.

The other case is that given price p′ and bundles S′ , there are not enough items to satisfy all the demand of buyers. But notice that if we assign all buyers their demands it is a nearly-feasible outcome. By Lemma 1, we can obtain a feasible and pair envy-free item pricing with no more than half of the revenue. Therefore, there exists a feasible and pair envy-free item pricing outcome in which the revenue is at least O(logm)-fraction of the revenue in any feasible and pair envy-free bundle pricing outcome.

The analysis above is almost tight since as we mentioned the gap between EFBP-MUL (or PEFBP-MUL) and PEFIPMUL is at least Ω(logn).

From Lemma 4 and Theorem 3 we immediately get the following theorem.

Theorem 6. There exists an algorithm that always returns a feasible and (pair) envy-free bundle pricing outcome that O(log n logm)-approximates the optimal envy-free revenue.

5.3 Single-minded Valuations with Free Disposal

Next, we consider the EFBP-MUL problem when buyers have single-minded valuations with free disposal. As in Section 3.2, single-minded valuations could be described by two parameters wi and ki. We are interested in revenue maximizing bundle pricing algorithms whose running time are polynomial in n and logm. We first state the NP-hardness of the problem. Then we show a pseudo-polynomial time algorithm and argue how to transfer it to an FPTAS.

Theorem7. The EFBP-MUL or PEFBP-MUL problemwhen buyers have single-minded valuations with free disposal is NP-hard but there exists an FPTAS.

A Pseudo-polynomial Algorithm We assume that buyers are sorted by their ki, that is, k1 ≤ . . . ≤ kn. Given buyer i, we denote by Li the set of buyers before i (including i) having greater valuations, i.e., Li = {j|j < i and wj > wi} ∪ {i}. The pesudo-polynomial algorithm largely depends on the following condition for envy-freeness. Consider any two buyers with k1 ≤ k2 and w1 > w2, in any feasible envy-free allocation, if the demand of buyer 2 is satisfied, then the demand of buyer 1 must be also satisfied. In other words, if the seller sells at least ki items to buyer i at price p, it must also sell at least kj items to every buyer j in Li at price at most p. Otherwise, the envy-freeness is violated. Hence, the pesudo-polynomial algorithm considers one buyer at each round. Given a target revenue, it computes the minimum number of items required in order to achieve an envy-free allocation. If there are not enough items an infinite number is returned.

Denote by S(i, t) the minimum number of items sold to the first i buyers such that the revenue is exactly t. Initially we set S(0, t) = 0 for t = 0, and S(0, t) = +∞ for all t = 1, . . . ,maxi wi · n. To compute S(i, t) for i = 1, . . . , n and t = 1, . . . ,maxi wi · n, we use the recursion:

where Li\j = Li \ Lj and Li∩j = Li ∩ Lj .

The first formula in the recursion describes the case when the buyer i receives nothing. The second formula is more involved. First, when the seller decides to satisfy the demand of a buyer i, by the envy-freeness, it must also satisfy the demands of all buyers in Li. Let j be the last buyer before buyer i such that the seller decides to sell. To ensure envyfreeness, the seller must have at least ∑j ′∈Li\j kj ′ items to fulfill the demand of these extra buyers. Now let us turn to the revenue. Each buyers in Li\j gives the seller a revenue of wi. In addition, for buyers in Li∩j, it is possible that the seller gets less revenue from these buyers when wi is smaller than wj. Therefore, in order to extract target revenue t, the sell must receive a revenue of at least t -wi|Li\j| +max(wj - wi, 0)|Li∩j| from the first j buyers. The optimal revenue r is given as the maximum t such that S(n, t) ≤ m.

FPTAS The algorithmgiven above is polynomial inW. We show that applying the standard technique allows us to compute a nearly optimal revenue in time that is polynomial in nand1/ϵ, where ϵ is the error bound. Let K = ϵW/n. Set w′i = ⌊wi/K⌋, and call the obtained problem with w′i the scaled problem. Now using the dynamic programming from the previous section, we can compute the optimal revenue for the scaled problem. The running time of the dynamic programming is O(n3 · ⌊W/K⌋) = O(n4/ϵ). Let X and P be the optimal allocation and payment in the original problem, and X′ and P′ the optimal allocation and payment in the scaled problem. For each buyer, because the rounding down, we can charge buyer i price K·p′ (x′i ) in the original problem. Since buyers are single-minded with free disposal, the envyfreeness in the scaled problem implies the envy-freeness in the original problem. The revenue is bounded by:

5.4 Non-decreasing Valuations

Finally, we consider a variant of the EFBP-MUL problem in which buyers have non-decreasing valuations. In this section, we present a simple and intuitive algorithm that extracts at least Ω( 1 log n ) fraction of the optimal revenue. Essentially, Algorithm 2 only sells the bundles of a particular size by setting high prices for other bundles. Denote ¯n(i, j) be the number of buyers who have value at least vi(j) for j items. Given i and j, let r = vi(j) · ¯n(i, j). Under the supply constraint, Algorithm 2 finds the optimal ˆi and ˆj that maximize r and sells ˆj Algorithm 2: A O(logn) approximation algorithm for non-decreasing valuations.

• 1 Compute ˆi and ˆj such that r is maximized and ˆj · ¯n(ˆi, ˆj) ≤ m; 2 For any j ∈ {1, . . . ,m}, set p(j) = +∞ except p(ˆj) = vˆi (ˆj);
• 3 For any i ∈ {1, . . . , n}, if vi(j) ≥ vˆi (ˆj), set xi = ˆj. Otherwise, set xi = 0.

items to buyers having at least vi(ˆj) for ˆj items at price vˆi (ˆj).

Theorem 8. Algorithm 2 always returns a feasible and (pair) envy-free bundle pricing outcome that O(logn)- approximates the optimal envy-free revenue.

6 Conclusion and FutureWork

To the best of our knowledge this is the first paper that investigates revenue maximizing envy-free pricing without budgets in multi-unit settings. We were able to demonstrate the revenue difference on two different notions of envy-freeness, and shed some light on the capabilities and limitations of both notions of envy-freeness for general, non-decreasing and singleminded valuations. Our paper should be seen as opening this research direction and it leaves a few open problems for further research, i.e., to close the lower and upper bounds of revenue maximizing envy-free (resp. pair envy-free) item or bundle pricing in different settings.

Acknowledgements

Gianpiero Monaco was supported by PRIN 2010-2011 research project ARS TechnoMedia (Algorithmics for Social Technological Networks), funded by the Italian Ministry of University and Research. Piotr Sankowski and Qiang Zhang would like to acknowledge the supports from ERC StG project PAAl 259515, and FET IP project MULTIPLEX 317532.