# pricing_problems_with_buyer_preselection__8293f346.pdf

Journal of Artificial Intelligence Research 74 (2022) 1791-1822 Submitted 02/2022; published 08/2022

Pricing Problems with Buyer Preselection

Vittorio Bil o VITTORIO.BILO@UNISALENTO.IT University of Salento, Italy.

Michele Flammini MICHELE.FLAMMINI@GSSI.IT GSSI, L Aquila, Italy.

Gianpiero Monaco GIANPIERO.MONACO@UNIVAQ.IT University of L Aquila, Italy.

Luca Moscardelli LUCA.MOSCARDELLI@UNICH.IT University of Chieti-Pescara, Italy.

We investigate the problem of preselecting a subset of buyers (also called agents) participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, namely market envy-freeness and agent envy-freeness, with the two state-of-the-art objective functions of social welfare and seller s revenue. When insisting on market envy-freeness, we prove that the problem cannot be approximated within n1 ε (with n being the number of buyers) for any ε > 0, under both objective functions; we also provide approximation algorithms with an approximation ratio tight up to subpolynomial multiplicative factors for social welfare and the seller s revenue. The negative result, in particular, holds even for markets with single-minded buyers. We also prove that maximizing the seller s revenue is NP-hard even for a single buyer, thus closing a previous open question. Under agent envy-freeness and for both objective functions, instead, we design a polynomial time algorithm transforming any stable outcome for a market involving any subset of buyers into a stable outcome for the whole market without worsening its performance. This result creates an interesting middleground situation where, if on the one hand buyer preselection cannot improve the performance of agent envy-free outcomes, on the other one it can be used as a tool for simplifying the combinatorial structure of the buyers valuation functions in a given market. Finally, we consider the restricted case of multi-unit markets, where all items are of the same type and are assigned the same price. For these markets, we show that preselection may improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms.

1. Introduction

Pricing-based mechanisms (Nagle & Holden, 2002) provide a fundamental approach for conflict resolution in several competitive scenarios, such as the allocation of scarce resources in multi-agent systems or the sale of items with limited supplies in monopolistic markets. While satisfying suitable constraints for coping with the autonomous and self-interested agents behavior, such as incentive-compatibility and/or fairness, these mechanisms also seek for the optimization of a given objective function. We consider a market with perfect information in which there is one seller selling m items to n buyers (also called agents). In the most general case, every buyer has a valuation for every possible set of items, and her utility is given by the valuation she has for the set of bought items minus the sum of the prices assigned to them by the pricing mechanism. Usually, optimal prices are the result of a challenging counterbalancing process. For instance, if, on the one hand, selecting low prices may be profitable for the seller when it attracts considerably more customers, on the other hand, it may leave some buyers unsatisfied, thus generating discontent. In particular, this happens when, in case of limited supply, a customer is negated the right to buy her preferred set of items, or even any item at all, despite the fact that she is willing to pay for them. In

2022 AI Access Foundation. All rights reserved.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

this case she is often called loser, as opposed to a customer receiving items, called winner. This situation is practically illustrated by the following example.

Example 1. Consider a market with 2 identical items (in this case, the pricing mechanism has to decide a unique price p) and 2 single-minded buyers, i.e., being interested only at buying a unique combination of items in the sense that any other combination gives them zero value. Buyer 1 has a valuation of 3 for obtaining both items, while buyer 2 has a valuation of 2 for a single item. Notice that, if 3

2 < p 2, only buyer 2 is willing to buy, and one item remains unsold. So, the seller s revenue is at most 2. On the other hand, if the price is set to p = 3

2, buyer 1 can purchase both items, leaving nothing to buyer 2. Thus, even though the seller gets a higher revenue of 3, buyer 2 is negated the right to buy an item, despite the fact that she is willing to pay for it: a sort of unfairness is present in the market.

For this reason, pricing problems are traditionally considered under the hypothesis of envy-freeness (Foley, 1967; Varian, 1974), which prescribes that, once a pricing strategy has been established, items have to be allocated to buyers in such a way that no one can get a higher utility by buying a different set of items. Apart from fairness, envy-free pricing possesses additional appealing properties. From a theoretical point of view, the following structural parallelism can be claimed: envy-freeness can be seen, in the context of markets, as a notion corresponding to the one of equilibria in the context of game theory or multi-agent systems. In fact, it decentralizes the market in the sense that buyers, up to a proper tie-breaking rule, autonomously converge to the allocation dictated by a sort of equilibrium, since it corresponds to their preferred choices (Easley & Kleinberg, 2010). From an economic point of view, envy-free pricing, by safeguarding the losers interests, shelters the seller from possible future losses due to their dissatisfaction. However, Bil o et al. (2017) show that, in certain markets, an intrinsic and unavoidable hurdle to the construction of a good quality envy-free solution may come from the presence of a set of disturbing customers, that is, a set of buyers such that at least one of them gets envious in any assignment of sufficiently high revenue. This observation naturally leads to the following intriguing question: What happens if envy-freeness is restricted to apply only to the set of winners? Can the seller raise enough more revenue (with certainty) today to compensate the (uncertain) future loss of potential customers? . This relaxed form of envy-freeness models indeed the situation in which the seller is allowed the freedom to discard any subset of buyers from the given instance, so as to get rid of envious losers in the assignment she would like to propose. In addition, one might consider buyer preselection as an application of personalized marketing (Kim, Kim, Oh, & Ryu, 2010; Weng & Liu, 2004) in which the seller, knowing the buyer valuations for instance by performing market research, advertises about the existence of the supply only to targeted buyers that, once involved, will all consider the allocation fair; the excluded ones then are simply unaware and will not feel any unfairness.

1.1 Our Contribution

Motivated by the above discussion, we introduce and investigate the buyer preselection problem in which, given a pricing problem PP with n buyers and m items, sold by a unique seller, we are interested in computing the best possible envy-free solution that can be achieved by removing a subset of buyers from PP. We consider four scenarios arising from the combination of two stability notions, called market envy-freeness and agent envy-freeness, with the two classical objective functions to be maximised, namely, the social welfare and the seller s revenue. In a market envy-free allocation, given a pricing of the items, each buyer gets the subset maximizing her utility (given by the difference between the valuation she has for the subset and the prices assigned to the items belonging to it) among all possible subsets that can be created from the set of available items; in an agent envy-free allocation, no buyer gets a better utility by receiving the bundle allocated to any winner. Thus, a market envy-free allocation is also agent envy-free. Moreover, both types of allocations are always guaranteed to exist, as it suffices to assign all items an arbitrarily high price, so that no winner is possible.

PRICING PROBLEMS WITH BUYER PRESELECTION

It is worth remarking that market envy-freeness is the strongest considered notion of envy-freeness, as it looks to any possible subset of items in the whole market (and for this reason we have called it market envy-freeness), while agent envy-freeness only cares about the bundles allocated to other winning buyers, and is therefore called agent envy-freeness. Throughout all the paper, we focus on polynomial time approximation algorithms, i.e., we require that the running time of the algorithms is polynomial in the size of the input instance. We first focus on the most general case, called market with combinatorial valuations, in which the buyers valuations are completely arbitrary. For market envy-free allocations and both objective functions, we show that the buyer preselection problem cannot be approximated within n1 ϵ for every ϵ > 0, unless P = NP. On the positive side, under the objective of maximising social welfare, we design an n-approximation algorithm, while, for the case of revenue maximization, we give an O(n log m)-approximation. These results are summarized in the first row of Table 1. In particular, they are obtained as follows: all but one buyer are discarded from the given instance, so that we are left with a pricing problem with a single buyer. While this problem is solvable in polynomial time under the objective of social welfare, for revenue maximization, it already exhibits challenging combinatorial structures and, to the best of our knowledge, has been considered before only by Balcan et al. (2008). There, an O(log m)-approximation is provided, but no lower bound on the problem complexity is given. We show that the problem is NP-hard, thus solving the corresponding open question. We also conjecture (see the discussion at the beginning of Section 3.2 for all details) that the pricing problem with k buyers cannot be approximated up to a factor smaller than k unless P = NP. As a first evidence of this conjecture, we provide, in Theorem 11, a formal proof for the case of k = 2. These results are summarized in Table 2.

Market type Objective function Negative results Positive results

n buyers, combinatorial valuations

Social welfare no n1 ϵ-approximation, ϵ > 0 (Theorem 6)

n-approximation (Theorem 10)

Revenue O(n log m)-approximation (Theorem 10)

n buyers, multi-unit market with identical items

Social welfare polynomial time solvable (Theorem 21) Revenue

n single-minded buyers, multi-unit market with identical items

Social welfare FPTAS (Theorem 22) Revenue NP-hardness (Theorem 23)

Table 1: Computational results for the buyer preselection problem under market envy-freeness.

We stress that efficient preselection can be profitable under two orthogonal directions: on the one hand, the removal of a subset of envious buyers may increase the value of the optimal solution; on the other hand, even when this does not happen or it has only a modest impact, simplifying the combinatorial structure defined by the valuation functions of the winners may lead to the design of better approximation algorithms. In fact, for the two preselection problems obtained by considering agent envy-free allocations, we show in Theorems 16 and 17 how to transform in polynomial time any allocation which is agent envy-free only for the subset of the winners to an agent envy-free allocation for all buyers without worsening its performance, with respect to both objective functions. Hence, although this transformation implies that, for agent envyfreeness, buyer preselection cannot improve the performance of stable outcomes, it can be used to map any agent envy-free allocation for a subset of winners obtained through preselection back to an agent envy-free allocation involving all buyers. Therefore, it can be used as an algorithmic tool for computing good stable

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

Market type Objective function Negative results Positive results

1 buyer, combinatorial valuations

Social welfare polynomial time solvable (Claim 8)

Revenue NP-hardness (Theorem 9)

O(log m)-approximation (Balcan et al., 2008)

2 buyers, combinatorial valuations

Social welfare no (2 ϵ)-approximation, ϵ > 0 (Theorem 11) Revenue

Table 2: Computational results for pricing problems (without preselection) with few buyers under market envy-freeness.

outcomes when preselection is not allowed. In fact, it can be first exploited to simplify the combinatorics of the problem, and then for mapping back the computed solution to one encompassing all the buyers. In this respect, consider for instance the case in which the set of buyers of a pricing problem PP can be partitioned in two (or more) subsets A and B, each containing only buyers of the same type, such as, unit-demand buyers or single-minded buyers or buyers with additive valuations. Assume also that the valuations of agents in A and B, when considered separately, allow to compute an r A-approximate (resp. r B-approximate) solution of the problem restricted to subset A (resp. B) by exploiting known or new simpler algorithms/techniques. This would give an easy r-approximation for pricing problem PP with r = r A +r B, by selecting the best of the two solutions obtained when considering the two subsets separately, whereas approximating PP directly would be much more challenging. In fact, consider an optimal solution of value opt and let opt A and opt B = opt opt A be the contributions to opt due to agents in A and B, respectively. When selecting the best of the two solutions, we obtain a solution of value v max n opt A

r A , opt B

max n opt A

r A , opt opt A

o that is minimized when opt A is such that opt A

r A = opt opt A

r B , which gives opt A =

opt r A r A+r B and v opt r A+r B .

Envy-freeness Objective function Lower bound Upper bound

market envy-freeness

Social welfare m ϵ, ϵ > 0 (Claim 20)

m (Claim 19) Revenue

agent envy-freeness

Social welfare (2 ϵ), ϵ > 0 (Claim 25) Revenue 2 (Theorem 24)

Table 3: How preselection can improve the objective functions of envy-free solutions in multi-unit markets with identical items. All lower bounds hold even in the case of single-minded buyers.

Finally, we consider the multi-unit case, where all items are of the same type and are assigned the same price. We show how preselection can improve the revenue and the social welfare of both market and agent envy-free solutions. In particular, for market envy-free allocations, we show a tight multiplicative factor of m for both objective functions. For agent envy-free allocations, we show a lower multiplicative bound of 2 for both the revenue and the social welfare, and prove that it is tight for the objective of revenue maximization. These results are summarized in Table 3. We also provide essentially tight results on the

PRICING PROBLEMS WITH BUYER PRESELECTION

complexity of computing optimal solutions for the buyer preselection problem under market envy-freeness: these results are summarized in the last two rows of Table 1.

1.1.1 COMPARISON BETWEEN OUR AND PREVIOUS RESULTS

