Arrow Research search

Author name cluster

John P. Dickerson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
1 author row

Possible papers

23

AAAI Conference 2023 Conference Paper

Do Invariances in Deep Neural Networks Align with Human Perception?

  • Vedant Nanda
  • Ayan Majumdar
  • Camila Kolling
  • John P. Dickerson
  • Krishna P. Gummadi
  • Bradley C. Love
  • Adrian Weller

An evaluation criterion for safe and trustworthy deep learning is how well the invariances captured by representations of deep neural networks (DNNs) are shared with humans. We identify challenges in measuring these invariances. Prior works used gradient-based methods to generate identically represented inputs (IRIs), ie, inputs which have identical representations (on a given layer) of a neural network, and thus capture invariances of a given network. One necessary criterion for a network's invariances to align with human perception is for its IRIs look 'similar' to humans. Prior works, however, have mixed takeaways; some argue that later layers of DNNs do not learn human-like invariances yet others seem to indicate otherwise. We argue that the loss function used to generate IRIs can heavily affect takeaways about invariances of the network and is the primary reason for these conflicting findings. We propose an adversarial regularizer on the IRI generation loss that finds IRIs that make any model appear to have very little shared invariance with humans. Based on this evidence, we argue that there is scope for improving models to have human-like invariances, and further, to have meaningful comparisons between models one should use IRIs generated using the regularizer-free loss. We then conduct an in-depth investigation of how different components (eg architectures, training losses, data augmentations) of the deep learning pipeline contribute to learning models that have good alignment with humans. We find that architectures with residual connections trained using a (self-supervised) contrastive loss with l_p ball adversarial data augmentation tend to learn invariances that are most aligned with humans. Code: github.com/nvedant07/Human-NN-Alignment

AAAI Conference 2023 Conference Paper

Networked Restless Bandits with Positive Externalities

  • Christine Herlihy
  • John P. Dickerson

Restless multi-armed bandits are often used to model budget-constrained resource allocation tasks where receipt of the resource is associated with an increased probability of a favorable state transition. Prior work assumes that individual arms only benefit if they receive the resource directly. However, many allocation tasks occur within communities and can be characterized by positive externalities that allow arms to derive partial benefit when their neighbor(s) receive the resource. We thus introduce networked restless bandits, a novel multi-armed bandit setting in which arms are both restless and embedded within a directed graph. We then present Greta, a graph-aware, Whittle index-based heuristic algorithm that can be used to efficiently construct a constrained reward-maximizing action vector at each timestep. Our empirical results demonstrate that Greta outperforms comparison policies across a range of hyperparameter values and graph topologies. Code and appendices are available at https://github.com/crherlihy/networked_restless_bandits.

AAAI Conference 2023 Conference Paper

Rawlsian Fairness in Online Bipartite Matching: Two-Sided, Group, and Individual

  • Seyed Esmaeili
  • Sharmila Duppala
  • Davidson Cheng
  • Vedant Nanda
  • Aravind Srinivasan
  • John P. Dickerson

Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator’s (expected) profit. Since fairness has become an important consideration that was ignored in the existing algorithms a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator’s profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.

AAAI Conference 2022 Conference Paper

Amortized Generation of Sequential Algorithmic Recourses for Black-Box Models

  • Sahil Verma
  • Keegan Hines
  • John P. Dickerson

Explainable machine learning (ML) has gained traction in recent years due to the increasing adoption of ML-based systems in many sectors. Algorithmic Recourses (ARs) provide “what if” feedback of the form “if an input datapoint were x0 instead of x, then an ML-based system’s output would be y0 instead of y. ” ARs are attractive due to their actionable feedback, amenability to existing legal frameworks, and fidelity to the underlying ML model. Yet, current AR approaches are single shot—that is, they assume x can change to x0 in a single time period. We propose a novel stochastic-control-based approach that generates sequential ARs, that is, ARs that allow x to move stochastically and sequentially across intermediate states to a final state x0. Our approach is model agnostic and black box. Furthermore, the calculation of ARs is amortized such that once trained, it applies to multiple datapoints without the need for re-optimization. In addition to these primary characteristics, our approach admits optional desiderata such as adherence to the data manifold, respect for causal relations, and sparsity—identified by past research as desirable properties of ARs. We evaluate our approach using three real-world datasets and show successful generation of sequential ARs that respect other recourse desiderata.

AAMAS Conference 2022 Conference Paper

Group Fairness in Bandits with Biased Feedback

  • Candice Schumann
  • Zhi Lang
  • Nicholas Mattei
  • John P. Dickerson

We propose a novel formulation of group fairness with biased feedback in the contextual multi-armed bandit (CMAB) setting. In the CMAB setting, a sequential decision maker must, at each time step, choose an arm to pull from a finite set of arms after observing some context for each of the potential arm pulls. In our model, arms are partitioned into two or more sensitive groups based on some protected feature(s) (e. g. , age, race, or socio-economic status). Initial rewards received from pulling an arm may be distorted due to some unknown societal or measurement bias. We assume that in reality these groups are equal despite the biased feedback received by the agent. To alleviate this, we learn a societal bias term which can be used to both find the source of bias and to potentially fix the problem outside of the algorithm. We provide a novel algorithm that can accommodate this notion of fairness for an arbitrary number of groups, and provide a theoretical bound on the regret for our algorithm. We validate our algorithm using synthetic data and two real-world datasets for intervention settings wherein we want to allocate resources fairly across groups.

AAMAS Conference 2022 Conference Paper

Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual

  • Seyed A. Esmaeili
  • Sharmila Duppala
  • Vedant Nanda
  • Aravind Srinivasan
  • John P. Dickerson

Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator’s (expected) profit. Recent reports have shown that certain demographic groups may receive less favorable treatment under pure profit maximization. As a result, a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator’s profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.

AAAI Conference 2021 Conference Paper

Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints

  • Brian Brubach
  • Darshan Chakrabarti
  • John P. Dickerson
  • Aravind Srinivasan
  • Leonidas Tsepenekas

Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms.

AAAI Conference 2021 Conference Paper

Indecision Modeling

  • Duncan C. McElfresh
  • Lok Chan
  • Kenzie Doyle
  • Walter Sinnott-Armstrong
  • Vincent Conitzer
  • Jana Schaich Borg
  • John P. Dickerson

AI systems are often used to make or contribute to important decisions in a growing range of applications, including criminal justice, hiring, and medicine. Since these decisions impact human lives, it is important that the AI systems act in ways which align with human values. Techniques for preference modeling and social choice help researchers learn and aggregate peoples’ preferences, which are used to guide AI behavior; thus, it is imperative that these learned preferences are accurate. These techniques often assume that people are willing to express strict preferences over alternatives; which is not true in practice. People are often indecisive, and especially so when their decision has moral implications. The philosophy and psychology literature shows that indecision is a measurable and nuanced behavior—and that there are several different reasons people are indecisive. This complicates the task of both learning and aggregating preferences, since most of the relevant literature makes restrictive assumptions on the meaning of indecision. We begin to close this gap by formalizing several mathematical indecision models based on theories from philosophy, psychology, and economics; these models can be used to describe (indecisive) agent decisions, both when they are allowed to express indecision and when they are not. We test these models using data collected from an online survey where participants choose how to (hypothetically) allocate organs to patients waiting for a transplant.

AAAI Conference 2021 Conference Paper

Optimal Kidney Exchange with Immunosuppressants

  • Haris Aziz
  • Ágnes Cseh
  • John P. Dickerson
  • Duncan C. McElfresh

Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body’s ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.

AAAI Conference 2021 Conference Paper

Scalable Equilibrium Computation in Multi-agent Influence Games on Networks

  • Fotini Christia
  • Michael Curry
  • Constantinos Daskalakis
  • Erik Demaine
  • John P. Dickerson
  • MohammadTaghi Hajiaghayi
  • Adam Hesterberg
  • Marina Knittel

We provide a polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding (Ahmadinejad et al. 2014, 2015). In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? We show that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time; we test our model by computing equilibria using mirror descent for the two-agent case on random graphs.

IJCAI Conference 2020 Conference Paper

