Search

We study the optimal design of a queueing system when agents' arrival and servicing are governed by a general Markov process. The designer of the system chooses entry and exit rules for agents, their service priority---or queueing discipline---as well as their information, while ensuring that agents have incentives to follow the designer's recommendations not only to join the queue but more importantly to stay in the queue. Under a mild condition, the optimal mechanism has a cutoff structure---agents are induced to enter up to a certain queue length and no agents are to exit the queue once they enter the queue; the agents on the queue are served according to a first-come-first-served (FCFS) rule; and they are given no information throughout the process beyond the recommendations they receive from the designer. FCFS is also necessary for optimality in a rich domain. We identify a novel role for queueing disciplines in regulating agents' beliefs, and their dynamic incentives, thus uncovering a hitherto unrecognized virtue of FCFS in this regard.

When selling information products, sometimes the seller can provide some free partial information to change people's valuations so that the overall revenue can possibly be increased. In this work, we study the general problem of advertising information products by revealing partial information. We consider buyers who are decision-makers. The outcomes of the decision problems depend on the state of the world that is unknown to the buyers. The buyers can make their own observations and thus can hold different personal beliefs about the state of the world. There is an information seller who has access to the state of the world. The seller can promote the information by revealing some partial information. We assume that the seller chooses a long-term advertising strategy and then commits to it. The buyers decide whether to purchase the full information product after seeing the partial information. The seller's goal is to maximize the expected revenue. We study the problem in two settings. (1) The seller targets buyers of a certain type. In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a simple function. The function is a product of two quantities. The first one is what we call the likelihood ratio, which depends on the buyer's personal belief about the state of the world. The second one is the cost of uncertainty, which represents the value of the information to the buyer. Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem, we prove that it is NP-hard to find the optimal mechanism. (2) For the general problem when the seller faces buyers of different types and only knows the distribution of their types, we provide an approximation algorithm when it is not too hard to predict the possible type of buyers who will make the purchase. For the general problem, we prove that it is NP-hard to find a constant-factor approximation.

We study the sample complexity of learning revenue-optimal multi-item auctions. We obtain the first set of positive results that go beyond the standard but unrealistic setting of item-independence. In particular, we consider settings where bidders' valuations are drawn from correlated distributions that can be captured by Markov Random Fields or Bayesian Networks -- two of the most prominent graphical models. We establish parametrized sample complexity bounds for learning an up-to-$\varepsilon$ optimal mechanism in both models, which scale polynomially in the size of the model, i.e.~the number of items and bidders, and only exponential in the natural complexity measure of the model, namely either the largest in-degree (for Bayesian Networks) or the size of the largest hyper-edge (for Markov Random Fields). We obtain our learnability results through a novel and modular framework that involves first proving a robustness theorem. We show that, given only ``approximate distributions'' for bidder valuations, we can learn a mechanism whose revenue is nearly optimal simultaneously for all ``true distributions'' that are close to the ones we were given in Prokhorov distance. Thus, to learn a good mechanism, it suffices to learn approximate distributions. When item values are independent, learning in Prokhorov distance is immediate, hence our framework directly implies the main result of Gonczarowski and Weinberg. When item values are sampled from more general graphical models, we combine our robustness theorem with novel sample complexity results for learning Markov Random Fields or Bayesian Networks in Prokhorov distance, which may be of independent interest. Finally, in the single-item case, our robustness result can be strengthened to hold under an even weaker distribution distance, the L\'evy distance.

