On Fair Price Discrimination in Multi-Unit Markets

1 Introduction

Charging customers different prices for the same item can be perceived as unfair at first, but it is actually widespread. As an example, when buying flight tickets, customers who arrive earlier usually get a better price. In an opposite way, the price of electronic devices like computers and cameras decreases over time. Beside this form of temporal discrimination, spatial discrimination is also consolidated in the sale of the same good with varying prices at different sites, like in different countries or shops. The lack of knowledge of the prices offered at different locations is often modeled in the literature as a cost of search, that is the cost that buyers have to pay in order to get information about the different prices at the various sites. Exploiting this cost, a firm is able to discriminate on subsets of buyers on the base of their mutual distances. A further type of discrimination occurs in users profiling, when premium customers such as frequent-flyers are charged lower prices with respect to the general public, or when some classes of buyers are recognized to be eligible for a better treatment, such as age discounts or financial aids.

Nice introductions on price discrimination together with the main arising scenarios and the related motivation can be found in [Varian, 1989; Phlips, 1983; Stokey, 1979; Laffont et al., 1998]. An interesting classification is due to A. Pigou in [Pigou, 1920], who detected the following three classes: - First-degree or perfect price discrimination, where the seller is admitted to set a different price for each unit of good, so as to perfectly adapt to each buyer's willingness to buy the item. - Second-degree or non-linear pricing, also known as bundle pricing, in which the seller is able to set a price based on the amount of items purchased by a single buyer, e.g. a smaller price per item for buyers who buy a bigger amount.

- Third-degree price discrimination, in which different buyers may be charged different linear prices, that is they are asked a fixed price per item which may be different from the one of the other buyers. Examples are student discounts or charging different prices in different days of the week.

The problem of maximizing the seller's revenue in combinatorial markets under the notion of envy-freeness has been widely investigated. Important works in the field are [Guruswami et al., 2005; Hartline and Yan, 2011; Cheung and Swamy, 2008; Balcan et al., 2008; Briest and Krysta, 2006], in which the authors designed logarithmic approximation algorithms under different assumptions. On the other hand, related hardness results were given by [Briest, 2008; Chalermsook et al., 2012; 2013b; 2013a; Demaine et al., 2008]. Further variants were considered by [Chen and Deng, 2010; Chen et al., 2011; Feldman et al., 2012; Anshelevich et al., 2017; Bil`o et al., 2017; Chen et al., 2016].

All these works did not consider discriminatory policies, or are related only to the second-degree discrimination, which is a somewhat weaker form of discrimination, as each bundle must be offered at the same (even if not linear) price to all the buyers in the market. Therefore, in this paper we focus on the more proper forms of discrimination related to the first- and third-degree scenarios. In particular, we introduce a unifying framework for "fair" discrimination pricing policies, which takes into account individual constraints among the buyers induced by their social relationships or by the information they can acquire about the other buyers. Namely, an arc from buyer i to buyer k indicates that i knows k or has access to the same buying strategy without paying any search cost, for instance buying at the same site. Then, in order for i to be satisfied or feel to be treated fairly, i can only be offered the same or a lower price for the same good with respect to k. Our framework is very general, as by modifying the structure of the graph is in turn able to incorporate in a unified setting all the fundamental "fair" price discrimination forms proposed in the literature, including the first- and third-degree ones. For instance, a directed chain of arcs can express temporal dependencies, undirected social graphs can model in a nice way spatial discrimination through the submarkets induced by their connected components, and directed trees of strongly connected components the hierarchical profiling of classes of users.

Under the above setting, we investigate the case of a single item on sale in a limited amount of copies, which is usually referred to as a multi-unit market and represents many real world scenarios (e.g. commodity markets) [Feldman et al., 2012; Brˆanzei et al., 2016; Monaco et al., 2015]. More precisely, we have a single seller who is willing to sell m identical copies to n buyers, who are interested in buying one or more copies. Buyers have a valuation function which describes how much they are willing to spend for each given number of copies, and resorting on these valuations the seller must decide what is the price per copy and the allocation. The multi-unit scenario considered by the above papers allows only to assign the same price per copy to all buyers, or in case of bundle pricing different non-linear prices to bundles containing a certain number of identical items. In any case, the same bundle must be offered at the same price to all the buyers.

