A Bayesian-optimal mechanism (BOM) is a
mechanism
Mechanism may refer to:
*Mechanism (engineering), rigid bodies connected by joints in order to accomplish a desired force and/or motion transmission
*Mechanism (biology), explaining how a feature is created
*Mechanism (philosophy), a theory that a ...
in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
s and knows the
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
of these variables.
A typical application is a seller who wants to sell some items to potential buyers. The seller wants to price the items in a way that will maximize their profit. The optimal prices depend on the amount that each buyer is willing to pay for each item. The seller does not know these amounts, but assumes that they are drawn from a certain known
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
. The phrase "Bayesian optimal mechanism design" has the following meaning:
* Bayesian means that we know the probability distribution from which the agents' valuations are drawn (in contrast to
prior-free mechanism design
A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution.
A typical application is a seller who wa ...
, which do not assume any prior probability distribution).
* Optimal means that we want to maximize the expected revenue of the auctioneer, where the expectation is over the randomness in the agents' valuations.
* Mechanism means that we want to design rules that define a
truthful mechanism In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
, in which each agent has an incentive to report their true value.
Example
There is one item for sale. There are two potential buyers. The valuation of each buyer is drawn
i.i.d.
In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is usual ...
from the uniform distribution on
,1
The
Vickrey auction
A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest ...
is a truthful mechanism and its expected profit, in this case, is 1/3 (the
first-price sealed-bid auction
A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids so that no bidder knows the bid of any other participant. The highest bi ...
is a non-truthful mechanism and
its expected profit is the same).
This auction is not optimal. It is possible to get a better profit by setting a
reservation price
In economics, a reservation (or reserve) price is a limit on the price of a good or a service. On the demand side, it is the highest price that a buyer is willing to pay; on the supply side, it is the lowest price a seller is willing to accept ...
. The Vickrey auction with a reservation price of 1/2 achieves an expected profit of 5/12, which in this case is optimal.
Notation
We assume that the agents have
single-parameter utility In mechanism design, an agent is said to have single-parameter utility if his valuation of the possible outcomes can be represented by a single number. For example, in an auction for a single item, the utilities of all agents are single-parametric, ...
functions, such as a single-item auction. Each agent
has a value
which represents the agent's "winning value" (e.g, the agent's valuation of the item). We do not know these values, but we do know that each
is drawn i.i.d. from a certain probability distribution. We denote by
the
cumulative distribution function
In probability theory and statistics, the cumulative distribution function (CDF) of a real-valued random variable X, or just distribution function of X, evaluated at x, is the probability that X will take a value less than or equal to x.
Ev ...
:
: