Sanmay Das

AAAI Conference 2026 Conference Paper

Optimally Auditing Adversarial Agents

• Sanmay Das
• Fang-Yi Yu
• Yuang Zhang

Fraud can pose a challenge in many resource allocation domains, including social service delivery and credit provision. For example, agents may misreport private information in order to gain benefits or access to credit. To mitigate this, a principal can design strategic audits to verify claims and penalize misreporting. In this paper, we introduce a general model of audit policy design as a principal-agent game with multiple agents, where the principal commits to an audit policy, and agents collectively choose an equilibrium that minimizes the principal’s utility. We examine both adaptive and non-adaptive settings, depending on whether the principal's policy can be responsive to the distribution of agent reports. Our work provides efficient algorithms for computing optimal audit policies in both settings and extends these results to a setting with limited audit budgets.

AAAI Conference 2025 Conference Paper

Active Geospatial Search for Efficient Tenant Eviction Outreach

• Anindya Sarkar
• Alex DiChristofano
• Sanmay Das
• Patrick J. Fowler
• Nathan Jacobs
• Yevgeniy Vorobeychik

Tenant evictions threaten housing stability and are a major concern for many cities. An open question concerns whether data-driven methods enhance outreach programs that target at-risk tenants to mitigate their risk of eviction. We propose a novel active geospatial search (AGS) modeling framework for this problem. AGS integrates property-level information in a search policy that identifies a sequence of rental units to canvas to both determine their eviction risk and provide support if needed. We propose a hierarchical reinforcement learning approach to learn a search policy for AGS that scales to large urban areas containing thousands of parcels, balancing exploration and exploitation and accounting for travel costs and a budget constraint. Crucially, the search policy adapts online to newly discovered information about evictions. Evaluation using eviction data for a large urban area demonstrates that the proposed framework and algorithmic approach are considerably more effective at sequentially identifying eviction cases than baseline methods.

AAAI Conference 2024 Conference Paper

Discretionary Trees: Understanding Street-Level Bureaucracy via Machine Learning

• Gaurab Pokharel
• Sanmay Das
• Patrick Fowler

Street-level bureaucrats interact directly with people on behalf of government agencies to perform a wide range of functions, including, for example, administering social services and policing. A key feature of street-level bureaucracy is that the civil servants, while tasked with implementing agency policy, are also granted significant discretion in how they choose to apply that policy in individual cases. Using that discretion could be beneficial, as it allows for exceptions to policies based on human interactions and evaluations, but it could also allow biases and inequities to seep into important domains of societal resource allocation. In this paper, we use machine learning techniques to understand street-level bureaucrats' behavior. We leverage a rich dataset that combines demographic and other information on households with information on which homelessness interventions they were assigned during a period when assignments were not formulaic. We find that caseworker decisions in this time are highly predictable overall, and some, but not all of this predictivity can be captured by simple decision rules. We theorize that the decisions not captured by the simple decision rules can be considered applications of caseworker discretion. These discretionary decisions are far from random in both the characteristics of such households and in terms of the outcomes of the decisions. Caseworkers typically only apply discretion to households that would be considered less vulnerable. When they do apply discretion to assign households to more intensive interventions, the marginal benefits to those households are significantly higher than would be expected if the households were chosen at random; there is no similar reduction in marginal benefit to households that are discretionarily allocated less intensive interventions, suggesting that caseworkers are using their knowledge and experience to improve outcomes for households experiencing homelessness.

AAMAS Conference 2024 Conference Paper

Geospatial Active Search for Preventing Evictions

• Anindya Sarkar
• Alex DiChristofano
• Sanmay Das
• Patrick J. Fowler
• Nathan Jacobs
• Yevgeniy Vorobeychik

Evictions are a threat to housing stability and a major concern for many cities. An open question is whether data-driven methods can enhance door-to-door outreach programs to target at-risk tenants. We model this problem using a new framework we term geospatial active search. Geospatial Active Search integrates visual information such as satellite imagery along with tabular data such as property and neighborhood-level information to create an online exploration plan. We develop an approach for the implementation of Geospatial Active Search in St. Louis to find properties containing tenants who will have an eviction filed against them.

IJCAI Conference 2024 Conference Paper

The Impact of Features Used by Algorithms on Perceptions of Fairness

• Andrew Estornell
• Tina Zhang
• Sanmay Das
• Chien-Ju Ho
• Brendan Juba
• Yevgeniy Vorobeychik