An Algorithm for Multi-Attribute Diverse Matching

  • Saba Ahmadi
  • Faez Ahmed
  • John P. Dickerson
  • Mark Fuge
  • Samir Khuller

Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e. g. , linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e. g. , country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application. The source code is made available at https: //github. com/faezahmed/diverse_matching.

AAAI Conference 2020 Short Paper

Clearing Kidney Exchanges via Graph Neural Network Guided Tree Search (Student Abstract)

  • Zeyu Zhao
  • John P. Dickerson

Kidney exchange is an organized barter market that allows patients with end-stage renal disease to trade willing donors—and thus kidneys—with other patient-donor pairs. The central clearing problem is to find an arrangement of swaps that maximizes the number of transplants. It is known to be NP-hard in almost all cases. Most existing approaches have modeled this problem as a mixed integer program (MIP), using classical branch-and-price-based tree search techniques to optimize. In this paper, we frame the clearing problem as a Maximum Weighted Independent Set (MWIS) problem, and use a Graph Neural Network guided Monte Carlo Tree Search to find a solution. Our initial results show that this approach outperforms baseline (non-optimal but scalable) algorithms. We believe that a learning-based optimization algorithm can improve upon existing approaches to the kidney exchange clearing problem.

AAAI Conference 2019 Conference Paper

Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu

In bipartite matching problems, vertices on one side of a bipartite graph are paired with those on the other. In its online variant, one side of the graph is available offline, while the vertices on the other side arrive online. When a vertex arrives, an irrevocable and immediate decision should be made by the algorithm; either match it to an available vertex or drop it. Examples of such problems include matching workers to firms, advertisers to keywords, organs to patients, and so on. Much of the literature focuses on maximizing the total relevance—modeled via total weight—of the matching. However, in many real-world problems, it is also important to consider contributions of diversity: hiring a diverse pool of candidates, displaying a relevant but diverse set of ads, and so on. In this paper, we propose the Online Submodular Bipartite Matching (OSBM) problem, where the goal is to maximize a submodular function f over the set of matched edges. This objective is general enough to capture the notion of both diversity (e. g. , a weighted coverage function) and relevance (e. g. , the traditional linear function)—as well as many other natural objective functions occurring in practice (e. g. , limited total budget in advertising settings). We propose novel algorithms that have provable guarantees and are essentially optimal when restricted to various special cases. We also run experiments on real-world and synthetic datasets to validate our algorithms.

AAMAS Conference 2019 Conference Paper

Online Resource Allocation with Matching Constraints

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Kanthi Kiran Sarpatwar
  • Aravind Srinivasan
  • Kun-Lung Wu
  • Pan Xu

Matching markets with historical data are abundant in many applications, e. g. , matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e. g. , candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi- Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit wi, j while consuming ae ∈ [0, 1]K quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it. ∗Part of this work is done when Pan Xu was an intern at the IBM T. J. Watson Research Center during the summer of 2016. Aravind Srinivasan’s research was supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc. Karthik Sankararaman’s research was supported in part by NSF Awards CNS-1010789 and CCF-1422569. John Dickerson’s research was supported by NSF IIS RI CAREER Award #1846237. Pan Xu’s research was supported by NSF Awards CNS-1010789, CCF-1422569 and NSF IIS RI CAREER Award #1846237. The authors also like to thank Google for a generous gift support. We thank Aditya Parameswaran and Xingjie Liu for useful discussions on datasets related to our problem. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

AAMAS Conference 2019 Conference Paper

The Diverse Cohort Selection Problem

  • Candice Schumann
  • Samsara N. Counts
  • Jeffrey S. Foster
  • John P. Dickerson

How should a firm allocate its limited interviewing resources to select the optimal cohort of new employees from a large set of job applicants? How should that firm allocate cheap but noisy resume screenings and expensive but in-depth in-person interviews? We view this problem through the lens of combinatorial pure exploration (CPE) in the multi-armed bandit setting, where a central learning agent performs costly exploration of a set of arms before selecting a final subset with some combinatorial structure. We generalize a recent CPE algorithm to the setting where arm pulls can have different costs and return different levels of information. We then prove theoretical upper bounds for a general class of arm-pulling strategies in this new setting. We apply our general algorithm to a real-world problem with combinatorial structure: incorporating diversity into university admissions. We take real data from admissions at one of the largest US-based computer science graduate programs and show that a simulation of our algorithm produces a cohort with hiring overall utility while spending comparable budget to the current admissions process at that university.

