Amos Azaria

AAMAS Conference 2024 Conference Paper

Coalition Formation with Bounded Coalition Size

• Chaya Levinger
• Noam Hazon
• Sofia Simola
• Amos Azaria

In many situations when people are assigned to coalitions, the utility of each person depends on the friends in her coalition. Additionally, in many situations, the size of each coalition should be bounded. This paper studies such coalition formation scenarios in both weighted and unweighted settings. Since finding a partition that maximizes the utilitarian social welfare is computationally hard, we provide a polynomial-time approximation algorithm. We also investigate the existence and the complexity of finding stable partitions. Namely, we show that the Contractual Strict Core (CSC) is never empty, but the Strict Core (SC) of some games is empty. Finding partitions that are in the CSC is computationally easy, but even deciding whether an SC of a given game exists is NP-hard. The analysis of the core is more involved. In the unweighted setting, we show that when the coalition size is bounded by 3 the core is never empty, and we present a polynomial time algorithm for finding a member of the core. However, for the weighted setting, the core may be empty, and we prove that deciding whether there exists a core is NP-hard.

AAMAS Conference 2024 Conference Paper

Source Detection in Networks using the Stationary Distribution of a Markov Chain

• Yael Sabato
• Amos Azaria
• Noam Hazon

Nowadays, the diffusion of information through social networks is a powerful phenomenon. One common way to model diffusions in social networks is the Independent Cascade (IC) model. Given a set of infected nodes according to the IC model, a natural problem is the source detection problem, in which the goal is to identify the unique node that has started the diffusion. Maximum Likelihood Estimation (MLE) is a common approach for tackling the source detection problem, but it is computationally hard. In this work, we propose an efficient method for the source detection problem under the MLE approach, which is based on computing the stationary distribution of a Markov chain. Using simulations, we demonstrate the effectiveness of our method compared to other state-of-the-art methods from the literature, both on random and real-world networks.

NeurIPS Conference 2023 Conference Paper

Read and Reap the Rewards: Learning to Play Atari with the Help of Instruction Manuals

• Yue Wu
• Yewen Fan
• Paul Pu Liang
• Amos Azaria
• Yuanzhi Li
• Tom M. Mitchell

High sample complexity has long been a challenge for RL. On the other hand, humans learn to perform tasks not only from interaction or demonstrations, but also by reading unstructured text documents, e. g. , instruction manuals. Instruction manuals and wiki pages are among the most abundant data that could inform agents of valuable features and policies or task-specific environmental dynamics and reward structures. Therefore, we hypothesize that the ability to utilize human-written instruction manuals to assist learning policies for specific tasks should lead to a more efficient and better-performing agent. We propose the Read and Reward framework. Read and Reward speeds up RL algorithms on Atari games by reading manuals released by the Atari game developers. Our framework consists of a QA Extraction module that extracts and summarizes relevant information from the manual and a Reasoning module that evaluates object-agent interactions based on information from the manual. An auxiliary reward is then provided to a standard A2C RL agent, when interaction is detected. Experimentally, various RL algorithms obtain significant improvement in performance and training speed when assisted by our design. Code at github. com/Holmeswww/RnR

AAMAS Conference 2023 Conference Paper

Social Aware Coalition Formation with Bounded Coalition Size

• Chaya Levinger
• Amos Azaria
• Noam Hazon

In many situations when people are assigned to coalitions the assignment must be social aware, i. e, the utility of each person is the number of friends in her coalition. Additionally, in many situations the size of each coalition should be bounded. This paper initiates the study of such coalition formation scenarios. We show that finding a partition that maximizes the utilitarian social welfare is computationally hard, and provide a polynomial-time approximation algorithm. We also investigate the existence and the complexity of finding stable partitions. Namely, we show that there always exists a Nash Stable (NS) partition and the Contractual Strict Core (CSC) is never empty, but the Strict Core (SC) of some games is empty. Finding partitions that are NS or in the CSC is computationally easy, but finding partitions that are in the SC is hard. The analysis of the core is more involved. When the coalition size is bounded by 3 the core is never empty, and we present a polynomial time algorithm for finding a member of the core. In all other cases, we provide additive and multiplicative approximations of the core. In addition, we show in simulation over 100 million games that a simple heuristic always finds a partition that is in the core.

NeurIPS Conference 2023 Conference Paper

SPRING: Studying Papers and Reasoning to play Games

• Yue Wu
• So Yeon Min
• Shrimai Prabhumoye
• Yonatan Bisk
• Russ R. Salakhutdinov
• Amos Azaria
• Tom M. Mitchell
• Yuanzhi Li