We investigate perceptions of fairness in the choice of features that algorithms use about individuals in a simulated gigwork employment experiment. First, a collection of experimental participants (the selectors) were asked to recommend an algorithm for making employment decisions. Second, a different collection of participants (the workers) were told about the setup, and a subset were ostensibly selected by the algorithm to perform an image labeling task. For both selector and worker participants, algorithmic choices differed principally in the inclusion of features that were non-volitional, and either directly relevant to the task, or for which relevance is not evident except for these features resulting in higher accuracy. We find that the selectors had a clear predilection for the more accurate algorithms, which they also judged as more fair. Worker sentiments were considerably more nuanced. Workers who were hired were largely indifferent among the algorithms. In contrast, workers who were not hired exhibited considerably more positive sentiments for algorithms that included non-volitional but relevant features. However, workers with disadvantaged values of non-volitional features exhibited more negative sentiment towards their use than the average, although the extent of this appears to depend considerably on the nature of such features.

AAMAS Conference 2023 Conference Paper

Counterfactually Fair Dynamic Assignment: A Case Study on Policing

• Tasfia Mashiat
• Xavier Gitiaux
• Huzefa Rangwala
• Sanmay Das

Resource assignment algorithms for decision-making in dynamic environments have been shown to sometimes lead to negative impacts on individuals from minority populations. We propose a framework for algorithmic assignment of scarce resources in a dynamic setting that seeks to minimize concerns around unfairness and the potential for runaway feedback loops that create injustices. Our model estimates an underlying true latent confounder in a biased dataset, and makes allocation decisions based on a notion of fair intervention. We present evidence for the plausibility of our model by analyzing a novel dataset obtained from the City of Chicago through FOIA requests, and plan to release this dataset along with a visualization tool for use by various stakeholders. We also show that, in a simulated environment, our counterfactually fair policy can allocate limited resources near optimally, and better than baseline alternatives.

JAIR Journal 2023 Journal Article

Fair and Efficient Allocation of Scarce Resources Based on Predicted Outcomes: Implications for Homeless Service Delivery

• Amanda R. Kube
• Sanmay Das
• Patrick J. Fowler

Artificial intelligence, machine learning, and algorithmic techniques in general, provide two crucial abilities with the potential to improve decision-making in the context of allocation of scarce societal resources. They have the ability to flexibly and accurately model treatment response at the individual level, potentially allowing us to better match available resources to individuals. In addition, they have the ability to reason simultaneously about the effects of matching sets of scarce resources to populations of individuals. In this work, we leverage these abilities to study algorithmic allocation of scarce societal resources in the context of homelessness. In communities throughout the United States, there is constant demand for an array of homeless services intended to address different levels of need. Allocations of housing services must match households to appropriate services that continuously fluctuate in availability, while inefficiencies in allocation could “waste” scarce resources as households will remain in-need and re-enter the homeless system, increasing the overall demand for homeless services. This complex allocation problem introduces novel technical and ethical challenges. Using administrative data from a regional homeless system, we formulate the problem of “optimal” allocation of resources given data on households with need for homeless services. The optimization problem aims to allocate available resources such that predicted probabilities of household re-entry are minimized. The key element of this work is its use of a counterfactual prediction approach that predicts household probabilities of re-entry into homeless services if assigned to each service. Through these counterfactual predictions, we find that this approach has the potential to improve the efficiency of the homeless system by reducing re-entry, and, therefore, system-wide demand. However, efficiency comes with trade-offs - a significant fraction of households are assigned to services that increase probability of re-entry. To address this issue as well as the inherent fairness considerations present in any context where there are insufficient resources to meet demand, we discuss the efficiency, equity, and fairness issues that arise in our work and consider potential implications for homeless policies.

IJCAI Conference 2023 Conference Paper

Incentivizing Recourse through Auditing in Strategic Classification

• Andrew Estornell
• Yatong Chen
• Sanmay Das
• Yang Liu
• Yevgeniy Vorobeychik

The increasing automation of high-stakes decisions with direct impact on the lives and well-being of individuals raises a number of important considerations. Prominent among these is strategic behavior by individuals hoping to achieve a more desirable outcome. Two forms of such behavior are commonly studied: 1) misreporting of individual attributes, and 2) recourse, or actions that truly change such attributes. The former involves deception, and is inherently undesirable, whereas the latter may well be a desirable goal insofar as it changes true individual qualification. We study misreporting and recourse as strategic choices by individuals within a unified framework. In particular, we propose auditing as a means to incentivize recourse actions over attribute manipulation, and characterize optimal audit policies for two types of principals, utility-maximizing and recourse-maximizing. Additionally, we consider subsidies as an incentive for recourse over manipulation, and show that even a utility-maximizing principal would be willing to devote a considerable amount of audit budget to providing such subsidies. Finally, we consider the problem of optimizing fines for failed audits, and bound the total cost incurred by the population as a result of audits.

AAAI Conference 2023 Conference Paper

Popularizing Fairness: Group Fairness and Individual Welfare

• Andrew Estornell
• Sanmay Das
• Brendan Juba
• Yevgeniy Vorobeychik

