Mixture Selection, Mechanism Design, and Signaling

Introduction

Lotteries, beliefs, mixed strategies — all are distributions arising as important objects in game theory. It is unsurprising, therefore, that algorithmic game theory is rife with algorithmic problems which — implicitly or explicitly — optimize over the space of distributions, or equivalently the simplex. In this paper, we identify a family of algorithmic problems over the simplex which arise over and over in game theory. We term problems in this class mixture selection, and examine their computational complexity.

Given a function $g$ from the solid $n$-dimensional hypercube to the bounded interval $$, and an integer$m$, we define the$m$-dimensional mixture selection problem for$g$as follows. The input to this problem is an$n\times m$matrix$A$with bounded entries, and the objective is to compute$x\in\Delta_{m}$maximizing$g(Ax)$. It is natural to expect that the computational complexity of mixture selection depends crucially on the “complexity” of the function$g$. We therefore identify two “smoothness” parameters of the function$g$ which control the extent to which mixture selection is tractable, and derive a simple approximation algorithm with guarantees degrading gracefully in those parameters. Moreover, we present evidence — in the form of hardness results — that smoothness in both senses is necessary for the kind of general results we obtain.

The first smoothness quantity is a familiar one, namely Lipschitz continuity in the $L^{\infty}$ metric. The second quantity, which we define and term noise stability, borrows ideas from related definitions of stability in other contexts (e.g. [KKL88, MOO10]), though is importantly different. Informally, a function $g$ from the solid $n$-dimensional hypercube to the real numbers is $\beta$-noise stable (or $\beta$-stable for short) if the random corruption of an $\alpha$-fraction of the $n$ inputs to $g$, with no individual input disproportionately likely to be corrupted, does not decrease the output of $g$ by more than $\alpha\beta$. We note that a Fourier-analytic notion of stability is closely-related to ours — we elaborate on this connection in Section 9.

This paper lays out a framework for tackling mixture selection problems, and presents a number of applications in mechanism design and optimal signaling in games. Notably, we find that we resolve or make progress on a number of known open problems, and some new ones, using our framework.

Our results for mixture selection can be viewed as generalizing the main insights of Lipton et al. [LMM03]. First, we show that when $g$ is noise stable and Lipschitz continuous, and $x\in\Delta_{m}$ is arbitrary, there is a sparse vector $\widetilde{x}$ for which $g(A\widetilde{x})$ is not much smaller than $g(Ax)$. The proof of this fact proceeds by sampling from $x$ and letting $\widetilde{x}$ be the empirical distribution, as in [LMM03]. However, when $g$ is sufficiently noise stable and Lipschitz continuous, we obtain a better tradeoff between the number of samples required and the error introduced into the objective than does [LMM03], and this is crucial for our applications. Our analysis bounds the expected difference between $g(Ax)$ and $g(A\widetilde{x})$ as the sum of two terms: The first term represents the error in the output of $g$ caused by the low-probability “large errors” in its $n$ inputs, and the second term represents the error in the output of $g$ introduced by the higher-probability “small errors” in its $n$ inputs. The first term is bounded using noise stability, and the second is bounded using Lipschitz continuity.

Second, we instantiate the above insight algorithmically, as does [LMM03]. Specifically, our algorithm enumerates vectors $\widetilde{x}$ of the desired sparsity in order to find an approximately optimal solution to our mixture selection problem. We note that our guarantees are all parametrized by the Lipschitz continuity $c$ and the noise stability $\beta$ of the function $g$. Most notably, we obtain an additive polynomial-time approximation scheme (PTAS) whenever both $\beta$ and $c$ are constants.

Third, we rule out certain natural extensions of our results assuming well-believed complexity-theoretic conjectures. We show that neither Lipschitz continuity nor noise stability alone suffices for an additive PTAS for mixture selection, and both together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS). For a function which is $O(1)$-stable yet $O(1)$-Lipschitz continuous only in the $L^{1}$ metric, we show approximation hardness by a reduction from the NP-hard maximum independent set problem. For a function which is $O(1)$-Lipschitz in $L^{\infty}$ yet not $O(1)$-stable, we show approximation hardness by a reduction from the planted clique problem. Finally, for a function which is both $O(1)$-Lipschitz in $L^{\infty}$ and $O(1)$-stable, we rule out an additive FPTAS via a reduction from the maximum independent set problem.

Despite the simplicity of our framework, we find that it has powerful implications for problems in mechanism design and optimal signaling in games. We feature four natural applications in this paper, three of which resolve or partially resolve outstanding open problems from prior work:

Lottery design: Dughmi, Han, and Nisan [DHN14] examined one of the most basic problems in mechanism design: that of designing the revenue-maximizing multi-item auction for a single unit-demand buyer with valuation represented implicitly via a sampling oracle. They reduced this problem to a regularized variant of itself, namely optimally designing a small number of lottery-price pairs — a small menu — from which the buyer is allowed to choose. We apply our framework to resolve the special case of this problem with a single lottery — i.e., a menu of size $1$. This follows from the Lipschitz continuity and noise stability of the function $g^{\text{(lottery)}}_{w}(t):=\mathop{max}\limits_{p}\{p\cdot\sum_{i=1}^{n}w_{i}\cdot I[t_{i}\geq p]\}$ for an arbitrary weight vector $w\in\Delta_{n}$, where $I[\mathcal{E}]$ is the indicator function for the event $\mathcal{E}$.

Revenue-maximizing signaling in probabilistic second-price auctions: Emek et al. [EFG+12] and Miltersen and Sheffet [BMS12] considered signaling in the context of a probabilistic second-price auction. In particular, the attributes of the item for sale are unknown, and the auctioneer must decide what information to reveal in order to maximize his revenue in this auction. This is particularly relevant in advertising auctions, where items are impressions associated with demographics that are a-priori unknown to the advertisers bidding in the auction. Whereas both papers presented a polynomial-time algorithm for this problem when bidder types are fixed, the general problem was shown to be NP-hard and its approximability was left largely open. Using our framework, a PTAS for the general problem follows easily. We use the fact that the function $\mathop{max2}$, which simply returns the second largest entry of a vector, is Lipschitz continuous and noise stable.