AAMAS Conference 2018 Conference Paper

Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu

Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this paper, we consider a special setting inspired from spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each worker-task assignment brings a distinct reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected rewards are maximized. To attack this challenge, we assume the arrival patterns of worker “types” and task “types” are not erratic and can be predicted from historical data. To be more specific, we consider a finite time horizon T and assume in each time-step, a single worker and task are sampled (i. e. , “arrive”) from two respective distributions independently, and this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online Task Assignment with Two-Sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0. 295. For the special case of OTA-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0. 343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all nonadaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0. 581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i. e. , all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.

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.

IJCAI Conference 2017 Conference Paper

Diverse Weighted Bipartite b-Matching

  • Faez Ahmed
  • John P. Dickerson
  • Mark Fuge

Bipartite matching, where agents on one side of a market are matched to agents or items on the other, is a classical problem in computer science and economics, with widespread application in healthcare, education, advertising, and general resource allocation. A practitioner's goal is typically to maximize a matching market's economic efficiency, possibly subject to some fairness requirements that promote equal access to resources. A natural balancing act exists between fairness and efficiency in matching markets, and has been the subject of much research. In this paper, we study a complementary goal---balancing diversity and efficiency---in a generalization of bipartite matching where agents on one side of the market can be matched to sets of agents on the other. Adapting a classical definition of the diversity of a set, we propose a quadratic programming-based approach to solving a submodular minimization problem that balances diversity and total weight of the solution. We also provide a scalable greedy algorithm with theoretical performance bounds. We then define the price of diversity, a measure of the efficiency loss due to enforcing diversity, and give a worst-case theoretical bound. Finally, we demonstrate the efficacy of our methods on three real-world datasets, and show that the price of diversity is not bad in practice. Our code is publicly accessible for further research.

JAIR Journal 2017 Journal Article

Multi-Organ Exchange

  • John P. Dickerson
  • Tuomas Sandholm

Kidney exchange, where candidates with organ failure trade incompatible but willing donors, is a life-saving alternative to the deceased donor waitlist, which has inadequate supply to meet demand. While fielded kidney exchanges see huge benefit from altruistic kidney donors (who give an organ without a paired needy candidate), a significantly higher medical risk to the donor deters similar altruism with livers. In this paper, we begin by exploring the idea of large-scale liver exchange, and show on demographically accurate data that vetted kidney exchange algorithms can be adapted to clear such an exchange at the nationwide level. We then propose cross-organ donation where kidneys and livers can be bartered for each other. We show theoretically that this multi-organ exchange provides linearly more transplants than running separate kidney and liver exchanges. This linear gain is a product of altruistic kidney donors creating chains that thread through the liver pool; it exists even when only a small but constant portion of the donors on the kidney side of the pool are willing to donate a liver lobe. We support this result experimentally on demographically accurate multi-organ exchanges. We conclude with thoughts regarding the fielding of a nationwide liver or joint liver-kidney exchange from a legal and computational point of view.

IJCAI Conference 2017 Conference Paper

Operation Frames and Clubs in Kidney Exchange

  • Gabriele Farina
  • John P. Dickerson
  • Tuomas Sandholm

A kidney exchange is a centrally-administered barter market where patients swap their willing yet incompatible donors. Modern kidney exchanges use 2-cycles, 3-cycles, and chains initiated by non-directed donors (altruists who are willing to give a kidney to anyone) as the means for swapping. We propose significant generalizations to kidney exchange. We allow more than one donor to donate in exchange for their desired patient receiving a kidney. We also allow for the possibility of a donor willing to donate if any of a number of patients receive kidneys. Furthermore, we combine these notions and generalize them. The generalization is to exchange among organ clubs, where a club is willing to donate organs outside the club if and only if the club receives organs from outside the club according to given specifications. We prove that unlike in the standard model, the uncapped clearing problem is NP-complete. We also present the notion of operation frames that can be used to sequence the operations across batches, and present integer programming formulations for the market clearing problems for these new types of organ exchanges. Experiments show that in the single-donation setting, operation frames improve planning by 34% - 51%. Allowing up to two donors to donate in exchange for one kidney donated to their designated patient yields a further increase in social welfare.

TIST Journal 2015 Journal Article

Automated Generation of Counterterrorism Policies Using Multiexpert Input

  • Anshul Sawant
  • John P. Dickerson
  • Mohammad T. Hajiaghayi
  • V. S. Subrahmanian

The use of game theory to model conflict has been studied by several researchers, spearheaded by Schelling. Most of these efforts assume a single payoff matrix that captures players’ utilities under different assumptions about what the players will do. Our experience in counterterrorism applications is that experts disagree on these payoffs. We leverage Shapley’s notion of vector equilibria, which formulates games where there are multiple payoff matrices, but note that they are very hard to compute in practice. To effectively enumerate large numbers of equilibria with payoffs provided by multiple experts, we propose a novel combination of vector payoffs and well-supported ϵ-approximate equilibria. We develop bounds related to computation of these equilibria for some special cases and give a quasipolynomial time approximation scheme (QPTAS) for the general case when the number of players is small (which is true in many real-world applications). Leveraging this QPTAS, we give efficient algorithms to find such equilibria and experimental results showing that they work well on simulated data. We then built a policy recommendation engine based on vector equilibria, called PREVE. We use PREVE to model the terrorist group Lashkar-e-Taiba (LeT), responsible for the 2008 Mumbai attacks, as a five-player game. Specifically, we apply it to three payoff matrices provided by experts in India--Pakistan relations, analyze the equilibria generated by PREVE, and suggest counterterrorism policies that may reduce attacks by LeT. We briefly discuss these results and identify their strengths and weaknesses from a policy point of view.

TIST Journal 2012 Journal Article

Adversarial Geospatial Abduction Problems

  • Paulo Shakarian
  • John P. Dickerson
  • V. S. Subrahmanian

Geospatial Abduction Problems (GAPs) involve the inference of a set of locations that “best explain” a given set of locations of observations. For example, the observations might include locations where a serial killer committed murders or where insurgents carried out Improvised Explosive Device (IED) attacks. In both these cases, we would like to infer a set of locations that explain the observations, for example, the set of locations where the serial killer lives/works, and the set of locations where insurgents locate weapons caches. However, unlike all past work on abduction, there is a strong adversarial component to this; an adversary actively attempts to prevent us from discovering such locations. We formalize such abduction problems as a two-player game where both players (an “agent” and an “adversary”) use a probabilistic model of their opponent (i.e., a mixed strategy). There is asymmetry as the adversary can choose both the locations of the observations and the locations of the explanation, while the agent (i.e., us) tries to discover these. In this article, we study the problem from the point of view of both players. We define reward functions axiomatically to capture the similarity between two sets of explanations (one corresponding to the locations chosen by the adversary, one guessed by the agent). Many different reward functions can satisfy our axioms. We then formalize the Optimal Adversary Strategy (OAS) problem and the Maximal Counter-Adversary strategy (MCA) and show that both are NP-hard, that their associated counting complexity problems are #P-hard, and that MCA has no fully polynomial approximation scheme unless P=NP. We show that approximation guarantees are possible for MCA when the reward function satisfies two simple properties (zero-starting and monotonicity) which many natural reward functions satisfy. We develop a mixed integer linear programming algorithm to solve OAS and two algorithms to (approximately) compute MCA; the algorithms yield different approximation guarantees and one algorithm assumes a monotonic reward function. Our experiments use real data about IED attacks over a 21-month period in Baghdad. We are able to show that both the MCA algorithms work well in practice; while MCA-GREEDY-MONO is both highly accurate and slightly faster than MCA-LS, MCA-LS (to our surprise) always completely and correctly maximized the expected benefit to the agent while running in an acceptable time period.