David Pennock

NeurIPS Conference 2025 Conference Paper

Stochastically Dominant Peer Prediction

• Yichi Zhang
• Shengwei Xu
• Grant Schoenebeck
• David Pennock

Eliciting reliable human feedback is essential for many machine learning tasks, such as learning from noisy labels and aligning AI systems with human preferences. Peer prediction mechanisms incentivize truthful reporting without ground truth verification by scoring agents based on correlations with peers. Traditional mechanisms, which ensure that truth-telling maximizes the \textbf{expected scores} in equilibrium, can elicit honest information while assuming agents' utilities are \textbf{linear functions} of their scores. However, in practice, non-linear payment rules are usually preferred, or agents' utilities are inherently non-linear. We propose \emph{stochastically dominant truthfulness (SD-truthfulness)} as a stronger guarantee: the score distribution of truth-telling stochastically dominates all other strategies, incentivizing truthful reporting for a wide range of monotone utility functions. Our first observation is that no existing peer prediction mechanism naturally satisfies this criterion without strong assumptions. A simple solution - rounding scores into binary lotteries — can enforce SD-truthfulness, but often degrades \emph{sensitivity}, a key property related to fairness and statistical efficiency. We demonstrate how a more careful application of rounding can better preserve sensitivity. Furthermore, we introduce a new enforced agreement (EA) mechanism that is theoretically guaranteed to be SD-truthful in binary-signal settings and, under mild assumptions, empirically achieves the highest sensitivity among all known SD-truthful mechanisms.

AAMAS Conference 2023 Conference Paper

Artificial Prediction Markets Present a Novel Opportunity for Human-AI Collaboration

• Tatiana Chakravorti
• Vaibhav Singh
• Sarah Rajtmajer
• Michael McLaughlin
• Robert Fraleigh
• Christopher Griffin
• Anthony Kwasnica
• David Pennock

Despite high-profile successes in the field of Artificial Intelligence, machine-driven technologies still suffer important limitations, particularly for complex tasks where creativity, planning, common sense, intuition, or learning from limited data is required. These limitations motivate effective methods for human-machine collaboration. Our work makes two primary contributions. We thoroughly experiment with an artificial prediction market model to understand the effects of market parameters on model performance for benchmark classification tasks. We then demonstrate, through simulation, the impact of exogenous agents in the market, where these exogenous agents represent primitive human behaviors.

AAAI Conference 2022 System Paper

A Synthetic Prediction Market for Estimating Confidence in Published Work

• Sarah Rajtmajer
• Christopher Griffin
• Jian Wu
• Robert Fraleigh
• Laxmaan Balaji
• Anna Squicciarini
• Anthony Kwasnica
• David Pennock

Explainably estimating confidence in published scholarly work offers opportunity for faster and more robust scientific progress. We develop a synthetic prediction market to assess the credibility of published claims in the social and behavioral sciences literature. We demonstrate our system and detail our findings using a collection of known replication projects. We suggest that this work lays the foundation for a research agenda that creatively uses AI for peer review.

JAIR Journal 2019 Journal Article

Fair Allocation of Indivisible Goods to Asymmetric Agents

• Alireza Farhadi
• Mohammad Ghodsi
• Mohammad Taghi Hajiaghayi
• Sébastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

AAAI Conference 2018 Conference Paper

Incentive-Compatible Forecasting Competitions

• Jens Witkowski
• Rupert Freeman
• Jennifer Vaughan
• David Pennock
• Andreas Krause

We consider the design of forecasting competitions in which multiple forecasters make predictions about one or more independent events and compete for a single prize. We have two objectives: (1) to award the prize to the most accurate forecaster, and (2) to incentivize forecasters to report truthfully, so that forecasts are informative and forecasters need not spend any cognitive effort strategizing about reports. Proper scoring rules incentivize truthful reporting if all forecasters are paid according to their scores. However, incentives become distorted if only the best-scoring forecaster wins a prize, since forecasters can often increase their probability of having the highest score by reporting extreme beliefs. Even if forecasters do report truthfully, awarding the prize to the forecaster with highest score does not guarantee that high-accuracy forecasters are likely to win; in extreme cases, it can result in a perfect forecaster having zero probability of winning. In this paper, we introduce a truthful forecaster selection mechanism. We lower-bound the probability that our mechanism selects the most accurate forecaster, and give rates for how quickly this bound approaches 1 as the number of events grows. Our techniques can be generalized to the related problems of outputting a ranking over forecasters and hiring a forecaster with high accuracy on future events.

AAAI Conference 2017 Conference Paper

Crowdsourced Outcome Determination in Prediction Markets

• Rupert Freeman
• Sebastien Lahaie
• David Pennock

