We answer the following question: At $t=1$, an expert has (probabilistic) information about a random outcome X. In addition, the expert will obtain further information about $X$ as time passes, up to some time t=T+1 at which X will be publicly revealed. (How) Can a protocol be devised that induces the expert, as a strict best response, to reveal at the outset his prior assessment of both X and the information flows he anticipates and, subsequently, what information he privately receives' (The protocol can provide the expert with payoffs that depend only on the realization of X, as well as any decisions he may take.) We show that this can be done with the following sort of protocol: At the penultimate time t=T, the expert chooses a payoff function from a menu of such functions, where the menu available to him was chosen by him at time $t=T-1$ from a menu of such menus, and so forth. We show that any protocol that affirmatively answers our question can be approximated by a protocol of the form described. We show how these results can be extended from discrete time to continuous time problems of this sort.

We study trading behavior and the properties of prices in informationally complex markets. Our model is based on the single-period version of the linear-normal framework of [Kyle 1985]. We allow for essentially arbitrary correlations among the random variables involved in the model: the true value of the traded asset, the signals of strategic traders, the signals of competitive market makers, and the demand coming from liquidity traders. We first show that there always exists a unique linear equilibrium, characterize it analytically, and illustrate its properties in a series of examples. We then use this equilibrium characterization to study the informational efficiency of prices as the number of strategic traders becomes large. If the demand from liquidity traders is uncorrelated with the true value of the asset or is positively correlated with it (conditional on other signals), then prices in large markets aggregate all available information. If, however, the demand from liquidity traders is negatively correlated with the true value of the asset, then prices in large markets aggregate all available information except that contained in liquidity demand.

No abstract available.

Prosper, the largest online social lending marketplace with nearly a million members and $178 million in funded loans, uses an auction amongst lenders to finance each loan. In each auction, the borrower specifies D, the amount he wants to borrow, and a maximum acceptable interest rate R. Lenders specify the amounts ai they want to lend, and bid on the interest rate, bi, they're willing to receive. Given that a basic premise of social lending is cheap loans for borrowers, how does the Prosper auction do in terms of the borrower's payment, when lenders are strategic agents with private true interest rates?

Motivated by the prevalence of online questionnaires in electronic commerce, and of multiple-choice questions in such questionnaires, we consider the problem of eliciting truthful answers to multiple-choice questions from a knowledgeable respondent. Specifically, each question is a statement regarding an uncertain future event, and is multiple-choice -- the responder must select exactly one of the given answers. The principal offers a payment, whose amount is a function of the answer selected and the true outcome (which the principal will eventually observe). This problem significantly generalizes recent work on truthful elicitation of distribution properties, which itself generalized a long line of work in elicitation of complete distributions. We provide necessary and sufficient conditions for the existence of payments that induce truthful answers, and give a characterization of those payments. We also study in greater details the common case of questions with ordinal answers, and illustrate our results with several examples of practical interest.

We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is #P-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.

We examine a class of wagering mechanisms designed to elicit truthful predictions from a group of people without requiring any outside subsidy. We propose a number of desirable properties for wagering mechanisms, identifying one mechanism - weighted-score wagering - that satisfies all of the properties. Moreover, we show that a single-parameter generalization of weighted-score wagering is the only mechanism that satisfies these properties. We explore some variants of the core mechanism based on practical considerations.

We investigate the problem of truthfully eliciting an expert's assessment of a property of a probability distribution, where a property is any real-valued function of the distribution such as mean or variance. We show that not all properties are elicitable; for example, the mean is elicitable and the variance is not. For those that are elicitable, we provide a representation theorem characterizing all payment (or "score") functions that induce truthful revelation. We also consider the elicitation of sets of properties. We then observe that properties can always be inferred from sets of elicitable properties. This naturally suggests the concept of elicitation complexity; the elicitation complexity of property is the minimal size of such a set implying the property. Finally we discuss applications to prediction markets.

We investigate asymptotically optimal keyword auctions, that is, auctions which maximize revenue as the number of bidders grows. We do so under two alternative behavioral assumptions. The first explicitly models the repeated nature of keyword auctions. It introduces a novel assumption on individual bidding, namely that bidders never overbid their value, and bid their actual value if shut out for long enough. Under these conditions we present a broad class of repeated auctions that are asymptotically optimal among all sequential auctions (a superset of repeated auctions). Those auctions have varying payment schemes but share the ranking method. The Google auction belongs to this class, but not the Yahoo auction, and indeed we show that the latter is not asymptotically optimal. (Nonetheless, with some additional distributional assumptions, the Yahoo auction can be shown to belong to a broad category of auctions that are asymptotically optimal among all auction mechanisms that do not rely on ad relevance.) We then look at the one-shot keyword auction, which can be taken to model repeated auctions in which relatively myopic bidders converge on the equilibrium of the full-information stage game. In this case we show that the Google auction remains asymptotically optimal and the Yahoo auction suboptimal. The distributional assumptions under which our theorems hold are quite general. We do however show that the Google auction is not asymptotically revenue-maximizing for general distributions.