Persuasion in voting: Alonso and Câmara [AC14] examine a simple election for selecting a binary outcome — say whether a ballot measure is passed — when voters are not fully informed of the consequences of the measure, and hence of their utilities. Each voter casts a Yes/No vote, and the measure passes if the fraction of Yes votes exceeds a certain pre-specified threshold. A principal — say a moderator of a political debate — can determine the protocol — or signaling scheme — through which information regarding the measure is gathered and shared with voters. We consider a principal concerned with maximizing the probability of the measure passing. [AC14] characterize the optimal signaling scheme and a number of its properties, though stop short of deriving an algorithm for optimal signaling. We design a multi-criteria PTAS for this problem using our framework. Along the way, we also design a bi-criteria PTAS for the related problem of maximizing the expected number of Yes votes in the election. For both results, we use the fact that the function $g^{\text{(vote-sum)}}(t)=\frac{1}{n}|\left\{i:t_{i}\geq 0\right\}|$ is noise stable and Lipschitz continuous in a bi-criteria sense.

Optimal signaling in normal form games: Dughmi [Dug14] examined the problem of optimal signaling in abstract normal form games, and ruled out an FPTAS even for two-player zero-sum games. The possibility for a PTAS for two-player zero-sum games, and a QPTAS for general games with a constant number of players, were left open. We show that a bi-criteria QPTAS for normal-form games with a constant number of players follows from our framework, and applies to a large and natural class of objective functions. We use the fact that every function is $O(n)$-stable, and the fact that the function measuring the quality of equilibria satisfies a bi-criteria notion of Lipschitz continuity which we define.

Additional Discussion of Related Work

As previously described, our framework generalizes and refines the main insight of [LMM03]. The recent work of Barman [Bar15] is also similar in spirit; in particular, the approximate variant of Caratheodory’s theorem employed in that paper can be viewed as a mixture selection problem with $g(Ax)=-||Ax-Ax^{*}||_{p}$ for a fixed vector $x^{*}$ and norm $p\geq 2$. Even though this function $g$ is neither Lipschitz continuous in $L^{\infty}$ nor noise stable, Barman exhibits a PTAS under the assumption that the columns of $A$ have small (i.e. constant) $p$-norm.

Framework

For a function $g:^{n}\rightarrow$ and a positive integer $m$, we define the following optimization problem which we term $m$-dimensional mixture selection for $g$: given an $n\times m$ matrix $A$ with entries in $$, find$x$in the$m$-dimensional simplex$\Delta_{m}$maximizing$f(x):=g(Ax)$. In this section, we present our notion of noise stability, and derive approximation algorithms for this problem when the function$g$is simultaneously noise stable and Lipschitz continuous with respect to the$L^{\infty}$ metric. Moreover, we show that neither requirement alone suffices for our results.

Our approximation guarantees will be additive — i.e., an $\epsilon$-approximation algorithm for mixture selection outputs $x\in\Delta_{m}$ with $f(x)\geq\mathop{max}_{y\in\Delta_{m}}f(y)-\epsilon$. To illustrate our techniques, we use the following function $g^{(\operatorname{mid})}:^{n}\to$, which averages all but the top and bottom quartiles of its inputs, as a running example.

where $t_{[i]}$ denote the ${i}^{\rm th}$ largest entry of $t$. Throughout the paper, we use $t_{i}$ to denote the ${i}^{\rm th}$ entry of $t$, and use $t_{[i]}$ to denote the ${i}^{\rm th}$ largest entry of $t$.

Though we present our framework for functions $g:^{n}\to$, we define mixture selection similarly for functions $g:^{n}\to$. The two definitions are equivalent up to normalization, and it is easy to verify that all our results and bounds for mixture selection carry through unchanged to either definition.

Our main result applies to functions $g$ which are both noise stable and Lipschitz continuous with respect to the $L^{\infty}$ metric. We now formalize these two conditions.

A function $g:^{n}\rightarrow$ is $c\text{-Lipschitz}$ continuous in $L^{\infty}$ — or $c\text{-Lipschitz}$ for short — if and only if for all $t,t^{\prime}$ in the domain of $g$, $|g(t)-g(t^{\prime})|\leq c{||t-t^{\prime}||}_{\infty}$. To illustrate, our example function $g^{(\operatorname{mid})}$ is $1$-Lipschitz. We note that Lipschitz continuity in $L^{\infty}$ is a stronger assumption than in any other $L^{p}$ norm.

Noise Stability

Our notion of noise stability captures the following desirable property of a function $g:^{n}\to$: if a random process corrupts (i.e., modifies arbitrarily) some of the inputs to $g$, with no individual input disproportionately likely to be corrupted, then the output of $g$ does not decrease by much in expectation. Such random corruption patterns are captured by our notion of a light distribution over subsets of $[n]$, defined below.

Let $\mathcal{D}$ be a distribution supported on subsets of $[n]$. For $\alpha\in(0,1]$, we say $\mathcal{D}$ is $\alpha\text{-Light}$ if and only if the following holds for all $i\in[n]$: $\operatorname*{Pr}_{R\sim\mathcal{D}}[i\in R]\leq\alpha.$

In other words, a light distribution bounds the marginal probability of any individual element of $[n]$. When corrupted inputs follow a light distribution, no individual input is too likely to be corrupted. However, we note that our notion of light distribution allows arbitrary correlations between the corruption events of various inputs. We define a noise stable function as one which is robust, in an average sense, to corrupting a subset $R$ of its $n$ inputs when $R$ follows a light distribution $\mathcal{D}$. Our notion of robustness is one-sided: we only require that our function’s output not decrease substantially in expectation. This one-sided guarantee suffices for all our applications, and is necessitated by some. We note that the light distribution $\mathcal{D}$, as well as the (corrupted) inputs, are chosen adversarially. We make use of the following notation in our definition: Given vectors $t,t^{\prime}\in^{n}$ and a set $R\subseteq[n]$, we say $t^{\prime}\stackrel{{\scriptstyle[}}{{R}}]{}{\approx}t$ if $t_{i}=t^{\prime}_{i}$ for all $i\not\in R$. In other words, if $t^{\prime}\stackrel{{\scriptstyle[}}{{R}}]{}{\approx}t$, then $t^{\prime}$ is a result of corrupting the entries of $t$ corresponding to $R$.

