# posted_pricing_sans_discrimination__469e4afc.pdf

Posted Pricing sans Discrimination

Shreyas Sekar Rensselaer Polytechnic Institute, Troy, NY-12180 shreyas.sekar@gmail.com

In the quest for market mechanisms that are easy to implement, yet close to optimal, few seem as viable as posted pricing. Despite the growing body of impressive results, the performance of most posted price mechanisms however, rely crucially on price discrimination in the presence of large supply or non-linear production costs. With this in mind, we study the problem of designing non-discriminatory pricing mechanisms for social welfare maximization in a Bayesian setting where the seller only has stochastic information regarding buyer valuations. Our main contribution is a framework for static item pricing in the face of production costs, i.e., the seller posts one price per good and buyers arrive sequentially and purchase utility-maximizing bundles. The framework yields constant factor approximations to the optimum welfare when buyer valuations are fractionally subadditive, and extends to settings where the seller is completely oblivious to buyer valuations. Our results indicate that even in markets with complex buyer valuations and nonlinear costs, it is possible to obtain good guarantees without price discrimination, i.e., charging buyers differently for the same good.

1 Introduction

In the quest for market mechanisms that are simple, yet approximately optimal [Hartline and Roughgarden, 2009], few candidates seem as appealing as posted price mechanisms, where the seller simply posts prices on the items and buyers consume utility-maximizing sets of goods. This optimism towards posted prices is not without cause: a long line of research has established that in addition to a slew of favorable properties, mechanisms based on posted pricing provide near-optimal performance guarantees in a number of diverse applications [Blumrosen and Holenstein, 2008; Feldman et al., 2015; Maehara et al., ]. More recently, some of these results have been extended to settings with general buyer valuations, where sellers only possess distributional information regarding the same [Feldman et al., 2015; Hsu et al., 2016]; such results are a crucial first step towards

the larger goal of understanding the performance of posted prices in more realistic, and general markets. Real markets, however, often feature sellers who possess multiple copies of goods or more generally, costs associated with producing or transporting each copy of good. Here, our picture of posted pricing mechanisms is far from complete. Papers dealing with multi-unit supply in combinatorial auctions have often resorted to price discrimination, i.e., charging buyers differing prices for the same good, in order to extract good performance bounds [Blum et al., 2011; Chakraborty et al., 2010; Cohen-Addad et al., 2016]. In the literature, one also encounters discriminative pricing policies under more benign labels such as dynamic pricing [Chakraborty et al., 2009], sequential postedpricing [Chawla et al., 2010] or non-anonymous reserve prices [Daskalakis and Pierrakos, 2011]. Looking beyond multi-unit supply to the more general case of production costs, little is known about the performance of posted price mechanisms when the underlying costs are non-linear, even less so in Bayesian settings.

Is discriminatory pricing essential for good performance in the presence of multi-unit supply? Do posted prices give desirable guarantees in a Bayesian setting involving production costs?

These are the questions that we seek to answer in this work. Our work is motivated by both theory and practice; price discrimination, while accepted practice in some industries (airline, taxis), is inherently unfair to the buyers and can lead to adverse effects in the long-run [Anderson et al., 2010]. On the other hand, extending the state-of-the-art in Bayesian Mechanism Design to markets with general buyer valuation functions and production costs often necessitates blurring the line between good and copy, resulting in mechanisms that price each copy of a single good as if it were a distinct good. Our central result answers both the questions posed above for Bayesian settings with fractionally subadditive (Xo S) buyer valuations and convex production costs. Specifically, we design an incentive compatible, non-discriminatory mechanism based on static posted prices that extracts a constant fraction of the optimum social welfare. At a high level, our work presents a strong case for treating buyers fairly: by bounding the gains obtained via discriminatory pricing, we argue that the incentives for discrimination may not offset the

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

negative impact of treating buyers unfairly. Market Model We consider a market with a set I of m goods and N buyers having combinatorial valuation functions: v : 2I R+ {0}, i.e., vj(S) denotes buyer j s value for a set S I of goods. The seller faces a convex production cost function with non-decreasing marginal costs for each good, i.e., for every i I, the seller incurs a cost of Ci(ℓ) for producing ℓunits of this good. Such convex costs strictly generalize settings with limited supply. For the majority of this work, we assume a Bayesian setting with prior F = F1 F2 . . . FN: buyer i s private valuation is drawn independently from distribution Fi, which is known to the seller. Our objective is to maximize the social welfare, which is defined as the total value derived by the buyers minus the production cost incurred by the seller. Towards this goal, we propose two types of posted pricing mechanisms depending on whether or not the seller has to commit to producing an exact amount of each good in advance. Both these mechanisms follow a simple template: (i) the seller posts a single price per good applicable to all buyers, and (ii) buyers arrive sequentially in some arbitrary, possibly adversarial order and purchase utility maximizing subsets of the available goods.