1.1 Our Contribution

In this paper, we study the problem of maximizing the social welfare or the seller's revenue by means of fair price discrimination in multi-unit markets according to the above framework. Namely, the price per copy of each buyer must be at most the lowest proposed to the buyers she knows directly. We investigate four different cases arising by considering i. social welfare and revenue maximization, and ii. single-minded and general valuations, that is when buyers are interested only in a specific amount of item copies, or do not have any restriction. Moreover, we consider different relevant social graph topologies.

We first point out that the gain from discrimination can be considerable. In fact, it can increase the seller's revenue or the social welfare up to a multiplicative factor equal to the number of item copies. We then provide polynomial time algorithms or hardness and approximation results in all the above mentioned cases.

More precisely, for single minded buyers, we show that the problems of maximizing the social welfare and the revenue are strongly NP-Hard. We then provide a polynomial time 2 - approximation algorithm for the social welfare maximization and an O(log n)- approximation one for the revenue. Finally, still for the revenue maximization, we give an improved (2 + ε)-approximation for the case of undirected social graphs.

For general valuations, we first provide a general construction able to reduce the corresponding instances into "nearly" equivalent single-minded ones. More precisely, the solutions provided by our single minded approximation algorithms for the reduced instances can be transformed into solutions for the initial instances without performance losses. Therefore, we again achieve a 2-approximation for the social welfare maximization and an O(log n + logm) one for the revenue, n · m being the number of buyers in the reduced instances. We remark that our reduction is also of independent interest, as it might be exploited in other settings for extending results from single-minded to general multi-unit instances.

Finally, we provide polynomial time optimal algorithms for all the realistic cases mentioned before, that is for undirected social graphs, graphs with a constant number of strongly connected components, and arborescences or directed trees of strongly connected components.

1.2 RelatedWork

Envy-freeness in multi-unit markets has already been investigated in [Feldman et al., 2012], where the authors studied the case of budgeted buyers and gave a hardness result together with a constant approximation algorithm for the problem of finding an allocation of optimal revenue. Later on [Monaco et al., 2015; Brˆanzei et al., 2016] investigated the problem with slightly different assumptions, providing several hardness and approximation results. In particular, [Monaco et al., 2015] considered revenue maximization in multi-unit markets under both the notion of envy-freeness and pair envy-freeness, both for item- and bundle-pricing. In this work we refer to the notion of envy-freeness given in [Guruswami et al., 2005].

The social influence over the set of buyers of a market has been recently studied in [Abebe et al., 2017; Chevaleyre et al., 2007; Flammini et al., 2018], where the authors generalized the concept of pair envy-freeness in the context of limited mutual knowledge of the buyers, restricting the pair envy-freeness constraints only to social neighbors. These works applied such a notion of social (or local) envy-freeness to the problems of cake cutting, distributed negotiation, and multi-unit markets. Notice that, despite the apparent similarity of our model with the one in [Flammini et al., 2018], which considers multi-unit markets with social graphs, even if some of our techniques are inspired to such a paper, our results refer to a completely different setting, as sociality influences discrimination of prices and not relaxations of the envy-freeness constraints. Finally, [Bil`o et al., 2017; Bil`o et al., 2018] considered the possibility of limiting the view of some buyers, not admitting them in the market. This concept is somewhat related to sociality, as it translates in limiting the social awareness of buyers acting on the social graph topology. In all the above cases, social graphs have been exploited to induce relaxed notions of envy-freeness.

Forms of price discrimination induced by social relationships have been considered in [Alon et al., 2013], where buyers who are neighbors in the social graph demand a difference of their proposed prices bounded by a parameter α. Several results on revenue maximization are provided under different assumptions, such as the possibility of excluding some buyers. Furthermore, [Amanatidis et al., 2016] extended such results to a generalized model having a non empty overlap with the multi-unit markets with single-minded valuations herein considered. However, the two settings are different, since on the one hand we consider additional supply and envy-freeness constraints, on the other hand they admit a certain tolerance in the discrimination due to the parameter α. Moreover, we also investigate the case of general valuations.