Given a function $g:^{n}\rightarrow$ and a real number $\beta\geq 0$, we say $g$ is $\beta$-stable if and only if the following holds for all $t\in^{n}$, $\alpha\in(0,1]$, and $\alpha\text{-Light}$ distributions $\mathcal{D}$ over subsets of $[n]$:

To illustrate this definition, we show that our example function $g^{(\operatorname{mid})}$ is $4\text{-stable}$. To see this, observe that changing $k$ entries of the input to $g^{(\operatorname{mid})}$ can decrease its output by at most $\frac{4k}{n}$. When $R$ is drawn from an $\alpha\text{-Light}$ distribution and $t$ is an arbitrary input, $4$-stability therefore follows from the linearity of expectations:

We note that every function $g:^{n}\to$ is $2n$-stable, which follows from the union bound.

As a useful building block for proving some of our functions stable, we show that stable functions can be combined to yield other stable functions if composed with a convex, nondecreasing, and Lipschitz continuous function.

Fix $\beta,c\geq 0$, and let $g_{1},g_{2},\ldots,g_{k}:^{n}\rightarrow$ be $\beta$-stable functions. For every convex function $h:^{k}\to$ which is nondecreasing in each of its arguments and $c$-Lipschitz continuous in $L^{\infty}$, the function $g(t):=h(g_{1}(t),\ldots,g_{k}(t))$ is $(\beta c)$-stable.

For all $t\in^{n}$ and all $\alpha\text{-Light}$ distributions $\mathcal{D}$,

As a consequence of the above proposition, a convex combination of $\beta$-stable functions is $\beta$-stable, and the point-wise maximum of $\beta$-stable functions is $\beta$-stable.

Consequences of Noise Stability and Lipschitz Continuity

We now state the two main results of our framework. Both results apply to functions $g:^{n}\to$ which are simultaneously Lipschitz continuous and noise stable, and $n\times m$ matrices $A$ with entries in $$. Given a vector$x\in\Delta_{m}$and integer$s>0$, we view$x$as a probability distribution over$[m]$, and use the random variable$\widetilde{x}\in\Delta_{m}$to denote the empirical distribution of$s$i.i.d. samples from$x$. Formally,$\widetilde{x}=\frac{1}{s}\sum_{i=1}^{s}e_{k_{i}}$, where$k_{1},\ldots,k_{s}\in[m]$are drawn i.i.d. according to$x$, and$e_{j}\in\Delta_{m}$denotes the${j}^{\rm th}$standard basis vector. Since$\widetilde{x}$is the average of$s$standard basis vectors, we say it is$s$-uniform.

We refer to a distribution $y\in\Delta_{m}$ as $s$-uniform if and only if it is the average of a multiset of $s$ standard basis vectors in $m$-dimensional space.

Our first result shows that when the number of samples $s$ is chosen as a suitable function of the Lipschitz continuity and noise stability parameters, $g(A\widetilde{x})$ is not much smaller than $g(Ax)$ in expectation over $\widetilde{x}$. At a high level, we bound this difference as a sum of two error terms: one accounts for the effect of low-probability large errors in the inputs $\widetilde{t}=A\widetilde{x}$ to $g$, and the other accounts for effect of higher-probability small errors in the inputs $\widetilde{t}$. The former error term is bounded using noise stability, and the latter error term is bounded using Lipschitz continuity.

Let $g:^{n}\rightarrow$ be $\beta\text{-stable}$ and $c\text{-Lipschitz}$ in $L^{\infty}$, let $A$ be an $n\times m$ matrix with entries in $$, let$\alpha,\delta>0$, and let$s\geq 2\ln({\frac{2}{\alpha}})/\delta^{2}$be an integer. Fix a vector$x\in\Delta_{m}$, and let the random variable$\widetilde{x}$denote the empirical distribution of$s$i.i.d. samples from probability distribution$x$. The following then holds:$\operatorname*{E}[g(A\widetilde{x}))]\geq g(Ax)-\alpha\beta-c\delta.$

Denote $t=Ax$ and $\widetilde{t}=A\widetilde{x}$. Note that $\widetilde{t}$ is a random variable. Also note that $t_{i}$ and $\widetilde{t}_{i}$ can be viewed as the mean and empirical mean, respectively, of a distribution supported on $A_{i,1},\ldots,A_{i,m}\in$. We say the ${i}^{\rm th}$ entry of $t$ is approximately preserved if $|t_{i}-\widetilde{t}_{i}|\leq\delta$, and we say it is corrupted otherwise. Let $R\subseteq[n]$ denote the set of corrupted entries. Hoeffding’s inequality, and our choice of the number of samples $s$, imply that $R$ follows an $\alpha\text{-Light}$ distribution.

Let $t^{\prime}$ be such that (1) $t^{\prime}_{i}=\widetilde{t}_{i}$ for $i\in R$, and (2) $t^{\prime}_{i}=t_{i}$ otherwise. Observe that $t^{\prime}\stackrel{{\scriptstyle[}}{{R}}]{}{\approx}t$, and ${||t^{\prime}-\widetilde{t}||}_{\infty}\leq\delta$. We can now bound the expected difference between $g(t)$ and $g(\widetilde{t})$ as a sum of the error introduced by corrupted entries and the error introduced by the approximately preserved entries of $t$:

Notice that if we fix the desired approximation error $\epsilon$, the minimum required number of samples $s$ in Theorem 2.5 to guarantee that $\operatorname*{E}[g(A\widetilde{x}))]\geq g(Ax)-\epsilon$ is obtained by minimizing $\lceil{2\ln({\frac{2}{\alpha}})/\delta^{2}}\rceil$ over $\alpha,\delta>0$ satisfying $\alpha\beta+\delta c\leq\epsilon$. Therefore, the required number of samples depends only on the error term $\epsilon$, the noise stability parameter $\beta$, and the Lipschitz continuity parameter $c$; in particular, it is independent of $n$ and $m$.

As a corollary of Theorem 2.5, we derive the following algorithmic result.