Group-fair learning methods typically seek to ensure that some measure of prediction efficacy for (often historically) disadvantaged minority groups is comparable to that for the majority of the population. When a principal seeks to adopt a group-fair approach to replace another, the principal may face opposition from those who feel they may be harmed by the switch, and this, in turn, may deter adoption. We propose that a potential mitigation to this concern is to ensure that a group-fair model is also popular, in the sense that, for a majority of the target population, it yields a preferred distribution over outcomes compared with the conventional model. In this paper, we show that state of the art fair learning approaches are often unpopular in this sense. We propose several efficient algorithms for postprocessing an existing group-fair learning scheme to improve its popularity while retaining fairness. Through extensive experiments, we demonstrate that the proposed postprocessing approaches are highly effective in practice.

AAAI Conference 2022 Conference Paper

Local Justice and the Algorithmic Allocation of Scarce Societal Resources

• Sanmay Das

AI is increasingly used to aid decision-making about the allocation of scarce societal resources, for example housing for homeless people, organs for transplantation, and food donations. Recently, there have been several proposals for how to design objectives for these systems that attempt to achieve some combination of fairness, efficiency, incentive compatibility, and satisfactory aggregation of stakeholder preferences. This paper lays out possible roles and opportunities for AI in this domain, arguing for a closer engagement with the political philosophy literature on local justice, which provides a framework for thinking about how societies have over time framed objectives for such allocation problems. It also discusses how we may be able to integrate into this framework the opportunities and risks opened up by the ubiquity of data and the availability of algorithms that can use them to make accurate predictions about the future.

AAMAS Conference 2021 Conference Paper

Efficient Nonmyopic Online Allocation of Scarce Reusable Resources

• Zehao Dong
• Sanmay Das
• Patrick Fowler
• Chien-Ju Ho

We study settings where a set of identical, reusable resources must be allocated in an online fashion to arriving agents. Each arriving agent is patient and willing to wait for some period of time to be matched. When matched, each agent occupies a resource for a certain amount of time, and then releases it, gaining some utility from having done so. The goal of the system designer is to maximize overall utility given some prior knowledge of the distribution of arriving agents. We are particularly interested in settings where demand for the resources far outstrips supply, as is typical in the provision of social services, for example homelessness resources. We formulate this problem as online bipartite matching with reusable resources and patient agents. We develop new, efficient nonmyopic algorithms for this class of problems, and compare their performance with that of greedy algorithms in a variety of simulated settings, as well as in a setting calibrated to real-world data on household demand for homelessness services. We find substantial overall welfare benefits to using our nonmyopic algorithms, particularly in more extreme settings – those where agents are unwilling or unable to wait for resources, and where the ratio of resource demand to supply is particularly high.

AAAI Conference 2021 Conference Paper

Incentivizing Truthfulness Through Audits in Strategic Classification

• Andrew Estornell
• Sanmay Das
• Yevgeniy Vorobeychik

In many societal resource allocation domains, machine learning methods are increasingly used to either score or rank agents in order to decide which ones should receive either resources (e. g. , homeless services) or scrutiny (e. g. , child welfare investigations) from social services agencies. An agency’s scoring function typically operates on a feature vector that contains a combination of self-reported features and information available to the agency about individuals or households. This can create incentives for agents to misrepresent their self-reported features in order to receive resources or avoid scrutiny, but agencies may be able to selectively audit agents to verify the veracity of their reports. We study the problem of optimal auditing of agents in such settings. When decisions are made using a threshold on an agent’s score, the optimal audit policy has a surprisingly simple structure, uniformly auditing all agents who could benefit from lying. While this policy can, in general be hard to compute because of the difficulty of identifying the set of agents who could benefit from lying given a complete set of reported types, we also present necessary and sufficient conditions under which it is tractable. We show that the scarce resource setting is more difficult, and exhibit an approximately optimal audit policy in this case. In addition, we show that in either setting verifying whether it is possible to incentivize exact truthfulness is hard even to approximate. However, we also exhibit sufficient conditions for solving this problem optimally, and for obtaining good approximations.

AAAI Conference 2021 Conference Paper

Scarce Societal Resource Allocation and the Price of (Local) Justice

• Quan Nguyen
• Sanmay Das
• Roman Garnett

