Ian A. Kash

TMLR Journal 2024 Journal Article

Group Fairness in Reinforcement Learning via Multi-Objective Rewards

• Jack Blandin
• Ian A. Kash

Recent works extend classification group fairness measures to sequential decision processes such as reinforcement learning (RL) by measuring fairness as the difference in decision-maker utility (e.g. accuracy) of each group. This approach suffers when decision-maker utility is not perfectly aligned with group utility, such as in repeat loan applications where a false positive (loan default) impacts the groups (applicants) and decision-maker (lender) by different magnitudes. Some works remedy this by measuring fairness in terms of group utility, typically referred to as their "qualification", but few works offer solutions that yield group qualification equality. Those that do are prone to violating the "no-harm" principle where one or more groups' qualifications are lowered in order to achieve equality. In this work, we characterize this problem space as having three implicit objectives: maximizing decision-maker utility, maximizing group qualification, and minimizing the difference in qualification between groups. We provide a RL policy learning technique that optimizes for these objectives directly by constructing a multi-objective reward function that encodes these objectives as distinct reward signals. Under suitable parameterizations our approach is guaranteed to respect the "no-harm" principle.

AAMAS Conference 2023 Conference Paper

An Analysis of Connections Between Regret Minimization and Actor Critic Methods in Cooperative Settings

• Chirag Chhablani
• Ian A. Kash

Counterfactual Multi-agent Policy Gradients (COMA) is a popular algorithm for learning in cooperative multi-agent reinforcement learning settings. COMA computes difference rewards to solve the multiagent credit assignment problem by providing a local learning signal for each agent. Similar to other popular Cooperative multiagent RL (MARL) algorithms, there is a lack of theoretical justification for COMA’s empirical success and specific way of doing credit assignment using difference rewards. We provide such a justification by connecting COMA’s update rule to regret minimization. We then use this connection to improve COMA’s performance by replacing usual softmax update with Neural Replicator Dynamics update from regret minimization literature. Experimental results on Starcraft II maps show the relevance of these theoretical insights for the performance of COMA in practice.

JAIR Journal 2023 Journal Article

Generalizing Group Fairness in Machine Learning via Utilities

• Jack Blandin
• Ian A. Kash

Group fairness definitions such as Demographic Parity and Equal Opportunity make assumptions about the underlying decision-problem that restrict them to classification problems. Prior work has translated these definitions to other machine learning environments, such as unsupervised learning and reinforcement learning, by implementing their closest mathematical equivalent. As a result, there are numerous bespoke interpretations of these definitions. This work aims to unify the shared aspects of each of these bespoke definitions, and to this end we provide a group fairness framework that generalizes beyond just classification problems. We leverage two fairness principles that enable this generalization. First, our framework measures outcomes in terms of utilities, rather than predictions, and does so for both the decision-maker and the individual. Second, our framework can consider counterfactual outcomes, rather than just observed outcomes, thus preventing loopholes where fairness criteria are satisfied through self-fulfilling prophecies. We provide concrete examples of how our utility fairness framework avoids these assumptions and thus naturally integrates with classification, clustering, and reinforcement learning fairness problems. We also show that many of the bespoke interpretations of Demographic Parity and Equal Opportunity fit nicely as special cases of our framework.

UAI Conference 2023 Conference Paper

Keep-Alive Caching for the Hawkes process

• Sushirdeep Narayana
• Ian A. Kash

We study the design of caching policies in applications such as serverless computing where there is not a fixed size cache to be filled, but rather there is a cost associated with the time an item stays in the cache. We present a model for such caching policies which captures the trade-off between this cost and the cost of cache misses. We characterize optimal caching policies in general and apply this characterization by deriving a closed form for Hawkes processes. Since optimal policies for Hawkes processes depend on the history of arrivals, we also develop history-independent policies which achieve near-optimal average performance. We evaluate the performances of the optimal policy and approximate polices using simulations and a data trace of Azure Functions, Microsoft’s FaaS (Function as a Service) platform for serverless computing

AAMAS Conference 2023 Conference Paper

Multiplicative Weight Updates for Extensive Form Games

• Chirag Chhablani
• Michael Sullins
• Ian A. Kash