Let $g:^{n}\to$ be $\beta\text{-stable}$ and $c\text{-Lipschitz}$, and let $m>0$ be an integer. For every $\delta,\alpha>0$, the $m$-dimensional mixture selection problem for $g$ admits an $(\alpha\beta+c\delta)$-approximation algorithm in the additive sense, with runtime $n\cdot m^{O(\log(1/\alpha)/\delta^{2})}\cdot T$, where $T$ denotes the time needed to evaluate $g$ on a single input.

Let $s\geq 2\ln(2/\alpha)/\delta^{2}$ be an integer. Our algorithm simply enumerates all $s$-uniform distributions, and outputs the one maximizing $g(Ax)$. This takes time $n\cdot m^{O(s)}\cdot T$. The approximation guarantee follows from Theorem 2.5 and the probabilistic method. ∎

As a consequence of Theorem 2.6, the mixture selection problem for $g^{(\operatorname{mid})}$ admits a polynomial-time approximation scheme (PTAS) in the additive sense. The same holds for every function $g$ which is $O(1)$-stable and $O(1)$-Lipschitz continuous. Specifically, by setting $\alpha=\frac{\epsilon}{2\beta}$ and $\delta=\frac{\epsilon}{2c}$, an $\epsilon$-approximation algorithm runs in time $n\cdot m^{O(c^{2}\log(\beta/\epsilon)/\epsilon^{2})}\cdot T$. Interestingly, neither noise stability nor Lipschitz continuity alone suffices for such a PTAS, as we argue in the next subsection.

The Necessity of Both Noise Stability and Lipschitz Continuity

We now present evidence that both our assumptions — Noise stability and Lipschitz continuity — appear necessary for general positive results along the lines of those in Theorem 2.6.

Stability alone is not sufficient. In Section 8.1, we define a function $g^{\text{(slope)}}:^{n}\rightarrow$ which is $1\text{-stable}$. Furthermore, $g^{\text{(slope)}}$ is $O(1)\text{-Lipschitz}$ with respect to the $L^{1}$ metric, which is a weaker property than Lipschitz continuity with respect to $L^{\infty}$. We show in Theorem 8.4 that there is a polynomial-time reduction from the maximum independent set problem on $n$-node graphs to the $n$-dimensional mixture selection for $g^{\text{(slope)}}$. Moreover, the reduction precludes a polynomial-time $\epsilon$-approximation algorithm in the additive sense for some constant $\epsilon>0$.

Lipschitz continuity alone is not sufficient. One might hope to prove NP-hardness of mixture selection in the absence of stability. However, we are out of luck in this regard: since every function $g:^{n}\to$ is $2n$-stable, Theorem 2.6 implies a quasipolynomial-time approximation scheme in the additive sense whenever $g$ is $O(1)$-Lipschitz. Nevertheless, we prove hardness of approximation assuming the planted clique conjecture ([Jer92] and [Kuč95]).

More specifically, in Section 8.2 we exhibit a reduction from the planted $k$-clique problem to mixture selection for the $3$-Lipschitz function $g^{\text{(clique)}}_{k}(t)=t_{[k]}-t_{[k+1]}+t_{[n]}$. When $k=\omega(\log^{2}n)$ and $A$ is the adjacency matrix of an $n$-node undirected graph $G$, we show that $\mathop{max}_{x}g^{\text{(clique)}}_{k}(Ax)\approx 1$ with high probability if $G$ contains a $k$-clique, and $\mathop{max}_{x}g^{\text{(clique)}}_{k}(Ax)\approx\frac{1}{2}$ with high probability if $G$ is the Erdös-Rényi random graph $G(n,\frac{1}{2})$.

A Bi-criteria Extension of the Framework

We have already showed that in the absence of Lipschitz continuity, one can not hope for a PTAS in general. Motivated by two of our applications, namely Optimal signaling in normal form games and Persuasion in voting, we extend our framework to the design of approximation algorithms for mixture selection with a bi-criteria guarantee when the function in question is stable but not Lipschitz continuous. We first define a $(\delta,\rho)$-relaxation of a function.

Given two functions $g,h:^{n}\rightarrow$ and parameters $\delta,\rho\geq 0$, we say $h$ is a $(\delta,\rho)$-relaxation of $g$ if for all $t_{1},t_{2}\in^{n}$ with ${||t_{1}-t_{2}||}_{\infty}\leq\delta$, $h(t_{2})\geq g(t_{1})-\rho$.

In lieu of the Lipschitz continuity condition, we prove our bounds for a relaxation of the function.

Let $g:^{n}\rightarrow$ be $\beta\text{-stable}$, let $A$ be an $n\times m$ matrix with entries in $$, let$\alpha>0$and$\delta,\rho\geq 0$, and let$s\geq 2\ln({\frac{2}{\alpha}})/\delta^{2}$be an integer. Fix a vector$x\in\Delta_{m}$, and let the random variable$\widetilde{x}$denote the empirical distribution of$s$i.i.d. samples from probability distribution$x$. The following then holds for any$(\delta,\rho)$-relaxation$h$of$g$,

Because the proof is almost identical to the proof of Theorem 2.5, we just mention the necessary modifications. Again, let $t=Ax$, let $\widetilde{t}=A\widetilde{x}$, let $R\subseteq[n]$ denote the set of corrupted inputs, and let $t^{\prime}$ be such that $t^{\prime}_{i}=\widetilde{t}_{i}$ for $i\in R$ and $t^{\prime}_{i}=t_{i}$ otherwise. Then

where the first inequality follows by noise stability of $g$, and the last inequality follows from the fact that $h$ is a $(\delta,\rho)$-relaxation of $g$. ∎

Having replaced Theorem 2.5 by Theorem 2.8, a similar computational result as Theorem 2.6 can be inferred in the bi-criteria sense.

Lottery Design for Revenue Maximization

To illustrate the utility of our framework, we start with a simple but basic open problem in Bayesian mechanism design posed by Dughmi, Han, and Nisan [DHN14]. An instance of the lottery design problem is given by a valuation matrix $A\in^{n\times m}$ and $n$ non-negative weights $w_{1},\ldots,w_{n}$ with $\sum_{i=1}^{n}w_{i}=1$. Here $n$ denotes the number of buyer types, $m$ denotes the number of items, and $w$ represents a probability distribution over types. Each $0\leq A_{i,j}\leq 1$ is the value of item $j$ to a buyer of type $i$. The goal is to design a single lottery-price pair $(x,p)$, with $x\in\Delta_{m}$ and $p\geq 0$, so that the expected revenue of the auction which offers the lottery $x$ over items at price $p$ to a buyer with type drawn according to $w$ is maximized. We assume the buyer is risk neutral, and therefore accepts the offer precisely if his type $i$ satisfies $A_{i}x\geq p$. Consequently, our goal is to choose $(x,p)$ maximizing $p\cdot\sum_{i=1}^{n}(w_{i}\cdot I[A_{i}x\geq p])$, where $I[\mathcal{E}]$ denotes the indicator function for the event $\mathcal{E}$.

