We consider a mechanism design problem where an auctioneer allocates k units of an item to multiunit demand buyers arriving in an online fashion, each with a constant private marginal value. The auctioneer can inspect buyers allocated to learn their types and use this information to lower payments to reward truthful buyers. By using tools from the Calculus of Variations, we fully characterize the optimal mechanism for a single-buyer problem subject to an upper bound on the allocation expectation. In particular, we characterize the optimal allocation strategy as the solution of an ordinary differential equation and establish that it is a continuous and monotonically increasing function of the buyer's types. With the solution to the single-buyer problem, and by using connections to the prophet inequality literature, we design an online mechanism that achieves [EQUATION] of the optimal (offline) revenue, where αmax denotes the highest fraction of all units a buyer requests.1

In this work, we revisit the multi-item order fulfillment model introduced by [Jasin and Sinha 2015]. Specifically, we study a dynamic setting in which an e-commerce platform (or online retailer) with multiple warehouses and finite inventory is faced with the problem of fulfilling orders that may contain multiple items. The platform's goal is to minimize the expected cost incurred from the fulfillment process, subject to warehouses' inventory constraints. Unlike the classical literature on multi-item fulfillment, we propose an alternative offline formulation of the problem. In particular, in our model, the platform sequentially selects methods to fulfill the arriving orders. A method consists of a set of facilities that will determine which warehouses the items will ship from and, more importantly, whether multi-item orders will be split. Under this formulation, we design a class of dynamic policies that combine ideas from randomized fulfillment, prophet inequalities and subgradient methods for the general multi-item fulfillment model. Specifically, by establishing connections between the fulfillment and prophet inequality literature, we prove that our algorithm is both asymptotically optimal and has strong approximation guarantees in non-asymptotic settings. Our result shows that there is a simple and near-optimal procedure for solving multi-item fulfillment problems once the online retailer has enough inventory, independently of other problem parameters. To the best of our knowledge, this is the first result of this type in the context of multi-item order fulfillment. In addition, and of independent interest, our analysis also leads to new asymptotically optimal bounds for network revenue management problems.

We study the design of optimal Bayesian data acquisition mechanisms for a platform interested in estimating the mean of a distribution by collecting data from privacy-conscious users. In our setting, users have heterogeneous sensitivities for two types of privacy losses corresponding to local and central differential privacy measures. The local privacy loss is due to the leakage of a user's information when she shares her data with the platform, and the central privacy loss is due to the released estimate by the platform to the public. The users share their data in exchange for a payment (e.g., through monetary transfers or services) that compensates for their privacy losses. The platform does not know the privacy sensitivity of users and must design a mechanism to solicit their preferences and then deliver both local and central privacy guarantees while minimizing the estimation error plus the expected payment to users. We first establish minimax lower bounds for the estimation error, given a vector of privacy guarantees, and show that a linear estimator is (near) optimal. We then turn to our main goal: designing an optimal data acquisition mechanism. We establish that the design of such mechanisms in a Bayesian setting (where the platform knows the distribution of users' sensitivities and not their realizations) can be cast as a nonconvex optimization problem. Additionally, for the class of linear estimators, we prove that finding the optimal mechanism admits a Polynomial Time Approximation Scheme.

We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using differential privacy. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both settings, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities. Under a regularity condition on the distribution of privacy sensitivities we develop efficient algorithmic mechanisms to solve this problem in both privacy settings. Our mechanism in the central setting can be implemented in time O (n log n) where n is the number of users and our mechanism in the local setting admits a Polynomial Time Approximation Scheme (PTAS).

We consider descending price auctions for selling m units of a good to unit demand i.i.d. buyers where there is an exogenous bound of k on the number of price levels the auction clock can take. The auctioneer's problem is to choose price levels p1 > p2 > ․․․ > pk for the auction clock such that auction expected revenue is maximized. The price levels are announced prior to the auction. We reduce this problem to a new variant of prophet inequality, which we call batched prophet inequality, where a decision-maker chooses k (decreasing) thresholds and then sequentially collects rewards (up to m) that are above the thresholds with ties broken uniformly at random. For the special case of m=1 (i.e., selling a single item), we show that the resulting descending auction with k price levels achieves 1- 1/ek of the unrestricted (without the bound of k) optimal revenue. That means a descending auction with just 4 price levels can achieve more than 98% of the optimal revenue. We then extend our results for m>1 and provide a closed-form bound on the competitive ratio of our auction as a function of the number of units m and the number of price levels k.

We consider the problem of selling a single item to n unit-demand buyers to maximize revenue, where the buyers' values are independently distributed (not necessarily identical) according to publicly known distributions but unknown to the buyers themselves, with the option of allowing buyers to inspect the item at a cost. This problem can be interpreted as a revenue maximizing variant of Weitzman's Pandora's problem with non-obligatory inspection. We present an approximation mechanism that achieves 1/2. The proposed mechanism generalizes to the case of selling k units of an item to unit-demand buyers, obtaining 1-1/√k+3 of the optimal revenue in expectation. The mechanism is sequential and has a simple implementation that works in an online setting where buyers arrive in an arbitrary unknown order, yet achieving the aforementioned approximation with respect to the optimal offline mechanism.

