Bayesian-optimal pricing
Bayesian-optimal pricing
- Bayesian-optimal pricing** (BO 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 (with zero cost), 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 <math>F(v)</math>, defined as the probability that the seller's valuation is less than <math>v</math>. Then, if the price is set to <math>p</math>, the expected value of the seller's revenue is: :<math>Rev(p) = p\cdot (1-F(p))</math> because the probability that the buyer will want to buy the item is <math>1-F(p)</math>, and if this happens, the seller's revenue will be <math>p</math>.
The seller would like to find the price that maximizes <math>Rev(p)</math>. The first-order condition, that the optimal price <math>p^</math> should satisfy, is: :<math>p^ = {1-F(p^)\over f(p^)}</math> where <math>f(p)=F'(p)=</math> the probability density function.
For example, if the probability distribution of the buyer's valuation is uniform in <math>[a,a+d]</math>, then <math>F(v)=(v-a)/d</math> and <math>f(v)=1/d</math> (in <math>[a,a+d]</math>). The first-order condition is <math>p^ = (a+d-p^)</math> which implies <math>p^ = (a+d)/2</math>. This is the optimal price only if it is in the range <math>[a,a+d]</math> (i.e., when <math>a\leq d</math>). Otherwise (when <math>a\geq d</math>), the optimal price is <math>p^ = a</math>.
This optimal price has an alternative interpretation: it is the solution to the equation: :<math>w(p^)=0</math> where <math>w</math> 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 <math>p^</math>.
Single item and many buyers In this setting, the seller has a single item to sell (with zero cost), 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: 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 [0,1] and there are <math>n</math> potential buyers: * the revenue of the BO auction (a [[vickrey-auction]] with reserve price determined by the probability distribution) is <math>1-2/n</math>; * the revenue of BO discriminatory pricing is <math>1-4/n</math>; * the revenue of BO symmetric pricing is <math>1-\log(n)/n</math>.
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 <math>F(x) = 1-1/x^2</math>: the revenue of the BO auction is <math>.88\sqrt{n}</math>; the revenue of BO discriminatory pricing is <math>.7\sqrt{n}</math>; * the revenue of BO symmetric pricing is <math>.64\sqrt{n}</math>.
Buyers with independent and different valuations Chawla 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 (for example: there is a limited number of units). They consider two kinds of discriminatory pricing schemes: In an order-oblivious pricing mechanism* (OPM), the mechanism-designer determines a price for each agent. The agents come in an arbitrary order. The mechanism guarantees are for worst-case (adversarial) order of the agents, determined after the agents' valuations are drawn. In a sequential pricing mechanism* (SPM), the mechanism-designer determines both a price for each agent, and an ordering on the agents. The mechanism loops over the agents in the pre-determined order. If the current agent can be served together with the previously-served agents (according to the constraints), then his personal price is offered to him, and he can either take it or leave it.
Their general scheme for calculating the prices is: For each agent <math>j</math>, calculate the probability <math>q_j</math> with which the BO mechanism (Myerson's mechanism) serves agent <math>j</math>. This can be calculated either analytically or by simulations. The price for agent <math>j</math> is <math>p_j := F_j^{-1}(1-C\cdot q_j)</math>, where <math>C</math> is a constant (either 1 or 1/2 or 1/3, depending on the setting). In other words, the price <math>p_j</math> satisfies the following condition: ::Prob[the valuation of agent <math>j</math> is at least <math>p_j</math>] = <math>C \times</math> Prob[the BO mechanism serves agent <math>j</math>]. If <math>C=1</math> 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.
<div id='OPM'> The approximation factors obtainable by an OPM depend on the structure of the constraints: 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 <math>f</math>. E.g, in a k-unit auction, the function is <math>f(S)=\min(|S|,k)</math> The revenue of the BO auction is at most <math>f(winners)\cdot Price</math>, where "Winners" is the set of k agents with highest valuations. The revenue of the BO SPM is at least <math>f(Demand)\cdot Price</math>, 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 <math>j</math> has the same probability <math>q_j</math> to be in "Winners" and to be in "Demand". However, in "Winners", there is high correlation between different agents (if one agent wins, there is more probability that other agents lose), 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 - <math>e/(e-1)</math> k-unit auctions (a sub-case of general matroids) - <math>1/(1-1/\sqrt{2\pi k})</math> * p-independent set systems (a generalization of the intersection of <math>p</math> matroids) - <math>p+1</math>. </div>
Different items and one unit-demand buyer In this setting, the seller has several different items for sale (e.g. cars of different models). There is one potential buyer, that is interested in a single item (e.g. a single car). The buyer has a different valuation for each item-type (i.e., he has a valuation-vector). Given the posted prices, the buyer buys the item that gives him the highest net utility (valuation minus price).
The buyer's valuation-vector is a random-vector from a multi-dimensional probability distribution. The seller wants to compute the price-vector (a price per item) 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: The revenue of the BO unit-demand pricing when there are <math>n</math> item-types is at most the revenue of the BO single-item auction when there are <math>n</math> potential buyers. When the buyer's valuations to the different items are independent draws from the same distribution, the BO unit-demand pricing that uses the same price to all items attains at least 1/2.17 of the revenue of the BO single-item auction. When the buyer's valuations are independent draws from different distributions, the BO unit-demand pricing that uses the same virtual-price (based on [[virtual-valuation]]s) attains at least 1/3 of the revenue of the BO single-item auction. They also consider the computational task of calculating the optimal price. The main challenge is to calculate <math>w^{-1}</math>, the inverse of the virtual valuation function. For discrete and regular valuation distribution, there is a polynomial-time 3-approximation. For continuous and regular* valuation distribution (available via an oracle) there is a polynomial-time (3+ε)-approximation with high probability, and a faster (6+ε)-approximation with probability 1.
Different items and many unit-demand buyers 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 (for example: each item can be allocated to at most one buyer; each buyer can get at most one item; etc).
Chawla and Hartline and Malec and Sivan for more details.