The lottery design problem is closely related to the general unit-demand single-buyer mechanism design problem considered in [DHN14], where the buyer’s type is drawn from a common knowledge prior distribution $\mathcal{B}$ given by a sampling oracle, and the buyer is to be presented with a menu consisting of several lottery-price pairs from which to choose. [DHN14] frame this mechanism design problem as a computational task of “learning” a good mechanism by sampling from $\mathcal{B}$, and use the size of the menu as a regularization constraint in order to prevent over-fitting the mechanism to the sampled data. The problem of maximizing the expected revenue by using a menu of at most a given size is the main algorithmic question in [DHN14], and its computational complexity is left largely open. When constrained to a menu with a single lottery, the goal is to choose $(x,p)$ maximizing the expected revenue $p\cdot\operatorname*{Pr}\limits_{a\sim\mathcal{B}}[ax\geq p]$.

Using our mixture selection framework, we first give an additive PTAS for the lottery design problem when the value distribution $\mathcal{B}$ is given explicitly by the matrix $A$ and weights $w$ as described above. We then extend our result to cases in which $\mathcal{B}$ can only be accessed through sampling, using fairly standard uniform convergence arguments. In Section 8.3 (Theorem 8.9), we rule out an additive FPTAS for this problem, and in doing so provide complexity-theoretic evidence that our PTAS — for both lottery design in particular and mixture selection for stable and Lipschitz-continuous functions more generally — is essentially the best we can hope for.

Given the number of buyer types $n$ and weights $w\in\Delta_{n}$, the lottery design problem is simply mixture selection for the function $g^{\text{(lottery)}}_{w}(t):^{n}\to$, defined below.

As the first step to applying our framework, we show that $g^{\text{(lottery)}}_{w}$ is noise stable. The high level idea is the following: if a subset of the inputs to $g^{\text{(lottery)}}_{w}$ is corrupted, then in the worst case each such input exceeded the price $p$ before corruption but not after corruption. This reduces the output of $g^{\text{(lottery)}}_{w}$ by at most the total weight of corrupted inputs. When corrupted inputs are chosen according to an $\alpha\text{-Light}$ distribution, their expected total weight is bounded by $\alpha$.

The function $g^{\text{(lottery)}}_{w}$ is $1\text{-stable}$.

Let $t\in^{n}$ be an arbitrary input to $g^{\text{(lottery)}}_{w}$. When $t^{\prime}$ is obtained from $t$ by corrupting the entries corresponding to $R\subseteq[n]$, an event we denote by $t^{\prime}\stackrel{{\scriptstyle[}}{{R}}]{}{\approx}t$, it is easy to see that $g^{\text{(lottery)}}_{w}(t^{\prime})\geq g^{\text{(lottery)}}_{w}(t)-w(R)$ where $w(R)=\sum_{i\in R}w_{i}$ denotes the total weight of corrupted entries. Moreover, when $R$ is a random variable drawn from an $\alpha\text{-Light}$ distribution $\mathcal{D}$, we can bound the expected loss: $\operatorname*{E}[w(R)]=\sum_{i=1}^{n}\operatorname*{Pr}[i\in R]\cdot w_{i}\leq\sum_{i}\alpha w_{i}=\alpha$. It follows that $g^{\text{(lottery)}}_{w}$ is $1\text{-stable}$.

Next, we prove Lipschitz continuity. The high-level idea is the following: if all inputs to $g^{\text{(lottery)}}_{w}$ decrease by $\delta$, then we need only decrease the price $p$ from expression (3.1) by $\delta$. The (weighted) fraction of inputs exceeding the price is at least the same as before.

The function $g^{\text{(lottery)}}_{w}$ is $1\text{-Lipschitz}$ continuous.

Consider $t,t^{\prime}\in^{n}$ with ${||t^{\prime}-t||}_{\infty}\leq\delta$. We prove that $g^{\text{(lottery)}}_{w}(t^{\prime})\geq g^{\text{(lottery)}}_{w}(t)-\delta$, and by symmetry it follows that $g^{\text{(lottery)}}_{w}(t)\geq g^{\text{(lottery)}}_{w}(t^{\prime})-\delta$. Let $p$ be the optimal price for $t$ — i.e. the maximizer of expression (3.1) — and define $p^{\prime}=\mathop{max}\{0,p-\delta\}$. Whenever $t_{i}\geq p$ we have $t^{\prime}_{i}\geq p^{\prime}$, and therefore $\sum\limits_{i=1}^{n}(w_{i}\cdot I[t^{\prime}_{i}\geq p^{\prime}])\geq\sum\limits_{i=1}^{n}(w_{i}\cdot I[t_{i}\geq p])$. It follows that $g^{\text{(lottery)}}_{w}(t^{\prime})\geq g^{\text{(lottery)}}_{w}(t)-\delta$. ∎

Combining Lemmas 3.1 and 3.2 with Theorem 2.6 yields an additive PTAS for lottery design.

There is an additive PTAS for the lottery design problem when the valuation distribution is given explicitly by a matrix $A\in^{n\times m}$ and a weight vector $w\in\Delta_{n}$.

2 Lottery Design in the Sample Oracle Model

So far, we have assumed that the buyer’s type distribution is given explicitly. We now show how to extend our results to the sample oracle model. Specifically, we assume the buyer’s type $a\in^{m}$ is drawn from a distribution $\mathcal{B}$ given by a sampling oracle, and seek a randomized approximation scheme with runtime (and number of samples) polynomial in $m$ for each desired approximation guarantee $\epsilon$. To simplify exposition we assume $\mathcal{B}$ has finite support, though our results hold more generally. As usual, our goal is to choose a lottery $x\in\Delta_{m}$ and a price $p\geq 0$ to maximize $\text{Rev}_{\mathcal{B}}(x,p)=p\cdot\operatorname*{Pr}\limits_{a\sim\mathcal{B}}[ax\geq p]$.