We explore properties and applications of the principal inertia components (PICs) between two discrete random variables X and Y. The PICs lie in the intersection of information and estimation theory, and provide a fine-grained decomposition of the dependence between X and Y. Moreover, the PICs describe which functions of X can or cannot be reliably inferred (in terms of MMSE), given an observation of Y. We demonstrate that the PICs play an important role in information theory, and they can be used to characterize information-theoretic limits of certain estimation problems. In privacy settings, we prove that the PICs are related to the fundamental limits of perfect privacy.

With the boom of big data, traditional source coding techniques face the common obstacle to decode only a small portion of information efficiently. In this paper, we aim to resolve this difficulty by introducing a specific type of source coding scheme called locally decodable source coding (LDSC). Rigorously, LDSC is capable of recovering an arbitrary bit of the unencoded message from its encoded version, by only feeding a small number of the encoded message to the decoder, and we call the decoder t-local if only t encoded symbols are required.We consider both almost lossless (block error) and lossy (bit error) cases for LDSC. First, we show that using linear encoder and a decoder with bounded locality, the reliable compress rate can not be less than one. More importantly, we show that even with a general encoder and 2-local decoders (t = 2), the rate of LDSC is still one. On the contrary, the achievability bounds for almost lossless and lossy compressions with excess distortion suggest that optimal compression rate is achievable when O(log n) encoded symbols is queried by the decoder with block-length n. We also show that, rate distortion is achievable when the number of queries is scaled over n with a bound on the rate in finite-length regime. Although the achievability bounds are simply based on the concatenation of code blocks, they outperform the existing bounds in succinct data structures literature.

We investigate the problem of intentionally disclosing information about a set of measurement points X (useful information), while guaranteeing that little or no information is revealed about a private variable S (private information). Given that S and X are drawn from a finite set with joint distribution pS,X, we prove that a non-trivial amount of useful information can be disclosed while not disclosing any private information if and only if the smallest principal inertia component of the joint distribution of S and X is 0. This fundamental result characterizes when useful information can be privately disclosed for any privacy metric based on statistical dependence. We derive sharp bounds for the tradeoff between disclosure of useful and private information, and provide explicit constructions of privacy-assuring mappings that achieve these bounds.

We consider the problem of diluting common randomness from correlated observations by separated agents. This problem creates a new framework to study statistical privacy, in which a legitimate party, Alice, has access to a random variable X, whereas an attacker, Bob, has access to a random variable Y dependent on X drawn from a joint distribution pX,Y. Alice's goal is to produce a non-trivial function of her available information that is uncorrelated with (has small correlation with) any function that Bob can produce based on his available information. This problem naturally admits a minimax formulation where Alice plays first and Bob follows her. We define dilution coefficient as the smallest value of correlation achieved by the best strategy available to Alice, and characterize it in terms of the minimum principal inertia components of the joint probability distribution pX,Y. We then explicitly find the optimal function that Alice must choose to achieve this limit. We also establish a connection between differential privacy and dilution coefficient and show that if Y is ε-differentially private from X, then dilution coefficient can be upper bounded in terms of ε. Finally, we extend to the setting where Alice and Bob have access to i.i.d. copies of (Xi, Yi), i = 1, ..., n and show that the dilution coefficient vanishes exponentially with n. In other words, Alice can achieve better privacy as the number of her observations grows.

We focus on the privacy-utility trade-off encountered by users who wish to disclose some information to an analyst, that is correlated with their private data, in the hope of receiving some utility. We rely on a general privacy statistical inference framework, under which data is transformed before it is disclosed, according to a probabilistic privacy mapping. We show that when the log-loss is introduced in this framework in both the privacy metric and the distortion metric, the privacy leakage and the utility constraint can be reduced to the mutual information between private data and disclosed data, and between non-private data and disclosed data respectively. We justify the relevance and generality of the privacy metric under the log-loss by proving that the inference threat under any bounded cost function can be upperbounded by an explicit function of the mutual information between private data and disclosed data. We then show that the privacy-utility tradeoff under the log-loss can be cast as the non-convex Privacy Funnel optimization, and we leverage its connection to the Information Bottleneck, to provide a greedy algorithm that is locally optimal. We evaluate its performance on the US census dataset. Finally, we characterize the optimal privacy mapping for the Gaussian Privacy Funnel.

A locally decodable source code (LDSC) allows the recovery of arbitrary parts of an unencoded message from its encoded version, using only a part of the encoded message as input, a challenge that arises when searching within compressed data sets. Simple source codes such as Huffman codes or Lempel-Ziv compression are not well suited to this task: A decoder starting at an arbitrary point within the compressed sequence generally cannot determine its position with respect to the boundaries between encoded symbols, or requires information found before the starting point in order to be able to decode. In this paper, we propose the use of subsets of self-synchronising variable-length T-codes as source codes and show that local decoding is feasible and practical using subsets of T-codes with bounded synchronisation delay (BSD).