A prediction market is a useful means of aggregating information about a future event. To function, the market needs a trusted entity who will verify the true outcome in the end. Motivated by the recent introduction of decentralized prediction markets, we introduce a mechanism that allows for the outcome to be determined by the votes of a group of arbiters who may themselves hold stakes in the market. Despite the potential conflict of interest, we derive conditions under which we can incentivize arbiters to vote truthfully by using funds raised from market fees to implement a peer prediction mechanism. Finally, we investigate what parameter values could be used in a real-world implementation of our mechanism.

AAMAS Conference 2017 Conference Paper

Fair Allocation of Indivisible Goods with Different Entitlements

• Alireza Farhadi
• MohammadTaghi Hajiaghayi
• Mohammad Ghodsi
• Sebastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang [14] wherein the agents are assumed to be symmetric. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Next, we assume that the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. We show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items. (The full version of the paper is available in https: //arxiv. org/abs/1703. 01649.) CCS Concepts •Computing methodologies → Multi-agent systems;

AAAI Conference 2014 Conference Paper

Betting Strategies, Market Selection, and the Wisdom of Crowds

• Willemien Kets
• David Pennock
• Rajiv Sethi
• Nisarg Shah

We investigate the limiting behavior of trader wealth and prices in a simple prediction market with a finite set of participants having heterogeneous beliefs. Traders bet repeatedly on the outcome of a binary event with fixed Bernoulli success probability. A class of strategies, including (fractional) Kelly betting and constant relative risk aversion (CRRA) are considered. We show that when traders are willing to risk only a small fraction of their wealth in any period, belief heterogeneity can persist indefinitely; if bets are large in proportion to wealth then only the most accurate belief type survives. The market price is more accurate in the long run when traders with less accurate beliefs also survive. That is, the survival of traders with heterogeneous beliefs, some less accurate than others, allows the market price to better reflect the objective probability of the event in the long run.

AAMAS Conference 2012 Conference Paper

Learning Performance of Prediction Markets with Kelly Bettors

• Alina Beygelzimer
• John Langford
• David Pennock

AAMAS Conference 2012 Conference Paper

TrustBets: Betting over an IOU Network

• Sharad Goel
• Mohammad Mahdian
• David Pennock
• Daniel Reeves

We consider the problem of operating a gambling market where players pay with IOUs instead of cash, and where in general not everyone trusts everyone else. Players declare their degree of trust in other players—for example, Alice trusts Bob for up to ten dollars, and Bob trusts Carol up to twenty dollars. The system determines what bets are acceptable according to the trust network. For example, Carol may be able to place a bet where she is at risk of losing ten dollars to Alice, even if Alice doesn’t trust Carol directly, because the IOU can be routed through Bob. We show that if agents can bet on n events with binary outcomes, the problem of determining whether a collection of bets is acceptable is NP-hard. In the special case when the trust network is a tree, the problem can be solved in polynomial time using a maximum flow algorithm.

NeurIPS Conference 2004 Conference Paper

Co-Validation: Using Model Disagreement on Unlabeled Data to Validate Classification Algorithms

• Omid Madani
• David Pennock
• Gary Flake

In the context of binary classification, we define disagreement as a mea- sure of how often two independently-trained models differ in their clas- sification of unlabeled data. We explore the use of disagreement for error estimation and model selection. We call the procedure co-validation, since the two models effectively (in)validate one another by comparing results on unlabeled data, which we assume is relatively cheap and plen- tiful compared to labeled data. We show that per-instance disagreement is an unbiased estimate of the variance of error for that instance. We also show that disagreement provides a lower bound on the prediction (gen- eralization) error, and a tight upper bound on the "variance of prediction error", or the variance of the average error across instances, where vari- ance is measured across training sets. We present experimental results on several data sets exploring co-validation for error estimation and model selection. The procedure is especially effective in active learning set- tings, where training sets are not drawn at random and cross validation overestimates error.

NeurIPS Conference 2002 Conference Paper

A Maximum Entropy Approach to Collaborative Filtering in Dynamic, Sparse, High-Dimensional Domains

• Dmitry Pavlov
• David Pennock

We develop a maximum entropy (maxent) approach to generating recom- mendations in the context of a user’s current navigation stream, suitable for environments where data is sparse, high-dimensional, and dynamic— conditions typical of many recommendation applications. We address sparsity and dimensionality reduction by first clustering items based on user access patterns so as to attempt to minimize the apriori probabil- ity that recommendations will cross cluster boundaries and then recom- mending only within clusters. We address the inherent dynamic nature of the problem by explicitly modeling the data as a time series; we show how this representational expressivity fits naturally into a maxent frame- work. We conduct experiments on data from ResearchIndex, a popu- lar online repository of over 470, 000 computer science documents. We show that our maxent formulation outperforms several competing algo- rithms in offline tests simulating the recommendation of documents to ResearchIndex users.