There is an additive polynomial-time randomized approximation scheme (PRAS) for the lottery design problem in the sample oracle model.

Recall that the PTAS in Theorem 3.3 optimizes over all $s$-uniform $m$-dimensional lotteries, where $s$ depends only on the desired approximation guarantee $\epsilon>0$, and is bounded by a polynomial in $\frac{1}{\epsilon}$. In particular, $s$ is independent of the number of types $n$, implying that the same approach of enumerating all $s$-uniform lotteries $\widetilde{x}$ would succeed in the sample oracle model were it not for our inability to evaluate $\mathop{max}_{p}\text{Rev}_{\mathcal{B}}(\widetilde{x},p)$ exactly.

We overcome this difficulty by Monte Carlo sampling from $\mathcal{B}$. Given $n$ types $a_{1},\ldots,a_{n}\in^{m}$ sampled from $\mathcal{B}$ and presented as the rows of a matrix $A\in^{n\times m}$, we run the PTAS from Theorem 3.3 with approximation parameter $\epsilon$ on the empirical distribution given by $A$ and uniform weights $w_{i}=\frac{1}{n}$ for all $i$. Taking $n$ to be a suitable polynomial in $m$, $\frac{1}{\epsilon}$, and $\log(\frac{1}{\gamma})$ — where $\gamma>0$ is a parameter — guarantees that $|\text{Rev}_{\mathcal{B}}(\widetilde{x},p)-p\cdot\frac{1}{n}\sum_{i=1}^{n}I[A_{i}\widetilde{x}\geq p]|\leq\epsilon$ simultaneously for all $s$-uniform lotteries $\widetilde{x}$ and prices $p$ with probability at least $1-\gamma$. This follows from standard tail bounds and the union bound, coupled with a uniform convergence argument over prices $p\in$. Therefore, with probability $1-\gamma$ our algorithm outputs a lottery-price pair whose expected revenue for a buyer drawn from $\mathcal{B}$ is within $O(\epsilon)$ from the optimal. ∎

Signaling

In the next few sections, we consider a number of Bayesian games in which a key parameter $\theta$, the state of nature, in part determines the payoff structure of the game. We use $\Theta$ to denote the set of all states of nature, and assume $\theta\in\Theta$ is drawn from a common-knowledge prior distribution which we denote by $\lambda$. In all our applications, we assume players a-priori know nothing about $\theta$ other than its prior distribution $\lambda$, and examine policies whereby a principal with access to the realized value of $\theta$ may commit to a policy of revealing information to the players regarding $\theta$. This is often referred to as signaling (see e.g. [EFG+12, BMS12, DIR14, Dug14]). We restrict our attention to symmetric signaling schemes, in which the principal must reveal the same information to all players in the game. Thus, a symmetric signaling scheme is given by a set $\Sigma$ of signals, and a (possibly randomized) map $\varphi$ from states of nature $\Theta$ to signals $\Sigma$. The goal of the principal, who is privy to confidential state-of-nature information, is to boost her own objective by using a signaling scheme $\varphi$ that optimally affects the outcome of the game.

In this section, in addition to providing the technical background for signaling schemes, we use our framework to define an abstract signaling problem and characterize its approximation complexity. This abstract problem captures the essence of all signaling problems considered in this paper.

Let $m=|\Theta|$. Abusing notation, we use $\varphi(\theta,\sigma)$ to denote the probability of announcing signal $\sigma\in\Sigma$ conditioned on the state of nature is $\theta\in\Theta$. It is well known ([KG09, Dug14]) that signaling schemes are in one-to-one correspondence with convex decompositions of the prior distribution $\lambda\in\Delta_{m}$: Formally, a signaling scheme $\varphi:\Theta\to\Sigma$ corresponds to the convex decomposition $\lambda=\sum_{\sigma\in\Sigma}\nu_{\sigma}\cdot\mu_{\sigma},$ where (1) $\nu_{\sigma}=\operatorname*{Pr}_{\theta\sim\Theta}[\varphi(\theta)=\sigma]=\sum_{\theta\in\Theta}\lambda(\theta)\varphi(\theta,\sigma)$ is the probability of announcing signal $\sigma$, and (2) $\mu_{\sigma}(\theta)=\operatorname*{Pr}_{\theta\sim\Theta}[\theta|\varphi(\theta)=\sigma]=\frac{\lambda(\theta)\varphi(\theta,\sigma)}{\nu_{\sigma}}$ is the posterior belief distribution of $\theta$ conditioned on signal $\sigma$. The converse is also true: every convex decomposition of $\lambda\in\Delta_{m}$ corresponds to a signaling scheme. Alternatively, the reader can view a signaling scheme $\varphi$ as the $m\times|\Sigma|$ matrix of pairwise probabilities $\varphi(\theta,\sigma)$ satisfying conditions (1) and (2) with respect to $\lambda\in\Delta_{m}$.

In this setup, the optimal choice of a signaling scheme is related to the concave envelope $f^{+}$ of the function $f$ ([KG09, Dug14]).$f^{+}$ is the point-wise lowest concave function $h$ for which $h(x)\geq f(x)$ for all $x$ in the domain. Equivalently, the hypograph of $f^{+}$ is the convex hull of the hypograph of $f$. Specifically, such a signaling scheme achieves $\sum_{\sigma}\nu_{\sigma}\cdot f(\mu_{\sigma})=f^{+}(\lambda)$. Thus, there exists a signaling scheme with $m+1$ signals that maximizes the principal’s objective, by applying Caratheodory’s theorem to the hypograph of $f$.

2 An Abstract Signaling Problem and its Polynomial-Time Approximation