Finally, [Feldman et al., 2012] mentioned the possibility of considering, besides bundling, other forms of "unfair" price discrimination, together with their potential positive effects on revenue maximization. Although the topic has been widely addressed in economics [Phlips, 1983; Stokey, 1979; Laffont et al., 1998], we believe that fair discrimination policies induced by social relationships have not been sufficiently investigated in the context of envy-free pricing and are the focus of the present work.

2 Preliminaries

A multi-unit market η can be represented by a tuple (N,M, (vi)i∈N), where N = {1, . . . , n} is a set of n buyers, M is a set of m identical items and for every buyer i ∈ N, vi = (vi(1), . . . , vi(m)) is a valuation function or vector which expresses, given a subset of items X ⊆ M of size j, the amount of money vi(j) ∈ R that buyer i is willing to pay for X. We assume that vi(0) = 0 and vi(j) ≥ 0 for every j, 1 ≤ j ≤ m and buyer i ∈ N.

We distinguish the following two different cases, according to the imposed restrictions on the valuation functions: singleminded, with buyers interested only in a certain amount of items and thus having positive valuation only for bundles of such a size, and general valuations, i.e., the unrestricted case. In the sequel, when dealing with single-minded valuations, we will denote by mi the unique preferred bundle size for which buyer i has a strictly positive valuation.

Since items in M are identical, we consider the pricing scheme called item-pricing, in which the seller must assign a single non-negative price per item pi ∈ R to each buyer i. The amount owed by i for a bundle of items X is thus pi · |X|, so that her utility for receiving X is ui(X, pi) = vi(|X|) - pi · |X|. In the sequel we will denote by p = (p1, . . . , pn) the price vector or n-tuple such that for every i, 1 ≤ i ≤ n, pi ≥ 0 is the price per item assigned to buyer i.

We assume that buyers in N are individuals of a population, whose relationships are represented by an underlying directed social graph G = (N,E). Each buyer i ∈ N is aware only of the prices proposed to the other buyers she knows directly, that is belonging to the subset N(i) = {k ∈ N|(i, k) ∈ E} of her neighbors in G. Under such an assumption, it is possible to define the following notion of fair price discrimination.

Definition 1. A price vector p is fair with respect to the social graph G = (N, E) if pi ≤ pk for every (i, k) ∈ E.

An allocation vector is an n-tuple X = (X1, . . . , Xn) such that Xi ⊆M is the set of items sold to buyer i.

A feasible outcome for market η is a pair (X, p) satisfying the following supply constraint: ∑ni=1 |Xi| ≤ m.

We say that a feasible outcome (X, p) for market η is envyfree if Xi ∈ argmaxX⊆Mui(X, pi) for every buyer i ∈ N. Notice that, for every i ∈ N, since vi(0) = 0, envy-freeness implies the classical assumption of individual rationality of the buyers, that is ui(Xi, pi) ≥ 0.

Definition 2. A feasible outcome (X, p) is fair under the social graph G if it is envy-free and its price vector is fair with respect to G.

Given an outcome (X, p), the achieved social welfare is sw(X, p) = ∑ni=1 vi(|Xi|) and the revenue raised by the seller is r(X, p) = ∑ni=1 pi · |Xi|. The (fair) pricing problem consists in determining a feasible outcome (X, p) for market η, which is fair under G and maximize social welfare or revenue. In the following we will denote by optsw(η,G) (resp. optr(η,G)) the maximum possible social welfare (resp. revenue) achievable by an outcome for η fair under G, and optsw(η) (resp. optr(η)) be the highest possible one achievable without price discrimination, or analogously by an outcome fair under the complete social graph. Clearly, by the individual rationality constraint, in any feasible outcome (X, p), sw(X, p) ≥ r(X, p), so that also optsw(η) ≥ optr(η) and optsw(η, G) ≥ optr(η, G).