We consider the allocation of scarce societal resources, where a central authority decides which individuals receive which resources under capacity or budget constraints. Several algorithmic fairness criteria have been proposed to guide these procedures, each quantifying a notion of local justice to ensure the allocation is aligned with the principles of the local institution making the allocation. For example, the efficient allocation maximizes overall social welfare, whereas the leximin assignment seeks to help the “neediest first. ” Although the “price of fairness” (PoF) of leximin has been studied in prior work, we expand on these results by exploiting the structure inherent in real-world scenarios to provide tighter bounds. We further propose a novel criterion – which we term LoINC (leximin over individually normalized costs) – that maximizes a different but commonly used notion of local justice: prioritizing those benefiting the most from receiving the resources. We derive analogous PoF bounds for LoINC, showing that the price of LoINC is typically much lower than that of leximin. We provide extensive experimental results using both synthetic data and in a real-world setting considering the efficacy of different homelessness interventions. These results show that the empirical PoF tends to be substantially lower than worst-case bounds would imply and allow us to characterize situations where the price of LoINC fairness can be high.

AAAI Conference 2020 Conference Paper

Deception through Half-Truths

• Andrew Estornell
• Sanmay Das
• Yevgeniy Vorobeychik

Deception is a fundamental issue across a diverse array of settings, from cybersecurity, where decoys (e. g. , honeypots) are an important tool, to politics that can feature politically motivated “leaks” and fake news about candidates. Typical considerations of deception view it as providing false information. However, just as important but less frequently studied is a more tacit form where information is strategically hidden or leaked. We consider the problem of how much an adversary can affect a principal’s decision by “half-truths”, that is, by masking or hiding bits of information, when the principal is oblivious to the presence of the adversary. The principal’s problem can be modeled as one of predicting future states of variables in a dynamic Bayes network, and we show that, while theoretically the principal’s decisions can be made arbitrarily bad, the optimal attack is NP-hard to approximate, even under strong assumptions favoring the attacker. However, we also describe an important special case where the dependency of future states on past states is additive, in which we can efficiently compute an approximately optimal attack. Moreover, in networks with a linear transition function we can solve the problem optimally in polynomial time.

UAI Conference 2020 Conference Paper

Election Control by Manipulating Issue Significance

• Andrew Estornell
• Sanmay Das
• Edith Elkind
• Yevgeniy Vorobeychik

Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control Rothe [2016]. One means of election control that has been proposed, pertinent to the spatial voting model, is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem becomes tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting behavior enables tractable manipulation.

AAAI Conference 2019 Conference Paper

Allocating Interventions Based on Predicted Outcomes: A Case Study on Homelessness Services

• Amanda Kube
• Sanmay Das
• Patrick J. Fowler

Modern statistical and machine learning methods are increasingly capable of modeling individual or personalized treatment effects. These predictions could be used to allocate different interventions across populations based on individual characteristics. In many domains, like social services, the availability of different possible interventions can be severely resource limited. This paper considers possible improvements to the allocation of such services in the context of homelessness service provision in a major metropolitan area. Using data from the homeless system, we use a counterfactual approach to show potential for substantial benefits in terms of reducing the number of families who experience repeat episodes of homelessness by choosing optimal allocations (based on predicted outcomes) to a fixed number of beds in different types of homelessness service facilities. Such changes in the allocation mechanism would not be without tradeoffs, however; a significant fraction of households are predicted to have a higher probability of re-entry in the optimal allocation than in the original one. We discuss the efficiency, equity and fairness issues that arise and consider potential implications for policy.

AAAI Conference 2019 Conference Paper

Revenue Enhancement via Asymmetric Signaling in Interdependent-Value Auctions

• Zhuoshu Li
• Sanmay Das

We consider the problem of designing the information environment for revenue maximization in a sealed-bid second price auction with two bidders. Much of the prior literature has focused on signal design in settings where bidders are symmetrically informed, or on the design of optimal mechanisms under fixed information structures. We study commonand interdependent-value settings where the mechanism is fixed (a second-price auction), but the auctioneer controls the signal structure for bidders. We show that in a standard common-value auction setting, there is no benefit to the auctioneer in terms of expected revenue from sharing information with the bidders, although there are effects on the distribution of revenues. In an interdependent-value model with mixed private- and common-value components, however, we show that asymmetric, information-revealing signals can increase revenue.

IJCAI Conference 2018 Conference Paper

Equilibrium Behavior in Competing Dynamic Matching Markets

• Zhuoshu Li
• Neal Gupta
• Sanmay Das
• John P. Dickerson

Rival markets like rideshare services, universities, and organ exchanges compete to attract participants, seeking to maximize their own utility at potential cost to overall social welfare. Similarly, individual participants in such multi-market systems also seek to maximize their individual utility. If entry is costly, they should strategically enter only a subset of the available markets. All of this decision making---markets competitively adapting their matching strategies and participants arriving, choosing which market(s) to enter, and departing from the system---occurs dynamically over time. This paper provides the first analysis of equilibrium behavior in dynamic competing matching market systems---first from the points of view of individual participants when market policies are fixed, and then from the points of view of markets when agents are stochastic. When compared to single markets running social-welfare-maximizing matching policies, losses in overall social welfare in competitive systems manifest due to both market fragmentation and the use of non-optimal matching policies. We quantify such losses and provide policy recommendations to help alleviate them in fielded systems.