To connect to our mixture selection framework, we consider signaling problems in which the principal’s utility $f(\mu)$ from a posterior distribution $\mu\in\Delta_{m}$ can be written as $g(A\mu)$ for a function $g:^{n}\to$ and a matrix $A\in^{n\times m}$. As described in Section 4.1, a signaling scheme $\varphi$ with signals $\Sigma$ corresponds to a family of probability-posterior pairs $\{(\nu_{\sigma},\mu_{\sigma})\}_{\sigma\in\Sigma}$ decomposing the prior $\lambda\in\Delta_{m}$ into a convex combination of posterior distributions (one per signal): $\lambda=\sum_{\sigma\in\Sigma}\nu_{\sigma}\mu_{\sigma}$. The objective of our signaling problem is then

We note that this signaling problem can alternatively be written as an (infinite-dimensional) linear program which searches over probability measures supported on $\Delta_{m}$ with expectation $\lambda$. The separation oracle for the dual of this linear program is a mixture selection problem. Whereas we do not use this infinite-dimensional formulation nor its dual directly, we nevertheless show that the same conditions — noise stability and Lipschitz continuity — on the function $g$ which lead to an approximation scheme for mixture selection also lead to a similar approximation scheme for our signaling problem with $f(\mu)=g(A\mu)$.

If $g$ is $\beta$-stable and $c$-Lipschitz, then for any constants $\alpha,\delta>0$, and for any integer $s\geq 2\delta^{-2}\ln(2/\alpha)$, there exists a signaling scheme $\widetilde{\varphi}$ for which every posterior distribution is $s$-uniform, and $F(\widetilde{\varphi})\geq OPT-(\alpha\beta+c\delta)$ where OPT denotes the value of the optimal signaling scheme.

Let $s\geq 2\delta^{-2}\ln(2/\alpha)$, and let $\tau\in[m^{s}]$ index all $s$-uniform posteriors, with $\widetilde{\mu}_{\tau}$ denoting the $\tau$’th such posterior. For an arbitrary signaling scheme $\varphi=(\Sigma,\{(\nu_{\sigma},\mu_{\sigma})\}_{\sigma\in\Sigma})$, we show that each posterior $\mu_{\sigma}$ can be decomposed into $s$-uniform posteriors without degrading the objective by more than $\alpha\beta+c\delta$; more formally:

$\mu_{\sigma}$ can be expressed as a convex combination of $s$-uniform posteriors as follows.

The value of objective function, i.e., $g(A\mu_{\sigma})$, is decreased by no more than $\alpha\beta+c\delta$ through this decomposition,

The existence of such a decomposition follows from Theorem 2.5: Fix $\sigma$, and let $\widetilde{\mu}\in\Delta_{m}$ be the empirical distribution of $s$ i.i.d. samples from distribution $\mu_{\sigma}\in\Delta_{m}$. The vector $\widetilde{\mu}$ is itself a random variable supported on $s$-uniform posteriors, its expectation is $\mu_{\sigma}$, and by Theorem 2.5 we have $\mathop{E}[g(A\widetilde{\mu})]\geq g(A\mu_{\sigma})-(\alpha\beta+c\delta)$. Therefore, by taking $\widetilde{\nu}_{\sigma,\tau}=\operatorname*{Pr}[\widetilde{\mu}=\widetilde{\mu}_{\tau}]$ for each $\tau\in[m^{s}]$ we get the desired decomposition of $\mu_{\sigma}$.

The lemma follows by composing the decomposition $\varphi$ with the decompositions of the posterior beliefs $\mu_{\sigma}$ to yield a signaling scheme $\widetilde{\varphi}$ with only $s$-uniform posteriors and $F(\widetilde{\varphi})\geq F(\varphi)-(\alpha\beta+c\delta)$. Specifically, the signals of $\widetilde{\varphi}$ are $\Sigma\times[m^{s}]$, where signal $(\sigma,\tau)$ has probability $\nu_{\sigma}\cdot\widetilde{\nu}_{\sigma,\tau}$ and induces the posterior $\widetilde{\mu}_{\tau}$. Note, however, that we can also “merge” all signals with the same posterior $\widetilde{\mu}_{\tau}$ without loss. Using Equation (4.1) and (4.2), it is easy to verify that this describes a valid signaling scheme with $F(\widetilde{\varphi})\geq F(\varphi)-(\alpha\beta+c\delta)$. ∎

Lemma 4.1 permits us to restrict attention to $s$-uniform posteriors without much loss in our objective. Since there are only $m^{s}$ such posteriors, a simple linear program with $m^{s}$ variables computes an approximately optimal signaling scheme.

If $g$ is $\beta$-stable and $c$-Lipschitz, then for any constant $\alpha,\delta>0$, there exists a deterministic algorithm that constructs a signaling scheme with objective value at least $OPT-(\alpha\beta+c\delta)$, where $OPT$ is the value of the optimal signaling scheme. Moreover, the algorithm runs in time $\operatorname{poly}(m^{\delta^{-2}\ln(1/\alpha)})\cdot n\cdot T$, where $T$ denotes the time needed to evaluate $g$ on a single input.

Let $s$ be an integer with $s\geq(2\delta^{-2}\ln(2/\alpha))$, denote $M=m^{s}$, and let $\left\{\mu_{1},\cdots,\mu_{M}\right\}$ be the set of all $s$-uniform posteriors. Lemma 4.1 shows that restricting to $s$-uniform posteriors only introduces an $\alpha\beta+c\delta$ additive loss in the objective. Thus it suffices to compute the optimal signaling scheme supported only on $s$-uniform posteriors. This can be done using the following linear program:

Note $\mu_{j}$ is the $j$’th $s$-uniform posterior — the only variables in this LP are $\nu_{1},\ldots,\nu_{M}$. ∎

Our proofs can be adapted to obtain a bi-criteria guarantee in the absence of Lipschitz continuity, as in Section 2. The following Theorem follows easily, and we omit the details.

Let $g,h:^{n}\to$ be such that $g$ is $\beta$-stable and $h$ is a $(\delta,\rho)$-relaxation of $g$, and let $\alpha>0$ be a parameter. There exists a deterministic algorithm which, when given as input a matrix $A\in^{n\times m}$ and a prior distribution $\lambda\in\Delta_{m}$, constructs a signaling scheme $\varphi=\{(\nu_{\sigma},\mu_{\sigma})\}_{\sigma\in\Sigma}$ such that