For the sake of brevity, we call (SINGLE,WELFARE)- pricing (resp. (GENERAL,WELFARE)-, (SINGLE,REVENUE)- and (GENERAL,REVENUE)-pricing) the pricing problem restricted to the instances of multi-unit markets with singleminded valuations and social welfare maximization (resp. general valuations and social welfare maximization, singleminded and revenue maximization, and general valuations and revenue maximization).

We will often reduce the pricing problem to a variant of the MULTIPLE-CHOICE KNAPSACK problem in which we are given ℓ classes {O1, . . . ,Oℓ} of objects to pack in a knapsack of capacity k. Each object oh,j ∈ Oh has a profit zh,j and a size wh,j, and we must pick at most one object from each class so as to maximize the sum of the profits of the selected objects without exceeding the knapsack capacity k. As shown in [Lawler, 1979], the problem is NP-hard, but it admits an FPTAS. MULTIPLE-CHOICE KNAPSACK has already been exploited by [Monaco et al., 2015; Brˆanzei et al., 2016; Flammini et al., 2018] in order to provide optimal algorithms or efficient approximations in different scenarios concerning multi-unit markets. Some of our algorithms are inspired to such constructions.

Before concluding the section, let us remark that discrimination of prices is a particularly worth investigating issue, as it can increase the achievable social welfare and revenue up to an mmultiplicative factor. This holds even for the very simple case of two single-minded buyers, as shown by the following example: buyer 1 with preferred size 1 and valuation v1(1) = 1 + ε for small ε, and buyer 2 with preferred size m and valuation v2(m) = m. Without discrimination the only possibility is selling a bundle of size 1 to buyer 1 at price at most 1+ε, yielding social welfare and revenue at most 1+ε. With price discrimination it is possible to assign a bundle of size m to buyer 2 at price 1 per item, and no item to buyer 1 asking her price at least 1 + ε. This provides social welfare and revenue m. Notice that this is strict, because it is always possible to achieve an m fraction of the optimum with discrimination, just assigning a bundle only to the buyer having the highest possible valuation per item, that is maximizing the ratio vi(mi)/mi.

Let us also finally stress that in multi-unit markets, while the size of the representation of instances with general valuations is polynomial in m, as different valuations must be specified for different bundle sizes, in single-minded instances the dependence is logarithmic in m, as for each buyer it is sufficient to specify the size of her unique preferred bundle, together with the corresponding valuation.

3 Single-Minded Valuations

We first show the following hardness results.

Theorem 3. The (SINGLE,WELFARE)- and (SINGLE, REVENUE)-pricing problems are strongly NP-hard.

Proof. We show the claim by reduction from the DENSEST K-SUBGRAPH problem in which, given an undirected graph H = (V, F) and an integer k, we are interested in determining a subset S ⊆ V with |S| ≤ k that maximizes the number of edges in the subgraph induced by S. Given an instance (H = (V, F), k) of DENSEST K-SUBGRAPH, the reduced instance is constructed as follows: a buyer iv for each v ∈ V and a buyer ie for each e ∈ F; arcs (iu, ie) and (iv, ie) in the social graph G for every e = {u, v} ∈ F; number of items m = k(2|F | + 1) + |F |; finally, non-null valuations are viv (2|F | + 1) = 2|F | + 1 + ε for each v ∈ V , with ε suitably small, and vie (1) = 1 for every e ∈ F .

By construction, any fair outcome for the reduced instance that maximizes the social welfare (or revenue) must allocate k buyers iv with v ∈ V , plus the highest possible number of buyers ie with e ∈ F . Moreover, since in any fair outcome if any buyer ie with e = {u, v} ∈ F is allocated then also iu and iv must receive their preferred bundles, it is immediate to see that there exists a fair outcome of social welfare (resp. revenue) k(2|F| + 1) + l if and only if there exists S ⊆ V with |S| ≤ k inducing a subgraph of l edges in H, hence the claim.

However, the problem can be suitably approximated.

Theorem 4. There exists a 2-approximation algorithm for (SINGLE,WELFARE)-pricing.

Proof. In the claimed algorithm we first execute the following pre-processing phase. Let G′ be the transitive closure of G and N >(i) be the set of buyers k such that vk(mk)/mk > vi(mi)/mi and there exists an arc (k, i) in G′ . Then, since there is a direct path from k to i in G and thus in any fair price vector the price assigned to k must be at most the one of i, if i has non-negative utility for her preferred bundle size mi, then k has strictly positive utility for hers. Therefore, since in any envy-free allocation all the buyers with strictly positive utility must be allocated the corresponding items, if buyer i gets her preferred bundle, then also every k ∈ N >(i) must. This implies that, if mi + ∑k∈N >(i) mk > m, i can not be allocated in any fair outcome. Therefore. all such buyers are discarded in the pre-processing phase, and this can be clearly accomplished in polynomial time. The residual market η′ thus preserves the optimal solutions of η and satisfies mi + ∑k∈N >(i) mk ≤ m for all the remaining buyers i.

Assume without loss of generality that buyers of η′ are listed in non increasing order with respect to the ratios vi(mi)/mi, that is such that vi(mi)/mi ≥ vk(mk)/mk if i < k. Let k be the first buyer in the order such that ∑ki=1 mi ≥ m. It is immediate to see that ∑ki=1 vi(mi) upper bounds the value optsw(η′ , G) of the optimal solution for η′ . Consider then the following two fair outcomes:

1. (X, p), where bundles Xi of size mi are allocated only to buyers i < k at price pi = vk-1(mk-1)/mk-1 per item, while pi = ∞ for i ≥ k;

ii. (X′ , p′ ), where bundles Xi of size mi are allocated only to buyers in {k} ∪N >(k) at price pi = vk(mk)/mk per item, while pi = ∞ for all the remaining buyers.

Both solutions can be computed in polynomial time and by construction are fair under G also for the initial market η. It remains to show that returning the best of the two outcomes provides the claimed 2-approximation. In fact, the achieved social welfare is equal to max{sw(X, p), sw(X′ , p′ )} ≥ sw(X,p)+sw(X′ ,p′ ) 2 ≥ optsw(η′ ,G) 2 = optsw(η,G) 2 .

A suitable approximation can be found also for the revenue maximization.

Theorem 5. There exists a O(logn)-approximation algorithm for (SINGLE,REVENUE)-pricing.

Proof. Consider the two outcomes (X, p) and (X′ , p′ ) for the instance (η,G) of (SINGLE,REVENUE)-pricing determined by the algorithm of Theorem 4. If sw(X, p) ≥ sw(X′ , p′ ), let h be the index that maximizes vh(mh) mh ∑hi=1 |Xi|. Then, allocating items to buyers 1, . . . , h at price vh(mh)/mh, we obtain a fair outcome for (η,G) of revenue vh(mh) mh ∑h-1 i=1 |Xi| ≥ ∑k-1 i=1 vi(mi) logn .

Analogously, if sw(X′ , p′ ) > sw(X, p), allocating items to all the buyers in {k} ∪ N >(k) at price vk(mk)/mk, we obtain a fair outcome of revenue at least vk(mk).

A refined improved approximation bound for revenue maximization can be achieved when focusing on undirected social graphs. We remark that under this assumption the problem remains computationally difficult. This comes directly by restriction to the case of complete social graphs, which corresponds to the classical problem without discrimination, shown NP-hard in [Monaco et al., 2015].

Theorem 6. The (SINGLE,REVENUE)-pricing problem restricted on undirected social graphs admits a (2 + ε)- approximation.

