Mechanism design is the subfield of economics that looks at economic systems from the point of view of an optimizing designer. This designer would like to build a system whereby agents' individual selfish optimization in equilibrium leads to global optimization of a desired objective. While it is preferable to be able to perform this optimization in the "worst case", that is, in the absence of any assumption on the input, this is often not possible. Bayesian priors on the agents' private information can circumvent such impossibility results.

Over the last few years a number of works have demonstrated the benefits of using Bayesian information to circumvent impossibilities in the worst case, as well as of applying computer science techniques such as approximation to classical problems in the economic theory of Bayesian mechanism design. These include, for example, approximately-optimal mechanisms for pricing and profit maximization in multi-parameter settings, black-box reductions from mechanism design to algorithm design, mechanism design for budget-constrained agents, simplicity versus optimality tradeoffs, and approximately optimal mechanisms for settings with unknown priors. Despite this progress, Bayesian mechanism design remains outside the mainstream of mechanism design research within the CS community.

The focus of the workshop will be on techniques for designing good mechanisms in Bayesian settings. Papers are expected to consider combinations of the following topics:

• Bayesian incentive compatible mechanism design
• Bayes-Nash mechanism design,
• Bayes-Nash price of anarchy,
• approximation mechanisms,
• simple versus optimal mechanisms,
• computational complexity, and
• prior-independence (where the Bayesian prior exists but is unknown to the designer).

The workshop will be held in conjunction with the ACM Conference on Electronic Commerce.

Dates

Part I: The first part of the tutorial is on the classical economic theory of Bayesian mechanism design. Mechanism design is a foundational theory of how to build systems to achieve a given designers objective even when participants in the system may strategize. One of the most fundamental mechanism design settings is in the allocation of a single resource, i.e., the single-item auction problem. The first topic we consider is social welfare maximization, i.e., allocating the resource to the agent who desires it the most. Here we compare and contrast the equilibrium outcomes of two auctions: the first-price auction and the second-price (a.k.a., Vickrey) auction. The second topic we consider is profit maximization. Here we examine the role that reserve prices play in increasing revenue in auctions. This topic culminates with a partial derivation of the optimal auction (a.k.a., the Myerson auction) and the observation that in natural settings this auction is a reserve-price based auction. Finally, we briefly describe how the theory extends to more general settings than single-item auctions. [slides]

Part II: The second part of the tutorial surveys four recent directions in approximately-optimal Bayesian mechanism design. Result 1: reserve prices are approximately optimal single-item auctions. Result 2: posted-pricings are approximately optimal multi-item mechanisms. Result 3: approximation of optimal auctions with a single-sample from the distribution. Result 4: reduction from BIC mechanism design to algorithm design. [slides]

For Bayesian combinatorial auctions, we present a general framework for reducing the mechanism design problem for many buyers to the mechanism design problem for one buyer. Our generic reduction works for any separable objective (e.g., welfare, revenue, etc) and any space of valuations (e.g. submodular, additive, etc) and any distribution of valuations as long as valuations of different buyers are distributed independently (not necessarily identically). Roughly speaking, we present two generic $n$-buyer mechanisms that use $1$-buyer mechanisms as black boxes. We show that if we have an $\alpha$-approximate $1$-buyer mechanism for each buyer\footnote{Note that we can use different $1$-buyer mechanisms for different buyers.} then our generic $n$-buyer mechanisms are $\frac{1}{2}\alpha$-approximation of the optimal $n$-buyer mechanism. Furthermore, if we have several copies of each item and no buyer ever needs more than $\frac{1}{k}$ of all copies of each item then our generic $n$-buyer mechanisms are $\gamma_k \alpha$-approximation of the optimal $n$-buyer mechanism where $\gamma_k \ge 1-\frac{1}{\sqrt{k+3}}$. Observe that $\gamma_k$ is at least $\frac{1}{2}$ and approaches $1$ as $k$ increases.

Applications of our main theorem include the following improvements on results from the literature. For each of the following models we construct a $1$-buyer mechanism and then apply our generic expansion: For revenue maximization in combinatorial auctions with hard budget constraints, \cite{BGGM10} presented a $\frac{1}{4}$-approximate BIC mechanism for additive/correlated valuations and an $O(1)$-approximate\footnote{$O(1)=\frac{1}{96}$} sequential posted pricing mechanism for additive/independent valuations. We improve this to a $\gamma_k$-approximate BIC mechanism and a $\gamma_k (1-\frac{1}{e})$-approximate sequential posted pricing mechanism respectively. For revenue maximization in combinatorial auctions with unit demand buyers, \cite{CHMS10} presented a $\frac{1}{6.75}$-approximate sequential posted pricing mechanism. We improve this to a $\frac{1}{2} \gamma_k$ approximate sequential posted pricing mechanism. We also present a $\gamma_k$-approximate sequential posted pricing mechanism for unit-demand multi-unit auctions(homogeneous) with hard-budget constraints. Furthermore, our sequential posted pricing mechanisms assume no control or prior information about the order in which buyers arrive.

We investigate the problem of optimal mechanism design, where an auctioneer wants to sell a set of goods to buyers, in order to maximize revenue. In a Bayesian setting buyers' valuations for the goods are drawn from a prior distribution D, which is often assumed to be known by the seller. We instead focus on cases where the seller has no knowledge at all, and `the buyers know each other better than the seller knows them'. In our model, D is not necessarily common knowledge. Instead, each player individually knows a posterior distribution associated with D. Since the seller relies on the buyers' knowledge to help him set a price, we call these types of auctions crowdsourced Bayesian auctions.