AAMAS Conference 2018 Conference Paper

Faster Policy Adaptation in Environments with Exogeneity: A State Augmentation Approach

• Zhuoshu Li
• Zhitang Chen
• Pascal Poupart
• Sanmay Das
• Yanhui Geng

The reinforcement learning literature typically assumes fixed state transition functions for the sake of tractability. However, in many real-world tasks, the state transition function changes over time, and this change may be governed by exogenous variables outside of the control loop. This can make policy learning difficult. In this paper, we propose a new algorithm to address the aforementioned challenge by embedding the state transition functions at different timestamps into a Reproducing Kernel Hilbert Space; the exogenous variable, as the cause of the state transition evolution, is estimated by projecting the embeddings into the subspace that preserves maximum variance. By augmenting the observable state vector with the estimated exogenous variable, standard RL algorithms such as Q-learning are able to learn faster and better. Experiments with both synthetic and real data demonstrate the superiority of our proposed algorithm over standard and advanced variants of Q-learning algorithms in dynamic environments.

IJCAI Conference 2018 Conference Paper

The Promise and Perils of Myopia in Dynamic Pricing With Censored Information

• Meenal Chhabra
• Sanmay Das
• Ilya Ryzhov

A seller with unlimited inventory of a digital good interacts with potential buyers with i. i. d. valuations. The seller can adaptively quote prices to each buyer to maximize long-term profits, but does not know the valuation distribution exactly. Under a linear demand model, we consider two information settings: partially censored, where agents who buy reveal their true valuations after the purchase is completed, and completely censored, where agents never reveal their valuations. In the partially censored case, we prove that myopic pricing with a Pareto prior is Bayes optimal and has finite regret. In both settings, we evaluate the myopic strategy against more sophisticated look-aheads using three valuation distributions generated from real data on auctions of physical goods, keyword auctions, and user ratings, where the linear demand assumption is clearly violated. For some datasets, complete censoring actually helps, because the restricted data acts as a "regularizer" on the posterior, preventing it from being affected too much by outliers.

IJCAI Conference 2017 Conference Paper

Coordinated Versus Decentralized Exploration In Multi-Agent Multi-Armed Bandits

• Mithun Chakraborty
• Kai Yee Phoebe Chua
• Sanmay Das
• Brendan Juba

In this paper, we introduce a multi-agent multi-armed bandit-based model for ad hoc teamwork with expensive communication. The goal of the team is to maximize the total reward gained from pulling arms of a bandit over a number of epochs. In each epoch, each agent decides whether to pull an arm, or to broadcast the reward it obtained in the previous epoch to the team and forgo pulling an arm. These decisions must be made only on the basis of the agent’s private information and the public information broadcast prior to that epoch. We first benchmark the achievable utility by analyzing an idealized version of this problem where a central authority has complete knowledge of rewards acquired from all arms in all epochs and uses a multiplicative weights update algorithm for allocating arms to agents. We then introduce an algorithm for the decentralized setting that uses a value-of-information based communication strategy and an exploration-exploitation strategy based on the centralized algorithm, and show experimentally that it converges rapidly to the performance of the centralized method.

IJCAI Conference 2016 Conference Paper

A Symbolic Closed-Form Solution to Sequential Market Making with Inventory

• Shamin Kinathil
• Scott Sanner
• Sanmay Das
• Nicol
• aacute; s Della Penna

Market-makers serve an important role as providers of liquidity and order in financial markets, particularly during periods of high volatility. Optimal market-makers solve a sequential decision making problem, where they face an exploration versus exploitation dilemma at each time step. A belief state MDP based solution was presented by Das and Magdon-Ismail [NIPS, 2008]. This solution however, was closely tied to the choice of a Gaussian belief state prior and did not take asset inventory into consideration when calculating an optimal policy. In this work we introduce a novel continuous state POMDP framework which is the first to solve, exactly and in closed-form, the optimal market making problem with inventory, fixed asset value, arbitrary belief state priors, trader models and reward functions via symbolic dynamic programming. We use this novel model and solution to show that sequentially optimal policies are heavily inventory-dependent and calculate policies that operate with bounded loss guarantees under a variety of market models and conditions.

AAMAS Conference 2016 Conference Paper

An Agent-Based Model of Competition Between Financial Exchanges: Can Frequent Call Mechanisms Drive Trade Away from CDAs?

• Zhuoshu Li
• Sanmay Das