Proof. Let us first informally discuss the basic intuition behind the algorithm. Given an instance (η,G) of (SINGLE,REVENUE)-pricing, if G is undirected, then any fair pricing under G must assign the same price to all of the buyers belonging to a same connected component. Thus, if N1, . . . ,Nℓ are the nodes corresponding to the maximal connected components of G, the problem translates in determining how many items must be allocated to each Nh. Let ηh be the submarket corresponding to the set of buyers in Nh. If we are able to solve the classical revenue maximization problem in multi-unit markets for every ηh and for every amount of items or supply assigned to ηh, then it is possible to pack the items among the components in the best possible way using MULTIPLE-CHOICE KNAPSACK as follows. We construct an instance K(η,G) having a class Oh for each ηh. Every Oh contains m objects oh,j for 1 ≤ j ≤ m, where each oh,j represents a revenue maximizing envy-free outcome for ηh with supply j. In particular, each oh,j has profit zi,j equal to the revenue of such an outcome and size wh,j = j. The knapsack capacity is set to m.

By construction, an optimal solution S∗ for K(η,G) directly induces a revenue maximizing fair outcome (X, p) for (η,G). Unfortunately, since (η,G) has size depending on log m and K(η, G) proportional to m, this construction is not polynomial. We solve this problem by sampling the supply values, losing only a constant factor of the optimal revenue. Namely, in K(η, G) we do not insert in each class Oh the objects oh,j for all the possible sizes j = 1, . . . ,m, but only for the at most ⌊log 32 m⌋+2 sizes j = ( 32 )0 , . . . , ( 32 )⌊log 32 m⌋ , m. The knapsack capacity is set to 32 m.

In order to measure the loss in revenue due to this sampling, consider a fair optimal outcome (X, p) for (η,G). If jh is the number of objects that (X, p) assigns to a given submarket ηh and k is the integer such that ( 32 )k-1 < jh ≤ min{( 32 )k ,m}, then in the sampled instance K(η,G) there is an object oh,j in class Oh with size j = min{( 32 )k ,m} < 32 jh. Since such an object represents an optimal outcome for submarket ηh with supply j, its profit zi,j is at least the one that (X, p) collects on the subset of buyers Nh of ηh. Therefore, all such objects correspond to a solution S for K(η,G) of profit at least r(X, p) and total size at most 3 2 m. Hence, the optimal solution S∗ for K(η,G) achieves at least such a revenue. In order to extract an outcome allocating at most m items, we can split S∗ in at most two sets S∗ 1 and S∗ 2 , each containing a subset of objects of overall size at most m, as follows. If S∗ contains an object oh,j of size j ≥ m2 , then S∗ 1 = {oh,j} and S∗ 2 = S \ S∗ 1 . If all objects in S∗ have size less than m2 , then we start inserting objects in S∗ 1 in any order till not exceeding total size m, and the remaining ones in S∗ 2 . In this way, again S∗ 1 thus not exceed size m, and since its size is greater than m2 , S∗ 2 has size less thanm. Consider then the set S∗ i of maximum profit between S∗ 1 and S∗ 2 . Allocating items only to the connected components corresponding to the objects oh,j ∈ Si according to the maximum revenue solutions for the related submarkets ηh with supply j, and assigning an infinite price to all the buyers of the other connected components, we can finally collect at least one half of the revenue of S∗ and thus of the optimal fair allocation (X, p) for (η,G).

A final observation concerns the fact that we are not really able to optimally solve K(η,G), nor the subproblems for determining the profits of the objects oh,j. However, in both cases we can use respectively the FPTAS of MULTIPLECHOICE KNAPSACK and the one in [Monaco et al., 2015] for the classical revenue maximization problem in multi-unit markets. These details only account for an additional ε loss in the final approximation.

4 General Valuations

In this section we drop any restriction on the buyers' valuations. We first observe that the hardness reduction of Theorem 3 for the single-minded case is polynomial also for general valuations, as m is polynomially bounded in the size of the starting DENSEST K-SUBGRAPH instance. Thus, the same negative result directly extends also to general valuations.

Theorem 7. The (GENERAL, REVENUE)- and (GENERAL, WELFARE)-pricing problems are strongly NP-hard.

A nice reduction from the general to the single-minded case allows to suitably extend the approximation results of the previous section to general valuations.

Theorem 8. There exists a 2-approximation algorithm for (GENERAL, WELFARE)-pricing.