In this subsection, we make a comparison between our results and the ones contained in other two papers (Flammini, Mauro, & Tonelli, 2019; Guruswami, Hartline, Karlin, Kempe, Kenyon, & Mc Sherry, 2005) that consider a similar model. Guruswami et al. (2005) were the first to deal with the problem of computing a market envy-free pricing of maximum revenue1. They consider the unit-demand setting where every buyer would like to buy at most one item, and the single-minded one where every buyer is only interested in a particular set of items. For the unit-demand setting they prove, by a reduction from the vertex cover problem, that computing a market envy-free pricing of maximum revenue is APX-hard even for the special case of unlimited supply. Moreover, they provide an O(log n) approximation algorithm for the limited supply unit-demand setting by using a Walrasian Equilibrium (that is a market envy-free outcome with the additional requirement that the market clears) with reserved prices. For the single-minded setting they prove, by a reduction from the max cut problem, that computing a market envy-free pricing of maximum revenue is APX-hard even for the special case of unlimited supply. Moreover, they present a simple algorithm assigning the same price to every item and prove that it is an O(log n + log m)-approximation for the unlimited supply case. Our paper differs from the one by Guruswami et al. (2005) in a variety of aspects. In particular, we consider the more general setting of combinatorial valuations and also focus of the notion of agent envy-freeness and on the objective function of social welfare. More importantly, we deal with the problem of preselecting buyers in order to get higher revenue or social welfare; this problem was not considered by Guruswami et al. We thus provide a new set of results, obtained by exploiting, in our proofs, different arguments and techniques. Specifically, we make use of reductions from the Maximum Independent Set problem, the Satisfiability problem and the Subset Sum problem to show our hardness results, whereas reductions from vertex cover and max cut problems were used by Guruswami et al. Moreover, the provided approximation or exact polynomial time algorithms are completely different from the ones given by Guruswami et al. Finally, we also exploit Walrasian Equilibria, but only when maximizing the social welfare under agent envy-freeness and in a different way with respect to the one considered by Guruswami et al. Flammini et al. (2019) consider the problem of computing envy-free pricing of maximum revenue for the multi-unit setting where all the items are identical. In particular, they consider social envy-freeness where buyers are the nodes of a given graph and envy is possible only among neighbors in the graph. We notice that social envy-freeness is a relaxation of agent envy-freeness. They provide tight complexity results for single-minded and general buyers valuations. Moreover, they introduce the price of envy-freeness and provide tight bounds for it in the considered setting. In our paper, as in the one by Flammini et al. (2019), we also consider the multi-unit setting. However, we get a different set of results. In particular, we show how preselection can improve both the revenue and the social welfare of both market and agent envy-free solutions. Moreover, we provide almost tight results on the complexity of computing optimal solutions for the buyer preselection problem under market envyfreeness. None of these problems were considered by Flammini et al. Finally, like other papers dealing with the multi-unit setting (Flammini et al., 2019; Monaco, Sankowski, & Zhang, 2015), in some cases we exploit polynomial reductions to the multiple-choice knapsack problem in order to prove our positive results in a constructive way.

1. Given that they only consider the notion of market envy-freeness, they call it simply envy-freeness without any further specification.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

1.2 Related Work

The literature on envy-free pricing is so vast that it cannot be exhaustively covered here. For this reason, we simply refer to the achievements which are mostly related to the model introduced by Guruswami et al. (2005) we consider in this paper. For the social welfare maximization without money transfers, Bouveret and Lang (2008) and Karp et al. (2014) consider the problem of assigning items to agents in an agent envy-free way. When money transfers are allowed, the VCG mechanism (Clarke, 1971; Groves, 1973; Vickrey, 1961) provides an optimal solution to the agent envy-free pricing problem. However, while this mechanism is efficiently computable in markets with unit-demand buyers, yet for single-minded ones its computation becomes NP-hard. Approximate solutions are still possible in this case thanks to the results by Archer et al. (2003). Also Walrasian Equilibria, which are market envy-free outcomes with the additional requirement that the market clears (Walras, 1954), provide an optimal solution to the problem (Bikhchandani & Mamer, 1997); however, they are guaranteed to exist only under very stringent hypothesis on the buyers valuation functions (Gul & Stacchetti, 1999). For the revenue maximization, several studies design logarithmic approximation algorithms for various special cases of market and agent envy-free problems (Balcan et al., 2008; Briest & Krysta, 2006; Cheung & Swamy, 2008; Guruswami et al., 2005; Hartline & Yan, 2011). Related hardness results are alsto studied in the literature (Briest, 2008; Chalermsook, Chuzhoy, Kannan, & Khanna, 2012; Chalermsook, Laekhanukit, & Nanongkai, 2013a, 2013b; Demaine, Feige, Hajiaghayi, & Salavatipour, 2008). Further variants such as large markets (Anshelevich, Kar, & Sekar, 2015), sharp demands where each buyer asks for a fixed quantity of items (Bil o et al., 2017; Chen & Deng, 2010; Chen, Deng, Goldberg, & Zhang, 2016), market with metric substitutability among the items (Chen, Ghosh, & Vassilvitskii, 2011), and buyers with budgets (Colini-Baldeschi, Leonardi, Sankowski, & Zhang, 2014; Feldman, Fiat, Leonardi, & Sankowski, 2012) are also considered. Feldman et al. (2016) propose an interesting relaxation of the notion of Walrasian Equilibrium, called Combinatorial Walrasian Equilibrium (CWE), obtained by grouping items into bundles so as to induce a reduced market to which, then, applying the notion of Walrasian Equilibrium. They show the existence of a CWE yielding a 2-approximation of the optimal social welfare and that of a CWE yielding a logarithmic approximation of the optimal revenue. Furthermore, Monaco et al. (2015) study the case of revenue maximization in multi-unit markets under both market and agent envy-freeness when allowing both item and bundle pricing. In our model, by preselecting buyers, we basically require that all the winners are envy-free (we consider both market and agent envy-freeness). Settings in which, in a similar way, envy-freeness is not guaranteed for all buyers, but only for the winners, are studied in the literature (Alon, Mansour, & Tennenholtz, 2013; Amanatidis, Markakis, & Sornat, 2016; Chen & Rudra, 2008; Elbassioni, Fouz, & Swamy, 2010; Nyman, Su, & Zerbib, 2020; Segal-Halevi & Nitzan, 2019; Segal-Halevi & Suksompong, 2019). In particular, Chen and Rudra (2008) consider weak Walrasian Equilibrium, a relaxed version of Walrasian Equilibrium in which the goal is that of maximizing the number of market envy-free buyers, with the condition that all the winners must be market envy-free. Alon et al. (2013) and Amanatidis et al. (2016) consider a relaxed version of market envy-freeness: in their model, identical items have to be sold to buyers, with every buyer constituting a node of a given unweighted graph; adjacent winning buyers have to pay similar prices for the received item, while the losers cannot envy. This feature is exploited to achieve higher revenue with respect to the classical case in which there cannot be losers, even if it makes the computational problem harder. Elbassioni et al. (2010) consider an approximated variant of agent envy-freeness that has to be guaranteed for the winners, in the case of bundle pricing (differently than the one of item pricing addressed in this paper). Nyman et al. (2020) study how to guarantee fairness for a portion of agents when cutting multiple cakes. Segal-Halevi and Nitzan (2019) deal with the division of a cake among groups, with the constraint of

PRICING PROBLEMS WITH BUYER PRESELECTION

guaranteeing fairness to a given portion of each group. Analogously, Segal-Halevi and Suksompong (2019), study a similar notion of group fairness for the case of indivisible goods. Moreover, other settings in which related fairness notions are dealt with in a similar way (i.e., by guaranteeing the considered fairness notion only for a portion of agents) are also studied in the literature (Segal Halevi, 2018; Ortega, 2018; Searns, 2020). In particular, Segal-Halevi considers the problem of redividing an heterogeneous resource in a way that balances fairness with ownership rights, guaranteeing ownership retention to at least for a portion of agents. Ortega deals with the monotonicity of assignments when merging two-sided matching markets, and succeeds to guarantee it for one half of agents. Searns considers the notion of maximin share guarantee when allocating indivisible items, by showing that this fairness notion can be obtained for a fraction of agents. Finally, some papers deal with multi-unit markets and consider a relaxed definition of market envyfreeness, in which, given a social graph, every agent (corresponding to a node) can only see the prices of items assigned to her neighbors (Flammini, Mauro, & Tonelli, 2018; Flammini et al., 2019). Similarly, several works in fair allocation of goods in absence of pricing assume an individual s view of the subjective well-being as based on a comparison with peers, that is restricting agent envy-freeness constraints to social neighbors (Abebe, Kleinberg, & Parkes, 2017; Chevaleyre, Endriss, & Maudet, 2007b). Moreover, distributed mechanisms for allocating indivisible goods under the absence of central control are investigated in the literature (Chevaleyre, Endriss, Estivie, & Maudet, 2007a; Chevaleyre et al., 2007b; Chevaleyre, Endriss, & Maudet, 2017); in this setting, given an underlying social structure, agents can locally agree on deals to exchange some of the goods in their possession, again under the assumption of agent envy-freeness restricted only to social neighbors.

2. Model and Definitions

In this section, we formally define the buyer preselection problem. In order to do that, we first have to define markets, stability notions and pricing problems.

2.1 Markets

A market with perfect information is a tuple Γ = (N, M, (vi)i N). We assume there is a seller who owns a set M of m items and wants to sell these items to a set N of n buyers (also called agents). For every buyer i N, vi : 2M R 0 is a valuation function expressing, given a set of items X M, the amount of money that buyer i is willing to pay for X; we assume that vi( ) = 0 for every buyer i N. The seller sets a price for each item. If a buyer buys a subset of items, her utility is the difference between the valuation and the purchase price, i.e., the amount of money she saves compared to her valuation. We will formally define the buyers utility in the next subsection. We assume that a buyer is indifferent between buying one of two or more different subsets of items giving her the same non-negative utility. In particular, a buyer is indifferent between buying a subset of items giving her zero utility and buying no items at all. Depending on the definition of the valuation functions, different types of markets can be modeled. In the most general case, called market with combinatorial valuations, function vi is completely arbitrary for every buyer i N. In a market with unit-demand buyers, vi(X) = 0 for every i N and X M with |X| > 1, that is, every buyer is only interested in singleton sets. In a market with single-minded buyers, for every i N, there exists a unique set of items X M such that vi(X) = 0, that is, every buyer is only interested in a particular set of items. In a market with additive valuations, vi(X) = P j X vi({j}) for every i N and X M. A valuation function v is monotone, if v(X) v(X ) for each X X. Finally, in a multi-unit market with identical items, all the m items are of the same type and so, for every i N, the valuation function becomes of the form vi : {0, 1, . . . , m} R 0, since it is only required to specify how much a buyer evaluates a set of k items, for every k {1, . . . , m} (clearly, vi(0) = 0).

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

In this paper we mostly focus on markets with combinatorial valuations (Sections 3 and 4) and on multiunit markets with identical items (Section 5).

2.2 Stable Outcomes

Fix a market Γ. A price vector is an m-tuple p = (p1, . . . , pm) such that, for every j M, pj R 0 { } is the price of item j.2 We denote by 0m the price vector assigning price 0 to all items. Given a price vector p and a set of items X M, ui(X, p) = vi(X) P j X pj is the utility of buyer i when buying X. The demand set of buyer i for the price vector p is the family Di(p) = argmax X Mui(X, p) of subsets of items maximizing i s utility according to the prices specified by p. An allocation vector is an n-tuple X = (X1, . . . , Xn) such that Xi M is the set of items sold to buyer i. The allocation vector X = (X1, . . . , Xn) is feasible if Xi Xi = for each i = i N. An outcome is a pair (X, p) such that X is feasible. Denote with OUT(Γ) the set of outcomes of Γ. Given any i N, a set of items X and a price vector p, the pair (X, p) is individually-rational for buyer i if ui(X, p) 0; given any allocation vector X = (X1, . . . , Xn), an outcome (X, p) is individually-rational if, for every i N, it holds that the pair (Xi, p) is individually rational for buyer i. Given an outcome (X, p), denote by M(X) = S i N Xi the set of items sold to some buyer according to a feasible allocation vector X. Moreover, buyer i is a winner if Xi = ; W(X) denotes the set of all winners in X. For an item j M(X), denote by b X(j) the buyer i W(X) such that j Xi. When the allocation vector is clear from the context, we simply write b(j). We say that a buyer i envies a set of items T in outcome (X, p) if ui(Xi, p) < ui(T, p). The following concepts define two types of stable outcomes for Γ.

Definition 1. An individually-rational outcome (X, p) is market envy-free if ui(Xi, p) ui(T, p) for every buyer i N and T M, that is, Xi Di(p) for every i N, i.e., no buyer in (X, p) envies any subset of items.

Definition 2. An individually-rational outcome (X, p) is agent envy-free if ui(Xi, p) ui(Xj, p) for every two buyers i, j N, i.e., no buyer in (X, p) envies any subset of items being assigned to other buyers.

Buyer Item set {1} {2} {1, 2}

1 1 0 5 2 4 0 0

Table 4: The buyers valuations of example 2.

Example 2. Consider a market Γ = (N, M, (vi)i N) with n = 2 buyers and m = 2 items. The buyers valuations are summarized in Table 4. Consider the outcome (X, p) = (({1, 2}, ), (2, 3)) assigning both items to buyer 1 for a total price of 5. First of all, notice that, given the price vector p, buyer 1 is obtaining the most profitable item set. This implies that (X, p) is agent envy-free, because buyer 2 cannot increase her utility by purchasing the set of items sold to buyer 1. However, (X, p) is not market envy-free because buyer 2 envies the item set {1} that would provide her a utility equal to v2({1}) p1 = 4 2 = 2. Consider now the outcome (X, p ) = (({1, 2}, ), (4, 1)) with the same allocation vector and a different price vector. Again, on the one hand, given the price vector p , buyer 1 is obtaining the most profitable item

2. For the case of multi-unit markets with identical items, it is only required to fix the price of a single item so that vector p collapses to a real number p 0.

PRICING PROBLEMS WITH BUYER PRESELECTION

set. On the other hand, under price vector p , buyer 2 cannot obtain a positive utility by choosing a different item set. Therefore, (X, p ) is market envy-free (and clearly also agent envy-free).