In the debate over high frequency trading, the frequent call (Call) mechanism has recently received considerable attention as a proposal for replacing the continuous double auction (CDA) mechanisms that currently run most financial markets. One natural question, which has begun to spur the development of new models, is the e↵ect of competition between platforms that use these two di↵erent mechanisms when agents can strategize over platform choice. In this paper we contribute to this nascent literature by developing an agent-based model of competition between a Call market and a CDA market. Our model incorporates patient informed traders (both high-frequency and not) who are willing to wait for order execution at their preferred price and impatient background traders who demand immediate execution. We show that there is a strong tendency for the Call market to absorb a significant fraction of trade under most equilibrium and approximate-equilibrium conditions. These equilibria typically lead to significantly higher welfare for the background traders, an important measure of social value, than the operation of an isolated CDA market.

IJCAI Conference 2016 Conference Paper

Trading on a Rigged Game: Outcome Manipulation in Prediction Markets

• Mithun Chakraborty
• Sanmay Das

Prediction markets are popular mechanisms for aggregating information about a future event. In situations where market participants may significantly influence the outcome, running the prediction market could change the incentives of participants in the process that creates the outcome. We propose a new game-theoretic model that captures two aspects of real-world prediction markets: (1) agents directly affect the outcome the market is predicting, (2) some outcome-deciders may not participate in the market. We show that this game has two types of equilibria: When some outcome-deciders are unlikely to participate in the market, equilibrium prices reveal expected market outcomes conditional on participants' private information, whereas when all outcome-deciders are likely to participate, equilibria are collusive - agents effectively coordinate in an uninformative and untruthful way.

NeurIPS Conference 2015 Conference Paper

Market Scoring Rules Act As Opinion Pools For Risk-Averse Agents

• Mithun Chakraborty
• Sanmay Das

A market scoring rule (MSR) – a popular tool for designing algorithmic prediction markets – is an incentive-compatible mechanism for the aggregation of probabilistic beliefs from myopic risk-neutral agents. In this paper, we add to a growing body of research aimed at understanding the precise manner in which the price process induced by a MSR incorporates private information from agents who deviate from the assumption of risk-neutrality. We first establish that, for a myopic trading agent with a risk-averse utility function, a MSR satisfying mild regularity conditions elicits the agent’s risk-neutral probability conditional on the latest market state rather than her true subjective probability. Hence, we show that a MSR under these conditions effectively behaves like a more traditional method of belief aggregation, namely an opinion pool, for agents’ true probabilities. In particular, the logarithmic market scoring rule acts as a logarithmic pool for constant absolute risk aversion utility agents, and as a linear pool for an atypical budget-constrained agent utility with decreasing absolute risk aversion. We also point out the interpretation of a market maker under these conditions as a Bayesian learner even when agent beliefs are static.

AAAI Conference 2015 Conference Paper

Price Evolution in a Continuous Double Auction Prediction Market With a Scoring-Rule Based Market Maker

• Mithun Chakraborty
• Sanmay Das
• Justin Peabody

The logarithmic market scoring rule (LMSR), the most common automated market making rule for prediction markets, is typically studied in the framework of dealer markets, where the market maker takes one side of every transaction. The continuous double auction (CDA) is a much more widely used microstructure for general financial markets in practice. In this paper, we study the properties of CDA prediction markets with zerointelligence traders in which an LMSR-style market maker participates actively. We extend an existing idea of Robin Hanson for integrating LMSR with limit order books in order to provide a new, self-contained market making algorithm that does not need “special” access to the order book and can participate as another trader. We find that, as expected, the presence of the market maker leads to generally lower bid-ask spreads and higher trader surplus (or price improvement), but, surprisingly, does not necessarily improve price discovery and market efficiency; this latter effect is more pronounced when there is higher variability in trader beliefs.

ICML Conference 2014 Conference Paper

Automated inference of point of view from user interactions in collective intelligence venues

• Sanmay Das
• Allen Lavoie

Empirical evaluation of trust and manipulation in large-scale collective intelligence processes is challenging. The datasets involved are too large for thorough manual study, and current automated options are limited. We introduce a statistical framework which classifies point of view based on user interactions. The framework works on Web-scale datasets and is applicable to a wide variety of collective intelligence processes. It enables principled study of such issues as manipulation, trustworthiness of information, and potential bias. We demonstrate the model’s effectiveness in determining point of view on both synthetic data and a dataset of Wikipedia user interactions. We build a combined model of topics and points-of-view on the entire history of English Wikipedia, and show how it can be used to find potentially biased articles and visualize user interactions at a high level.

AAAI Conference 2013 Conference Paper

Instructor Rating Markets

• Mithun Chakraborty
• Sanmay Das
• Allen Lavoie
• Malik Magdon-Ismail
• Yonatan Naamad