1. On the Fly Mechanisms (OTF): The seller fixes an upper bound on the number of copies of each good that he is willing to produce and incurs a production cost only for the items that are actually sold. Once the number of copies of a good sold reaches the upper bound, the item becomes unavailable for future buyers.

2. Commitment Mechanisms: The seller commits to producing a certain quantity of each good and incurs production costs whether or not those items are sold.

When the seller has limited supply, the two classes of mechanisms are equivalent. However, for strictly non-linear production costs, on the fly mechanisms are a relaxation of commitment mechanisms. Finally, all of the mechanisms in this work are trivially dominant strategy incentive compatible.

Comparisons to Existing Work: Dynamic Pricing and Unit Supply To the best of our knowledge, there are no previous results in Bayesian mechanism design dealing with convex production costs (specifically with a view towards non-discriminatory pricing). This is particularly surprising given that increasing marginal costs are a natural consideration in many markets since the limited supply assumption is too pessimistic and additional sources can often be found at higher cost [Blum et al., 2011]. At the same time, the current work acts as a bridge between the closely related streams of literature pertaining to multi-unit combinatorial auctions [Bartal et al., 2003; Blum et al., 2011; Huang and Kim, 2015] and posted pricing with unit-supply [Feldman et al., 2015]. The literature on multi-unit combinatorial auctions has yielded constant-factor approximations for maximizing social welfare in the presence of limited supply and production costs, albeit by offering different posted prices to different buyers. In this work, we study the same setting and approximate social welfare via the more

demanding class of static, non-discriminatory pricing mechanisms instead of dynamic pricing as in previous work 1. On the other hand, in [Feldman et al., 2015], the authors use nondiscriminatory posted prices to maximize welfare when the seller has exactly one unit supply of each good. We extend their result to settings with non-linear production costs on the goods.

1.1 Summary of Contributions

Central Result: 4-approximate On the Fly Mechanism We begin with the class of OTF mechanisms for buyers having Xo S valuations, which generalize submodular functions. We present a black-box reduction that transforms any approximation algorithm Alg for the allocation problem: the problem of allocating goods to buyers to maximize social welfare , into a non-discriminatory posted price mechanism that ensures a social welfare of 1

2E v F[SW(Alg( v))], where SW(Alg( v)) is the welfare guaranteed by Alg on input valuations v. The black-box result makes use of both a demand oracle and an Xo S oracle for the buyer valuations. To supplement the reduction, we also present a poly-time 2-approximation algorithm (Alg) for the allocation problem with Xo S buyers and convex costs. Together, they yield our main computational result: a mechanism that posts a single price per good and extracts one-fourth of the optimum welfare for arbitrary buyer arrival orders and convex costs. (Significance of the Result) Previously, posted pricing mechanisms with good welfare approximations were only known for restrictive settings with one unit supply of each good and no production cost [Feldman et al., 2015]. Although their result could arguably be extended to markets with increased supply, this would require posting different prices for different copies of the same item, i.e., by treating identical copies of a good as distinct goods, any problem with multi-unit supply can be reduced to one with unit supply. On the contrary, our mechanism offers the same price on all copies of a good and makes no assumption on the cost function other than convexity, which is standard in market design [Blum et al., 2011]. Commitment Mechanism and Xo S valuations: For the challenging class of commitment mechanisms, our framework yields welfare guarantees that are sensitive to the structure of the allocation returned by the algorithm. Formally, we define an instance to be α-bounded (as in [Feige et al., 2013]) with respect to an allocation algorithm Alg, if in the solution returned by the algorithm, the expected value derived by the buyers is at least a factor α times the expected production cost incurred by the seller. Then, our mechanism obtains desirable welfare guarantees when α is large, i.e., for instances where the algorithm returns a solution whose expected social welfare is large compared to the cost incurred. More specifically, we present a non-discriminatory commitment mechanism whose approximation factor to the optimum welfare is 4 α 1

α 2 for Xo S buyers (α > 2). If the cost functions are sufficiently convex , then α is large irrespective

