Bayesian-optimal pricing


Bayesian-optimal pricing is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids.

Single item and single buyer

In the simplest setting, the seller has a single item to sell, and there is a single potential buyer. The highest price that the buyer is willing to pay for the item is called the valuation of the buyer. The seller would like to set the price exactly at the buyer's valuation. Unfortunately, the seller does not know the buyer's valuation. In the Bayesian model, it is assumed that the buyer's valuation is a random variable drawn from a known probability distribution.
Suppose the cumulative distribution function of the buyer is, defined as the probability that the seller's valuation is less than. Then, if the price is set to, the expected value of the seller's revenue is:
because the probability that the buyer will want to buy the item is, and if this happens, the seller's revenue will be.
The seller would like to find the price that maximizes. The first-order condition, that the optimal price should satisfy, is:
where the probability density function.
For example, if the probability distribution of the buyer's valuation is uniform in, then and . The first-order condition is which implies. This is the optimal price only if it is in the range .
Otherwise, the optimal price is.
This optimal price has an alternative interpretation: it is the solution to the equation:
where is the virtual valuation of the agent. So in this case, BO pricing is equivalent to the Bayesian-optimal mechanism, which is an auction with reserve-price.

Single item and many buyers

In this setting, the seller has a single item to sell, and there are multiple potential buyers whose valuations are a random vector drawn from some known probability distribution. Here, different pricing methods come to mind:
In the multiple-buyer setting, BO pricing is no longer equivalent to BO auction: in pricing, the seller has to determine the price/s in advance, while in auction, the seller can determine the price based on the agents' bids. The competition between the buyers may enable the auctioneer to raise the price. Hence, in theory, the seller can obtain a higher revenue in an auction.
Example. There are two buyers whose valuations are distributed uniformly in the range.
In practice, however, an auction is more complicated for the buyers since it requires them to declare their valuation in advance. The complexity of the auction process might deter buyers and ultimately lead to loss of revenue. Therefore, it is interesting to compare the optimal pricing revenue to the optimal auction revenue, to see how much revenue the seller loses by using the simpler mechanism.

Buyers with independent and identical valuations

Blumrosen and Holenstein study the special case in which the buyers' valuations are random variables drawn independently from the same probability distribution. They show that, when the distribution of the buyers' valuations has bounded support, BO-pricing and BO-auction converge to the same revenue. The convergence rate is asymptotically the same when discriminatory prices are allowed, and slower by a logarithmic factor when symmetric prices must be used. For example, when the distribution is uniform in and there are potential buyers:
In contrast, when the distribution of the buyers' valuations has unbounded support, the BO-pricing and the BO-auction might not converge to the same revenue. E.g., when the cdf is :
and Hartline and Malec and Sivan study the setting in which the buyers' valuations are random variables drawn independently from different probability distributions. Moreover, there are constraints on the set of agents that can be served together. They consider two kinds of discriminatory pricing schemes:
Their general scheme for calculating the prices is:
If then the marginal-probability that an agent is served by the SPM is equal to the marginal-probability that it is served by the BO auction.

The approximation factors obtainable by an OPM depend on the structure of the constraints:
Moreover, they show two lower bounds:
  • An OPM cannot guarantee more than 1/2 the revenue of the BO auction, even in the single-item setting.
  • An OPM cannot guarantee more than the revenue of the BO auction when there are downwards-closed non-matroid constraint.


The approximation factors obtainable by an SPM are naturally better:
  • Uniform matroid, partition matroid - e/ ≅ 1.58
  • General matroid - 2
  • Intersection of two matroids - 3
The lower bound is approximately 1.25.
Yan explains the success of the sequential-pricing approach based on the concept of correlation gap, in the following way. The revenue of a mechanism is related to a set function. E.g, in a k-unit auction, the function is
  • The revenue of the BO auction is at most, where "Winners" is the set of k agents with highest valuations.
  • The revenue of the BO SPM is at least, where "Demand" is the set of agents whose valuation is [|above] the price.
Both "Winners" and "Demand" are random-sets, determined by the agents' valuations. Moreover, by carefully setting the price, it is possible to ensure that each agent has the same probability to be in "Winners" and to be in "Demand". However, in "Winners", there is high correlation between different agents, while in "Demand", the agents are independent. Therefore, the correlation gap is an upper bound on the loss of performance when using BO SPM instead of BO auction. This gives the following approximation factors:
  • General matroid -
  • k-unit auctions -
  • p-independent set systems -.

Different items and one unit-demand buyer

In this setting, the seller has several different items for sale. There is one potential buyer, that is interested in a single item. The buyer has a different valuation for each item-type. Given the posted prices, the buyer buys the item that gives him the highest net utility.
The buyer's valuation-vector is a random-vector from a multi-dimensional probability distribution. The seller wants to compute the price-vector that gives him the highest expected revenue.
Chawla and Hartline and Kleinberg study the case in which the buyer's valuations to the different items are independent random variables. They show that:
They also consider the computational task of calculating the optimal price. The main challenge is to calculate, the inverse of the virtual valuation function.
In this setting, there are different types of items. Each buyer has different valuations for different items, and each buyer wants at most one item. Moreover, there are pre-specified constraints on the set of buyer-item pairs that can be allocated together.
Chawla and Hartline and Malec and Sivan study two kinds of discriminatory pricing schemes:
A sequential-pricing mechanism is, in general, not a truthful mechanism, since an agent may decide to decline a good offer in hopes of getting a better offer later. It is truthful only when, for every buyer, the buyer-item pairs for that buyer are ordered in decreasing order of net-utility. Then, it is always best for the buyer to accept the first offer. A special case of that situation is the single-parameter setting: for every buyer, there is only a single buyer-item pair.
To every multi-parameter setting corresponds a single-parameter setting in which each buyer-item pair is considered an independent agent. In the single-parameter setting, there is more competition. Therefore, the BO revenue in the single-parameter setting is an upper bound on the BO revenue in the multi-parameter setting. Therefore, if an OPM is an r-approximation to the optimal mechanism for a single-parameter setting, then it is also an r-approximation to the corresponding multi-parameter setting. See above for approximation factors of OPMs in various settings.
See Chapter 7 "Multi-dimensional Approximation" in for more details.

Many unit-demand buyers and sellers

Recently, the SPM scheme has been extended to a double auction setting, where there are both buyers and sellers. The extended mechanism is called 2SPM. It is parametrized by an order on the buyers, an order on the sellers, and a matrix of prices - a price for each buyer-seller pair. The prices are offered to in order to buyers and sellers who may either accept or reject the offer. The approximation ratio is between 3 and 16, depending on the setting.