Open-world survival games pose significant challenges for AI algorithms due to their multi-tasking, deep exploration, and goal prioritization requirements. Despite reinforcement learning (RL) being popular for solving games, its high sample complexity limits its effectiveness in complex open-world games like Crafter or Minecraft. We propose a novel approach, SPRING, to read Crafter's original academic paper and use the knowledge learned to reason and play the game through a large language model (LLM). Prompted with the LaTeX source as game context and a description of the agent's current observation, our SPRING framework employs a directed acyclic graph (DAG) with game-related questions as nodes and dependencies as edges. We identify the optimal action to take in the environment by traversing the DAG and calculating LLM responses for each node in topological order, with the LLM's answer to final node directly translating to environment actions. In our experiments, we study the quality of in-context "reasoning" induced by different forms of prompts under the setting of the Crafter environment. Our experiments suggest that LLMs, when prompted with consistent chain-of-thought, have great potential in completing sophisticated high-level trajectories. Quantitatively, SPRING with GPT-4 outperforms all state-of-the-art RL baselines, trained for 1M steps, without any training. Finally, we show the potential of Crafter as a test bed for LLMs. Code at github. com/holmeswww/SPRING

AAAI Conference 2022 Short Paper

Criticality-Based Advice in Reinforcement Learning (Student Abstract)

• Yitzhak Spielberg
• Amos Azaria

One of the ways to make reinforcement learning (RL) more efficient is by utilizing human advice. Since human advice is expensive, the central question in advice-based reinforcement learning is, how to decide in which states the agent should ask for advice. To approach this challenge, various advice strategies have been proposed. Although all of these strategies distribute advice more efficiently than naive strategies, they rely solely on the agent’s estimate of the action-value function, and therefore, are rather inefficient when this estimate is not accurate, in particular, in the early stages of the learning process. To address this weakness, we present an approach to advice-based RL, in which the human’s role is not limited to giving advice in chosen states, but also includes hinting apriori, before the learning procedure, in which sub-domains of the state space the agent might require more advice. For this purpose we use the concept of critical: states in which choosing the proper action is more important than in other states.

IS Journal 2022 Journal Article

Deep Learning Architectures for Approximating Goldbach’s Function in New Regions

• Avigail Stekel
• Amos Azaria

Goldbach conjecture is one of the most famous open mathematical problems. He asserts that: Every even number greater than two is the sum of two prime numbers. The Goldbach function receives an even number and returns the number of different ways to write it as an unordered sum of two prime numbers. We developed a simple multilayer perceptron that attempts to predict Goldbach’s function. This simple model performs well when trained and tested on numbers up to 4 million. However, as expected, the model’s performance significantly deteriorates when trained on smaller numbers (up to 4 million) but tested on larger numbers (4–10 million). To overcome this problem, we present two novel deep learning architectures. In these architectures, we introduce two types of multiplication layers, which we believe are more appropriate for solving mathematical relations. We show that both architectures significantly outperform the simple multilayer perceptron when trained on smaller numbers and tested on larger numbers. We further improve the performance of the deep learning architectures by using a known analytically derived estimation that is used in order to normalize the model’s output.

AAAI Conference 2022 Short Paper

Explainable Shapley-Based Allocation (Student Abstract)

• Meir Nizri
• Noam Hazon
• Amos Azaria

The Shapley value is one of the most important normative division scheme in cooperative game theory, satisfying basic axioms. However, some allocation according to the Shapley value may seem unfair to humans. In this paper, we develop an automatic method that generates intuitive explanations for a Shapley-based payoff allocation, which utilizes the basic axioms. Given a coalitional game, our method decomposes it to sub-games, for which it is easy to generate verbal explanations, and shows that the given game is composed of the sub-games. Since the payoff allocation for each sub-game is perceived as fair, the Shapley-based payoff allocation for the given game should seem fair as well. We run an experiment with 210 human participants and show that when applying our method, humans perceive Shapley-based payoff allocation as significantly more fair than when using a general standard explanation.

IJCAI Conference 2022 Conference Paper

Irrational, but Adaptive and Goal Oriented: Humans Interacting with Autonomous Agents

• Amos Azaria

Autonomous agents that interact with humans are becoming more and more prominent. Currently, such agents usually take one of the following approaches for considering human behavior. Some methods assume either a fully cooperative or a zero-sum setting; these assumptions entail that the human's goals are either identical to that of the agent, or their opposite. In both cases, the agent is not required to explicitly model the human’s goals and account for humans' adaptation nature. Other methods first compose a model of human behavior based on observing human actions, and then optimize the agent’s actions based on this model. Such methods do not account for how the human will react to the agent's actions and thus, suffer an overestimation bias. Finally, other methods, such as model free reinforcement learning, merely learn which actions the agent should take at which states. While such methods can, theoretically, account for human adaptation nature, since they require extensive interaction with humans, they usually run in simulation. By not considering the human’s goals, autonomous agents act selfishly, lack generalization, require vast amounts of data, and cannot account for human’s strategic behavior. Therefore, we call for pursuing solution concepts for autonomous agents interacting with humans that consider the human’s goals and adaptive nature.