1It is noteworthy that the results in [Blum et al., 2011] were obtained for a prior-free setting; we obtain stronger approximation guarantees under a distributional assumption.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

of the buyer valuations, and our mechanism provides good bounds. Sampling Buyer Distributions: Our mechanisms for the Bayesian setting exhibit a runtime polynomial in the support size of the product distribution F. However, one can convert these mechanisms into computationally efficient procedures in a straightforward manner by repeatedly sampling valuation profiles and computing allocations for the sampled valuations. Specifically, applying the sampling techniques in [Feldman et al., 2015], we obtain mechanisms that run in time polynomial in N, m, and 1

ϵ with an additive welfare loss of ϵ from the stated bound. In order to clearly illustrate our technical ideas and avoid messy notation, we suppress the sampling aspect of our mechanisms for the rest of this work.

1.2 Other Related Work This paper also bridges the gap between two closely related fields: auction theory, and envy-free item pricing. Although the mechanisms in this work technically fall under the purview of Bayesian mechanism design [Chawla et al., 2010], they are not auctions in the traditional sense as they do not elicit any input from the buyers; hence, they are trivially dominant strategy incentive compatible (DSIC). Our work is closer in spirit to envy-free pricing algorithms for computing Walrasian equilibrium [Roughgarden and Talgam-Cohen, 2015]. Since Walrasian equilibria do not exist [Gul and Stacchetti, 1999] for complex valuations such as Xo S, one could view the pricing mechanisms in this work as relaxations that sacrifice envy-freeness but guarantee existence and welfare. To the best of our knowledge, there are no mechanisms in the literature that meet all of the desiderata fulfilled by our framework: (i) general buyer valuations (Xo S), (ii) (convex) production cost functions, (iii) non-discriminatory pricing, (iv) non-identically distributed buyers, and (v) dominant strategy incentive compatibility. However, if we relax some of these constraints, we stumble upon a number of closely related works (see for example [Bei and Huang, 2011; Brˆanzei et al., 2014]). Owing to their popularity in real-world applications, there has been a surge in the theoretical investigation of dynamic pricing mechanisms. Specifically, [Blum et al., 2011; Huang and Kim, 2015] look at an OTF-like mechanism where the seller offers different prices in each round and prove welfare bounds that depend on the nature of the production cost function. On the other hand, our mechanism guarantees fairness as the prices remain static throughout. Moreover, our OTF mechanism obtains a 4-approximation to the optimum welfare for arbitrary convex production costs.

2 Model and Preliminaries

As defined previously, we consider a set I of m goods: each i I has a convex production cost, i.e., for any ℓ, the seller incurs a (marginal) cost of ci(ℓ) for producing the ℓth copy of this good, and ci(ℓ) is non-decreasing as ℓincreases. The seller can choose to produce any number of goods for which he faces an aggregate production cost of Ci(ℓ) = Pℓ r=1 ci(r). Such convex costs strictly generalize limited supply. For instance, ci(ℓ) = 0 for ℓ k and

ci(ℓ) = otherwise, indicates a fixed supply of k units. Given an allocation S = (S1, S2, . . . , SN) where Sj is the set of goods allocated to buyer j, suppose that i I, ki represents the number of units of this good allocated to the buyers. Then, the social welfare of this allocation is SW( S) = PN j=1 vj(Sj) P i I Ci(ki). For the rest of this work, we will assume that all buyers have monotone nondecreasing Xo S valuations, which strictly generalize many well-studied functions such as unit-demand, budget additive, and submodular valuations [Dobzinski et al., 2010]. Fractionally Subadditive (or Xo S ) Valuations a set of additive functions (a1, . . . , ar) such that for any T I, v(T) = maxr j=1 aj(T). An additive function (also known as a clause) aj has a single value aj(i) for each i I so that for a set T of goods, aj(T) = P i T aj(i). Oracle Access The standard approach in the literature while dealing with set functions (where the input representation is exponential in size) is to assume the presence of an oracle that allows indirect query access to the valuation. All of our results in Sections 3 and 4 assume black-box access to two types of oracles: (i) a demand oracle that when queried with a vector of prices p returns a set S that maximizes the quantity v(S) P i S pi, and (ii) an Xo S oracle that for an Xo S function v and a set T I returns the additive clause al that maximizes al(T). We refer the reader to [Dobzinski et al., 2010] for a thorough comparison of these two oracles.

Seller s Mechanism: Static Posted Prices A posted pricing mechanism with item prices is said to be static or non-discriminatory if no two buyers are offered the same good at different prices. We now formally define the two types of mechanisms considered in this work. Note that both our mechanisms do not elicit any input from the buyers. On the fly mechanism In an OTF mechanism, a seller incurs production costs only for the goods that are actually sold to the buyers. 1. the seller posts a price vector p where pi is the price of good i I, and fixes an upper bound ki on the number of copies of each good i that he is willing to produce. 2. buyers arrive in some arbitrary order; each buyer looks at the set of available goods and purchases her utility maximizing bundle. 3. an item becomes unavailable once the number of copies purchased equals the upper bound. The upper bound can be thought of as the seller preparing his machinery for producing a certain number of goods, but stopping short of actually producing them. Commitment Mechanism In a commitment mechanism, the seller produces the goods before the buyers arrive and thus incurs an additional cost for any goods that are not sold. From an algorithmic perspective, these mechanisms are much harder than on the fly mechanisms. 1. the seller posts a single price per good and produces a fixed quantity of each good in advance. 2. buyers arrive in some arbitrary order, and each buyer purchases her utility maximizing bundle from the remaining items.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

3 On the fly mechanism for Xo S buyers

In this section, we present our main result: an OTF mechanism that obtains a 4-approximation to the optimum welfare. The mechanism comprises of two independent components: (i) a black-box reduction for transforming any algorithm for the allocation problem into a posted price mechanism that guarantees the half of the social welfare of the algorithm (ii) a 2-approximation algorithm for the allocation problem. We first state the black-box result formally.

Claim 3.1. Given a product distribution F, an algorithm Alg, demand and Xo S oracles, we can compute in poly-time a price vector p and supply upper bound k such that the OTF mechanism with these parameters provides a welfare guarantee (in expectation) of 1

2E v F[SW(Alg( v))].

Such black-box reductions (from pricing to the allocation problem) have recently gained traction in mechanism design [Bei and Huang, 2011; Dughmi et al., 2017; Feldman et al., 2015] as they allow us to reuse the extensive techniques developed for computing welfare maximizing allocations in order to derive prices that indirectly result in desirable allocations. However, the black-box techniques developed in [Bei and Huang, 2011; Dughmi et al., 2017] only yield Bayesian incentive compatible (BIC) mechanisms, whereas the above claim trivially indicates dominant strategy incentive compatibility. Claim 3.1 strictly generalizes the black-box result in [Feldman et al., 2015] for deriving welfare-maximizing prices for settings with unit supply and our proof is inspired by the approach developed in that paper. However, owing to the nonlinear nature of the production costs, the pricing scheme that we propose is more involved than the one used by [Feldman et al., 2015]. More specifically, when dealing with unit supply, one can achieve good social welfare by simply pricing each item at a fraction of its (expected) contribution towards the social welfare of some allocation. However, this approach does not yield desirable guarantees with production costs. Instead, we generalize the single-item pricing scheme from [Feldman et al., 2015] in a non-trivial direction by pricing each item at the average of its contribution towards the buyer welfare and its contribution towards the production cost, i.e., for every copy of the item produced, we create a dummy buyer whose valuation equals the marginal production cost and then price the item at its average contribution towards social welfare. We reiterate the important point that when the representation of F is not polynomial, using standard sampling techniques [Feldman et al., 2015], we can get a welfare guarantee of 1

2E v F[SW(Alg( v))] ϵ in poly-time. Before proving the theorem, we state the concomitant allocation algorithm .

Algorithm for Allocating Goods to Xo S buyers The secondary algorithmic contribution of this section is a 2-approximation algorithm for the following allocation problem: given a set I of goods with convex production costs and deterministic Xo S valuations, compute an allocation S = (S1, . . . , SN) that maximizes social welfare. Note that the allocation algorithm is only applicable for a single profile of buyer valuations, i.e., the deterministic setting. Our pricing

mechanism uses this algorithm as a black-box for different valuations drawn from F.

Claim 3.2. (Allocation Algorithm) For any given input with Xo S buyer valuations, Algorithm 1 returns an allocation of goods to buyers such that the resulting social welfare is at least one-half of that of the welfare maximizing allocation.

Algorithm 1 Allocation Algorithm for Xo S buyers