Recent research in Nash equilibrium (NE) computation in extensive forms games (EFGs), such as poker, show that it is possible to compute strong solutions for two-player zero-sum games via regret minimization in theory and practice. Regret minimization is less well-understood in other classes of EFGs, even with perfect information. We introduce an approach based on converting the EFG into its corresponding normal form game (NFG). This faces two challenges. First, the exponential increase in the size of the NFG representation makes the straightforward use of regret minimization algorithms, like Multiplicative weights update (MWU) variants, on the resulting game impractical. Second, it is not clear how the updates in the normal form version of the game translate to the update in the behavioral strategies of the extensive form. We address these two challenges by introducing Extensive-form Implementation of Normal-form Regret minimization (EINR). Like CFR, it can be applied locally and recursively to the decision nodes in extensive form version. Further, we show a way to extend the EINR implementation to simultaneous move games where each agent knows the state of the game only when all the other players have acted in the game. Experiments on a zero-sum extensive form game and a cooperative simultaneous move game provide a comparison to CFR.

UAI Conference 2022 Conference Paper

Dynamic relocation in ridesharing via fixpoint construction

• Ian A. Kash
• Zhongkai Wen
• Lenore D. Zuck

To address spatial imbalances in the supply and demand of drivers, ridesharing platforms can make use of policies to direct driver relocation. We study a simple model of this problem, which allows us to give a constructive characterization of the unique fixpoint of system dynamics. Using this construction, we design a dynamic policy that provides stronger, than previous work, guarantees about its rate of convergence to the fixpoint. Simulations demonstrate the benefits of our approach.

AAAI Conference 2021 Conference Paper

Fair and Efficient Allocations with Limited Demands

• Sushirdeep Narayana
• Ian A. Kash

We study the fair division problem of allocating multiple resources among a set of agents with Leontief preferences that are each required to complete a finite amount of work, which we term “limited demands. ” We examine the behavior of the classic Dominant Resource Fairness (DRF) mechanism in this setting and show it is fair but only weakly Pareto optimal and inefficient in many natural examples. We propose as an alternative the Least Cost Product (LCP) mechanism, a natural adaptation of Maximum Nash Welfare to this setting. We characterize the structure of allocations of the LCP mechanism in this setting, show that it is Pareto efficient, and that it satisfies the relatively weak fairness property of sharing incentives. While we prove it satisfies the stronger fairness property of (expected) envy freeness in some special cases, we provide a counterexample showing it does not do so in general, a striking contrast to the “unreasonable fairness” of Maximum Nash Welfare in other settings. Simulations suggest, however, that these violations of envy freeness are rare in randomly generated examples.

JAIR Journal 2021 Journal Article

On the Cluster Admission Problem for Cloud Computing

• Ludwig Dierks
• Ian A. Kash
• Sven Seuken

Cloud computing providers face the problem of matching heterogeneous customer workloads to resources that will serve them. This is particularly challenging if customers, who are already running a job on a cluster, scale their resource usage up and down over time. The provider therefore has to continuously decide whether she can add additional workloads to a given cluster or if doing so would impact existing workloads’ ability to scale. Currently, this is often done using simple threshold policies to reserve large parts of each cluster, which leads to low efficiency (i.e., low average utilization of the cluster). We propose more sophisticated policies for controlling admission to a cluster and demonstrate that they significantly increase cluster utilization. We first introduce the cluster admission problem and formalize it as a constrained Partially Observable Markov Decision Process (POMDP). As it is infeasible to solve the POMDP optimally, we then systematically design admission policies that estimate moments of each workload’s distribution of future resource usage. Via extensive simulations grounded in a trace from Microsoft Azure, we show that our admission policies lead to a substantial improvement over the simple threshold policy. We then show that substantial further gains are possible if high-quality information is available about arriving workloads. Based on this, we propose an information elicitation approach to incentivize users to provide this information and simulate its effects.

JAAMAS Journal 2019 Journal Article

Strategic behavior and learning in all-pay auctions: an empirical study using crowdsourced data

• Yoram Bachrach
• Ian A. Kash
• Joel Oren

Abstract We analyze human behavior in crowdsourcing contests using an all-pay auction model where all participants exert effort, but only the highest bidder receives the reward. We let workers sourced from Amazon Mechanical Turk participate in an all-pay auction, and contrast the game theoretic equilibrium with the choices of the humans participants. We examine how people competing in the contest learn and adapt their bids, comparing their behavior to well-established online learning algorithms in a novel approach to quantifying the performance of humans as learners. For the crowdsourcing contest designer, our results show that a bimodal distribution of effort should be expected, with some very high effort and some very low effort, and that humans have a tendency to overbid. Our results suggest that humans are weak learners in this setting, so it may be important to educate participants about the strategic implications of crowdsourcing contests.