AAAI Conference 2022 Short Paper

Social Aware Assignment of Passengers in Ridesharing (Student Abstract)

• Chaya Levinger
• Noam Hazon
• Amos Azaria

We analyze the assignment of passengers in a shared ride, which considers the social relationship among the passengers. Namely, there is a fixed number of passengers in each vehicle, and the goal is to recommend an assignment of the passengers such that the number of friendship relations is maximized. We show that the problem is computationally hard, and we provide an approximation algorithm.

AAAI Conference 2021 Conference Paper

Conversational Neuro-Symbolic Commonsense Reasoning

• Forough Arabshahi
• Jennifer Lee
• Mikayla Gawarecki
• Kathryn Mazaitis
• Amos Azaria
• Tom Mitchell

In order for conversational AI systems to hold more natural and broad-ranging conversations, they will require much more commonsense, including the ability to identify unstated presumptions of their conversational partners. For example, in the command “If it snows at night then wake me up early because I don’t want to be late for work” the speaker relies on commonsense reasoning of the listener to infer the implicit presumption that they wish to be woken only if it snows enough to cause traffic slowdowns. We consider here the problem of understanding such imprecisely stated natural language commands given in the form of if-(state), then-(action), because- (goal) statements. More precisely, we consider the problem of identifying the unstated presumptions of the speaker that allow the requested action to achieve the desired goal from the given state (perhaps elaborated by making the implicit presumptions explicit). We release a benchmark data set for this task, collected from humans and annotated with commonsense presumptions. We present a neuro-symbolic theorem prover that extracts multi-hop reasoning chains, and apply it to this problem. Furthermore, to accommodate the reality that current AI commonsense systems lack full coverage, we also present an interactive conversational framework built on our neurosymbolic system, that conversationally evokes commonsense knowledge from humans to complete its reasoning chains.

AAAI Conference 2021 Short Paper

Deep Reinforcement Learning for a Dictionary Based Compression Schema (Student Abstract)

• Keren Nivasch
• Dana Shapira
• Amos Azaria

An increasingly important process of the internet age and the massive data era is file compression. One popular compression scheme, Lempel–Ziv–Welch (LZW), maintains a dictionary of previously seen strings. The dictionary is updated throughout the parsing process by adding new encountered substrings. Klein, Opalinsky and Shapira (2019) recently studied the option of selectively updating the LZW dictionary. They show that even inserting only a random subset of the strings into the dictionary does not adversely affect the compression ratio. Inspired by their approach, we propose a reinforcement learning based agent, RLZW, that decides when to add a string to the dictionary. The agent is first trained on a large set of data, and then tested on files it has not seen previously (i. e. , the test set). We show that on some types of input data, RLZW outperforms the compression ratio of a standard LZW.

EUMAS Conference 2021 Conference Paper

Explaining Ridesharing: Selection of Explanations for Increasing User Satisfaction

• David Zar
• Noam Hazon
• Amos Azaria

Abstract Transportation services play a crucial part in the development of modern smart cities. In particular, on-demand ridesharing services, which group together passengers with similar itineraries, are already operating in several metropolitan areas. These services can be of significant social and environmental benefit, by reducing travel costs, road congestion and \(CO_2\) emissions. Unfortunately, despite their advantages, not many people opt to use these ridesharing services. We believe that increasing the user satisfaction from the service will cause more people to utilize it, which, in turn, will improve the quality of the service, such as the waiting time, cost, travel time, and service availability. One possible way for increasing user satisfaction is by providing appropriate explanations comparing the alternative modes of transportation, such as a private taxi ride and public transportation. For example, a passenger may be more satisfied from a shared-ride if she is told that a private taxi ride would have cost her 50% more. Therefore, the problem is to develop an agent that provides explanations that will increase the user satisfaction. We model our environment as a signaling game and show that a rational agent, which follows the perfect Bayesian equilibrium, must reveal all of the information regarding the possible alternatives to the passenger. In addition, we develop a machine learning based agent that, when given a shared-ride along with its possible alternatives, selects the explanations that are most likely to increase user satisfaction. Using feedback from humans we show that our machine learning based agent outperforms the rational agent and an agent that randomly chooses explanations, in terms of user satisfaction.

AAAI Conference 2020 Conference Paper

AI for Explaining Decisions in Multi-Agent Environments

• Sarit Kraus
• Amos Azaria
• Jelena Fiosina
• Maike Greve
• Noam Hazon
• Lutz Kolbe
• Tim-Benjamin Lembcke
• Jorg P. Muller