This paper considers prior-independent mechanism design, namely identifying a single mechanism that has near optimal performance on every prior distribution. We show that mechanisms with truthtelling equilibria, a.k.a., revelation mechanisms, do not always give optimal prior-independent mechanisms and we define the revelation gap to quantify the non-optimality of revelation mechanisms. This study suggests that it is important to develop a theory for the design of non-revelation mechanisms. Our analysis focuses on welfare maximization in single-item auctions for agents with budgets and a natural regularity assumption on their distribution of values. The all-pay auction (a non-revelation mechanism) is the Bayesian optimal mechanism; as it is prior-independent it is also the prior-independent optimal mechanism (a 1-approximation). We prove a lower bound on the prior-independent approximation of revelation mechanisms of 1.013 and that the clinching auction (a revelation mechanism) is a prior-independent $e \approx 2.714$ approximation. Thus the revelation gap for single-item welfare maximization with public budget agents is in $[1.013, e]$. Some of our analyses extend to the revenue objective, position environments, and irregular distributions.

The problem of designing a profit-maximizing, Bayesian incentive compatible and individually rational mechanism with flexible consumers and costly heterogeneous supply is considered. In our setup, each consumer is associated with a flexibility set that describes the subset of goods the consumer is equally interested in. Each consumer wants to consume one good from its flexibility set. The flexibility set of a consumer and the utility it gets from consuming a good from its flexibility set are its private information. We adopt the flexibility model of [1] and focus on the case of nested flexibility sets -- each consumer's flexibility set can be one of k nested sets. Examples of settings with this inherent nested structure are provided. On the supply side, we assume that the seller has an initial stock of free supply but it can purchase more goods for each of the nested sets at fixed exogenous prices. We characterize the allocation and purchase rules for a profit-maximizing, Bayesian incentive compatible and individually rational mechanism as the solution to an integer program. The optimal payment function is pinned down by the optimal allocation rule in the form of an integral equation. We show that the nestedness of flexibility sets can be exploited to obtain a simple description of the optimal allocations, purchases and payments in terms of thresholds that can be computed through a straightforward iterative procedure., Comment: 8 pages. arXiv admin note: text overlap with arXiv:1607.02526

We consider the design of a revenue-optimal mechanism when two items are available to be sold to a single buyer whose valuation is uniformly distributed over an arbitrary rectangle $[c_1,c_1+b_1]\times[c_2,c_2+b_2]$ in the positive quadrant. We provide an explicit, complete solution for arbitrary nonnegative values of $(c_1,c_2,b_1,b_2)$. We identify eight simple structures, each with at most $4$ (possibly stochastic) menu items, and prove that the optimal mechanism has one of these eight structures. We also characterize the optimal mechanism as a function of $(c_1,c_2,b_1,b_2)$. The structures indicate that the optimal mechanism involves (a) an interplay of individual sale and a bundle sale when $c_1$ and $c_2$ are low, (b) a bundle sale when $c_1$ and $c_2$ are high, and (c) an individual sale when one of them is high and the other is low. To the best of our knowledge, our results are the first to show the existence of optimal mechanisms with no exclusion region. We further conjecture, based on promising preliminary results, that our methodology can be extended to a wider class of distributions., Comment: A preliminary version of the manuscript was published in Proceedings of the 12th Conference on Web and Internet Economics (WINE), 2016, Montreal, Canada

A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to $n$ bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a {\em prior-independent} mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first {\em full Bulow-Klemperer} results in {\em multi-dimensional} environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environment's {\em competition complexity}. Using the recent duality-based framework of Cai et al. [2016] for reasoning about optimal revenue, we show that the competition complexity of $n$ bidders with additive valuations over $m$ independent, regular items is at most $n+2m-2$ and at least $\log(m)$. We extend our results to bidders with additive valuations subject to downward-closed constraints, showing that these significantly more general valuations increase the competition complexity by at most an additive $m-1$ factor. We further improve this bound for the special case of matroid constraints, and provide additional extensions as well.