We describe the design of Instructor Rating Markets (IRMs) where human participants interact through intelligent automated market-makers in order to provide dynamic collective feedback to instructors on the progress of their classes. The markets are among the first to enable the empirical study of prediction markets where traders can affect the very outcomes they are trading on. More than 200 students across the Rensselaer campus participated in markets for ten classes in the Fall 2010 semester. In this paper, we describe how we designed these markets in order to elicit useful information, and analyze data from the deployment. We show that market prices convey useful information on future instructor ratings and contain significantly more information than do past ratings. The bulk of useful information contained in the price of a particular class is provided by students who are in that class, showing that the markets are serving to disseminate insider information. At the same time, we find little evidence of attempted manipulation by raters. The markets are also a laboratory for comparing different market designs and the resulting price dynamics, and we show how they can be used to compare market making algorithms.

AAAI Conference 2013 Conference Paper

On the Social Welfare of Mechanisms for Repeated Batch Matching

• Elliot Anshelevich
• Meenal Chhabra
• Sanmay Das
• Matthew Gerrior

We study hybrid online-batch matching problems, where agents arrive continuously, but are only matched in periodic rounds, when many of them can be considered simultaneously. Agents not getting matched in a given round remain in the market for the next round. This setting models several scenarios of interest, including many job markets as well as kidney exchange mechanisms. We consider the social utility of two commonly used mechanisms for such markets: one that aims for stability in each round (greedy), and one that attempts to maximize social utility in each round (max-weight). Surprisingly, we find that in the long term, the social utility of the greedy mechanism can be higher than that of the max-weight mechanism. We hypothesize that this is because the greedy mechanism behaves similarly to a soft threshold mechanism, where all connections below a certain threshold are rejected by the participants in favor of waiting until the next round. Motivated by this observation, we propose a method to approximately calculate the optimal threshold for an individual agent to use based on characteristics of the other agents participating, and demonstrate experimentally that social utility is high when all agents use this strategy. Thresholding can also be applied by the mechanism itself to improve social welfare; we demonstrate this with an example on graphs that model pairwise kidney exchange.

AAMAS Conference 2012 Conference Paper

Do Experts Help in Two-Sided Search?

• Yinon Nahum
• David Sarne
• Sanmay Das
• Onn Shehory

AAMAS Conference 2012 Conference Paper

On the Social Welfare of Mechanisms for Repeated Batch Matching

• Elliot Anshelevich
• Meenal Chhabra
• Sanmay Das
• Matthew Gerrior

We study hybrid online-batch matching problems, where agents arrive continuously, but are only matched in periodic rounds, when many of them can be considered simultaneously. Agents not getting matched in a given round remain in the market for the next round. This setting models several scenarios of interest, including many job markets as well as kidney exchange mechanisms. We consider the social utility of two commonly used mechanisms for such markets: one that aims for stability in each round (greedy), and one that attempts to maximize social utility in each round (maxweight). Surprisingly, we find that in the long term, the social utility of the greedy mechanism can be higher than that of the max-weight mechanism. We hypothesize that this is because the greedy mechanism behaves similarly to a soft threshold mechanism, where all connections below a certain threshold are rejected by the participants in favor of waiting until the next round. Motivated by this observation, we propose a method to approximately calculate the optimal threshold for an individual agent, based on characteristics of the other agents, and demonstrate empirically that social utility is high when all agents use this strategy.

JAAMAS Journal 2011 Journal Article

Anarchy, stability, and utopia: creating better matchings

• Elliot Anshelevich
• Sanmay Das
• Yonatan Naamad

Abstract Historically, the analysis of matching has centered on designing algorithms to produce stable matchings as well as on analyzing the incentive compatibility of matching mechanisms. Less attention has been paid to questions related to the social welfare of stable matchings in cardinal utility models. We examine the loss in social welfare that arises from requiring matchings to be stable, the natural equilibrium concept under individual rationality. While this loss can be arbitrarily bad under general preferences, when there is some structure to the underlying graph corresponding to natural conditions on preferences, we prove worst case bounds on the price of anarchy. Surprisingly, under simple distributions of utilities, the average case loss turns out to be significantly smaller than the worst-case analysis would suggest. Furthermore, we derive conditions for the existence of approximately stable matchings that are also close to socially optimal, demonstrating that adding small switching costs can make socially (near-)optimal matchings stable. Our analysis leads to several concomitant results of interest on the convergence of decentralized partner-switching algorithms, and on the impact of heterogeneity of tastes on social welfare.

AAMAS Conference 2011 Conference Paper

Expert-Mediated Search

• Meenal Chhabra
• Sanmay Das
• David Sarne

Increasingly in both traditional, and especially Internet-based marketplaces, knowledge is becoming a traded commodity. This paper considers the impact of the presence of knowledge-brokers, or experts, on search-based markets with noisy signals. For example, consider a consumer looking for a used car on a large Internet marketplace. She sees noisy signals of the true value of any car she looks at the advertisement for, and can disambiguate this signal by paying for the services of an expert (for example, getting a Carfax report, or taking the car to a mechanic for an inspection). Both the consumer and the expert are rational, self-interested agents. We present a model for such search environments, and analyze several aspects of the model, making three main contributions: (1) We derive the consumer's optimal search strategy in environments with noisy signals, with and without the option of consulting an expert; (2) We find the optimal strategy for maximizing the expert's profit; (3) We study the option of market designers to subsidize search in a way that improves overall social welfare. We illustrate our results in the context of a plausible distribution of signals and values.

AAMAS Conference 2011 Conference Paper

Learning the Demand Curve in Posted-Price Digital Goods Auctions

• Meenal Chhabra
• Sanmay Das

Online digital goods auctions are settings where a seller with an unlimited supply of goods (e. g. music or movie downloads) interacts with a stream of potential buyers. In the posted price setting, the seller makes a take-it-or-leave-it offer to each arriving buyer. We study the seller's revenue maximization problem in posted-price auctions of digital goods. We find that algorithms from the multi-armed bandit literature like UCB, which come with good regret bounds, can be slow to converge. We propose and study two alternatives: (1) a scheme based on using Gittins indices with priors that make appropriate use of domain knowledge; (2) a new learning algorithm, LLVD, that assumes a linear demand curve, and maintains a Beta prior over the free parameter using a moment-matching approximation. LLVD is not only (approximately) optimal for linear demand, but also learns fast and performs well when the linearity assumption is violated, for example in the cases of two natural valuation distributions, exponential and log-normal.

UAI Conference 2011 Conference Paper

Near-Optimal Target Learning With Stochastic Binary Signals

• Mithun Chakraborty
• Sanmay Das
• Malik Magdon-Ismail

ICRA Conference 2010 Conference Paper

Predictive State Representations for grounding human-robot communication

• Eric M. Meisner
• Sanmay Das
• Volkan Isler
• Jeffrey C. Trinkle
• Selma Sabanovic
• Linnda R. Caporael

Allowing robots to communicate naturally with humans is an important goal for social robotics. Most approaches have focused on building high-level probabilistic cognitive models. However, research in cognitive science shows that people often build common ground for communication with each other by seeking and providing evidence of understanding through behaviors like mimicry. Predictive State Representations (PSRs) allow one to build explicit, low-level models of the expected outcomes of actions, and are therefore well-suited for tasks that require providing such evidence of understanding. Using human-robot shadow puppetry as a prototype interaction study, we show that PSRs can be used successfully to both model human interactions, and to allow a robot to learn on-line how to engage a human in an interesting interaction.

NeurIPS Conference 2008 Conference Paper

Adapting to a Market Shock: Optimal Sequential Market-Making

• Sanmay Das
• Malik Magdon-Ismail

We study the profit-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the first optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher profits later.

AAMAS Conference 2008 Conference Paper

The Effects of Market-Making on Price Dynamics

• Sanmay Das

This paper studies market-makers, agents responsible for maintaining liquidity and orderly price transitions in markets. Market-makers include major firms making markets on global stock exchanges, as well as software agents that run behind the scenes on novel electronic markets like prediction markets. We use a sophisticated model of marketmaking to build richer agent-based models of markets and show how these models can be useful both in understanding properties of existing markets and in predicting the impacts of structural changes. For example, we show how competition among market-makers can lead to significantly faster price discovery following a jump in the true value of an asset. We also show that myopic profit-maximization, apart from leading to poor market quality, is sub-optimal even for a monopolistic market-maker. This observation leads to an interesting characterization of the market-maker’s explorationexploitation dilemma as a tradeoff between price discovery and profit-taking.

IJCAI Conference 2005 Conference Paper

Two-Sided Bandits and the Dating Market

• Sanmay Das
• Emir

We study the decision problems facing agents in repeated matching environments with learning, or two-sided bandit problems, and examine the dating market, in which men and women repeatedly go out on dates and learn about each other, as an example. We consider three natural matching mechanisms and empirically examine properties of these mechanisms, focusing on the asymptotic stability of the resulting matchings when the agents use a simple learning rule coupled with an -greedy exploration policy. Matchings tend to be more stable when agents are patient in two different ways — if they are more likely to explore early or if they are more optimistic. However, the two forms of patience do not interact well in terms of increasing the probability of stable outcomes. We also define a notion of regret for the two-sided problem and study the distribution of regrets under the different matching mechanisms.

AIJ Journal 2002 Journal Article

The influence of social norms and social consciousness on intention reconciliation

• Barbara J. Grosz
• Sarit Kraus
• David G. Sullivan
• Sanmay Das

ICML Conference 2001 Conference Paper

Filters, Wrappers and a Boosting-Based Hybrid for Feature Selection

• Sanmay Das