For this crowdsourced Bayesian model and many environments of interest we show that, for arbitrary type distributions D (in particular, correlated ones), it is possible to design mechanisms matching to a significant extent the performance of the optimal classical mechanisms where the seller knows D. Our results are ``existential" for a broad class of environments (including combinatorial auctions) and ``constructive" for auctions of a single good.

To obtain our results, we use two techniques: (1) Proper scoring rules to elicit information from the bidders; and (2) a quantitative version of the classical Bulow-Klemperer inequality. The first technique lets us build mechanisms that guarantee good revenue, even when player's second and higher-order beliefs about each other are wrong. The second allows us to upper bound the revenue of an optimal mechanism with n players by a (1 - 1/n) fraction of the revenue of the optimal mechanism with n-1 players. We believe that both techniques are new to Bayesian optimal auctions and of independent interest for future work.

We consider online posted-price mechanisms with limited supply. A seller has $k$ items for sale and is facing $n$ potential buyers ("agents") that are arriving sequentially. Each agent is interested in buying one item. Each agent's value for an item is an IID sample from some fixed distribution with support [0,1]. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue.

We focus on mechanisms that do not use any information about the distribution; such mechanisms are called detail-free. They are desirable because knowing the distribution is unrealistic in many practical scenarios. We study how the revenue of such mechanisms compares to the revenue of the optimal offline mechanism that knows the distribution ("offline benchmark").

We present a detail-free online posted-price mechanism whose revenue is within $O((k \log n)^{2/3})$, in additive terms, of the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without any assumptions if the benchmark is relaxed to fixed-price mechanisms.

The upper bound can be improved to $O(\sqrt{k} \log n)$ for $k<\frac{n}{2e}$ under a stronger, yet quite common, assumption on the distribution: monotone hazard rate. A strong intuition from prior work suggests that one should not hope for a sufficiently general upper bound that is better than $O(\sqrt{k})$.

We introduce, analyze, and evaluate the following mechanism for allocating a single indivisible good when the goal is welfare of the n agents amongst whom it is to be allocated: arbitrarily and publicly choose an agent h; elicit bids for the good; allocate the good to the highest bidder and charge him the second highest bid; pay each agent 1/n times the second highest bid amongst the other agents; pay agent h 2/n times the difference between the second and third highest bids. This mechanism is strongly budget-balanced and strategyproof for all agents besides h. h's optimal bid will deviate from truth, but in such a way that leads to negligible inefficiency in expectation.

We solve the optimal multi-dimensional mechanism design problem when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that the values of each bidder for the items are i.i.d., but allow different distributions for each bidder. In the second setting, we allow the values of each bidder for the items to be arbitrarily correlated, but assume that the bidders are i.i.d. For all eps > 0, we obtain an efficient additive eps-approximation, when the value distributions are bounded, or a multiplicative (1-eps)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition (this is a widely studied class of distributions in Economics.)

We consider the problem of converting an arbitrary approximation algorithm for a single-parameter social welfare problem into a computationally efficient incentive compatible mecha- nism. We ask for reductions that are black-box, meaning that they require only oracle access to the given algorithm and (in particular) do not require explicit knowledge of the problem constraints. We demonstrate that, while such transformations exist in Bayesian settings of partial information, any computationally efficient transformation that guarantees ex post incentive compatibility must sometimes incur a polynomially large loss in worst-case performance. This implies that there is no prior-free deterministic reduction from algorithms to Bayesian incentive compatible mechanisms without loss.

The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. (This does not fall inside the well-studied "singleparameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space -- based on the bids -- and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6-approximated even if the "reserve pricing" is required to be symmetric across bidders.

We consider a market for an indivisible good with m buyers, each of whom wishes to buy at most one item, and m sellers, each of whom has one item to sell. The traders privately know their values/costs, which are statistically dependent. Two mechanisms for trading are considered. The buyer's bid double auction collects bids and offers from traders and determines trade by selecting a market-clearing price. It fails to achieve all possible gains from trading because of the strategic bidding by traders. The designed mechanism is a revelation mechanism in which honest reporting of values/costs is incentive compatible and all gains from trading are achieved in equilibrium. This optimality, however, comes at the expense of plausibility: (i) the monetary transfers among the traders are defined in terms of the traders' beliefs about each other's value/cost; (ii) a trader may suffer a loss ex post; (iii) the mechanism may run a sub- sidy/deficit ex post, and (iv) the mechanism may be gamed by sellers. We compare here the virtues of the simple yet mildly inefficient buyer's bid double auction to the flawed yet perfectly efficient designed mechanism.

The conference is soliciting full papers on Bayesian mechanism design topics outlined above. Submitted papers will be evaluated on significance, originality, technical quality, and exposition. The workshop will not have an archival proceedings and will consider papers simultaneously submitted for publication elsewhere subject to their expected publication being after June 9th, 2011 (the last day of the Conference on Electronic Commerce). To receive full consideration papers should be submitted to bayesmech2011@gmail.com by Friday, April 15th. Notification of accepted papers will be on Friday, April 29th.

Organization

Organizers: Shuchi Chawla (UW-Madison) and Jason Hartline (Northwestern U)

Program Committee: Shuchi Chawla (UW-Madison), Costis Daskalakis (MIT), Anupam Gupta (CMU), Jason Hartline (Northwestern U.), Nicole Immorlica (Northwestern U.), Anna Karlin (Washington), Azarakhsh Malekian (Northwestern U.), Mallesh Pai (U. Penn.).