---
title: "Posted Pricing sans Discrimination"
authors:
  - "Shreyas Sekar"
doi: "10.24963/ijcai.2017/55"
url: "https://ijcai.org/proceedings/2017/55"
pdf: "https://ijcai.org/proceedings/2017/0055.pdf"
venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"
year: 2017
pages: "388-394"
track: "Main track"
keywords:
  - "Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems"
  - "Agent-based and Multi-agent Systems: Noncooperative Games"
---

# Posted Pricing sans Discrimination

Shreyas Sekar

*Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 388-394. DOI: [10.24963/ijcai.2017/55](https://doi.org/10.24963/ijcai.2017/55)

## Abstract

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" when multiple copies of a good are available. For the more general case with non-linear production costs on each good, hardly anything is known for general multi-good markets. With this in mind, we study the problem of social welfare maximization in a Bayesian setting where the seller can produce any number of copies of a good but faces convex production costs for the same.      Our central contribution is a structured framework for decision making and static item pricing in the face of uncertainty and production costs, i.e., the seller decides how much to produce and posts a single price per good that is common to all buyers, the buyers arrive sequentially and purchase utility maximizing bundles of goods. The framework yields constant factor approximations to the optimum welfare when buyer valuations are fractionally subadditive, extends to more general valuations and also settings where the seller is completely oblivious to buyer valuations. Our work presents the first known results for non-discriminatory pricing in environments with non-linear costs where we only have access to stochastic information regarding buyer preferences. At a high level, our results imply that it is often possible to obtain good guarantees without discriminating against buyers, i.e., charging them differently for the same good.

## Full text

## 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 (XoS) 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 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 XoS 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 2 E⃗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 XoS oracle for the buyer valuations. To supplement the reduction, we also present a poly-time 2-approximation algorithm (Alg) for the allocation problem with XoS 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 XoS 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 algorithmAlg, 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 XoS buyers (α > 2). If the cost functions are 'sufficiently convex', then α is large irrespective of the buyer valuations, and our mechanism provides good bounds.

1 It 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.

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 RelatedWork

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 XoS, 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 (XoS), (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(ℓ) = ∑ℓ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) = ∑Nj=1 vj(Sj) - ∑i∈I Ci(ki). For the rest of this work, we will assume that all buyers have monotone nondecreasing XoS valuations, which strictly generalize many well-studied functions such as unit-demand, budget additive, and submodular valuations [Dobzinski et al., 2010].

Fractionally Subadditive (or 'XoS') Valuations ∃ a set of additive functions (a1, . . . , ar) such that for any T ⊆ I, v(T) = maxrj=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) = ∑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) - ∑i∈S pi, and (ii) an XoS oracle that for an XoS 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.

## 3 On the fly mechanism for XoS 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 XoS 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 12 E⃗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 2 E⃗v∼F[SW(Alg(⃗v))] - ϵ in poly-time. Before proving the theorem, we state the concomitant 'allocation algorithm'.

## Algorithm for Allocating Goods to XoS 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 XoS 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 XoS 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 XoS buyers

Input: Access to buyer valuations in the form of Demand, XoS 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 (ajr ) denote the maximizing XoS clause for buyer j and set Sj. Set qj(i) = ajr (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 fromXi 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 XoS 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 XoS 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.

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 ∑kℓ=1 [vℓ - ci(ℓ)]. We are not interested in negative welfare, so we assume that ∑kℓ=1 vℓ ≥ ∑kℓ=1 ci(ℓ). Define the following functions: (i) Buyer Surplus: fi(p) = ∑kℓ=1 [vℓ -p] (this denotes the total utility derived by the buyers at price p) and (ii) Seller Profit: πi(p) = pk - ∑kℓ=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.

<!-- formula-not-decoded -->

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 ) = 12 (∑kℓ=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 XoS 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 XoS 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) = ∑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) = ∑j∈Ni(⃗v) oj(i) - ∑ki(⃗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α SWi;
3. for every good i, p∗i k∗ i -Ci(k∗ i ) ≥ 1α SWi.

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 XoS clause that maximizes Aj(⃗a), i.e., vj (Aj (⃗a)) = oj (Aj (⃗a)) = ∑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 [∑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 ∑i∈I ∑Nj=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 ∑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).

<!-- formula-not-decoded -->

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[∑i∈S(⃗v) (k∗ i p∗i - Ci(k∗ i )) + ∑i∈U(⃗v) (ti(⃗v)p∗i -Ci(ti(⃗v)))].

Moreover, it is not hard to deduce that the term ti(⃗v)p∗i - ∑ti(⃗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α ∑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 2 + 1 2 E⃗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)] 2 = 12 SWi ≥ 0.

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 = 12 (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))]) = 12 SWi.
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 [∑Nj=1 vj (Aj (⃗v))- ∑i∈I Ci(ki(⃗v))]. Then, the instance is said to be α-bounded with respect to Alg for α ≥ 1 if E⃗v∼F [∑Nj=1 vj(Aj(⃗v))] ≥ αE⃗v∼F [∑i∈I Ci(ki(⃗v))].

Our main result in this section is a commitment mechanism that obtains a 4 α-1 α-2 approximation to the optimumwelfare: 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 ] α-2 α-1 .
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 6 E⃗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 - pE⃗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 arXiv), we answer this question in the affirmative by presenting an OTF mechanism for markets with XoS buyers and convex costs that achieves a O(logmlogN)-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.

## References

1. [Anderson et al., 2010] Eric T Anderson, Duncan I Simester, et al. Price stickiness and customer antagonism. The Quar- terly Journal of Economics, 125(2):729-765, 2010.
2. [Bartal et al., 2003] Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auc- tions. In Proceedings of TARK, pages 72-87, 2003.
3. [Bei and Huang, 2011] Xiaohui Bei and Zhiyi Huang. Bayesian incentive compatibility via fractional assign- ments. In Proceedings of SODA 2011, pages 720-733, 2011.
4. [Blum et al., 2011] Avrim Blum, Anupam Gupta, Yishay Mansour, and Ankit Sharma. Welfare and profit maximiza- tion with production costs. In Proceedings of FOCS 2011, pages 77-86, 2011.
5. [Blumrosen and Holenstein, 2008] Liad Blumrosen and Thomas Holenstein. Posted prices vs. negotiations: an asymptotic analysis. In Proceedings of ACM EC, page 49, 2008.
6. [Brânzei et al., 2014] Simina Brânzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederik- sen, and Jie Zhang. The fisher market game: Equilibrium and welfare. In Proceedings of AAAI 2014, pages 587- 593, 2014.
7. [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 NETWORK- ING, pages 172-185, 2011.
8. [Chakraborty et al., 2009] Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna. Dynamic and non-uniform pricing strategies for revenue maximization. In Proceed- ings of FOCS 2009, pages 495-504, 2009.
9. [Chakraborty et al., 2010] Tanmoy Chakraborty, Eyal Even- Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrish- nan. Approximation schemes for sequential posted pric- ing in multi-unit auctions. In Proceedings of WINE 2010, pages 158-169, 2010.
10. [Chawla et al., 2010] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pric- ing. In Proceedings of STOC 2010, pages 311-320, 2010.
11. [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.
12. [Daskalakis and Pierrakos, 2011] Constantinos Daskalakis and George Pierrakos. Simple, optimal and efficient auctions. In Proceedings of WINE, pages 109-121, 2011.
13. [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.
14. [Dughmi et al., 2017] Shaddin Dughmi, Jason D. Hartline, Robert D. Kleinberg, and Rad Niazadeh. Bernoulli fac- tories and black-box reductions in mechanism design. In Proceedings of STOC, 2017.
15. [Feige et al., 2013] Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, and Hamid Nazerzadeh. PASS approximation: A framework for analyzing and designing heuristics. Al- gorithmica, 66(2):450-478, 2013.
16. [Feldman et al., 2015] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of SODA, pages 123-135, 2015.
17. [Gul and Stacchetti, 1999] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1):95-124, 1999.
18. [Hartline and Roughgarden, 2009] Jason D. Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of ACM EC 2009, pages 225-234, 2009.
19. [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.
20. [Hsu et al., 2016] Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra. Do prices co- ordinate markets? In Proceedings of STOC 2016, 2016.
21. [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.
22. 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.
23. [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.