Binary hypothesis testing under the Neyman-Pearson formalism is a statistical inference framework for distinguishing data generated by two different source distributions. Privacy restrictions may require the curator of the data or the data respondents themselves to share data with the test only after applying a randomizing privacy mechanism. Using mutual information as the privacy metric and the relative entropy between the two distributions of the output (postrandomization) source classes as the utility metric (motivated by the Chernoff-Stein Lemma), this work focuses on finding an optimal mechanism that maximizes the chosen utility function while ensuring that the mutual information based leakage for both source distributions is bounded. Focusing on the high privacy regime, an Euclidean information-theoretic (E-IT) approximation to the tradeoff problem is presented. It is shown that the solution to the E-IT approximation is independent of the alphabet size and clarifies that a mutual information based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihood., Comment: 8 pages, 5 figures, conference

We study mechanisms for differential privacy on finite datasets. By deriving \emph{sufficient sets} for differential privacy we obtain necessary and sufficient conditions for differential privacy, a tight lower bound on the maximal expected error of a discrete mechanism and a characterisation of the optimal mechanism which minimises the maximal expected error within the class of mechanisms considered.

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately , each at its optimal price, and bundling together , in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

Optimal mechanism design enjoys a beautiful and well-developed theory, and also a number of killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search engines auction off online advertising. There are, however, some basic problems for which the traditional optimal mechanism design approach is ill-suited --- either because it makes overly strong assumptions, or because it advocates overly complex designs. The thesis of this paper is that approximately optimal mechanisms allow us to reason about fundamental questions that seem out of reach of the traditional theory. This survey has three main parts. The first part describes the approximately optimal mechanism design paradigm --- how it works, and what we aim to learn by applying it. The second and third parts of the survey cover two case studies, where we instantiate the general design paradigm to investigate two basic questions. In the first example, we consider revenue maximization in a single-item auction with heterogeneous bidders. Our goal is to understand if complexity --- in the sense of detailed distributional knowledge --- is an essential feature of good auctions for this problem, or alternatively if there are simpler auctions that are near-optimal. The second example considers welfare maximization with multiple items. Our goal here is similar in spirit: when is complexity --- in the form of high-dimensional bid spaces --- an essential feature of every auction that guarantees reasonable welfare? Are there interesting cases where low-dimensional bid spaces suffice?, Comment: Based on a talk given by the author at the 15th ACM Conference on Economics and Computation (EC), June 2014

We consider optimal mechanism design for the case with one buyer and two items. The buyer's valuations towards the two items are independent and additive. In this setting, optimal mechanism is unknown for general valuation distributions. We obtain two categories of structural results that shed light on the optimal mechanisms. The first category of results state that, under certain mild condition, the optimal mechanism has a monotone menu. In other words, in the menu that represents the optimal mechanism, as payment increases, the allocation probabilities for both items increase simultaneously. Applying this theorem, we derive a version of revenue monotonicity theorem that states stochastically superior distributions yield more revenue. Moreover, our theorem subsumes a previous result regarding sufficient conditions under which bundling is optimal. The second category of results state that, under certain conditions, the optimal mechanisms have few menu items. Our first result in this category says, for certain distributions, the optimal menu contains at most 4 items. The condition admits power (including uniform) density functions. Based on a similar proof of this result, we are able to obtain a wide class of distributions where bundling is optimal. Our second result in this category works for a weaker condition, under which the optimal menu contains at most 6 items. This condition includes exponential density functions. Our last result in this category works for unit-demand setting. It states that, for uniform distributions, the optimal menu contains at most 5 items. All these results are in sharp contrast to Hart and Nisan's recent result that finite-sized menu cannot guarantee any positive fraction of optimal revenue for correlated valuation distributions., Comment: 25 pages, 11 figures

