We present a simple theoretical framework, and corresponding practical procedures, for comparing probabilistic models on real data in a traditional machine learning setting. This framework is based on the theory of proper scoring rules, but requires
only basic algebra and probability theory to understand and verify. The theoretical concepts presented are well-studied, primarily in the statistics literature. The goal of this paper is to advocate their wider adoption for performance evaluation in empirical machine learning.
Prediction markets are often used as mechanisms to aggregate information about a future event, for example, whether a candidate will win an election. The event is typically assumed to be exogenous. In reality, participants may influence the outcome,
and therefore (1) running the prediction market could change the incentives of participants in the process that creates the outcome (for example, agents may want to change their vote in an election), and (2) simple results such as the myopic incentive compatibility of proper scoring rules no longer hold in the prediction market itself. We introduce a model of games of this kind, where agents first trade in a prediction market and then take an action that influences the market outcome. Our two-stage two-player model, despite its simplicity, captures two aspects of real-world prediction markets: (1) agents may directly influence the outcome, (2) some of the agents instrumental in deciding the outcome may not take part in the prediction market. We show that this game has two different types of perfect Bayesian equilibria, which we term LPP and HPP, depending on the values of the belief parameters: in the LPP domain, equilibrium prices reveal expected market outcomes conditional on the participants private information, whereas HPP equilibria are collusive -- participants effectively coordinate in an uninformative and untruthful way.
We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets
threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithms Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.