Explanation is necessary for humans to understand and accept decisions made by an AI system when the system’s goal is known. It is even more important when the AI system makes decisions in multi-agent environments where the human does not know the systems’ goals since they may depend on other agents’ preferences. In such situations, explanations should aim to increase user satisfaction, taking into account the system’s decision, the user’s and the other agents’ preferences, the environment settings and properties such as fairness, envy and privacy. Generating explanations that will increase user satisfaction is very challenging; to this end, we propose a new research direction: Explainable decisions in Multi-Agent Environments (xMASE). We then review the state of the art and discuss research directions towards efficient methodologies and algorithms for generating explanations that will increase users’ satisfaction from AI systems’ decisions in multi-agent environments.

JAAMAS Journal 2019 Journal Article

An agent for learning new natural language commands

• Amos Azaria
• Shashank Srivastava
• Tom M. Mitchell

Abstract Teaching via natural language is an intuitive way for end users to add functionality to a virtual assistant, enabling them to personalize their assistant with new commands without requiring the intervention of the system developer, who cannot possibly anticipate all of an end user’s needs. In this paper we introduce our Learning by Instruction Agent (LIA), the first virtual assistant, for an email domain, that is capable of learning how to perform new commands taught by end users in natural language. LIA grounds the semantics of each command in terms of primitive executable procedures. When a user provides LIA with a command that it does not understand, it prompts the user to explain the command through a sequence of natural language steps. From this input, LIA learns the meaning of the new command and how to generalize the command to novel situations. For example, having been taught how to “forward an email to Alice”, it can correctly understand “forward this email to Bob”. We show that users that were assigned to interact with LIA completed the task quicker than users assigned to interact with a non-learning agent. These results demonstrate the potential of natural language teaching to improve the capabilities of intelligent personal assistants. We annotated 4759 natural language statements with their associated computer readable execution commands (logical forms) to form a dataset (which we publicize in this paper). We present the performance of several different parser methods on this dataset.

AAMAS Conference 2019 Conference Paper

The Multimodal Correction Detection Problem

• Amos Azaria
• Keren Nivasch

In order for socially aware agents to be truly useful, they should have abilities associated with human intelligence, such as the ability to detect their own mistakes from user reactions. This is an instance of implicit feedback. In this work we address the problem of detecting an agent’s mistakes by identifying when the user tries to correct the agent. We refer to this problem as the Correction Detection task. We use a multimodal approach, using both the voice (acoustics and non-verbal sounds) as well as the transcript of the user’s spoken commands.

AAAI Conference 2018 Short Paper

Did I Say Something Wrong?: Towards a Safe Collaborative Chatbot

• Merav Chkroun
• Amos Azaria

Chatbots have been a core measure of AI since Turing has presented his test for intelligence, and are also widely used for entertainment purposes. In this paper we present a platform that enables users to collaboratively teach a chatbot responses, using natural language. We present a method of collectively detecting malicious users and using the commands taught by these users to further mitigate activity of future malicious users.

IJCAI Conference 2017 Conference Paper

Parsing Natural Language Conversations using Contextual Cues

• Shashank Srivastava
• Amos Azaria
• Tom Mitchell