We derive the optimal $\epsilon$-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has {\em staircase-shaped} probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a {\em geometric mixture of uniform probability distributions}, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the optimal noise probability distributions with minimum expectation of noise amplitude and power. Comparing the optimal performances with those of the Laplacian mechanism, we show that in the high privacy regime ($\epsilon$ is small), Laplacian mechanism is asymptotically optimal as $\epsilon \to 0$; in the low privacy regime ($\epsilon$ is large), the minimum expectation of noise amplitude and minimum noise power are $\Theta(\Delta e^{-\frac{\epsilon}{2}})$ and $\Theta(\Delta^2 e^{-\frac{2\epsilon}{3}})$ as $\epsilon \to +\infty$, while the expectation of noise amplitude and power using the Laplacian mechanism are $\frac{\Delta}{\epsilon}$ and $\frac{2\Delta^2}{\epsilon^2}$, where $\Delta$ is the sensitivity of the query function. We conclude that the gains are more pronounced in the low privacy regime., Comment: 40 pages, 5 figures. Part of this work was presented in DIMACS Workshop on Recent Work on Differential Privacy across Computer Science, October 24 - 26, 2012

We investigate the design of mechanisms to incentivize high quality in crowdsourcing environments with strategic agents, when entry is an endogenous, strategic choice. Modeling endogenous entry in crowdsourcing is important because there is a nonzero cost to making a contribution of any quality which can be avoided by not participating, and indeed many sites based on crowdsourced content do not have adequate participation. We use a mechanism with monotone, rank-based, rewards in a model where agents strategically make participation and quality choices to capture a wide variety of crowdsourcing environments, ranging from conventional crowdsourcing contests to crowdsourced content as in online Q&A forums. We first explicitly construct the unique mixed-strategy equilibrium for such monotone rank-order mechanisms, and use these participation probabilities and quality distribution to address the design of incentives for two kinds of rewards that arise in crowdsourcing. We first show that for attention rewards as in crowdsourced content, the entire equilibrium distribution improves when the rewards for every rank but the last are as high as possible. In particular, when producing the lowest quality content has low cost, the optimal mechanism displays all but the worst contribution. We next investigate settings where there is a total reward that can be arbitrarily distributed amongst all participants, as in crowdsourcing contests. Unlike with exogenous entry, here the expected number of participants can be increased by subsidizing entry, which could potentially improve the expected quality of the best contribution. However, we show that free entry is dominated by taxing entry- making all entrants pay a small fee, which is rebated to the winner along with whatever rewards were already assigned, can improve the quality of the best contribution over a winner-take-all contest with no taxes., In Proceedings of the 21st International World Wide Web Conference: WWW 2012

In mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, we are able to adapt statistical machine learning techniques to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a specific structure imposed on the discriminant function, such that it implicitly learns a corresponding payment rule with desirable incentive properties. We extend the framework to adopt succinct k -wise dependent valuations, leveraging a connection with maximum a posteriori assignment on Markov networks to enable training to scale up to settings with a large number of items; we evaluate this construction in the case where k=2. We present applications to multiparameter combinatorial auctions with approximate winner determination, and the assignment problem with an egalitarian outcome rule. Experimental results demonstrate that the construction produces payment rules with low ex post regret, and that penalizing classification error is effective in preventing failures of ex post individual rationality.

Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami et al. (2005) propose this problem and give logarithmic approximations (in the number of consumers) when each consumer's values for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic inapproximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter settings; however, logarithmic approximations are inadequate for this purpose. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this problem. Here a consumer has a valuation for each different item and their value for a set of items is simply the maximum value they have for any item in the set. We assume that the preferences of the consumers are drawn from a distribution, the standard assumption in economics; furthermore, the setting of a specific set of customers with known preferences, which is employed in all prior work in algorithmic pricing, is a special case of this general problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature., Comment: A preliminary version of this work appeared at the ACM EC'07 conference. The current version contains improved results and simpler algorithms

A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Privacy can be rigorously quantified using the framework of {\em differential privacy}, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a {\em geometric mechanism} $M^*$ -- a discrete variant of the simple and well-studied Laplace mechanism -- that is {\em simultaneously expected loss-minimizing} for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: {\em every} potential user $u$, no matter what its side information and preferences, derives as much utility from $M^*$ as from interacting with a differentially private mechanism $M_u$ that is optimally tailored to $u$., Comment: rewritten for clarity, typos corrected