Denote by MEF(Γ) and AEF(Γ) the sets of market envy-free and agent envy-free outcomes for Γ, respectively. Notice that MEF(Γ) AEF(Γ) and MEF(Γ) = (and so also AEF(Γ) = ), since the outcome (X, p) such that Xi = for every i N and pj = for every j M is individually-rational and market envy-free. In our proofs we sometimes need also the following fundamental notion of stability.

Definition 3. A Walrasian Equilibrium is a market envy-free outcome with the additional requirement that the market clears, i.e., every unsold item is assigned price zero.

We denote by WE(Γ) the set of Walrasian Equilibria for Γ. Notice that WE(Γ) MEF(Γ) AEF(Γ).

2.3 Pricing Problems

Fix an outcome (X, p) for a market Γ. The revenue raised by (X, p) is REV(X, p) = P j M(X) pj. The social welfare generated by (X, p) is SW(X, p) = P i N ui(Xi) + P j M(X) pj = P i W(X) vi(Xi), i.e., it is given by the sum of the utilities of the seller and of all buyers. Note that, since the utility of the seller, i.e., the revenue P j M(X) pj, is cancelled out by the total price paid by the buyers, social welfare does not depend on the price vector p; moreover, under the assumption of individual rationality, it holds that SW(X, p) REV(X, p). In the following, we formally define the pricing problem. Roughly speaking, it is an optimization problem that, given in input a market (i.e., a set of items and a set of buyers with their valuations), an envyfree notion (i.e., market envy-freeness or agent envy-freeness) and an objective function (i.e., social welfare or revenue), returns an allocation of items to buyers and a pricing vector for the items (i.e., an outcome) maximizing the objective function and satisfying the given envy-free notion. Given a market Γ, let sol(Γ) OUT(Γ) denote any subset of outcomes for Γ and obj : OUT(Γ) R 0 denote an objective function associating a non-negative value to every outcome for Γ. Let opt(Γ, sol, obj) := argmax(X,p) sol(Γ){obj(X, p)} denote the set of outcomes in sol(Γ) maximizing the objective function obj.

Definition 4. The pricing problem PP = (Γ, sol, obj) is an optimization problem which, given a market Γ, an envy-freeness notion sol and an objective function obj, asks for an outcome o (PP) opt(PP).

In this paper, we consider the cases in which sol {MEF, AEF} and obj {REV, SW}.

2.4 Oracles

Fix a pricing problem PP = (Γ, sol, obj). As we have seen, when Γ is a market with combinatorial valuations, any algorithm for PP needs to deal with an input of exponential size. In order to circumvent this problem and remain within the realm of polynomial time algorithms, it is usually assumed that functions vis are not given as an input of the problem and are replaced by a polynomial time (with respect to n and m) oracle providing information about a buyer s valuation function. An oracle is usually assumed to answer two types of questions: a value query which, given a buyer i N and a set of items X, returns the valuation vi(X), and a demand query which, given a price vector p and a buyer i N, returns any set in Di(p). We remark that all algorithms in this paper exploiting oracles are polynomial also in the sense that they call the oracle a polynomial number of times. Therefore, when the oracle is polynomially computable, the algorithm computation is polynomial as well.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

2.5 The Buyer Preselection Problem

Given a market Γ = (N, M, (vi)i N) and a subset of buyers N N, the submarket of Γ induced by N is the market Γ(N ) = (N , M, (vi)i N ). We are now ready to define the buyer preselection problem. Roughly speaking, it is defined upon a pricing problem PP = (Γ, sol, obj), with Γ = (N, M, (vi)i N), and returns a pair (N , o ). In particular, it aims at selecting a subset N N of buyers to admit to the market so that submarket Γ(N ) induced by N is such that the returned outcome o maximizes, among all possible choices of the buyers to admit to the market, the objective function (i.e., social welfare or revenue) while satisfying the given envy-free notion.

Definition 5. The buyer preselection problem is an optimization problem BPP(PP) which, given a pricing problem PP = (Γ, sol, obj) with Γ = (N, M, (vi)i N), asks for a pair (N (BPP(PP)), o (BPP(PP))) such that N (BPP(PP)) argmax N N{opt(Γ(N ), sol, obj)} and o (BPP(PP)) opt(Γ(N (BPP(PP))), sol, obj), that is, o (BPP(PP)) is the best outcome which can be realized in all possible submarkets of Γ.

Clearly, by definition, for every pricing problem PP, obj(o (PP)) obj(o (BPP(PP))), that is, buyer preselection can only improve the quality of the optimal solution. Coming back to Example 1, it is worth noticing that, without considering preselection, all market envyfree outcomes cannot sell (both) items to the first buyer: in this case, the price should be at most 3

2 and the second buyer would be envious. Therefore, market envy-free outcomes can sell an item only to the second buyer at price 3

2 < p 2. In particular, an outcome maximizing social welfare and revenue is o = (( , {1}), 2), i.e., the one selling a copy of the item only to the second buyer at price 2: it holds that REV(o) = SW(o) = 2. If we exploit buyer preselection, we can exclude from the market the second buyer, and we can sell both items to the first buyer at price 3

2, thus obtaining outcome o = (({1, 2}), 3

2): in such a way, we obtain REV(o ) = SW(o ) = 3, thus increasing the performance of envy-free solutions. In Section 5 it is shown that preselection can be profitable, in terms of social welfare and revenue, also when considering agent envy-free outcomes.

3. Results for Market Envy-Free Outcomes

In this section, we consider the buyer preselection problems BPP(Γ, MEF, SW) and BPP(Γ, MEF, REV) in their most general form, that is, when Γ is a market with combinatorial valuations. We start by providing a severe lower bound on their best-possible approximation guarantee. We achieve this result by designing an approximation-preserving reduction from the Maximum Independent Set problem, which cannot be approximated within a factor of n1 ϵ unless P = NP (Zuckerman, 2007). Interestingly, this lower bound holds even under the more stringent assumption of single-minded buyers.

Theorem 6. Let PP = (Γ, MEF, obj) be a pricing problem with obj {REV, SW} and Γ being a market with combinatorial valuations. For every ϵ > 0, the buyer preselection problem BPP(PP) cannot be approximated within n1 ϵ, unless P = NP, even when Γ is a market with single-minded buyers.

Proof. We prove the claim through an approximation-preserving reduction from the Maximum Independent Set problem, in which, given an undirected graph, it is asked for a subset of nodes, no two of which are adjacent, of maximum cardinality. To this aim, consider an instance of the Maximum Independent Set problem defined by a graph G = (V, E) and denote with δi(G) the set of edges incident to node i. We create a market Γ = (N, M, (vi)i N) with single-minded buyers as follows: we set N = V , M = E and, for every i N, we define the valuation function vi in such a way that, for every X M,

vi(X) = 1 if X = δi(G) 0 otherwise.

PRICING PROBLEMS WITH BUYER PRESELECTION

Fix any subset of buyers N N. Given an individually-rational outcome o = (X, p) OUT(Γ(N )), define VREV(o) := {i V : P j Xi pj > 0} and VSW(o) := {i V : vi(Xi) > 0}. By construction of the valuation functions, both VREV(o) and VSW(o) have to be independent sets for G. Let obj {REV, SW}. Since P j Xi pj 1 and vi(Xi) 1 for every i N , it follows that

obj(o) |Vobj(o)|. (1)

Let V V be a maximum independent set for G. It is easy to see that the outcome (X , p ) such that X i = δi(G) for every i V and

p j = 1/δi(G) if j δi(G) 0 otherwise.

is a market envy-free outcome (actually it is also a Walrasian Equilibrium because the market clears, i.e, every unsold item is assigned price zero) for market Γ(V ). This implies

obj(o (BPP(PP))) obj(X , p ) = |V |. (2)

Assume, for the sake of contradiction, that there exists an approximation algorithm for BPP(PP) returning an outcome o such that n1 ϵobj(o) obj(o (BPP(PP))) for some ϵ > 0. Using (2), we get n1 ϵobj(o) |V | which combined with (1) implies that n1 ϵ|Vobj(o)| |V |: a contradiction to the inapproximability result for the Maximum Independent Set problem.

As a positive result, we show that, by building upon (approximation) algorithms for pricing problems defined on markets with a constant number of buyers, it is possible to obtain approximation algorithms for the buyer preselection problem. The key ingredient is provided by the following lemma.

Lemma 7. Given a buyer preselection problem BPP(PP), where PP = (Γ, MEF, obj) with obj {REV, SW}, and a positive integer k n, if there exists a polynomial time algorithm Ak running in time T(k) and returning an outcome for the pricing problem defined on markets with k buyers whose objective value is at least an αk fraction of the optimal social welfare, then BPP(PP) admits an n

k αk - approximation algorithm running in time O(nk)T(k).

Proof. Assume that o (BPP(PP)) := (X , p ). For every i N (BPP(PP)), define

obji(o (BPP(PP))) = P j X i p j if obj = REV, vi(X i ) if obj = SW, (3)

so that obji(o (BPP(PP))) is the contribution of buyer i to the objective value in the optimal solution of BPP(PP). Let

N k = N (BPP(PP)) if |N (BPP(PP))| k, argmax N N (BPP(PP)):|N| k P i N vi(X i ) otherwise,

be a subset of N (BPP(PP)) having cardinality min{k, |N (BPP(PP))|} and maximizing the overall valuation of the allocated bundles. Roughly speaking, given an optimal outcome o (BPP(PP)) of the buyer preselction problem, N k just maximizes the sum of valuations of allocated bundles among all subsets of at most k (preselected) buyers, independently from the considered objective function obj. For k |N (BPP(PP))|, we get X

i N (BPP(PP)) vi(X i ) |N (BPP(PP))|

i N k vi(X i ), (4)

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

by definition. When k < |N (BPP(PP))|, set N (BPP(PP)) can be partitioned into l |N (BPP(PP))|

subsets each having cardinality k, except for at most one set which we denote by S. Clearly, any set S of cardinality k satisfies P i S vi(X i ) P i N k vi(X i ) by the definition of N k. Moreover, also P i S vi(X i ) P i N k vi(X i ) holds as S can be extended to a set of cardinality k by adding k |S| buyers from N k \ S without worsening the overall valuation of the allocated bundles. Thus, we conclude that (4) holds for any value of k. Consider algorithm Best which, given Γ and k, calls Ak on all O(nk) possible subsets of k buyers and returns the solution, let us call it o Best, with the largest objective value. We show that the approximation guarantee of o Best is n

k αk. Let o MEF(Γ(N k)) be the outcome returned by Ak when executed on the pricing problem (Γ(N k), MEF, obj). We have

obj(o (BPP(PP))) = X

i N (BPP(PP)) obji(o (BPP(PP)))

i N (BPP(PP)) vi(X i )

i N k vi(X i )

m αkobj(o Best),

where the first inequality comes from (3) and the fact that, because of individual rationality, P j X i p j vi(X i ); the second inequality follows from (4) together with |N (BPP(PP))| n; the third inequality comes from the approximation guarantee of algorithm Ak; and the last inequality holds as Best returns the outcome with highest objective value.

As a consequence of Theorem 6 and Lemma 7, the buyer preselection problem BPP(Γ, MEF, obj), with obj {REV, SW}, admits a polynomial time algorithm asymptotically achieving the best possible approximation guarantee (up to subpolynomial factors), whenever there is a constant value k for which the pricing problem defined on markets with k buyers admits a polynomial time algorithm computing a market envy-free outcome providing a k-approximation of the optimal social welfare. Clearly, the value of k for which better approximation guarantees are ideally expected is k = 1. For this reason, in the following subsection, we focus on the solution of pricing problems with a unique buyer.

3.1 Pricing Problems Defined on Markets with a Unique Buyer

Throughout this subsection, we assume that there is only one buyer in the market. Therefore, for the sake of simplicity, we remove the subscript 1 from the notation. As a warm-up, we start by considering the simpler case in which obj = SW.

Claim 8. Let Γ be a market with a single buyer and combinatorial valuations. The pricing problem PP = (Γ, MEF, SW) can be solved in polynomial time.

In fact, observe that an outcome (X , 0m) such that X argmax X Mv(X) is such that (X , 0m) opt(PP), and a set X argmax X Mv(X) can be obtained in polynomial time by using the price vector 0m as the input of an oracle demand query. We show, in the next theorem, that the case of obj = REV is NP-hard. Before our contribution, only an approximation algorithm was known (Balcan et al., 2008, Lemma 7). Towards this end, we exploit a

PRICING PROBLEMS WITH BUYER PRESELECTION

polynomial time reduction from 3SAT, in which a given boolean formula φ is transformed into a market with a unique buyer and monotone combinatorial valuations, whose items are the literals of φ.

Theorem 9. Let Γ be a market with a single buyer and combinatorial monotone valuations. The pricing problem PP = (Γ, MEF, REV) is NP-hard.