In this work, we focus on semantic parsing of natural language conversations. Most existing methods for semantic parsing are based on understanding the semantics of a single sentence at a time. However, understanding conversations also requires an understanding of conversational context and discourse structure across sentences. We formulate semantic parsing of conversations as a structured prediction task, incorporating structural features that model the `flow of discourse' across sequences of utterances. We create a dataset for semantic parsing of conversations, consisting of 113 real-life sequences of interactions of human users with an automated email assistant. The data contains 4759 natural language statements paired with annotated logical forms. Our approach yields significant gains in performance over traditional semantic parsing.

AAAI Conference 2016 Conference Paper

Instructable Intelligent Personal Agent

• Amos Azaria
• Jayant Krishnamurthy
• Tom Mitchell

Unlike traditional machine learning methods, humans often learn from natural language instruction. As users become increasingly accustomed to interacting with mobile devices using speech, their interest in instructing these devices in natural language is likely to grow. We introduce our Learning by Instruction Agent (LIA), an intelligent personal agent that users can teach to perform new action sequences to achieve new commands, using solely natural language interaction. LIA uses a CCG semantic parser to ground the semantics of each command in terms of primitive executable procedures defining sensors and effectors of the agent. Given a natural language command that LIA does not understand, it prompts the user to explain how to achieve the command through a sequence of steps, also specified in natural language. A novel lexicon induction algorithm enables LIA to generalize across taught commands, e. g. , having been taught how to “forward an email to Alice, ” LIA can correctly interpret the command “forward this email to Bob. ” A user study involving email tasks demonstrates that users voluntarily teach LIA new commands, and that these taught commands significantly reduce task completion time. These results demonstrate the potential of natural language instruction as a significant, under-explored paradigm for machine learning.

AAAI Conference 2016 Conference Paper

Personalized Alert Agent for Optimal User Performance

• Avraham Shvartzon
• Amos Azaria
• Sarit Kraus
• Claudia Goldman
• Joachim Meyer
• Omer Tsimhoni

Preventive maintenance is essential for the smooth operation of any equipment. Still, people occasionally do not maintain their equipment adequately. Maintenance alert systems attempt to remind people to perform maintenance. However, most of these systems do not provide alerts at the optimal timing, and nor do they take into account the time required for maintenance or compute the optimal timing for a specific user. We model the problem of maintenance performance, assuming maintenance is time consuming. We solve the optimal policy for the user, i. e. , the optimal timing for a user to perform maintenance. This optimal strategy depends on the value of user’s time, and thus it may vary from user to user and may change over time. Based on the solved optimal strategy we present a personalized maintenance agent, which, depending on the value of user’s time, provides alerts to the user when she should perform maintenance. In an experiment using a spaceship computer game, we show that receiving alerts from the personalized alert agent significantly improves user performance.

JAAMAS Journal 2015 Journal Article

Autonomous agents and human cultures in the trust–revenge game

• Amos Azaria
• Ariella Richardson
• Avi Rosenfeld

Abstract Autonomous agents developed by experts are embedded with the capability to interact well with people from different cultures. When designing expert agents intended to interact with autonomous agents developed by non-game theory agents (NGTE), it is beneficial to obtain insights on the behavior of these NGTE agents. Is the behavior of these NGTE agents similar to human behavior from different cultures? This is an important question as such a quality would allow an expert agent interacting with NGTE agents to model them using the same methods that are used to model humans from different cultures. To study this point, we evaluated NGTE agents behavior using a game called the Trust–Revenge game, which is known in social science for capturing different human tendencies. The Trust–Revenge game has a unique subgame-perfect equilibrium strategy profile, however, very rarely do people follow it. We compared the behavior of autonomous agents to the actions of several human demographic groups—one of which is similar to the designers of the autonomous agents. We claim that autonomous agents are similar to human players from various cultures. This enables the use of approaches, developed for handling cultural diversity among humans, to be applied for interaction with NGTE agents. This paper also analyzes additional aspects of autonomous agents behavior and whether composing autonomous agents affects human behavior.

IJCAI Conference 2015 Conference Paper

Intelligent Agent Supporting Human-Multi-Robot Team Collaboration

• Ariel Rosenfeld
• Noa Agmon
• Oleg Maksimov
• Amos Azaria
• Sarit Kraus

The number of multi-robot systems deployed in field applications has risen dramatically over the years. Nevertheless, supervising and operating multiple robots at once is a difficult task for a single operator to execute. In this paper we propose a novel approach for utilizing advising automated agents when assisting an operator to better manage a team of multiple robots in complex environments. We introduce the Myopic Advice Optimization (MYAO) Problem and exemplify its implementation using an agent for the Search And Rescue (SAR) task. Our intelligent advising agent was evaluated through extensive field trials, with 44 non-expert human operators and 10 low-cost mobile robots, in simulation and physical deployment, and showed a significant improvement in both team performance and the operator’s satisfaction.

JAAMAS Journal 2015 Journal Article

Strategic advice provision in repeated human-agent interactions

• Amos Azaria
• Ya’akov Gal
• Claudia V. Goldman

Abstract This paper addresses the problem of automated advice provision in scenarios that involve repeated interactions between people and computer agents. This problem arises in many applications such as route selection systems, office assistants and climate control systems. To succeed in such settings agents must reason about how their advice influences people’s future actions or decisions over time. This work models such scenarios as a family of repeated bilateral interaction called “choice selection processes”, in which humans or computer agents may share certain goals, but are essentially self-interested. We propose a social agent for advice provision ( SAP ) for such environments that generates advice using a social utility function which weighs the sum of the individual utilities of both agent and human participants. The SAP agent models human choice selection using hyperbolic discounting and samples the model to infer the best weights for its social utility function. We demonstrate the effectiveness of SAP in two separate domains which vary in the complexity of modeling human behavior as well as the information that is available to people when they need to decide whether to accept the agent’s advice. In both of these domains, we evaluated SAP in extensive empirical studies involving hundreds of human subjects. SAP was compared to agents using alternative models of choice selection processes informed by behavioral economics and psychological models of decision-making. Our results show that in both domains, the SAP agent was able to outperform alternative models. This work demonstrates the efficacy of combining computational methods with behavioral economics to model how people reason about machine-generated advice and presents a general methodology for agent-design in such repeated advice settings.

AAAI Conference 2014 Conference Paper

Advice Provision for Choice Selection Processes with Ranked Options

• Amos Azaria
• Ya'akov Gal
• Claudia Goldman
• Sarit Kraus

Choice selection processes are a family of bilateral games of incomplete information in which a computer agent generates advice for a human user while considering the effect of the advice on the user’s behavior in future interactions. The human and the agent may share certain goals, but are essentially self-interested. This paper extends selection processes to settings in which the actions available to the human are ordered and thus the user may be influenced by the advice even though he doesn’t necessarily follow it exactly. In this work we also consider the case in which the user obtains some observation on the sate of the world. We propose several approaches to model human decision making in such settings. We incorporate these models into two optimization techniques for the agent advice provision strategy. In the first one the agent used a social utility approach which considered the benefits and costs for both agent and person when making suggestions. In the second approach we simplified the human model in order to allow modeling and solving the agent strategy as an MDP. In an empirical evaluation involving human users on AMT, we showed that the social utility approach significantly outperformed the MDP approach.

AAAI Conference 2014 Conference Paper

Leveraging Fee-Based, Imperfect Advisors in Human-Agent Games of Trust

• Cody Buntain
• Amos Azaria
• Sarit Kraus

This paper explores whether the addition of costly, imperfect, and exploitable advisors to Berg’s investment game enhances or detracts from investor performance in both one-shot and multi-round interactions. We then leverage our findings to develop an automated investor agent that performs as well as or better than humans in these games. To gather this data, we extended Berg’s game and conducted a series of experiments using Amazon’s Mechanical Turk to determine how humans behave in these potentially adversarial conditions. Our results indicate that, in games of short duration, advisors do not stimulate positive behavior and are not useful in providing actionable advice. In long-term interactions, however, advisors do stimulate positive behavior with significantly increased investments and returns. By modeling human behavior across several hundred participants, we were then able to develop agent strategies that maximized return on investment and performed as well as or significantly better than humans. In one-shot games, we identified an ideal investment value that, on average, resulted in positive returns as long as advisor exploitation was not allowed. For the multi-round games, our agents relied on the corrective presence of advisors to stimulate positive returns on maximum investment.

TIST Journal 2014 Journal Article

Strategic Information Disclosure to People with Multiple Alternatives

• Amos Azaria
• Zinovi Rabinovich
• Claudia V. Goldman
• Sarit Kraus

In this article, we study automated agents that are designed to encourage humans to take some actions over others by strategically disclosing key pieces of information. To this end, we utilize the framework of persuasion games—a branch of game theory that deals with asymmetric interactions where one player (Sender) possesses more information about the world, but it is only the other player (Receiver) who can take an action. In particular, we use an extended persuasion model, where the Sender’s information is imperfect and the Receiver has more than two alternative actions available. We design a computational algorithm that, from the Sender’s standpoint, calculates the optimal information disclosure rule. The algorithm is parameterized by the Receiver’s decision model (i.e., what choice he will make based on the information disclosed by the Sender) and can be retuned accordingly. We then provide an extensive experimental study of the algorithm’s performance in interactions with human Receivers. First, we consider a fully rational (in the Bayesian sense) Receiver decision model and experimentally show the efficacy of the resulting Sender’s solution in a routing domain. Despite the discrepancy in the Sender’s and the Receiver’s utilities from each of the Receiver’s choices, our Sender agent successfully persuaded human Receivers to select an option more beneficial for the agent. Dropping the Receiver’s rationality assumption, we introduce a machine learning procedure that generates a more realistic human Receiver model. We then show its significant benefit to the Sender solution by repeating our routing experiment. To complete our study, we introduce a second (supply--demand) experimental domain and, by contrasting it with the routing domain, obtain general guidelines for a Sender on how to construct a Receiver model.

AAAI Conference 2013 Conference Paper

Advice Provision in Multiple Prospect Selection Problems

• Amos Azaria
• Sarit Kraus

When humans face a broad spectrum of topics, where each topic consists of several options, they usually make a decision on each topic separately. Usually, a person will perform better by making a global decision, however, taking all consequences into account is extremely difficult. We present a novel computational method for advice-generation in an environment where people need to decide among multiple selection problems. This method is based on the prospect theory and uses machine learning techniques. We graphically present this advice to the users and compare it with an advice which encourages the users to always select the option with a higher expected outcome. We show that our method outperforms the expected outcome approach in terms of user happiness and satisfaction.

AAAI Conference 2013 Conference Paper

Analyzing the Effectiveness of Adversary Modeling in Security Games

• Thanh Nguyen
• Rong Yang
• Amos Azaria
• Sarit Kraus
• Milind Tambe

Recent deployments of Stackelberg security games (SSG) have led to two competing approaches to handle boundedly rational human adversaries: (1) integrating models of human (adversary) decision-making into the game-theoretic algorithms, and (2) applying robust optimization techniques that avoid adversary modeling. A recent algorithm (MATCH) based on the second approach was shown to outperform the leading modeling-based algorithm even in the presence of significant amount of data. Is there then any value in using human behavior models in solving SSGs? Through extensive experiments with 547 human subjects playing 11102 games in total, we emphatically answer the question in the affirmative, while providing the following key contributions: (i) we show that our algorithm, SU-BRQR, based on a novel integration of human behavior model with the subjective utility function, significantly outperforms both MATCH and its improvements; (ii) we are the first to present experimental results with security intelligence experts, and find that even though the experts are more rational than the Amazon Turk workers, SU-BRQR still outperforms an approach assuming perfect rationality (and to a more limited extent MATCH); (iii) we show the advantage of SU-BRQR in a new, large game setting and demonstrate that sufficient data enables it to improve its performance over MATCH.

JAAMAS Journal 2013 Journal Article

Automated agents for reward determination for human work in crowdsourcing applications

• Amos Azaria
• Yonatan Aumann
• Sarit Kraus

Abstract Crowdsourcing applications frequently employ many individual workers, each performing a small amount of work. In such settings, individually determining the reward for each assignment and worker may seem economically beneficial, but is inapplicable if manually performed. We thus consider the problem of designing automated agents for automatic reward determination and negotiation in such settings. We formally describe this problem and show that it is NP-hard. We therefore present two automated agents for the problem, based on two different models of human behavior. The first, the Reservation Price Based Agent (RPBA), is based on the concept of a RP, and the second, the No Bargaining Agent (NBA) which tries to avoid any negotiation. The performance of the agents is tested in extensive experiments with real human subjects, where both NBA and RPBA outperform strategies developed by human experts.

AAMAS Conference 2013 Conference Paper

Modeling Human Adversary Decision Making in Security Games: An Initial Report

• Thanh H. Nguyen
• James Pita
• Rajiv Maheswaran
• Milind Tambe
• Amos Azaria
• Sarit Kraus

Motivated by recent deployments of Stackelberg security games (SSGs), two competing approaches have emerged which either integrate models of human decision making into game-theoretic algorithms or apply robust optimization techniques that avoid adversary modeling. Recently, a robust technique (MATCH) has been shown to significantly outperform the leading modeling-based algorithms (e. g. , Quantal Response (QR)) even in the presence of significant amounts of subject data. As a result, the effectiveness of using human behaviors in solving SSGs remains in question. We study this question in this paper.

AAAI Conference 2013 Conference Paper

Social Rankings in Human-Computer Committees

• Moshe Bitan
• Ya’akov Gal
• Sarit Kraus
• Elad Dokow
• Amos Azaria

Despite committees and elections being widespread in the real-world, the design of agents for operating in humancomputer committees has received far less attention than the theoretical analysis of voting strategies. We address this gap by providing an agent design that outperforms other voters in groups comprising both people and computer agents. In our setting participants vote by simultaneously submitting a ranking over a set of candidates and the election system uses a social welfare rule to select a ranking that minimizes disagreements with participants’ votes. We ran an extensive study in which hundreds of people participated in repeated voting rounds with other people as well as computer agents that differed in how they employ strategic reasoning in their voting behavior. Our results show that over time, people learn to deviate from truthful voting strategies, and use heuristics to guide their play, such as repeating their vote from the previous round. We show that a computer agent using a best response voting strategy was able to outperform people in the game. Our study has implication for agent designers, highlighting the types of strategies that enable agents to succeed in committees comprising both human and computer participants. This is the first work to study the role of computer agents in voting settings involving both human and agent participants.

AAMAS Conference 2012 Conference Paper

Automated Agents for Human Persuasion

• Amos Azaria

AAAI Conference 2012 Conference Paper

Automated Strategies for Determining Rewards for Human Work

• Amos Azaria
• Yonatan Aumann
• Sarit Kraus

We consider the problem of designing automated strategies for interactions with human subjects, where the humans must be rewarded for performing certain tasks of interest. We focus on settings where there is a single task that must be performed many times by different humans (e. g. answering a questionnaire), and the humans require a fee for performing the task. In such settings, our objective is to minimize the average cost for effectuating the completion of the task. We present two automated strategies for designing efficient agents for the problem, based on two different models of human behavior. The first, the Reservation Price Based Agent (RPBA), is based on the concept of a reservation price, and the second, the No Bargaining Agent (NBA), uses principles from behavioral science. The performance of the agents has been tested in extensive experiments with real human subjects, where NBA outperforms both RPBA and strategies developed by human experts.

AAMAS Conference 2012 Conference Paper

Giving Advice to People in Path Selection Problems

• Amos Azaria
• Zinovi Rabinovich
• Sarit Kraus
• Claudia Goldman
• Omer Tsimhoni

We present a novel computational method for advice-generation in path selection problems which are difficult for people to solve. The advisor agent's interests may conflict with the interests of the people who receive the advice. Such optimization settings arise in many human-computer applications in which agents and people are self-interested but also share certain goals, such as automatic route-selection systems that also reason about environmental costs. This paper presents an agent that clusters people into one of several types, based on how their path selection behavior adheres to the paths presented to them by the agent who does not necessarily suggest their most preferred paths. It predicts the likelihood that people will deviate from these suggested paths and uses a decision theoretic approach to suggest paths to people which will maximize the agent's expected benefit given the people's deviations. This technique was evaluated empirically in an extensive study involving hundreds of human subjects solving the path selection problem in mazes. Results showed that the agent was able to outperform alternative methods that solely considered the benefit to the agent or the person, or did not provide any advice.

AAAI Conference 2012 Conference Paper

Strategic Advice Provision in Repeated Human-Agent Interactions

• Amos Azaria
• Zinovi Rabinovich
• Sarit Kraus
• Claudia Goldman
• Ya'akov Gal

This paper addresses the problem of automated advice provision in settings that involve repeated interactions between people and computer agents. This problem arises in many real world applications such as route selection systems and office assistants. To succeed in such settings agents must reason about how their actions in the present influence people’s future actions. This work models such settings as a family of repeated bilateral games of incomplete information called “choice selection processes”, in which players may share certain goals, but are essentially self-interested. The paper describes several possible models of human behavior that were inspired by behavioral economic theories of people’s play in repeated interactions. These models were incorporated into several agent designs to repeatedly generate offers to people playing the game. These agents were evaluated in extensive empirical investigations including hundreds of subjects that interacted with computers in different choice selections processes. The results revealed that an agent that combined a hyperbolic discounting model of human behavior with a social utility function was able to outperform alternative agent designs, including an agent that approximated the optimal strategy using continuous MDPs and an agent using epsilongreedy strategies to describe people’s behavior. We show that this approach was able to generalize to new people as well as choice selection processes that were not used for training. Our results demonstrate that combining computational approaches with behavioral economics models of people in repeated interactions facilitates the design of advice provision strategies for a large class of real-world settings.

AAAI Conference 2012 Conference Paper

Strategic Advice Provision in Repeated Human-Agent Interactions (Abstract)

• Amos Azaria
• Zinovi Rabinovich
• Sarit Kraus
• Claudia Goldman
• Ya'akov Gal

This paper addresses the problem of automated advice provision in settings that involve repeated interactions between people and computer agents. This problem arises in many real world applications such as route selection systems and office assistants. To succeed in such settings agents must reason about how their actions in the present influence people’s future actions. The paper describes several possible models of human behavior that were inspired by behavioral economic theories of people’s play in repeated interactions. These models were incorporated into several agent designs to repeatedly generate offers to people playing the game. These agents were evaluated in extensive empirical investigations including hundreds of subjects that interacted with computers in different choice selections processes. The results revealed that an agent that combined a hyperbolic discounting model of human behavior with a social utility function was able to outperform alternative agent designs. We show that this approach was able to generalize to new people as well as choice selection processes that were not used for training. Our results demonstrate that combining computational approaches with behavioral economics models of people in repeated interactions facilitates the design of advice provision strategies for a large class of real-world settings.

AAAI Conference 2011 Conference Paper

Strategic Information Disclosure to People with Multiple Alternatives

• Amos Azaria
• Zinovi Rabinovich
• Sarit Kraus
• Claudia Goldman

This paper studies how automated agents can persuade humans to behave in certain ways. The motivation behind such agent’s behavior resides in the utility function that the agent’s designer wants to maximize and which may be different from the user’s utility function. Specifically, in the strategic settings studied, the agent provides correct yet partial information about a state of the world that is unknown to the user but relevant to his decision. Persuasion games were designed to study interactions between automated players where one player sends state information to the other to persuade it to behave in a certain way. We show that this game theory based model is not sufficient to model human-agent interactions, since people tend to deviate from the rational choice. We use machine learning to model such deviation in people from this game theory based model. The agent generates a probabilistic description of the world state that maximizes its benefit and presents it to the users. The proposed model was evaluated in an extensive empirical study involving road selection tasks that differ in length, costs and congestion. Results showed that people’s behavior indeed deviated significantly from the behavior predicted by the game theory based model. Moreover, the agent developed in our model performed better than an agent that followed the behavior dictated by the game-theoretical models.