Evaluating Multiple Guesses by an Adversary via a Tunable Loss Function

We consider a problem of guessing, wherein an adversary is interested in knowing the value of the realization of a discrete random variable $X$ on observing another correlated random variable $Y$. The adversary can make multiple (say, $k$) guesses. The adversarys guessing strategy is assumed to minimize $alpha$-loss, a class of tunable loss functions parameterized by $alpha$. It has been shown before that this loss function captures well known loss functions including the exponential loss ($alpha=1/2$), the log-loss ($alpha=1$) and the $0$-$1$ loss ($alpha=infty$). We completely characterize the optimal adversarial strategy and the resulting expected $alpha$-loss, thereby recovering known results for $alpha=infty$. We define an information leakage measure from the $k$-guesses setup and derive a condition under which the leakage is unchanged from a single guess.