Proof. We prove the claim through a reduction from 3SAT. To this aim, given a boolean formula φ, let V(φ) denote the set of its variables and L(φ) the set of all literals on variables in V(φ), i.e., either a variable or its negation. Denote ν = |V(φ)|, so that |L(φ)| = 2ν. Throughout this proof, we assume ν 4. We shall denote by vi the ith variable in V(φ) and by xi and xi the two literals related to vi. An assignment for φ is a function f : V(φ) {0, 1} associating each variable of φ with a boolean value. Denote with F(φ) the set of all possible assignments for φ and with φ(f) the boolean value obtained by evaluating all literals occurring in φ according to the following rule: if f(vi) = 1, then xi = 1 and xi = 0, whereas, if f(vi) = 0, then xi = 0 and xi = 1. An assignment f can be also defined by listing the ν literals which are evaluated 1 according to f. φ is satisfiable if there exists an assignment f F(φ) such that φ(f) = 1 and is not satisfiable if, for every assignment f F(φ), φ(f) = 0. Given a set of literals X L(φ), we say that X represents V(φ) if X contains at least one literal for each variable in V(φ). Observe that any set X representing V(φ) needs have at least ν elements. A formula φ is an instance of 3SAT if φ is expressed in Conjunctive Normal Form and each clause is the disjunction of 3 literals, so that φ can be completely expressed by listing the set C = {c1, . . . , cγ} of its clauses, where each clause is a set of three literals. Given an instance φ := C of 3SAT, we construct a market Γ = ({1}, M, v) with a unique buyer such that M = L(φ) and, for each X M, the valuation function v is defined as follows:

ν if X represents V(φ), 3 + ϵ if X does not represent V(φ) and X contains a clause in C, 0 if X = , 1 otherwise,

where ϵ > 0 is arbitrarily small. Observe that, by the definitions of ϵ and ν, the valuation of a set X either stays the same or increases when adding new items, so that v is monotone. For example, the instance C = {{x1, x2, x3}, { x1, x2, x4}, { x2, x3, x4}, {x1, x3, x4}} defines the boolean formula

φ := (x1 x2 x3) ( x1 x2 x4) ( x2 x3 x4) (x1 x3 x4),

which has four variables V(φ) = {v1, v2, v3, v4} and eight literals L(φ) = {x1, x1, x2, x2, x3, x3, x4, x4}. The assignment f1 = {x1, x2, x3, x4} satisfies φ as f1 cj = for each j [γ], while the assignment f2 = { x1, x2, x3, x4} does not satisfy φ, as it does not intersect c1. The set of items X1 = {x1, x2, x2, x3, x4} represents V(φ) as X1 {xi, xi} = for each i [ν], while the set of items X2 = {x1, x2, x2, x3, x3} does not represent V(φ), as X2 {x4, x4} = . Moreover, X2 contains clause c1. Thus, v(X1) = ν and v(X2) = 3 + ϵ. Finally, X3 = {x1, x2, x2, x3} neither represents V(φ) nor contains a clause in C, so that v(X3) = 1. Clearly Γ can be constructed in polynomial time with respect to the representation of φ. However, in order to complete the reduction, we have to construct an oracle which can answer both demand and value queries in polynomial time. To this aim, observe first that both ν and γ are polynomial in the representation of φ. Hence, given a set of literals X, determining whether it contains a clause in C, or whether it represents V(φ) can be performed in polynomial time, so that value queries can be efficiently answered. In order to provide an efficient response to a demand query, we first observe that, by the definition of v, the answer to a demand query is a set X satisfying exactly one of the following four properties: (1) X represents V(φ), (2) X contains a clause in C but does not represent V(φ), (3) X is the empty set; (4) X is non-empty and neither

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

represents V(φ) nor contains a clause in C. Moreover, as item prices are non-negative and the valuation of all sets satisfying the same property is the same, a set X i maximizing the buyer s utility among all the ones satisfying properties (1), (2) and (4) can be obtained by selecting the ν items obtained by choosing, for each variable in V(φ), the related literal having the lowest price (doable in O(ν) time), the three items of smallest total price among all the triplets belonging to a clause in C (doable in O(γ) time) and the item of smallest price (doable in O(ν) time), respectively. It follows that a response to the demand query can be done by selecting the set providing the higher buyer s utility among the empty set (giving a utility equal to 0) and the sets maximizing the utility among all the ones satisfying properties (1), (2) and (4), computed as described above. Thus, market Γ can be generated and managed in polynomial time. With respect to the example outlined above, consider the pricing vector p = (2, 3, 1, 4, 2, 1, 0, 2) for the set of items M = L(φ) = {x1, x1, x2, x2, x3, x3, x4, x4}. The item yielding the highest utility is x4 for which u({x4}, p) = 1 0 = 1. The set of items containing a clause and not representing V(φ) yielding the highest utility is c4 for which u(c4, p) = 3 + ϵ 4 = 1 + ϵ. The set of items representing V(φ) yielding the highest utility is X = {x1, x2, x3, x4} for which u(X, p) = 4 4 = 0. Finally, the empty set yields a utility equal to 0. Thus, the demand query answers by returning bundle {x4}. Now, in order to complete the proof, we show that there exists a market envy-free outcome o MEF(Γ) such that REV(o) = ν if and only if φ is satisfiable. Assume first that φ is satisfiable and let f be a satisfying assignment for φ. Let X be the set of literals which are evaluated 0 in f and let p be the pricing vector such that all literals in X are priced 1, while all literals in L(φ) \ X are priced . By definition, X represents V(φ), thus, we have u(X, p) = 0, so that ((X), p) is individually-rational. Moreover, X D(p). In fact, for every X = X such that X represents V(φ), u(X , p) < 0 since X has to contain at least one item priced ; for every X such that X does not represents V(φ) and X contains a clause in C, u(X , p) < 0 since, as we have φ(f) = 1, X has to contain at least one item priced ; for every non-empty X such that X neither represents V(φ) nor contains a clause in C, we have v(X ) = 1, so that u(X , p) 0. Hence, (X, p) MEF(Γ) and REV(X, p) = ν. Secondly, assume that there exists an outcome (X, p) MEF(Γ) such that REV(X, p) = ν. By construction of the valuation function, this is possible only if X represents V(φ) and P j X pj = ν, so that u(X, p) = 0. However, since v({ℓ}) = 1 for every ℓ L(φ), (X, p) MEF(Γ) implies that it must also be pj 1 for each j X. Hence, we can conclude that pj = 1 for each j X. Assume, for the sake of contradiction, that φ is not satisfiable. This implies that the assignment induced by all literals in L(φ) \ X cannot satisfy φ, that is, there exists a clause cj C such that cj X. This implies u(cj, p) = 3 + ϵ 3 = ϵ > 0 thus contradicting (X, p) MEF(Γ). Hence, φ has to be satisfiable.

On the positive side, Balcan et al. (2008) derive an O(log m)-approximation algorithm for this problem. An interesting feature of this algorithm is that its performance guarantee holds also with respect to the maximum social welfare which is an upper bound to the maximum revenue, thus allowing the application of Lemma 7. Hence, by combining Lemma 7 with Claim 8 and the result by Balcan et al. (2008), we obtain the following upper bounds.

Theorem 10. Let Γ be a market with combinatorial valuations and let PP = (Γ, MEF, obj) be a pricing problem with obj {REV, SW}. The buyer preselection problem BPP(PP) admits an n-approximation when obj = SW, and an O(n log m)-approximation when obj = REV.

It is worth noticing that, given the proof of Lemma 7 when k = 1, the preselection claimed in Theorem 10 is somehow oblivious , as it can be obtained by exploiting the minimum possible number of oracle queries. In fact, to determine the buyer having the highest valuation for a single bundle, a single demand query is sufficient for each buyer (it suffices asking for a bundle in the demand set when all prices are set equal to zero).

PRICING PROBLEMS WITH BUYER PRESELECTION

In light of the lower bound given in Theorem 6, the upper bounds given in Theorem 10 are (unless P = NP) asymptotically tight up to subpolynomial multiplicative factors (notice that even for obj = SW, the lower bound of n1 ϵ for any ϵ > 0 may be a subpolynomial multiplicative factor far from the upper bound of n).

3.2 Pricing Problems Defined on Markets with Few Buyers

From the inapproximability result of Theorem 6 it follows that, given any ϵ > 0, for any n n(ϵ), there exists a preselection problem with n buyers which cannot be approximated up to n1 ϵ unless P = NP. Conversely, by Lemma 7 it follows that an n

k αk approximation is possible if the pricing problem (without preselection) on markets with k buyers, k being a constant, admits an αk-approximation (satisfying some additional assumptions). It is worth noticing that a stronger negative result on the complexity of the preselection problem, stating that, given any ϵ > 0, for any n n(ϵ), there exists a preselection problem with n buyers which cannot be approximated up to n ϵ (unless P = NP), would imply that the pricing problems (without preselection) with k buyers cannot be approximated up to a factor smaller than k (unless P = NP), even for every constant value of k. In fact, if the considered stronger result about the preselection problem held, it would follow that, given any ϵ > 0, for any n n(ϵ) such that k divides n and any integer k 1, n

k αk > n ϵ, which implies αk > k. Although these results cannot be formally claimed, we conjecture they may be true. As a first evidence of our conjectures, we provide, in the following, a formal proof for the case of k = 2, leaving the extension to any value of k as an open problem. The proof of this result builds on the ideas exploited in the proof of Theorem 9 with some additional technicalities and extends to even agent envy-freeness.

Theorem 11. Let Γ be a market with two buyers and combinatorial monotone valuations. The pricing problem PP = (Γ, sol, obj), with sol {MEF, AEF} and obj {REV, SW}, cannot be approximated up to a factor α < 2 unless P = NP.

Proof. Again, we prove the claim through a reduction from 3SAT (see the proof of Theorem 9 for basic definitions and notation). Given an instance φ := C of 3SAT, we construct a market Γ = ([2], M, v1, v2) with two buyers as follows. The set of items M is obtained by creating γ different copies of each literal, one for each of the γ clauses, and then associating a different item to every copy; so M = {xj i : i [ν], j [γ]} { xj i : i [ν], j [γ]} and |M| = 2νγ, where xj i and xj i are the jth copies of the two literals associated with variable vi V(φ). For example, if C = {c1, c2} = {{x1, x2, x3}, { x1, x2, x3}}, we have V(φ) = {v1, v2, v3}, L(φ) = {x1, x1, x2, x2, x3, x3} and M = {x1 1, x2 1, x1 1, x2 1, x1 2, x2 2, x1 2, x2 2, x1 3, x2 3, x1 3, x2 3}. Given a set of items X M, we say that X represents V(φ) if, for each variable vi V(φ), X contains all items associated to the γ copies of one of the two literals associated to vi, that is, for each i [ν], either {x1 i , . . . xγ i } X or { x1 i , . . . xγ i } X. Thus, any set X representing V(φ) needs have at least νγ items. Similarly, we say that X represents C if, for each clause cj C, X contains the jth copy of at least one of the three literals contained in cj. For instance, clause c1 = {x1, x2, x3} is represented by X = {x1 1}, but is not represented by X = {x2 1, x1 2}. As, by construction, each clause has its dedicated copies of the literals, no item can represent more than one clause. Hence, any set X representing C needs have at least γ items. The valuation functions of the two buyers are defined as follows:

v1(X) = 1 if X represents V(φ), 0 otherwise.

v2(X) = 1 if X represents C and |X| νγ, 0 otherwise.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

Observe that, for both buyers, the valuation of a set X either stays the same or increases when adding new items, so that both v1 and v2 are monotone. Clearly Γ can be constructed in polynomial time with respect to the representation of φ. However, in order to complete the reduction, we have to implement an oracle which can answer demand and value queries in polynomial time. To this aim, observe first that both ν and γ are polynomial in the representation of φ. Hence, given a set of items X, determining whether it represents either V(φ) or C can be performed in polynomial time, so that value queries can be efficiently answered for both buyers. In order to provide an efficient answer to a demand query for a given price vector p, we consider the two buyers separately. For buyer 1, observe that, by the definition of v1, the answer to a demand query is either a set X representing V(φ) or the empty set. Moreover, as item prices are non-negative and the valuation of all sets representing V(φ) is the same under v1, a set X maximizing the buyer s utility among all the ones representing V(φ) can be obtained by selecting, for each variable in V(φ), the literal whose copies amount for the lowest total price. Formally, for each i [ν], we choose {x1 i , . . . , xγ i } if P j [γ] p(xj i) P j [γ] p( xj i) and { x1 i , . . . , xγ i } otherwise. This choice can be performed in O(νγ) time. For buyer 2, observe that, by the definition of v2, the answer to a demand query is either a set X representing C and such that |X| νγ or the empty set. Moreover, as item prices are non-negative and the valuation of all sets representing representing C and having cardinality at least νγ is the same under v2, a set X maximizing the buyer s utility among all the ones representing C and such that |X | νγ can be obtained by selecting, for each clause cj C and each literal in cj, the cheapest among their jth copies and then the νγ γ cheapest items among the remaining ones. Formally, for each j [γ], if cj = {ℓ1, ℓ2, ℓ3}, any item belonging to argmin{p(ℓj i) : i [3]} is chosen. Then, the cheapest items among the leftovers are added. The entire selection can be performed in O(νγ) time, after having ordered the price vector. Thus, market Γ can be generated and managed in polynomial time. Now, in order to complete the proof, we show that there exists a market envy-free outcome o MEF(Γ) such that SW(o) = REV(o) = 2 if φ is satisfiable and that, whenever φ is not satisfiable, for any outcome o OUT(Γ), we have SW(o) 1 and REV(o) 1. As market envy-free outcomes are also agent envy-free ones, it follows that any α-approximation algorithm for the pricing problem (Γ, sol, obj), with sol {MEF, AEF}, obj {SW, REV} and α < 2, could be used to solve 3SAT, thus implying P = NP. Assume first that φ is satisfiable and let f be a satisfying assignment for φ. Let L be the set of literals which are false in f and let X denote the set of items corresponding to all the copies of literals in L , so that |X| = νγ. Let p be the pricing vector in which all items are priced 1 νγ . By definition, X represents V(φ), thus, we have u1(X, p) = 0, so that (X, p) is individually rational for buyer 1. Moreover, as every set of items representing V(φ) needs have at least νγ items, none of them can give buyer 1 a utility larger than zero. Thus, X D1(p). As f is a satisfying assignment, by definition of L , it follows that L(φ) \ L is a set of literals satisfying φ. This implies that, for any clause cj C, there exists a literal ℓ L(φ) \ L such that ℓ cj. Thus, the jth copy of ℓcan represent clause cj. As this property holds for each cj C, set M \ X represents C and satisfies |M \ X| = νγ. It follows that u2(M \ X, p) = 0, so that (M \ X, p) is individually rational for buyer 2, and therefore outcome o = ((X, M \ X), p) is individually-rational. Moreover, as every set of items yielding a non-zero valuation to buyer 2 needs have at least νγ items, none of them can give buyer 2 a utility larger than zero. Thus, M \ X D2(p). Hence, we conclude that o MEF(Γ) and SW(o) = REV(o) = 2. Now assume that φ is not satisfiable. We claim that, for any set of items X representing V(φ), there cannot exist a set Y M \ X representing C. Assume the contrary, by way of contradiction. That is, there exists a set of items Y M \ X such that, for each cj C, Y contains the jth copy of a literal occurring in cj. This implies that there exists a set of literals L L(φ) such that L cj = for each j [γ]. As X represents V(φ) and X Y = , it follows that, for any variable vi V(φ), L cannot contain both xi and xi. Thus, by setting to true every literal in L , we obtain a satisfying assignment for φ, contradicting the

