Peer prediction mechanisms incentivize self-interested agents to truthfully report their signals even in the absence of verification, by comparing agents' reports with their peers. We propose two new mechanisms, Source and Target Differential Peer Prediction, and prove very strong guarantees for a very general setting. Our Differential Peer Prediction mechanisms are strongly truthful: Truth-telling a strict Bayesian Nash equilibrium. Also, truth-telling pays strictly higher than any other equilibria, excluding permutation equilibria, which pays the same amount as truth-telling. The guarantees hold for asymmetric priors which the mechanisms need not know (prior-free) in the signal question setting. Moreover, they only require three agents, each of which submits a signal item report: one reports her forecast and the others their signals. Our proof technique is straightforward, conceptually motivated, and turns on the logarithmic scoring rule's special properties. Moreover, we can recast the Bayesian Truth Serum mechanism [11] into our framework. We can also extend our results to the setting of continuous signals with a slightly weaker guarantee on the optimality of the truthful equilibrium.

We investigate traffic routing both from the perspective of real world data as well as theory. First, we reveal through data analytics a natural but previously uncaptured regularity of real world routing behavior. Agents only consider paths whose free-flow costs (informally their lengths) are within a small multiplicative constant of the optimal free-flow cost path connecting their source and destination. We complement our data analytics with a robust theoretical framework, by providing provably tight bounds on the price of anarchy for arbitrary classes of cost functions, and then we apply such results to the case of polynomial cost functions.

We consider the problem of online resume-filtering, in which resumes are presented to an algorithm one-by-one, and the algorithm must give immediate decisions on whether to grant the applicants interviews. We cast this problem as a secretary problem, and seek to develop competitive algorithms. Algorithms which sift through applications typically numerically score applicants, providing a basis for comparison. However, there is prevalence of bias in evaluations of applicants from different demographic groups, and these complex socio-economic issues pose unique modelling challenges. To address these issues, we introduce poset bias, which assumes that the algorithm can only observe rankings of applicants according to a fixed (but unknown) partial order. This allows for a more individualized notion of bias compared to existing models. Under this model, we present an algorithm with an order-optimal competitive ratio, and we conduct an empirical study on a public dataset to compare the performance of several algorithms.

We investigate revenue guarantees for auction mechanisms in a model where a distribution is specified for each bidder, but only some of the distributions are correct. The subset of bidders whose distribution is correctly specified (henceforth, the “green bidders”) is unknown to the auctioneer. The question we address is whether the auctioneer can run a mechanism that is guaranteed to obtain at least as much revenue, in expectation, as would be obtained by running an optimal mechanism on the green bidders only. For single-parameter feasibility environments, we find that the answer depends on the feasibility constraint. For matroid environments, running the optimal mechanism using all the specified distributions (including the incorrect ones) guarantees at least as much revenue in expectation as running the optimal mechanism on the green bidders. For any feasibility constraint that is not a matroid, there exists a way of setting the specified distributions and the true distributions such that the opposite conclusion holds.

In this paper we introduce the Ad Types Problem, a generalization of the traditional positional auction model for ad allocation that better captures some of the challenges that arise when ads of different types need to be interspersed within a user feed of organic content. We give an efficient algorithm for the special case where there is no constraint on how frequently ads can be shown to the user, and prove hardness for the case where we need to enforce a minimum distance between two ads based on their type.