Input: Access to buyer valuations in the form of Demand, Xo S oracles Initialization Phase 1: S1, S2, . . . , SN // Initial Allocation 2: Define p s.t. pi = ci(1) i I // Internal Prices Allocation Phase: For each buyer j 1, 2, . . . , N

3: Let S j be the utility-maximizing bundle demanded by buyer j at prices p; set Sj = S j 4: Let (aj r) denote the maximizing Xo S clause for buyer j and set Sj. Set qj(i) = aj r(i) for all i Sj. 5: Update: For each item i Sj, let Xi be the set of buyers who have received a copy of i so far. 6: If pi corresponds to qj(i) for some j Xi, remove j from Xi and remove item i from j s allocation. 7: Update pi = min{ci(|Xi| + 1), minj Xi qj(i)}.

The functioning of Algorithm 1 can be interpreted as follows: the market consists of N + 1 buyers (buyer 0 is the seller) who arrive sequentially in some arbitrary order. Each new buyer can acquire their maximum utility bundle by purchasing each item from either the seller (at the current marginal production) or from previous buyers (at a price derived from the Xo S clause corresponding to that buyer). Note that while Algorithm 1 uses prices as an internal device, its final output is simply an allocation and does not involve any pricing. Our algorithm generalizes the 2-approximation algorithm for Xo S buyers and unit-supply first studied in [Dobzinski et al., 2010] to settings with production costs. The main implication of Claims 3.1 and 3.2 is a computationally efficient posted pricing mechanism whose welfare guarantee is one-fourth that of the optimum allocation.

Theorem 3.3. We can compute in poly-time a price vector p and supply vector k such that for any arrival order, the expected welfare of the posted price mechanism with these prices is at least one-fourth of the optimum social welfare.

All of the heavy-lifting for the above theorem is done by Claim 3.1, and it suffices to prove the claim. Proof of Claim 3.1 We now present a general framework for non-discriminatory pricing in the presence of convex production costs. The framework consists of two ingredients: first, we provide a technique to derive prices for each good separately. Second, we provide some sufficient conditions for obtaining pricing mechanisms with good welfare for arbitrary valuations.

Framework Part I: Profit-Surplus Equivalence We now restrict our attention to markets with a single good i and show how to derive prices that obtain good welfare.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Suppose we allocate k units of this good to buyers whose valuations for the good are v1 v2 . . . vk. The total welfare due to this particular allocation is Pk ℓ=1[vℓ ci(ℓ)]. We are not interested in negative welfare, so we assume that Pk ℓ=1 vℓ Pk ℓ=1 ci(ℓ). Define the following functions: (i) Buyer Surplus: fi(p) = Pk ℓ=1[vℓ p] (this denotes the total utility derived by the buyers at price p) and (ii) Seller Profit: πi(p) = pk Pk ℓ=1 ci(ℓ). The purpose of this section is to identify a convenient price where profit and surplus coincide (see Lemma 3.4); such a price is desirable for both the buyers and the seller. The choice of this price is justified in Lemma 3.5. Observe that both πi(p) and fi(p) are continuous and monotone in p with fi(0) πi(0) whereas fi(v1) πi(v1). So, there must exist some price p i [0, v1] satisfying the following condition.

(Profit-Surplus Equivalence)fi(p i ) = πi(p i ). (1)

Lemma 3.4. The total profit if all k items are sold at price p i is exactly half the social welfare due to i, i.e., πi(p i ) =

1 2 Pk ℓ=1[vℓ ci(ℓ)] .

The lemma follows from Equation 1 using simple algebra.

Framework Part 2: Sufficient Conditions We now identify sufficient conditions that lead to OTF mechanisms having good welfare guarantees for Xo S valuations. Specifically, suppose that we are given as input an allocation algorithm Alg. We propose three conditions that a price vector must satisfy so that the OTF mechanism with these prices provides an expected welfare that is comparable to that of the allocation returned by Alg in expectation over F Notation: Let Alg( v) = (A1( v), . . . , AN( v)) denote the allocation output by Alg for valuation profile v. Suppose that under this allocation, Ni( v) represents the set of buyers to whom good i is allocated, and ki( v) = |Ni( v)|. Fixing v, let oj be the Xo S clause corresponding to buyer j that maximizes oj(Aj( v)), i.e., oj(Aj( v)) = vj(Aj( v)). Then, we define the total value derived from good i, Vi( v) = P j Ni( v) oj(i), and also Vi = E v F[Vi( v)]. Similarly, we can also define the quantity representative of social welfare SWi( v) = P