PRICING PROBLEMS WITH BUYER PRESELECTION

assumption that φ is not satisfiable. We conclude that, when φ is not satisfiable, any outcome o OUT(Γ), no matter whether o meets some envy-freeness property or not, cannot assign to both buyers a set of items of value 1. Thus, SW(o) 1 and REV(o) 1.

4. Results for Agent Envy-Free Outcomes

In this section, we consider the buyer preselection problem BPP(Γ, AEF, obj) with obj {REV, SW} and Γ being a market with combinatorial valuations. Since we deal with agent envy-free outcomes, we suppose that the price of any unsold item is infinite. Formally, given a solution (N, o), where outcome o = (X, p), for the buyer preselection problem BPP(Γ, AEF, obj) with Γ = (N, M, (vi)i N), we have that, for any j M \ M(X), pj = . We start by considering the buyer preselection problem BPP(Γ, AEF, REV). We are going to show how it is possible to transform an agent envy-free solution ( N, o) with preselection into anther one (without preselection) having a non-smaller revenue. In order to do that, we first need an additional definition and some lemmas.

Definition 12. A solution ( N, o), where o = ( X, p), for the buyer preselection problem BPP(Γ, AEF, REV) is called maximal if there is no solution ( N, o ) for the same buyer preselection problem BPP(Γ, AEF, REV) with the same subset of preselected agents N where outcome o = ( X, p ) is such that p j pj, for any j M, and there is at least an item k M( X) such that p k > pk.

Informally, a solution ( N, o) for the buyer preselection problem BPP(Γ, AEF, REV) (i.e., where AEF holds for agents in N) is maximal if it is not possible to obtain another one with the same allocation vector, in which we increase the price of at least one sold item while keeping the prices of the remaining items unchanged. The following claim shows that any non-maximal solution can be efficiently transformed into another one (with the same allocation vector) being maximal.

Claim 13. Given a solution ( N, o), where o = ( X, p), for the buyer preselection problem BPP(Γ, AEF, REV), it is always possible to compute in polynomial time a solution ( N, o ) for the buyer preselection problem BPP(Γ, AEF, REV) with the same allocation vector, i.e., with o = ( X, p ), such that REV( o ) REV( o).

Proof. Given an allocation vector X = ( X1, . . . , X| N|), consider the following linear program.

subject to vi( Xi) P

j Xi pj vi( Xz) P

j Xz pj, i N, z N

j Xi pj 0, i N

pj 0 j = 1, . . . , m

Notice that, since we start from an agent envy-free solution, the linear program always admits a feasible solution. It is easy to see that, by solving the linear program, we get a pricing vector for the allocation X such that the obtained solution is agent envy-free and the revenue is maximized. Clearly, this solution is also maximal.

The following lemmas show some interesting properties of maximal solutions that will be useful in the proof of Theorem 16.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

Lemma 14. Given a maximal solution ( N, o), where o = ( X, p), for the buyer preselection problem BPP(Γ, AEF, REV) with Γ = (N, M, (vi)i N), there exists a buyer i W( X) such that ui( Xi, p) = 0.

Proof. Assume, for the sake of contradiction, that for any i W( X) it holds that ui( Xi, p) > 0. Let t W( X) be the winner with the minimum (greater than zero) utility. Then, for any i W( X), let us consider any item ji Xi (i.e., ji is any item sold to buyer i). By increasing the prices of all ji, for any i W( X), by the quantity ut( Xt, p), we obtain another solution (with the same allocation vector X) for BPP(Γ, AEF, REV). In particular, we notice that the new solution is still agent envy-free since, by raising the price of each bundle by the same quantity, we do not create new envy. Moreover, each buyer has still greater or equal than zero utility. This is a contradiction to the fact that solution ( N, o) is maximal.

Lemma 15. Given a maximal solution ( N, o), where o = ( X, p), for the buyer preselection problem BPP(Γ, AEF, REV), with Γ = (N, M, (vi)i N), for any buyer i W( X) such that ui( Xi, p) > 0, there exists ti W( X), where i = ti, such that ui( Xi, p) = ui( Xti, p).

Proof. Clearly, since ( N, o) is a solution for the BPP(Γ, AEF, REV), then for any i, i W( X) it holds that ui( Xi, p) ui( Xi , p). That is, among all the sold bundles, Xi is the one that gives maximum utility to buyer i. Assume, for the sake of contradiction, that there exists i W( X) such that for any i W( X) \ {i} it holds that ui( Xi, p) > ui( Xi , p). Let l W( X) \ {i} such that ui( Xl, p) ui( Xv, p), for any v W( X) \ {i}, i.e., Xl is the bundle giving maximum utility to buyer i if we exclude bundle Xi. By increasing the price of an item j Xi by the quantity ui( Xi, p) max{ui( Xl, p); 0} we obtain another solution (with the same allocation vector X and higher revenue) for BPP(Γ, AEF, REV). In fact, since we started from an agent envy-free outcome, from one hand we have that buyer i still gets the bundle for which she has the maximum utility (that is still greater or equal than zero). On the other hand, for each other buyer but i, it still holds that she does not envy buyer i (as well as none of the other buyers) since we have increased the price of the bundle assigned to i. This is a contradiction to the fact that solution ( N, o) is maximal.

We are now ready to prove the following theorem.

Theorem 16. Let Γ = (N, M, (vi)i N) be a market with combinatorial valuations and PP = (Γ, AEF, REV) be a pricing problem. Given any solution ( N, o) for the buyer preselection problem BPP(PP), it is possible to compute in polynomial time an outcome o AEF(Γ) for problem PP such that REV(o) REV( o).

Proof. Without loss of generality, we can assume that solution ( N, o) is maximal, because, otherwise, it can be transformed by Claim 13 in a maximal one with at least the same revenue. Let o = ( X, p). We show how to constructively get in polynomial time the outcome o AEF(Γ) starting from ( N, o). For any buyer i N \ N, let Ui be the set of bundles belonging to X giving maximum and positive (i.e., greater than zero) utility to i. Moreover, for any i N, let Ei X \ { Xi} be the set of bundles such that, for any Xj Ei, ui( Xi, p) = ui( Xj, p), (i.e., Ei is the set of sold bundles giving to buyer i the same utility as bundle Xi). By Lemma 15 we know that Ei = whenever ui( Xi, p) > 0. If, for every buyer i N \ N, it holds that Ui = , it implies that o AEF(Γ) and the theorem holds. Otherwise, let us define the following directed graph G = (N, A). We first notice that given an allocation vector X = (X1, X2, . . .), we have that the bundle Xi, which is the set of items sold to buyer i, univocally identifies the buyer i. That is, in the following we will use Xi also for identifying buyer i. For instance, Ei identifies both the set of bundles and the set of buyers getting bundles in Ei. The set of nodes of the graph G is the set of buyers N. Moreover, for any i N \ N and for any j Ui, there is a directed edge (i, j) A. Finally, for any i N and for any j Ei, there is a directed edge (i, j) A.

PRICING PROBLEMS WITH BUYER PRESELECTION

Let us consider any buyer i N \ N such that Ui = . Then we argue that, in the graph G there is a directed path a = i, i , i , . . . , z, j from node i to another j N such that uj( Xj, p) = 0. Notice that such path can be efficiently computed by performing a breadth first search starting from node i. Suppose, for the sake of contradiction, that such path does not exist. It implies that the sub-tree rooted in the node i contains all winners, excluding i, having utility strictly greater than zero. Let us denote with Ti W( X) the set of winners belonging to such sub-tree rooted in the node i. Notice that for any j Ti, it holds that Ej Ti. By exploiting arguments similar to the ones exploited in the proofs of lemmas 14 and 15, it is possible to show that ( N, o) is not a maximal solution: a contradiction. Indeed, for any j Ti, let lj W( X) \ Ej such that uj( Xlj, p) uj( Xi, p), for any i W( X) \ Ej, that is, Xlj is the bundle giving maximum utility to buyer j among all the bundles assigned to buyers in W( X) \ Ej. Notice that uj( Xj, p) > uj( Xlj, p). Let δ = minj Ti(uj( Xj, p) uj( Xlj, p)). For any j Ti, let us consider any item ij Xj (i.e., ij is an item sold to buyer j). By increasing by δ the prices of all ij, for any j Ti, we obtain another solution ( N, o ) for the buyer preselection problem BPP(PP) with the same allocation vector X where we have increased the price of at least one sold item while keeping the prices of the other ones unchanged. This is in contradiction with the fact that the solution ( N, o) is maximal. Therefore, given the path a, we can obtain a new allocation vector where buyer i becomes a winner and buyer j gets no item. Recall that uj( Xj, p) = 0 and therefore node j would not envy any bundle. In particular, node (i.e., buyer) i gets the bundle Xi , node i gets the bundle Xi and so on, and finally node j gets no item. That is, the new allocation vector X is as follows: any buyer not in the path a gets the same allocation as in X, and moreover X i = Xi , X i = Xi , . . . , X z = Xj, X j = . In this way we get a new solution ( N = N {i}, o ), where o = ( X , p), for the buyer preselection problem BPP(Γ, AEF, REV) with the same revenue as ( N, o), and where node i is not excluded anymore. However, notice that the obtained solution could be not maximal anymore. Indeed, we need to make it maximal and such that buyer j would be still not envious. We can get it by using a linear program similar to the one defined in the proof of Claim 13, with some further constraints. In particular, we want that the total price of any bundle is at least as it is in solution ( N, o). Notice that in the new allocation vector the set of sold bundles is the same, because we are just changing the allocation of bundles to buyers. Given the allocation X , let us consider the following linear program.

subject to vi( X i) P

j X i p j vi( X z) P

j X z p j, i N , z N

j X i p j P

j X i pj, i N

p j 0 j = 1, . . . , m

Notice that the above defined linear program admits at least a feasible solution, being ( N , o ), where o = ( X , p). It is easy to see that, by solving the linear program, we get a maximal solution ( N , o ), where o = ( X , p ), for the buyer preselection problem BPP(Γ, AEF, REV). Indeed, remind that a solution for the buyer preselection problem is such that AEF holds among preselected buyers. If the solution to this linear programming is not maximal it means that we can get a new outcome for the buyer preselection problem with the same set of preselected buyers N with the same allocation where we can increase the price of at least one sold item while keeping the prices of the remaining items unchanged. However, this new outcome satisfies all the constraints of the linear programming and this is a contradiction with the fact that in the linear programming we maximize the sum of the prices of sold items. Moreover, notice that in the obtained maximal solution, buyer j has still maximum utility at most zero, that is, buyer j is not envious and we do not need to exclude her from the market.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

At this point, for each buyer i not in the market, we compute again (as before) the set Ui, and for any buyer i in the market the set Ei. We then repeat the same procedure described above. Notice that the sets Ui and Ei, and the edges in the graph G can be in general different at any step. Finally, since at each step we include a new buyer in the market (without excluding any other buyer) and the prices of the bundles never decrease, we are able to get in polynomial time outcome o AEF(Γ) such that REV(o) REV( o), as desired.

Buyer Item set {1} {2} {3} {4} {5} {6} {7} {8}

1 2 3 4 4 4 1 3 5 2 3 2 3 3 4 1 4 4 3 4 4 1 3 3 3 5 5 4 2 3 3 2 4 1 3 3 5 3 2 0 3 5 0 7 4

Table 5: The buyers valuations of Example 3.

We now present an illustrating example showing how Theorem 16 works for a specific instance of the problem. In particular, we consider a market with additive valuations to make things simpler.

Example 3. Let Γ = (N, M, (vi)i N) be a market with additive valuations with n = 5 buyers and m = 8 items, and PP = (Γ, AEF, REV) a pricing problem. The buyers valuations for each item are reported in Table 5. Let us consider the solution ( N, o) for the buyer preselection problem BPP(PP) where N = {1, 2, 3} and o = ( X, p) = (( X1, X2, X3), ( p1, p2, p3, p4, p5, p6, p7, p8)) = (({1, 2, 3}, {4, 5, 6}, {7, 8}), (2, 3, 3, 3, 4, 1, 5, 4)). Notice that u1( X1, p) = 1, u2( X2, p) = 0, and u3( X3, p) = 1. It is easy to check that ( N, o) is a maximal solution (see Definition 12) for the buyer preselection problem BPP(PP). In fact, if we increase the price of any item assigned to buyer 2 (i.e., p4, p5 and p6) her utility becomes negative. Moreover, if we increase the price of any item assigned to buyer 1 (i.e., p1, p2 and p3) her utility becomes smaller than one and the resulting outcome would not be agent envy-free since u1( X2, p) = 1. Finally, if we increase the price of any item assigned to buyer 3 (i.e., p7 and p8) her utility becomes smaller than one and the resulting outcome would not be agent envy-free since u3( X2, p) = 1. We now show how, by exploiting Theorem 16, starting from the solution ( N, o), we can compute an outcome o AEF(Γ) for problem PP such that REV(o) REV( o). In the first iteration of the theorem we have that U4 = since u4( X1, p) = 0, u4( X2, p) = 1 and u4( X3, p) = 2. Moreover, U5 = { X3} since u5( X1, p) = 3, u5( X2, p) = 0 and u5( X3, p) = 2. Finally, it is easy to check that E1 = { X2}, E2 = , and E3 = { X1, X2}. Therefore, we get the directed graph G = (N, E) where E = {(1, 2), (3, 1), (3, 2), (5, 3)}. A graphical representation of graph G is reported in Figure 1.

Figure 1: The graph G of Example 3.

PRICING PROBLEMS WITH BUYER PRESELECTION

Let us consider the directed path a = 5, 3, 2 in G (notice that we could also consider the path a = 5, 3, 1, 2 ). We get the new solution ( N , o ) for the buyer preselection problem BPP(PP) where N = {1, 2, 3, 5} and o = ( X , p ) = (( X1 , X2 , X3 , X5 ), ( p 1, p 2, p 3, p 4, p 5, p 6, p 7, p 8)) = (({1, 2, 3}, , {4, 5, 6}, {7, 8}), (2, 3, 3, 3, 4, 1, 5, 4)). Notice that in the new solution buyer 5 is a winner and buyer 2 gets no item, and that we do not get a smaller revenue with respect to ( N, o). We further notice that ( N , o ) is not maximal. Therefore, we apply the linear program defined in the proof of Theorem 16 to ( N , o ) and get, for instance, the following maximal solution ( N , o ) where N = N and o = ( X , p ) = (( X1 , X2 , X3 , X5 ), ( p 1, p 2, p 3, p 4, p 5, p 6, p 7, p 8)) = (({1, 2, 3}, , {4, 5, 6}, {7, 8}), (2, 3, 4, 3, 4, 2, 7, 4)). We notice that by solving the linear program we do not get a different allocation of items to buyers with respect to ( N , o ), and that item prices do not decrease. In the second iteration considered in the proof of the theorem we still have that U4 = . We conclude that (N, o) where o = (X, p) = ((X1, X2, X3, X4, X5), (p1, p2, p3, p4, p5, p6, p7, p8)) = (({1, 2, 3}, , {4, 5, 6}, , {7, 8}), (2, 3, 4, 3, 4, 2, 7, 4)) is such that o AEF(Γ) and REV(o) REV( o) (in particular, in this example we have that REV(o) > REV( o)).

We now consider the buyer preselection problem BPP(Γ, AEF, SW). Analogously to Theorem 16 holding for the revenue maximization case, next theorem shows that an agent envy-free outcome for the buyer preselection problem can be efficiently transformed in an agent envy-free outcome, for the corresponding pricing problem (without preselection), having at least the same social welfare.

Theorem 17. Let Γ = (N, M, (vi)i N) be a market with combinatorial valuations and PP = (Γ, AEF, SW) a pricing problem. Given any solution ( N, o) for the buyer preselection problem BPP(PP), it is possible to compute in polynomial time an outcome o AEF(Γ) for problem PP such that SW(o) SW( o).

Proof. We first give an intuitive explanation of what we do in this proof. Given any solution ( N, o) for the buyer preselection problem BPP(PP) where the market is Γ = (N, M, (vi)i N), we create a new market Γ = (N, M , (v i)i N) with unit-demand buyers and where the number of items is | N|. More precisely, there is an item in M for each sold bundle in ( N, o). Moreover, for each buyer i N, the valuation v i({j}) that i has for item j in market Γ is equal to the valuation vi( Xj) that i has for the corresponding sold bundle in ( N, o) for market Γ (we assume, without loss of generality, that each buyer in N gets a nonempty bundle in the outcome o). We then consider a Walrasian equilibrium for market Γ which, we recall, is a market envy-free outcome with the additional requirement that the market clears and which has the important property of maximizing the social welfare. We finally obtain, by using the Walrasian equilibrium, an agent envy-free outcome for the pricing problem (without preselection) for market Γ with social welfare greater or equal than SW( o). We now proceed with the formal proof. Without loss of generality, let us assume that the agents orderings in N and N are such that the i-th agent of N is also the i-th agent of N (for i = 1, . . . , | N|). Let o = ( X, p) be the considered outcome for problem BPP(Γ, AEF, SW). Consider a new market Γ = (N, M , (v i)i N) with unit-demand buyers, where M = {1, . . . , m } with m = | N| and (v i)i N are such that v i({j}) = vi( Xj). Consider the allocation vector X = (X 1, . . . , X n) for market Γ , in which X i = {i} for any i = 1, . . . , m , and X i = for any i = m + 1, . . . , n. It is easy to check that SW(X , p) = SW( o) for any price vector p. Recall that, given any market Γ, WE(Γ) denotes the set of Walrasian Equilibria for Γ. By the well known First Welfare Theorem (Nisan, Roughgarden, Tardos, & Vazirani, 2007, Theorem 11.13), whenever they exist, Walrasian equilibria maximize social welfare over all possible outcomes. It is also known (Kelso & Crawford, 1982; Leme & Wong, 2017) that a market with gross substitutes valuations always admits a Walrasian Equilibrium that can be computed in polynomial time and with a polynomial number of calls to the value oracle. Moreover, a market with unit-demand buyers (as Γ ) is a special case of a market with gross substitutes valuations in which the value oracle trivially requires polynomial time to be implemented, and

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

therefore always admits a Walrasian Equilibrium that can be computed in polynomial time. Thus, we can compute in polynomial time an outcome o = (X , p ) for market Γ such that (i) SW(o ) SW(X , p) = SW( o) (for any price vector p) and (ii) o WE(Γ ). Let Y = S j M(X ) Xj be the set of all items of market Γ corresponding to items of market Γ sold in allocation X , and, for any i = 1, . . . , n such that X i = , let ki be the unique element of X i . Now, consider the outcome o = (X, p) for market Γ, where X = (X1, . . . , Xn) is such that, for any i = 1, . . . , n,

if X i = then set Xi = as well;

otherwise, set Xi = Xki and, for any j Xki, set pj = p ki | Xki|.

Finally, for any j / Y , set pj = 0. Clearly, by construction, for any i, j = 1, . . . , n such that Xj = , it holds that vi(Xj) = v i({kj}) and ui(Xj, p) = u i({kj}, p ). Therefore, SW(o) = SW(o ) (hence we obtain SW(o) SW( o)) and, given that o WE(Γ ), it follows that o AEF(Γ).

As a consequence of Theorems 16 and 17, we obtain the following corollary.

Corollary 18. Let Γ = (N, M, (vi)i N) be a market with combinatorial valuations. For obj {REV, SW}, given an α-approximate solution (N, o) (with α 1) for the buyer preselection problem BPP(PP) with PP = (Γ, AEF, obj), it is possible to compute in polynomial time an outcome o AEF(Γ) approximating the optimal solution of PP by a factor equal to α.

On the one hand, Corollary 18 tells us that, for obj {REV, SW}, any inapproximability result holding for a pricing problem PP = (Γ, AEF, obj) directly extends to the buyer preselection problem BPP(PP); on the other hand, it tells us that any α-approximation algorithm for BPP(PP) is also an α-approximation algorithm for PP. Thus, as discussed in Section 1.1, preselection can be exploited as an algorithmic framework for designing approximation algorithms for the normal market scenario (without preselection).

5. The Multi-Unit Case

In this section we study the multi-unit case, in which all the m items are of the same type. Recall that, for every i N, the valuation function becomes of the form vi : {0, 1, . . . , m} R 0. Notice that, in this case, the market requires Ω(nm) bits to be represented, because every buyer has a valuation for every possible number of items. Furthermore, in this case an allocation vector X can be specified by the number of items assigned to each buyer, i.e., X = (x1, . . . , xn), with xi {0, . . . , m} for any i = 1, . . . , n, and Pn i=1 xi m. Finally, we set the item price to p (i.e., all the items have the same price) and the total price for selling x items is px. A particular situation of multi-unit market arises when one assumes single-minded buyers; in this case, for every agent i = 1, . . . , n, the valuation function vi can be completely defined by specifying how much every agent valuates the set containing ki items (being the only set she is interested in). Notice that, in this particular case, the market requires Ω(n log m) bits to be represented, because, for every buyer i, it is necessary to represent integer ki. We first focus on the case of market envy-free solutions. The following claim says that preselection cannot improve the revenue and social welfare of envy-free solutions by a factor greater than m.

Claim 19. Given a multi-unit market Γ with identical items and a pricing problem PP = (Γ, MEF, obj) with obj {REV, SW}, it holds that obj(o (BPP(PP))) m obj(o (PP)).

PRICING PROBLEMS WITH BUYER PRESELECTION

Proof. We now show that a market envy-free solution (without preselection) which is a 1/m-approximation with respect to both the optimal social welfare and the optimal revenue (with preselection) can be obtained by selling j items to the buyer i such that ( i, j) argmaxi=1,...,n;j=1,...,m vi(j)

j at price v i( j)

j , i.e., we are

considering outcome (X, p) such that x i = j and xi = 0 for all i = i, and p = v i( j)

j . First of all, notice that the utility of all buyers in outcome (X, p) is 0: buyer i has utility v i(j) jp = v i(j) j v i( j)

j = 0 and all other buyers clearly have utility equal to 0 as they receive no item. The market envy-freeness follows because, for every buyer i = 1, . . . , n (including buyer i) and any j = 1, . . . , m, it holds that vi(j) jp = vi(j) j v i( j)

j 0 (by the choice of i and j).

Finally, the approximation ratio follows by the fact that (X, p) is selling at least an item at price p = v i( j)

j and in no solution (even with preselection, selling at most all m items) there can exist an item sold at a price p > p, because the corresponding buyer i buying j items would have utility vi(j) jp < 0 for any i {1, . . . , n} and j {1, . . . , m} (again by the choice of i and j).

We notice that the above bound is tight: next claim shows that preselection can improve both the revenue and the social welfare of a multi-unit market with identical items of a factor at least m ϵ (for any ϵ > 0), in the case of single-minded buyers.

Claim 20. For any ϵ > 0, there exists a multi-unit market Γ with single-minded buyers and identical items, and a pricing problem PP = (Γ, MEF, obj) with obj {REV, SW}, such that obj(o (BPP(PP))) (m ϵ)obj(o (PP)).

This claim follows from the following example.

Example 4. Consider a market with only two single-minded buyers. Buyer 1 has a valuation of 1 + ϵ , for an ϵ > 0, for receiving any (one) item. Buyer 2 has a valuation of m for receiving all the m items. Notice that, in any market envy-free outcome for the setting without preselection, buyer 2 receives no item. In fact, if buyer 2 receives m items, the item price p must be at most 1. Thus, buyer 1 would be envious since she would get no item (i.e., there are not enough items). Therefore, for the market without preselection, the only feasible solutions are selling one item to buyer 1 at price at least 1 and at most 1 + ϵ . Thus the optimal revenue and the optimal social welfare are equal to 1 + ϵ . However, if we exclude buyer 1 and consider the submarket with only buyer 2, we can sell m items at item price 1, thus obtaining a revenue and social welfare of m. We get that, for any 0 < ϵ < m, m 1+ϵ m ϵ when 0 < ϵ ϵ m ϵ.

Now we focus on the computation of either an optimal or an approximate solution for the preselection problem in the case of market envy-free outcomes, both for the social welfare and the revenue objective functions. Both Theorem 21, holding for the multi-unit case, and Theorem 22, holding for the special case of single-minded buyers, exploit reductions to the 0-1 Multiple-Choice Knapsack Problem, that is defined as follows. The 0-1 Multiple-Choice Knapsack Problem (0-1 MCKP) is a generalization of the classical Knapsack problem introduced by Lawler (1979). In this problem, we are given σ elements, partitioned into α classes C1, C2, . . . , Cα, to be packed in some knapsack of capacity c. Notice that σ = Pα i=1 |Ci|. For every i = 1, . . . , α, each element e Ci has a profit βe and a volume γe, and the problem is to choose a set E containing at most one element from each class such that the profit sum is maximized without the volume sum exceeding capacity c. It is known that this problem can be optimally solved in pseudo-polynomial time, i.e., in time O(σc) (Martello & Toth, 1990, Section 2.12).