JAIR Journal 2018 Journal Article

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). We show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations. The cost of providing the incentives is not borne by the MAS and does not come from fines charged for norm violations (fines may be impossible to levy in a system where agents are free to leave and rejoin again under a different identity). Instead, monitoring incentives come from (scrip) fees for accessing the services provided by the MAS. In some cases, perfect monitoring (and hence enforcement) can be achieved: no norms will be violated in equilibrium. In other cases, we show that, while it is impossible to achieve perfect enforcement, we can get arbitrarily close; we can make the probability of a norm violation in equilibrium arbitrarily small. We show using simulations that our theoretical results, which apply to systems with a large number of agents, hold for multi-agent systems with as few as 1000 agents–the system rapidly converges to the steady-state distribution of scrip tokens necessary to ensure monitoring and then remains close to the steady state.

IJCAI Conference 2018 Conference Paper

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems (Extended Abstract)

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al. , 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations.

AAMAS Conference 2016 Conference Paper

Decentralised Norm Monitoring in Open Multi-Agent Systems (Extended Abstract)

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

IJCAI Conference 2015 Conference Paper

Non-Myopic Negotiators See What's Best

• Yair Zick
• Yoram Bachrach
• Ian A. Kash
• Peter Key

We consider revenue negotiation problems in iterative settings. In our model, a group of agents has some initial resources, used in order to generate revenue. Agents must agree on some way of dividing resources, but there’s a twist. At every time-step, the revenue shares received at time t are agent resources at time t + 1, and the game is repeated. The key issue here is that the way resources are shared has a dramatic effect on longterm social welfare, so in order to maximize individual long-term revenue one must consider the welfare of others, a behavior not captured by other models of cooperation and bargaining. Our work focuses on homogeneous production functions. We identify conditions that ensure that the socially optimal outcome is an ε-Nash equilibrium. We apply our results to some families of utility functions, and discuss their strategic implications.

JAAMAS Journal 2014 Journal Article

Market manipulation with outside incentives

• Yiling Chen
• Xi Alice Gao
• Ian A. Kash

Abstract Much evidence has shown that prediction markets can effectively aggregate dispersed information about uncertain future events and produce remarkably accurate forecasts. However, if the market prediction will be used for decision making, a strategic participant with a vested interest in the decision outcome may manipulate the market prediction to influence the resulting decision. The presence of such incentives outside of the market would seem to damage the market’s ability to aggregate information because of the potential distrust among market participants. While this is true under some conditions, we show that, if the existence of such incentives is certain and common knowledge, in many cases, there exist separating equilibria where each participant changes the market probability to different values given different private signals and information is fully aggregated in the market. At each separating equilibrium, the participant with outside incentives makes a costly move to gain trust from other participants. While there also exist pooling equilibria where a participant changes the market probability to the same value given different private signals and information loss occurs, we give evidence suggesting that two separating equilibria are more natural and desirable than many other equilibria of this game by considering domination-based belief refinement, social welfare, and the expected payoff of either participant in the game. When the existence of outside incentives is uncertain, however, trust cannot be established between players if the outside incentive is sufficiently large and we lose the separability at equilibria.

AAMAS Conference 2011 Conference Paper

Information Elicitation for Decision Making

• Yiling Chen
• Ian A. Kash

Proper scoring rules, particularly when used as the basis for a prediction market, are powerful tools for eliciting and aggregating beliefs about events such as the likely outcome of an election or sporting event. Such scoring rules incentivize a single agent to reveal her true beliefs about the event. Othman and Sandholm introduced the idea of a decision rule to examine these problems in contexts where the information being elicited is conditional on some decision alternatives. For example, "What is the probability having ten million viewers if we choose to air new television show X? What if we choose Y? " Since only one show can actually air in a slot, only the results under the chosen alternative can ever be observed. Othman and Sandholm developed proper scoring rules (and thus decision markets) for a single, deterministic decision rule: always select the action with the greatest probability of success. In this work we significantly generalize their results, developing scoring rules for other deterministic decision rules, randomized decision rules, and situations where there may be more than two outcomes (e. g. less than a million viewers, more than one but less than ten, or more than ten million).

AAMAS Conference 2009 Conference Paper

Multiagent Learning in Large Anonymous Games

• Ian A. Kash
• Eric J. Friedman
• Joseph Y. Halpern

In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if bestreply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.

SODA Conference 2003 Conference Paper

Compact representations of separable graphs

• Daniel K. Blandford
• Guy E. Blelloch
• Ian A. Kash