j Ni( v) oj(i) Pki( v) ℓ=1 ci(ℓ), and its expected value SWi.

Lemma 3.5. Given an approximation algorithm Alg, suppose that there exists a price vector p and an upper bound supply vector k , satisfying the following conditions

1. for every good i, p i k i Ci(k i ) 0;

2. for every good i, Vi p i E v F[ki( v)] 1

3. for every good i, p i k i Ci(k i ) 1

Then, an on the fly mechanism with parameters ( p , k ) results in a welfare of E v F[SW (Alg( v))]

Proof. Fix some valuation profile v F, and a buyer j. Suppose that for this valuation, Soldj( v) is the set of goods that are sold out (supply limit reached) when buyer j arrives. Consider another valuation profile a j for buyers other than j, so that this valuation is independent of v. Define a = (vj, a j),

and define oj to be the Xo S clause that maximizes Aj( a), i.e., vj(Aj( a)) = oj(Aj( a)) = P i Aj( a) oj(i). Under the fixed valuation v and for each a j, buyer j could have purchased the set of goods in Aj( a) \ Soldj( v). Therefore, the utility of this buyer under the fixed valuation is at least E a j[P i I 1(j Ni( a)).1(i / Soldj( v)).oj(i) p i ]. Observe that Soldj( v) does not depend on a j whereas Ni( a) and oj(i) depend only on a. Therefore, summing up the above quantity for all buyers and taking the expectation over v, we get that the expected total surplus (buyer utility) is at least P i I PN j=1 E v[1(i / Soldj( v))]E a[1(j Ni( a)).oj(i) p i ]. Applying the definition of Vi, this quantity can be rewritten as P i I Pr(i is not sold out)E v[Vi( v) ki( v)p i ]. Finally, from Condition (2) of the lemma, we get our final lower bound on the aggregate buyer utility (surplus).

j=1 uj( v)] 1

i I Pr(i is not sold out)SWi.

Next, for any fixed valuation v, let S( v) and U( v) be the set of items that are sold out (all k i copies), and the ones that are not respectively. Suppose that for any v, ti( v) is the number of copies of good i sold by the mechanism. Then, the seller s profit (in expectation) is exactly E v F[P i S( v)(k i p i Ci(k i )) + P i U( v)(ti( v)p i Ci(ti( v)))]. Moreover, it is not hard to deduce that the term ti( v)p i Pti( v) ℓ=1 ci(ℓ) is non-negative for all i as per our choice of p i . Therefore, ignoring the profit due to the unsold items, we can apply the third condition in the lemma statement and get the following lower bound on the expected profit: 1 α P i I Pr(i is sold out)SWi. By definition, social welfare is simply the expected buyer surplus plus the expected seller profit. Adding up our two lower bounds, we can complete the proof of the lemma.

Final leg: Showing the Black-Box Result Armed with our framework from the previous sections, we are now ready to prove the black-box reduction in Claim 3.1. Specifically, we will compute prices based on the first part of the framework and then show that a mechanism with these prices satisfies the conditions of Lemma 3.5 for α = 2.

Pricing Scheme: For every good i, set (i) p i = Vi 2k i +