Theorem 21. Given a pricing problem PP = (Γ, MEF, obj), where Γ = (N, M, (vi)i N) is a multiunit market with identical items and obj {REV, SW}, the buyer preselection problem BPP(PP) can be

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

optimally solved in time O(nm2) (i.e., in polynomial time in the size of the instance, given that the instance requires Ω(nm) space for its representation).

Proof. Recall that solving the buyer preselection problem BPP(PP) corresponds to finding a subset N of agents to admit to the market and an optimal outcome o = (X , p ), where, since we are considering a multi-unit market, p is just the price of a single item. In order to prove the claim, we first show that it is possible to compute in polynomial time a set P containing the optimal price p for problem BPP(PP). Consider the set P defined as follows:

P = {y|y > 0 i N k,k 0,...,m,k =k vi(k) ky = vi(k ) k y}.

P can be computed in O(nm2) time, i.e., in polynomial time in the size of the instance: in fact, for all buyers i N and for all pairs (k, k ) of integers belonging to {0, 1, . . . , m} such that k = k , P contains the solution y of equality vi(k) yk = vi(k ) yk . Coming back to Example 1, Table 6 shows that, in this case, P = 3

i k k equation solution 1 0 1 0 = v1(1) y y = v1(1) = 0 1 0 2 0 = v1(2) 2y y = v1(2)

2 1 1 2 v1(1) y = v1(2) 2y y = v1(2) v1(1) = 3 2 0 1 0 = v2(1) y y = v2(1) = 2 2 0 2 0 = v2(2) 2y y = v2(2)

2 = 0 2 1 2 v2(1) y = v2(2) 2y y = v2(2) v2(1) = 2

Table 6: The values in set P relative to the market of Example 1.

Now, let (N , o ), with o = (X , p ), be an optimal solution for BPP(PP) with the highest possible item price p and assume by contradiction that p P; let p P the smallest element of P such that p > p . Notice that this element p P has to exist, because p must satisfy, for any i = 1, . . . , n, vi( xi) p xi 0 and y satisfying equality vi( xi) y xi = 0 belongs to P. Since p induces a market envy-free solution, it has to satisfy, for every i = 1, . . . , n, constraint vi( xi) p xi vi(j) p j for any j = 0, . . . , m; since, p P, given how P is defined, it follows that all the above constraints are not satisfied in a strict manner, i.e., it holds that, for every i = 1, . . . , n, vi( xi) p xi > vi(j) p j for any j = 0, . . . , m. Therefore, p still continues to satisfy all envy-free constraints (with some inequalities possibly become strict). It follows that we have found a new envy-free outcome o such that SW(o ) = SW(o ) and REV(o ) > REV(o ): a contradiction to the fact that o was the optimal outcome with the highest possible item price. Therefore, since the number of values that can be assigned to p in order to obtain an optimal outcome is polynomial in the size of the instance, it remains to show that, given a fixed price p , it is possible to optimally compute in polynomial time a subset N of agents to admit to the market and an allocation X . In fact, the optimal solution of BPP(PP) is given by the best solution among the ones obtained for all the candidate prices belonging to P. We now provide a polynomial reduction from our problem to 0-1 MCKP. Given an instance I of BPP(PP) and fixed a price p , we construct an instance I of 0-1 MCKP as follows: We have α = n classes (one class for each buyer) and the capacity c = m. Consider, for every buyer i = 1, . . . , n, the number of items providing her with the highest possible positive utility: let Ui = (arg maxk=0,...,m (vi(k) kp ))\{0} be the set containing these values. Notice that if a buyer i has negative utility for all possible bundles of k = 1, . . . , m items, then arg maxk=0,...,m (vi(k) kp ) = {0} and Ui = . It is easy to check that, in

PRICING PROBLEMS WITH BUYER PRESELECTION

every market envy-free solution, allocation X must satisfy xi Ui for every agent i = 1, . . . , n receiving at least an item. For every i = 1, . . . , n, consider set Ui: for every k Ui, we add to class Ci an element e such that γe = k and

βe = kp if obj = REV;

βe = vi(k) if obj = SW.

Notice that the total number of elements σ is at most nm. If we consider again the market of Example 1, we have α = 2 classes and capacity c = 2. Moreover, if we set p = 3

2 and consider obj = SW, U1 = {2} and U2 = {1}: we therefore add to class C1 an element e1 such that γe1 = 2 and βe1 = v1(2) = 3, and to class C2 an element e2 such that γe2 = 1 and βe2 = v2(1) = 2. Given a solution E for I with total profit β = P e E βe, it is possible to obtain a solution for I with fixed price p , i.e., a subset N of agents to admit to the market and an allocation X, as follows: N contains the agents associated to classes containing an element belonging to E, i.e., N = {i|Ci E = }, and the allocation vector X = ( x1, . . . , xn) is such that, for every i N, xi = γe if there exists an element e Ci E. Let o = ( X, p ); clearly, obj( o) = β. Furthermore, by the way Ui is defined, outcome o is market envy-free. Coming back to the example considered above, if we consider solution E containing only element e1 (of total profit 3), then we admit to the market only buyer 1 and allocate 2 items to her, thus obtaining a market envy-free outcome of social welfare 3. Conversely, given a subset N of preselected agents and an outcome o = (X, p ) for I, it is possible to obtain a solution for I with the profit being equal to obj(o) as follows: for every i N, add to E element e Ci such that γe = xi (by recalling the definition of Ui, it holds that this element e belongs to Ci because outcome o is market envy-free). Clearly, the total profit β = P e E βe = obj(o). The claim follows by noticing that, since σ nm and c = m, the pseudo-polynomial algorithm by Martello and Toth (1990) is in fact polynomial with respect to the size of the instance of problem BPP(PP).

For the special case of single-minded buyers, by exploiting the same ideas used for proving Theorem 21, the following theorem provides an FPTAS, i.e., a fully polynomial time approximation scheme. More precisely, an FPTAS for a problem is an approximation scheme providing, for any ϵ > 0, a (1 + ϵ)- approximation algorithm whose time complexity is polynomial both in the input size and in 1/ϵ; we call ϵ the FPTAS parameter.

Theorem 22. Given a pricing problem PP = (Γ, MEF, obj), where Γ = (N, M, (vi)i N) is a multiunit market with single-minded buyers and identical items, for obj {REV, SW}, the buyer preselection problem BPP(PP) admits a fully polynomial approximation scheme generating algorithms with execution time O n2

ϵ , i.e., polynomial both in the instance size (given that the instance requires Ω(n log m) space for its representation) and in 1/ϵ, where ϵ is the FPTAS parameter.

Proof. Since we are considering a multi-unit market with identical items, the proof is analogous to the one of Theorem 21: We will first show that it is possible to compute in polynomial time a set P containing the optimal price p for problem BPP(PP), and then we will show that, given a fixed price p , it is possible to optimally compute in polynomial time a subset N of agents to admit to the market and an allocation X . The critical point here is that in this case an instance of the buyer preselection problem requires only Ω(n log m) bits. First of all, we have to check that the computation of the possible optimal prices is still polynomial. In order to compute, analogously to the proof of Theorem 21 (notice that if buyer i is single-minded, she does

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

not envy bundles with size different from ki), set P containing the optimal price p for problem BPP(PP), we note that in this case P can be defined as follows:

P = {y|y > 0 i N vi(ki) yki = 0}.

Therefore, it is possible to compute set P in time O(n). Furthermore, since in this case, for every i = 1, . . . , n, | Ui| 1 (where Ui is defined as in the proof of Theorem 21), also the reduction from our problem to 0-1 MCKP is still polynomial and σ n. Finally, notice that in this case we cannot exploit the pseudo-polynomial algorithm by Martello and Toth (1990) having complexity O(σc) = O(nm), because m cannot be guaranteed to be polynomial in the size of the instance being Ω(n log m). The claimed FPTAS result follows from the FPTAS provided by Lawler (1979) for 0-1 MCKP, running in time O α log α + ασ

ϵ , that in our reduction becomes O n2

We complement the result of Theorem 22 by showing the NP-hardness of the problem of computing the maximum revenue for the case of market envy-free in multi-unit markets with single-minded buyers and identical items. The following theorem is proved by exploiting a reduction from the Subset Sum problem.

Theorem 23. Given a pricing problem PP = (Γ, MEF, REV), where Γ = (N, M, (vi)i N) is a multi-unit market with single-minded buyers and identical items, the buyer preselection problem BPP(PP) is NP-hard.

Proof. We use a reduction from the Subset Sum problem, that is defined as follows: given a set of integers and an integer s, does any non-empty subset sum to s? Let n be the number of elements {a1, a2, . . . , an} in the given instance of the Subset Sum problem, and let s be the required sum. We assume that Pn i=1 ai > s, as otherwise the problem is trivial. For all ai in the input of the Subset Sum problem, we create a corresponding buyer i with the following valuation. Buyer i has valuation ai for receiving ai items, and zero otherwise. Moreover, we set the number of items m = s. If there is a solution for the given instance of the Subset Sum problem, then by setting the item price p = 1 and selling to corresponding buyers gives us a feasible and envy-free outcome in which the revenue equals to m. It is easy to see that m is an upper bound to the maximum revenue. In fact, every buyer has a value per item equal to 1, and therefore, by individual rationality, no buyer can be assigned items priced more than 1. On the other hand, if the revenue of the optimal outcome to the buyer preselection problem is equal to m, we can obtain a solution to the Subset Sum problem. Notice that we can obtain a revenue of m only if we sell exactly m items at item price p = 1. In fact, at item price p > 1, we sell no item, and at item price p < 1, we do not get an optimal solution.

We now focus on the case of agent envy-free solutions. We first notice that the results of Section 4 claiming that buyer preselection in agent envy-free solutions does not improve the quality of outcomes (with respect to neither social welfare nor revenue maximization) do not hold for the multi-unit case, because in this case it is not possible to change the price of some items without influencing the other ones; actually, as proved in Claim 25, preselection can improve, with respect to both social welfare and revenue maximization, the quality of outcomes. We start by showing that, for multi-unit markets with identical items and general valuations, preselection can improve the revenue by a multiplicative factor of at most 2.

Theorem 24. Given a solution ( N, o) for the buyer preselection problem BPP(PP), with PP = (Γ, AEF, REV) and Γ = (N, M, (vi)i N) being a multi-unit market with identical items, it is possible to compute in polynomial time an outcome o AEF(Γ) for problem PP such that REV( o) 2REV(o).

PRICING PROBLEMS WITH BUYER PRESELECTION

Proof. Let o = ( X, p). In the following we will show how to compute in polynomial time an outcome o AEF(Γ) with o = (X, p) such that (i) p p and (ii) |M(X)| |M( X)| 2 : this directly implies that REV(o) REV( o)

2 , because outcome o sells at least one half of the items sold by outcome o at a price at least equal to p. See Example 5 and the subsequent discussion for a clarifying example showing how this proof can be exploited in order to obtain an outcome o AEF(Γ) with REV(o) REV( o)

2 . For every j = 1, . . . , m, let aj be the number of items that could be sold to some buyers in bundles of cardinality j at price p (we require that these buyers obtain a non-negative utility for a bundle of j items). More formally, for every j = 1, . . . , m, let Bj( p) = {i|vi(j) j p 0} be the subset of agents obtaining a non-negative utility for a bundle with j items; then, aj = j|Bj( p)|. We divide the proof in two disjoint cases.

If there exists j {1, . . . , m} such that aj |M( X)| 2 , outcome o = (X, p) is such that xk = j for every k Bj( p), and xk = 0 otherwise. By setting p = p, by the definition of aj, we know that aj items could be sold without generating envy.

If aj m, we are done.

If j |M( X)| 2 , we can increase the price p so that only buyer i, with i such that vi(j) = maxn k=1 vk(j), is assigned the bundle (notice that in this way no other buyer is envious).

It remains to deal with the subcase in which aj > m and j < |M( X)| 2 : We increment price p until the number of buyers x with positive utility is such that xj m. We then assign bundles of j items to all buyers with positive utility and to as many buyers with zero utility as possible, thus selling at least m j items. Notice that (i) since j < |M( X)| 2 implies that m j > |M( X)| 2 , this process leads to

obtain at least |M( X)| 2 assigned items and (ii) again no buyer is envious.

If for all j {1, . . . , m} it holds that aj < |M( X)| 2 , outcome o = (X, p) (with the same price as in outcome o) is computed as follows.

For any i = 1, . . . , n and k = 1, . . . , m, let u k i = maxk t=0{vi(t) t p} be the maximum possible utility of buyer i for bundles of at most k items and b k i = max{j|0 j k vi(j) j p = u k i } the maximum size of a bundle for buyer i that achieves utility u k i . Moreover, for any k = 1, . . . , m and j = 0, . . . , k, let Bk,j = {i|b k i = j} be the set of buyers having j items as their best bundle of maximum utility, among all bundles made up to k items, and resolving ties by selecting the bundle of maximum size. Notice that, for any k = 1, . . . , m, sets Bk,0, . . . , Bk,k partition the set N of buyers.

Notice that Bk,j can be computed in time poly(n, m). In fact, for any i {1, . . . , n}, u k i and b k i can be computed in time being linear in k m (by enumerating all the k candidates that can realize the requested maximum) and Bk,j can be computed in time proportional to nk (by computing b k i for i = 1, . . . , n, i.e., for all the n buyers in the market).