where $OPT$ is the maximizer of $F(\varphi^{*})=\sum_{\sigma\in\Sigma^{*}}\nu^{*}_{\sigma}g(A\mu^{*}_{\sigma})$ over signaling schemes $\varphi^{*}=\{(\nu^{*}_{\sigma},\mu^{*}_{\sigma})\}_{\sigma\in\Sigma^{*}}$. Moreover, the algorithm runs in time $\operatorname{poly}(m^{\delta^{-2}\ln(1/\alpha)})\cdot n\cdot T$, where $T$ denotes the time needed to evaluate $h$ on a single input.

We note that our proof suggests an extension of the result in Theorem 4.2 to cases in which $f$ is given by a “black box” oracle, so long as we are promised that it is of the form $f(\mu)=g(A\mu)$. In this model the runtime of our algorithm does not depend on $n$, but instead depends on the cost of querying $f$. We also point out that that even though we precompute the quality of all $m^{s}$ posteriors, we can guarantee that our output signaling scheme uses at most $m+1$ signals; this is because LP (4.3) has only $m+1$ constraints, and therefore admits an optimal solution where at most $m+1$ variables are non-zero.

Signaling in Probabilistic Second-Price Auctions

We examine signaling in probabilistic second-price auctions, as considered by Emek et al. [EFG+12] and Miltersen and Sheffet [BMS12]. In this setting, the item being auctioned is probabilistic, and the instantiation of the item is known to the auctioneer but not to the bidders. The auctioneer commits to a signaling scheme for (partially) revealing information about the item for sale before subsequently running a second-price auction. We consider a probabilistic second-price auction described by the following parameters:

An integer $n$ denoting the number of bidders. We index the players by the set $[n]=\left\{1,\ldots,n\right\}$.

An integer $m$ denoting the number of states of nature. We index states of nature by the set $\Theta=\left\{1,\ldots,m\right\}$. Each $\theta\in\Theta$ represents a possible instantiation of the item being sold.

A common-knowledge prior distribution $\lambda\in\Delta_{m}$ on the states of nature.

A common-knowledge prior distribution $\mathcal{D}$ on valuation matrices $\mathcal{V}\in^{n\times m}$, given either explicitly or as a “black-box” sampling oracle. For a valuation matrix $\mathcal{V}$, entry $\mathcal{V}_{ij}$ denotes the value of player $i$ for the item corresponding to state of nature $j$.

The game being played is the following: (a) The auctioneer first commits to a signaling scheme $\varphi:\Theta\to\Sigma$; (b) A state of nature $\theta\in\Theta$ is drawn according to $\lambda$ and revealed to the auctioneer but not the bidders; (c) The auctioneer reveals a public signal $\sigma\sim\varphi(\theta)$ to all the bidders; (d) A valuation matrix $\mathcal{V}\in^{n\times m}$ is drawn according to $\mathcal{D}$, and each player $i$ learns his value $\mathcal{V}_{i,j}$ for each potential item $j$; (e) Finally, a second-price auction for the item is run.

As an example, consider an auction for an umbrella: the state of nature $\theta$ can be the weather tomorrow, which determines the utility $\mathcal{V}_{i,\theta}$ of an umbrella to player $i$. We assume that $\lambda$ and $\mathcal{D}$ are independent. We also emphasize that a bidder knows nothing about $\theta$ other than its distribution $\lambda$ and the public signal $\sigma$, and the auctioneer knows nothing about $\mathcal{V}$ besides its distribution $\mathcal{D}$ prior to running the auction.

We adopt the (unique) dominant-strategy truth-telling equilibrium as our solution concept. Specifically, given a signaling scheme $\varphi:\Theta\to\Sigma$ and a signal $\sigma\in\Sigma$, in the subgame corresponding to $\sigma$ it is a dominant strategy for player $i$ to bid $\operatorname*{E}_{\theta\sim\lambda}[\mathcal{V}_{i\theta}|\varphi(\theta)=\sigma]$ — his posterior expected value for the item conditioned on the received signal $\sigma$. Therefore the item goes to the player with maximum posterior expected value, at a price equal to the second-highest posterior expected value.

The algorithmic problem we consider is the one faced by the auctioneer in step (a) — namely computing an optimal signaling scheme — assuming the auctioneer looks to maximize expected revenue. It was shown in [EFG+12, BMS12] that polynomial-time algorithms exist for several special cases of this problem. However, the general problem was shown to be NP-hard even with 3 bidders — specifically, no additive FPTAS exists unless P = NP. In this section, we resolve the approximation complexity of this basic signaling problem by giving an additive PTAS. We note that variations of this problem were considered in [GNS07, GD13], with different constraints on the signaling scheme — the results in these works are not directly relevant to our model.

Given a signaling scheme $\varphi$ expressed as a decomposition $\{\nu_{\sigma},\mu_{\sigma}\}_{\sigma\in\Sigma}$ of the prior distribution $\lambda$, we can express the auctioneer’s expected revenue as

where the function $\mathop{max2}$ returns the second largest entry of a given vector, i.e. $\mathop{max2}(t)=t_{}$. To apply our main theorem, we need to show that the revenue in a subgame with posterior distribution $\mu\in\Delta_{m}$ — namely $\operatorname*{E}_{\mathcal{V}\sim\mathcal{D}}\mathop{max2}(\mathcal{V}\mu)$ — can be written in the form $g(W\mu)$ for a matrix $W$. To facilitate our discussion we assume that the valuation distribution $\mathcal{D}$ has finite support size $C$, though this is without loss of generality. Imagine we form a large matrix $W$ by stacking matrices in the support of $\mathcal{D}$ on top of each other. Formally, $W=[\mathcal{V}_{1}^{T},\mathcal{V}_{2}^{T},\cdots,\mathcal{V}_{C}^{T}]^{T}$ where $\mathcal{V}_{i}$ is the $i$th matrix in the support of $\mathcal{D}$. When matrix $\mathcal{V}_{i}$ is drawn from $\mathcal{D}$, we take the second-highest bid from the rows of $W$ corresponding to $\mathcal{V}_{i}$ (rows $(i-1)\cdot n+1$ to $i\cdot n$, where $n$ is the number players). For $S\subseteq[nC]$ and $t\in^{nC}$, let $\mathop{max2}_{S}(t)$ denote the second-highest value among entries of $t$ indexed by $S$. Then we can write the auctioneer’s expected revenue as