E v F[Ci(ki( v)]

2k i and (ii) k i = E v F[ki( v)].

Note that p i denotes the price that results in profit-surplus equivalence, taken in expectation over F. We assume without loss of generality that k i is integral for all i. It only remains to prove that these prices and supply constraints satisfy the conditions of Lemma 3.5 with α = 2.

1. Condition (1): p i k i Ci(k i ) 0: By definition, p i k i Ci(k i ) = Vi

2E v F[Ci(ki( v)] Ci(k i ). Since the cost functions are convex, we can apply Jensen s inequality and get that E v F[Ci(ki( v)] Ci(E v F[ki( v)]) = Ci(k i ). Therefore, we get that p i k i Ci(k i ) Vi

2 E v F[Ci(ki( v)]

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

2. Condition (2): Vi p i E v F[ki( v)] 1 αSWi: As per the definition of p i , we have that p i k i = 1 2(Vi + E v F[Ci(ki( v))]). Taking the negative of this equation and adding Vi to both sides gives us Vi p i k i = 1 2(Vi E v F[Ci(ki( v))]) = 1

3. Condition (3): p i k i Ci(k i ) 1

αSWi: This follows from the proof of Condition (1) for α = 2.

4 Commitment Mechanisms We move on to the much harder class of mechanisms, where the seller has to initially commit to producing a fixed amount of each good under uncertainty, and therefore, incurs a loss on every item that is not sold. Given an instance of our problem and an algorithm Alg, using the same notation as in the proof of Claim 3.1, the expected social welfare provided by the algorithm is E v F [SW(Alg( v))] = E v F [PN j=1 vj(Aj( v)) P i I Ci(ki( v))]. Then, the instance is said to be α-bounded with respect to Alg for α 1 if E v F [PN j=1 vj(Aj( v))] αE v F [P i I Ci(ki( v))]. Our main result in this section is a commitment mechanism that obtains a 4 α 1

α 2 approximation to the optimum welfare: for large enough values of α, we obtain a constant factor approximation and as α , the performance of the commitment mechanism approaches that of the OTF mechanism from Theorem 3.3. α-boundedness captures the recoverable welfare in terms of the initial investment. In previous work [Feige et al., 2013], α-boundedness was defined in terms of the optimum solution for a given instance; on the other hand, our definition depends both on the instance and the benchmark algorithm. Theorem 4.1. 1. Given an allocation algorithm Alg, for every instance with fractionally subadditive buyers that is α-bounded with respect to Alg for α [2, ], there exists a commitment mechanism that extracts a welfare of E v F[ SW (Alg( v))

2. For any given instance with fractionally subadditive buyers, we can compute posted prices in poly-time such that the resulting commitment mechanism always guarantees a social welfare within a factor 4 α 1

α 2 of the optimum allocation, as long as the instance is α-bounded with respect to the algorithm from Claim 3.2. Discussion: Essentially the parameter α allows us to distinguish between good and bad instances of our problem. The performance of our commitment mechanism improves as α increases. In many markets, it is reasonable to expect that the cost of producing the goods is not too large in comparison to the social value [Feige et al., 2013]. Alternatively, if the production cost function is sufficiently convex, then the solution returned by our algorithm from Claim 3.2 is always αbounded for a large enough value of α to ensure good welfare. For example, if ci(ℓ) = ℓ2 for all i I and Alg allocates at least 3-copies of every good, then the resulting allocation is α-bounded for α = 2.5 and our commitment mechanism provides a welfare guarantee of 1

6E v[SW(Alg( v))]. (Proof Sketch) The proof relies on the same framework as the OTF mechanism from Section 3, so we only sketch the

key differences. In the proof of Claim 3.1, we defined profit and surplus functions for every i I and selected a price p i so that the profit due to the sold items is exactly the surplus due to the unsold items, and the profit due to the unsold items is non-negative. However, this is no longer true for commitment mechanisms as the profit due to the unsold items may be negative due to the incurred production costs, thereby leading to poor welfare. To compensate for the negative profits when items are unsold, the main idea is to reduce prices so that the higher surplus offsets the increased production costs when the items are unsold. Using the same notation as in the proof of Claim 3.1, we define a reduced surplus function for each good i, hi(p) = Vi p E v F[ki( v)] E v[Ci(ki( v))] = fi(p) E v[Ci(ki( v))]. For every good i I, we select its price p i to be the point where hi(p) = πi(p), i.e., where reduced surplus and profit meet, and quantity to produce as k i = E v F[ki( v)]. Using the same sequence of ideas as in the proof of Claim 3.1, the theorem follows.

5 Conclusions and Future Directions

In this work, we considered the problem of maximizing social welfare in the presence of distributional information regarding buyer valuations. Our main contribution is a nondiscriminatory posted pricing mechanism that achieves onefourth of the optimum welfare even when the seller faces convex production costs on the goods. Convex costs are a natural generalization of fixed supply and capture the diseconomies of scale that occur when expensive resources are utilized to achieve higher levels of production, for example, when manufacturing plants have a standard capacity up to which they incur constant marginal costs but the marginal cost increases beyond this threshold due to overtime, new equipment, etc. [Hochbaum and Wagner, 2015]. Other applications of convex costs include the energy cost incurred by a data center as a function of utilization [Buchbinder et al., 2011]. A natural question that arises is whether our results can be extended to settings with concave production costs or economies of scale. As a first step in this direction, we can show good approximations for social welfare when the derivative of the concave function is not too volatile. All of our results assume that we can access the buyer valuation functions by means of oracle queries, which is a standard assumption in the literature. However, it is natural to envisage prior-free scenarios where the seller has absolutely no information about buyer valuations. Can we design posted pricing mechanisms in such an extreme case? In the full version of this paper (available on ar Xiv), we answer this question in the affirmative by presenting an OTF mechanism for markets with Xo S buyers and convex costs that achieves a O(log m log N)-approximation to the optimum social welfare. Previously, good approximations were only known for dynamic pricing mechanisms [Blum et al., 2011].

Acknowledgements

The author wishes to express his gratitude to Elliot Anshelevich and Brendan Lucier for providing useful feedback on an earlier version of this paper.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

[Anderson et al., 2010] Eric T Anderson, Duncan I Simester, et al. Price stickiness and customer antagonism. The Quarterly Journal of Economics, 125(2):729 765, 2010.

[Bartal et al., 2003] Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auctions. In Proceedings of TARK, pages 72 87, 2003.

[Bei and Huang, 2011] Xiaohui Bei and Zhiyi Huang. Bayesian incentive compatibility via fractional assignments. In Proceedings of SODA 2011, pages 720 733, 2011.

[Blum et al., 2011] Avrim Blum, Anupam Gupta, Yishay Mansour, and Ankit Sharma. Welfare and profit maximization with production costs. In Proceedings of FOCS 2011, pages 77 86, 2011.

[Blumrosen and Holenstein, 2008] Liad Blumrosen and Thomas Holenstein. Posted prices vs. negotiations: an asymptotic analysis. In Proceedings of ACM EC, page 49, 2008.

[Brˆanzei et al., 2014] Simina Brˆanzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, and Jie Zhang. The fisher market game: Equilibrium and welfare. In Proceedings of AAAI 2014, pages 587 593, 2014.

[Buchbinder et al., 2011] Niv Buchbinder, Navendu Jain, and Ishai Menache. Online job-migration for reducing the electricity bill in the cloud. In Proceedings of NETWORKING, pages 172 185, 2011.

[Chakraborty et al., 2009] Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna. Dynamic and non-uniform pricing strategies for revenue maximization. In Proceedings of FOCS 2009, pages 495 504, 2009.

[Chakraborty et al., 2010] Tanmoy Chakraborty, Eyal Even Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan. Approximation schemes for sequential posted pricing in multi-unit auctions. In Proceedings of WINE 2010, pages 158 169, 2010.

[Chawla et al., 2010] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multiparameter mechanism design and sequential posted pricing. In Proceedings of STOC 2010, pages 311 320, 2010.

[Cohen-Addad et al., 2016] Vincent Cohen-Addad, Alon Eden, Michal Feldman, and Amos Fiat. The invisible hand of dynamic market pricing. In Proceedings of ACM EC 2016, pages 383 400, 2016.

[Daskalakis and Pierrakos, 2011] Constantinos Daskalakis and George Pierrakos. Simple, optimal and efficient auctions. In Proceedings of WINE, pages 109 121, 2011.

[Dobzinski et al., 2010] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res., 35(1):1 13, 2010.

[Dughmi et al., 2017] Shaddin Dughmi, Jason D. Hartline, Robert D. Kleinberg, and Rad Niazadeh. Bernoulli factories and black-box reductions in mechanism design. In Proceedings of STOC, 2017. [Feige et al., 2013] Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, and Hamid Nazerzadeh. PASS approximation: A framework for analyzing and designing heuristics. Algorithmica, 66(2):450 478, 2013. [Feldman et al., 2015] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of SODA, pages 123 135, 2015. [Gul and Stacchetti, 1999] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1):95 124, 1999. [Hartline and Roughgarden, 2009] Jason D. Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of ACM EC 2009, pages 225 234, 2009. [Hochbaum and Wagner, 2015] Dorit S Hochbaum and Michael R Wagner. Production cost functions and demand uncertainty effects in price-only contracts. IIE Transactions, 47(2):190 202, 2015. [Hsu et al., 2016] Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra. Do prices coordinate markets? In Proceedings of STOC 2016, 2016. [Huang and Kim, 2015] Zhiyi Huang and Anthony Kim. Welfare maximization with production costs: a primal dual approach. In Proceedings of SODA 2015, pages 59 72, 2015. [Maehara et al., ] Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, and Ken-ichi Kawarabayashi. Optimal pricing for submodular valuations with bounded curvature. In Proceedings of AAAI 2017. [Roughgarden and Talgam-Cohen, 2015] Tim Roughgarden and Inbal Talgam-Cohen. Why prices need algorithms. In Proceedings of ACM EC 2015, pages 19 36, 2015.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)