For k = 1, . . . , m, consider allocation Xk = (xk 1, . . . , xk n) such that, for every i = 1, . . . , n, xk i = j if i Bk,j. By the definition of Bk,j it follows that allocation Xk is envy-free. Moreover, it can be easily verified that |M(X1)| = a1 and, for any j = 2, . . . , m, |M(Xj)| |M(Xj 1)| aj.

If |M(Xm)| m, the claim trivially follows by setting X = Xm because we are allocating at least all items allocated in o.

Otherwise, let k be the minimum value of k = 2, . . . , m such that |M(Xk )| > m: the claim follows by setting X = Xk 1. In fact, since |M(Xk )| |M(Xk 1)| ak |M( X)| 2 , it follows that

|M(Xk 1)| m |M( X)| 2 |M( X)| 2 .

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

We now show that there exist multi-unit markets with identical items in which preselection can improve both the revenue and the social welfare in the case of single-minded buyers, thus closing in a tight way the previous bound.

Claim 25. For any ϵ > 0, there exists a multi-unit market Γ with single-minded buyers and identical items, and a pricing problem PP = (Γ, AEF(Γ), obj) with obj {REV, SW}, such that obj(o (BPP(PP))) (2 ϵ)obj(o (PP)).

This claim follows from the following example.

Example 5. Consider a market with x + 1 single-minded buyers. Buyer 1 has a valuation of x for receiving x items. Buyer i, for any i = 2, 3, . . . , x + 1, has a valuation of 1 + ϵ , for a small ϵ > 0, for receiving any (one) item. Finally, the number of items is 2x 1. Notice that, in any agent envy-free outcome for the setting without preselection, if buyer 1 receives x items, then the item price p must be at most 1. Moreover, no buyer i, for any i = 2, 3, . . . , x + 1, can get items. The reason is that such buyers have positive utility for receiving one item, but the number of items is not sufficient to satisfy all of them. Therefore, the only chance is selling no bundle of one item. Thus, on one hand, without preselection, the best revenue and social welfare is x(1 + ϵ ). It can be obtained by selling one item to buyers i, for any i = 2, 3, . . . , x+1, at price 1+ϵ . On the other hand, if we consider the submarket with only buyers 1, 2, . . . , x (i.e., we exclude one buyer that has a valuation of 1+ϵ for receiving any (one) item), we can sell 2x 1 items at item price 1, that is x items to buyer 1, and one item to buyers i, for any i = 2, . . . , x, thus obtaining a revenue and social welfare of 2x 1. We get that, for any x > 1

ϵ and 0 < ϵ < 2, 2x 1 x(1+ϵ ) 2 ϵ when 0 < ϵ xϵ 1 x(2 ϵ). Notice that xϵ 1 x(2 ϵ) > 0. If we consider the latter solution ( N, o) of the buyer preselection problem with N = {1, . . . , x} and o = ( X, p) such that p = 1 and x items are sold to the first buyer, while other x 1 items to the remaining x 1 buyers (one item for each of them), we can exploit the proof of Theorem 24 as follows. First of all, notice that REV( o) = |M( X)| = 2x 1 and, since B1(1) = {2, 3, . . . , x + 1}, Bx(1) = {1} (and Bj(1) = for all j {1, x}), it holds that a1 = ax = x. Therefore, we are in the first case considered in the proof, given that a1 = ax |M( X)| 2 . In fact, an agent envy-free solution o with REV(o) = x can be obtained by selling, at price p = p = 1, either only a bundle of x items to buyer 1, or x bundles of one item to buyers 2, 3, . . . , x + 1.

It is worth noticing that, on the one hand, preselection can be exploited as an algorithmic framework for designing good approximation algorithms (losing only a multiplicative factor of 2) for the normal market scenario without preselection; on the other hand, since the optimal revenue with preselection is at most twice the one without, an α-approximation algorithm for the normal market without preselection, is a 2αapproximation one for market with preselection.

6. Final Remarks and Future Work

Many results holding for market envy-free outcomes and the objective function of social welfare extend to the notion of Walrasian Equilibrium. In particular, the inapproximability result of Theorem 6 (as already noticed in its proof) and the n-approximation algorithm for the buyer preselection problem of Theorem 10 (given that the outcome considered in Claim 8 has all prices set to 0) directly extend to Walrasian Equilibria. Notice also that, for the remaining uncovered cases, that is when the goal is that of optimizing the seller s revenue, there is no reason for requiring market clearance, a condition clearly limiting the power of setting prices so as to maximize the revenue. The main problems which are left open are: for markets with a unique buyer, closing the gap between NP-hardness and the logarithmic approximation for the case of revenue maximization and market envy-free

PRICING PROBLEMS WITH BUYER PRESELECTION

solutions; for markets with few buyers, proving (or disproving) the conjecture stated at the beginning of Section 3.2; for the multi-unit case with agent envy-free outcomes, determining an upper bound to the social welfare improvement achievable by preselection and settling the complexity of computing optimal solutions, for both objective functions.

Acknowledgements

Preliminary versions of this paper appeared in the proceedings of AAMAS 2018 and MFCS 2018 (Bil o, Flammini, Monaco, & Moscardelli, 2018a, 2018b). We thank the anonymous referees for their valuable comments that helped improving the presentation of the paper and also generalizing and making stronger some of our results. This work was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR Algorithms, Games, and Digital Markets (2017R9FHSR 002).

Abebe, R., Kleinberg, J. M., & Parkes, D. C. (2017). Fair division via social comparison. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 281 289. ACM Press.

Alon, N., Mansour, Y., & Tennenholtz, M. (2013). Differential pricing with inequity aversion in social networks. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC), pp. 9 24. ACM Press.

Amanatidis, G., Markakis, E., & Sornat, K. (2016). Inequity aversion pricing over social networks: Approximation algorithms and hardness results. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 9:1 9:13. Schloss Dagstuhl - Leibniz Zentrum f ur Informatik.

Anshelevich, E., Kar, K., & Sekar, S. (2015). Envy-free pricing in large markets: Approximating revenue and welfare. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 52 64. Springer.

Archer, A., Papadimitriou, C. H., Talwar, K., & Tardos, E. (2003). An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Mathematics, 1(2), 129 150.

Balcan, M. F., Blum, A., & Mansour, Y. (2008). Item pricing for revenue maximization. In Proceedings of the 9th ACM Conference on Electronic Commerce (EC), pp. 50 59. ACM Press.

Bikhchandani, S., & Mamer, J. W. (1997). Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74(2), 386 413.

Bil o, V., Flammini, M., & Monaco, G. (2017). Approximating the revenue maximization problem with sharp demands. Theoretical Computer Science, 662, 9 30.

Bil o, V., Flammini, M., Monaco, G., & Moscardelli, L. (2018a). On the impact of buyers preselection in pricing problems. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1871 1873. ACM Press.

Bil o, V., Flammini, M., Monaco, G., & Moscardelli, L. (2018b). Pricing problems with buyer preselection. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 47:1 47:16. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik.

Bouveret, S., & Lang, J. (2008). Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. J. Artif. Intell. Res., 32, 525 564.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

Briest, P. (2008). Uniform budgets and the envy-free pricing problem. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 808 819. Springer.

Briest, P., & Krysta, P. (2006). Single-minded unlimited supply pricing on sparse instances. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1093 1102. ACM Press.

Chalermsook, P., Chuzhoy, J., Kannan, S., & Khanna, S. (2012). Improved hardness results for profit maximization pricing problems with unlimited supply. In Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 73 84. Springer.

Chalermsook, P., Laekhanukit, B., & Nanongkai, D. (2013a). Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more. In Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 1557 1576. ACM Press.

Chalermsook, P., Laekhanukit, B., & Nanongkai, D. (2013b). Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 370 379. IEEE Computer Society.

Chen, N., & Deng, X. (2010). Envy-free pricing in multi-item markets. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), pp. 418 429. Springer.

Chen, N., Deng, X., Goldberg, P. W., & Zhang, J. (2016). On revenue maximization with sharp multi-unit demands. Journal of Combinatorial Optimization, 31(3), 1174 1205.

Chen, N., Ghosh, A., & Vassilvitskii, S. (2011). Optimal envy-free pricing with metric substitutability. SIAM Journal on Computing, 40(3), 623 645.

Chen, N., & Rudra, A. (2008). Walrasian Equilibrium: Hardness, approximations and tractable instances. Algorithmica, 52(1), 44 64.

Cheung, M., & Swamy, C. (2008). Approximation algorithms for single-minded envy-free profitmaximization problems with limited supply. In Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS), pp. 35 44. IEEE Computer Society.

Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2007a). Reaching envy-free states in distributed negotiation settings. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1239 1244. ijcai.org.

Chevaleyre, Y., Endriss, U., & Maudet, N. (2007b). Allocating goods on a graph to eliminate envy. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pp. 700 705. AAAI Press.

Chevaleyre, Y., Endriss, U., & Maudet, N. (2017). Distributed fair allocation of indivisible goods. Artificial Intelligence, 242, 1 22.

Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11, 17 33.

Colini-Baldeschi, R., Leonardi, S., Sankowski, P., & Zhang, Q. (2014). Revenue maximizing envy-free fixed-price auctions with budgets. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), pp. 233 246. Springer.

Demaine, E. D., Feige, U., Hajiaghayi, M., & Salavatipour, M. R. (2008). Combination can be hard: Approximability of the unique coverage problem. SIAM Journal on Computing, 38(4), 1464 1483.

Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press.

PRICING PROBLEMS WITH BUYER PRESELECTION

Elbassioni, K. M., Fouz, M., & Swamy, C. (2010). Approximation algorithms for non-single-minded profitmaximization problems with limited supply. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), pp. 462 472. Springer.

Feldman, M., Fiat, A., Leonardi, S., & Sankowski, P. (2012). Revenue maximizing envy-free multi-unit auctions with budgets. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pp. 532 549. ACM Press.

Feldman, M., Gravin, N., & Lucier, B. (2016). Combinatorial Walrasian Equilibrium. SIAM Journal on Computing, 45(1), 29 48.

Flammini, M., Mauro, M., & Tonelli, M. (2018). On fair price discrimination in multi-unit markets. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp. 247 253. ijcai.org.

Flammini, M., Mauro, M., & Tonelli, M. (2019). On social envy-freeness in multi-unit markets. Artif. Intell., 269, 1 26.

Foley, D. (1967). Resource allocation and the public sector. Yale Economic Essays, 7, 45 98.

Groves, T. (1973). Incentives in teams. Econometrica, 41, 617 631.

Gul, F., & Stacchetti, E. (1999). Walrasian Equilibrium with gross substitutes. Journal of Economic Theory, 87, 95 124.

Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Kenyon, C., & Mc Sherry, F. (2005). On profitmaximizing envy-free pricing. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1164 1173. ACM Press.

Hartline, J., & Yan, Q. (2011). Envy, truth, and profit. In Proceedings of the 12th ACM Conference on Electronic Commerce (EC), pp. 243 252. ACM Press.

Karp, J., Kazachkov, A. M., & Procaccia, A. D. (2014). Envy-free division of sellable goods. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp. 728 734. AAAI Press.

Kelso, A. S., & Crawford, V. P. (1982). Job matching, coalition formation, and gross substitutes. Econometrica, 50, 1483 1504.

Kim, J. K., Kim, H. K., Oh, H. Y., & Ryu, Y. U. (2010). A group recommendation system for online communities. International Journal of Information Management, 30(3), 212 219.

Lawler, E. L. (1979). Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 44(4), 339 356.

Leme, R. P., & Wong, S. C. (2017). Computing Walrasian Equilibria: Fast algorithms and structural properties. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 632 651. ACM Press.

Martello, S., & Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., USA.

Monaco, G., Sankowski, P., & Zhang, Q. (2015). Revenue maximization envy-free pricing for homogeneous resources. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 90 96. ijcai.org.

Nagle, T. T., & Holden, R. K. (2002). The strategy and tactics of pricing : A guide to profitable decision making. Prentice-Hall, USA.

Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic Game Theory. Cambridge University Press.

BIL O, FLAMMINI, MONACO, & MOSCARDELLI

Nyman, K., Su, F. E., & Zerbib, S. (2020). Fair division with multiple pieces. Discrete Applied Mathematics, 283, 115 122.

Ortega, J. (2018). Social integration in two-sided matching markets. Journal of Mathematical Economics, 78, 119 126.

Searns, A. (2020). Rethinking resource allocation: Fairness and computability. Master s thesis, Rochester Institute of Technology. Accessed from https://scholarworks.rit.edu/theses/10651.

Segal-Halevi, E. (2018). Redividing the cake. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), p. 498 504. ijcai.org.

Segal-Halevi, E., & Nitzan, S. (2019). Fair cake-cutting among families. Social Choice and Welfare, 53, 709 740.

Segal-Halevi, E., & Suksompong, W. (2019). Democratic fair allocation of indivisible goods. Artificial Intelligence, 277, 103167.

Varian, H. R. (1974). Equity, envy, and efficiency. Journal of Economic Theory, 9, 63 91.

Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16, 8 37.

Walras, L. (1954). Elements of Pure Economics. Allen and Unwin.

Weng, S. S., & Liu, M. J. (2004). Feature-based recommendations for one-to-one marketing. Expert Systems with Applications, 26(4), 493 508.

Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1), 103 128.