Proof. In order to prove the claim, we show how to reduce any instance (η,G) of (GENERAL, WELFARE)-pricing into an instance (η′ ,G′ ) of (SINGLE, WELFARE)-pricing with the following two properties:

ii. exploiting the algorithm of Theorem 4 it is possible to obtain a fair outcome (X′ , p′ ) for (η′ ,G′ ) which can be directly transformed into a fair outcome (X, p) for (η,G) with sw(X, p) ≥ sw(X′ , p′ ).

This clearly proves the theorem.

The reduction is obtained as follows. Consider a buyer i of η, and let Si = {m1i , ...,mℓi }, with m1i ≤ ... ≤ mℓi , be the set of the bundle sizes that are preferred by i for some positive price pi, that is maximizing her utility for such a price. By the definition of Si, if j < k then vi(mji ) ≤ vi(mki ), otherwise size mki would be never preferred. Moreover, if bundle size mji is preferred by i for a given price pi, comparing the utility of i for sizes mji , mj-1 i and sizes mji ,mj+1 i , we obtain (vi(mji ) - vi(mj-1 i ))/(mji -mj-1 i ) ≥ pi ≥ (vi(mj+1 i ) - vi(mji ))/(mj+1 i -mji ). For the sake of brevity, in the sequel we denote the quantity (vi(mji ) - vi(mj-1 i ))/(mji -mj-1 i ) simply as vj i .

In η′ we associate ℓ distinct single-minded marginal buyers i1, . . . , iℓ to buyer i as follows: i1 has preferred size m1i , that is valuation function vi1 (m1i ) = vi(m1i ), 0 otherwise; furthermore, for each j > 1, ij has valuation function vij (mji -mj-1 i ) = vi(mji ) - vi(mj-1 i ), 0 otherwise.

For what concerns the social graph G′ , for each buyer i of η, G′ contains arcs (ij , ik) for each j > k. Moreover, for each pair of buyers i, l such that (i, l) belongs to G, G′ contains an arc (ij, lk) if vj i > vk l .

Intuitively, in such a reduction, the allocation of a bundle of size mji to buyer i corresponds to the allocation of bundles of preferred size to the prefix of the marginal buyers i1, . . . , ij in η′ .

Let us first prove that optsw(η′ ,G′ ) ≥ optsw(η,G). To this aim, we show how to transform a fair outcome (X, p) for (η,G) into a fair one (X′ , p′ ) for (η′ ,G′ ) such that sw(X′ , p′ ) = sw(X, p). If |Xi| = mji in (X, p), then in (X′ , p′ ) we allocate to all the marginal buyers ik with k ≤ j their preferred bundles at price pi, and no bundle to all the remaining buyers (asking them an infinite price). In this way, for each buyer i of η, |Xi| = ∑jk=1 |X′ ik |, and vi(|Xi|) = ∑jk=1 vik (|X′ ik |). Notice that, since the mji is the preferred bundle of buyer i in η, we must have that vk i ≥ pi for every k ≤ j. Thus, (X′ , p′ ) is feasible. Moreover, since we propose the same price pi to all buyers ij , if p is a fair pricing under G, also p′ is fair under G′ . In conclusion, (X′ , p′ ) is a fair outcome for (η′ , G′ ) with sw(X′ , p′ ) = sw(X, p).

Consider now the solution (X′ , p′ ) for η′ obtained by the algorithm of Theorem 4, where the buyers are ordered in non increasing order of their values vj i , and in case of ties for two buyers ij, ik with j < k, that is if vj i = vk i , putting ij before ik in the ordering (recall that by the above observations it must be vj i ≥ vk i ). Since by the ordering and by the construction of the algorithm (X′ , p′ ) can allocate only a prefix of marginal buyers i1, . . . , ij in η′ associated to each i of η, in (X′ , p′ ) we can assign a bundle of size mji to buyer i at the price proposed to ij in (X′ , p′ ). It is easy to see that (X, p) is a fair outcome for (η, G) with sw(X, p) = sw(X′ , p′ ).

We are also able to devise a suitable approximation algorithm for the revenue maximization problem.

Theorem 9. There exists a O(logn+ logm)-approximation algorithm for (GENERAL, REVENUE)-pricing.

Proof. (Sketch) Given an instance (η,G) of (GENERAL, REVENUE)-pricing, using the same arguments of Theorem 8, we can obtain a fair outcome (X′ , p′ ) for the reduced single-minded instance (η′ ,G′ ) with sw(X′ , p′ ) ≥ optsw(η,G)/2 ≥ optr(η,G)/2, allocating only prefixes of buyers i1, . . . , ij in η′ .

As in Theorem 5, we can extract from (X′ , p′ ) an outcome (X′′ , p′′ ) of revenue r(X′′ , p′′ ) ≥ sw(X′ , p′ )/ log n′ , where n′ is the number of buyers in η′ , still allocating only prefixes of buyers i1, . . . , ij in η′ .

Again resorting to the arguments of Theorem 8, we can transform (X′′ , p′′ ) into a fair outcome for (η,G) with the same revenue. The theorem then follows by observing that in the reduction n′ ≤ n · m.

We now focus our attention to specific cases allowing optimal polynomial time algorithms. To this aim observe that, since buyers in a same strongly connected components must be offered identical prices, a convenient way to represent G is through the graph of its strongly connected components. Namely, each node represents a component and there is an arc between two nodes if the same happens between the corresponding components. Such a graph is clearly a DAG, and properly restricting its topology we can find interesting polynomial sub-cases. In particular, we are able to prove the following theorem, that includes all the interesting realistic cases mentioned in the introduction.

Theorem 10. There exists a polynomial time optimal algorithm for (GENERAL,WELFARE)- and (GENERAL,REVENUE)-pricing under any of the following restrictions on the social graph G: i. G is undirected, ii.

G contains a constant number of strongly connected components, iii. the graph of the strongly connected components of G is an arborescence.

Proof. (Sketch) For undirected social graphs, a polynomial time algorithm can be obtained by the same initial construction proposed in the proof of Theorem 6 by observing that, since the size of the input instance (η,G) now is polynomial in m, sampling is no longer necessary. Moreover, both the knapsack instance K(η,G) and the determination of the optimal market outcomes corresponding to the objects oh,j can be solved in polynomial time.

Let us now consider the remaining two cases. Let N1, . . . ,Nℓ be the sets of buyers corresponding to the strongly connected components of G, and η1, . . . , ηℓ be the corresponding submarkets. Since all the buyers in a same component must be offered the same price, as shown in [Monaco et al., 2015], for each ηk there exists a set Popt Nk of polynomial size containing all the candidate optimal prices.

For a constant number k of strongly connected components, it is possible to exhaustively search among a polynomial number of candidate optimal price vectors and return the best determined outcome.

For arborescences of strongly connected components, the basic idea behind the algorithm is that, along a path of the arborescence, some submarkets can be forced by their neighbors to set some prices which they would not set on their own. However, these prices must be optimal for some other submarket on the path. We can then use dynamic programming to find an optimal solution by combing the optimal outcome of each single subtree of submarkets, in such a way that, for respecting the fairness, non-increasing prices are proposed along each path, and the global supply constraint is satisfied. This holds both for social welfare and revenue maximization. Details will appear in the full version of the paper.

5 Conclusions and FutureWork

We proposed a framework able to capture many realistic scenarios in which a discriminatory pricing is acceptable by buyers. We considered both social welfare and revenue maximization, under different hypotheses on the buyers valuations and the social graph topology, providing polynomial time optimal algorithms, hardness results and suitable approximations. Our framework is very general and we believe will capture future research attention.

Beside improving our approximation results, it would be worth considering other types of markets with non identical items, unit-demand buyers, single-minded valuations on non homogeneous items, and so forth. It would be also interesting to consider different notions of envy-freeness, such as pair envy-freeness, social envy-freeness, proportionality, etc.

Finally, the issue of influencing the social graph topology so as to increase the achievable social welfare or revenue appears another challenging interesting research direction.