Sarit Kraus

JAAMAS Journal 2026 Journal Article

A Logic for Characterizing Multiple Bounded Agents

• John Grant
• Sarit Kraus
• Donald Perlis

Abstract We describe a meta-logic for characterizing the evolving internal reasoning of various families of agents. We view the reasoning of agents as ongoing processes rather than as fixed sets of conclusions. Our approach utilizes a strongly sorted calculus, distinguishing the application language, time, and various syntactic sorts. We have established soundness and completeness results corresponding to various families of agents. This allows for useful and intuitively natural characterizations of such agents' reasoning abilities. We discuss and contrast consistency issues as in the work of Montague and Thomason. We also show how to represent the concept of focus of attention in this framework.

AAAI Conference 2026 Conference Paper

EvoGrad: Evolutionary-Weighted Gradient and Hessian Learning for Black-Box Optimization

• Yedidya Kfir
• Elad Sarafian
• Yoram Louzoun
• Sarit Kraus

Black-box algorithms aim to optimize functions without access to their analytical structure or gradient information, making them essential when gradients are unavailable or computationally expensive to obtain. Traditional methods for black-box optimization (BBO) primarily utilize non-parametric models, but these approaches often struggle to scale effectively in large input spaces. Conversely, parametric approaches, which rely on neural estimators and gradient signals via backpropagation, frequently encounter substantial gradient estimation errors, limiting their reliability. Explicit Gradient Learning (EGL), a recent advancement, directly learns gradients using a first-order Taylor approximation and has demonstrated superior performance compared to both parametric and non-parametric methods. However, EGL inherently remains local and myopic, often faltering on highly non-convex optimization landscapes. In this work, we address this limitation by integrating global statistical insights from the evolutionary algorithm CMA-ES into the gradient learning framework, effectively biasing gradient estimates towards regions with higher optimization potential. Moreover, we enhance the gradient learning process by estimating the Hessian matrix, allowing us to correct the second-order residual of the Taylor series approximation. Our proposed algorithm, EvoGrad2 (Evolutionary Gradient Learning with second-order approximation), achieves state-of-the-art results on the synthetic COCO test suite, exhibiting significant advantages in high-dimensional optimization problems. We further demonstrate EvoGrad2's effectiveness on challenging real-world machine learning tasks, including adversarial training and code generation, highlighting its ability to produce more robust, high-quality solutions. Our results underscore EvoGrad2's potential as a powerful tool for researchers and practitioners facing complex, high-dimensional, and non-linear optimization problems.

AAAI Conference 2026 Conference Paper

Explaining Decentralized Multi-Agent Reinforcement Learning Policies

• Kayla Boggess
• Sarit Kraus
• Lu Feng

Multi-Agent Reinforcement Learning (MARL) has gained significant interest in recent years, enabling sequential decision-making across multiple agents in various domains. However, most existing explanation methods focus on centralized MARL, failing to address the uncertainty and nondeterminism inherent in decentralized settings. We propose methods to generate policy summarizations that capture task ordering and agent cooperation in decentralized MARL policies, along with query-based explanations for “When,” “Why Not,” and “What” types of user queries about specific agent behaviors. We evaluate our approach across four MARL domains and two decentralized MARL algorithms, demonstrating its generalizability and computational efficiency. User studies show that our summarizations and explanations significantly improve user question-answering performance and enhance subjective ratings on metrics such as understanding and satisfaction.

JAAMAS Journal 2026 Journal Article

Negotiation on Data Allocation in Multi-Agent Environments

• Rina Azoulay-Schwartz
• Sarit Kraus

Abstract In this paper, we consider the problem of data allocation in environments of self-motivated servers, where information servers respond to queries from users. New data items arrive frequently and have to be allocated in the distributed system. The servers have no common interests, and each server is concerned with the exact location of each of the data items. There is also no central controller. We suggest using a negotiation framework which takes into account the passage of time during the negotiation process itself. Using this negotiation mechanism, the servers have simple and stable negotiation strategies that result in efficient agreements without delays. We provide heuristics for finding the details of the strategies which depend on the specific settings of the environment and which cannot be provided to the agents in advance. We demonstrate the quality of the heuristics, using simulations. We consider situations characterized by complete, as well as incomplete, information and prove that our methods yield better results than the static allocation policy currently used for data allocation for servers in distributed systems.

IS Journal 2026 Journal Article

The Microsoft-Northwestern-WITNESS Benchmark for Deepfake Detection

• Thomas Roca
• Marco Postiglione
• Chongyang Gao
• Isabel Gortner
• Zuzanna Wojciak
• Pengce Wang
• Mahsa Alimardani
• Shirin Anlen

We introduce the Microsoft-Northwestern-WITNESS (MNW) deepfake detection benchmark, a dataset designed to evaluate and improve artificial intelligence (AI)-generated content detection algorithms. The dataset contains more than 50, 000 artifacts (images, videos, and audio files) generated by us. It also includes real-world examples of AI-manipulated or suspicious media encountered by journalists and human rights defenders globally, annotated by experts to reflect practical, high-stakes detection scenarios. The MNW dataset will be periodically updated to cover emerging generators and includes adversarial examples created with state-of-the-art attacks. This is a collaborative effort, and we encourage generative AI model developers to help maintain the dataset’s currency. This dataset is intended solely for evaluation purposes and cannot be used for training or commercial purposes. We recommend that entities purchasing detection solutions avoid using our dataset to evaluate commercial tools. Our goal is to establish high standards for developers and enhance the reliability of detection systems.

IS Journal 2026 Journal Article

Top 10 Most Influential Papers in Artificial Intelligence Since 2000

• Bo An
• Sarit Kraus
• Michael Wooldridge

To commemorate the 70th anniversary of artificial intelligence (AI), IEEE Intelligent Systems has identified the 10 most impactful articles in AI published since 2000, marking the field’s evolution from its 1956 origins into a foundational pillar of modern science. The selection process combined rigorous quantitative indicators with the informed judgment of a panel of distinguished experts. The resulting list reflects a broad consensus on the milestones that have redefined AI, spanning the diverse and multifaceted landscape of the discipline. Together, these landmark articles laid the foundations for modern AI and continue to influence its evolution.

AAAI Conference 2025 Conference Paper

Bayesian Persuasion with Externalities: Exploiting Agent Types

• Jonathan Shaki
• Jiarui Gan
• Sarit Kraus

We study a Bayesian persuasion problem with externalities. In this model, a principal sends signals to inform multiple agents about the state of the world. Simultaneously, due to the existence of externalities in the agents' utilities, the principal also acts as a correlation device to correlate the agents' actions. We consider the setting where the agents are categorized into a small number of types. Agents of the same type share identical utility functions and are treated equitably in the utility functions of both other agents and the principal. We study the problem of computing optimal signaling strategies for the principal, under three different types of signaling channels: public, private, and semi-private. Our results include revelation-principle-style characterizations of optimal signaling strategies, linear programming formulations, and analysis of in/tractability of the optimization problems. It is demonstrated that when the maximum number of deviating agents is bounded by a constant, our LP-based formulations compute optimal signaling strategies in polynomial time. Otherwise, the problems are NP-hard.

AAMAS Conference 2025 Conference Paper

Contrastive Explainable Clustering with Differential Privacy

• DungXXX Nguyen
• Ariel Vetzler
• Sarit Kraus
• Anil Vullikanti

This paper presents a novel approach to Explainable AI (XAI) that combines contrastive explanations with differential privacy for clustering algorithms. Focusing on k-median and k-means problems, we calculate contrastive explanations as the utility difference between original clustering and clustering with a centroid fixed to a specific data point. This method provides personalized insights into centroid placement. Our key contribution is demonstrating that these differentially private explanations achieve essentially the same utility bounds as non-private explanations. Experiments across various datasets show that our approach offers meaningful, privacy-preserving, and individually relevant explanations without significantly compromising clustering utility. This work advances privacy-aware machine learning by balancing data protection, explanation quality, and personalization in clustering tasks.

AIJ Journal 2025 Journal Article

Defending a city from multi-drone attacks: A sequential Stackelberg security games approach

• Dolev Mutzari
• Tonmoay Deb
• Cristian Molinaro
• Andrea Pugliese
• V.S. Subrahmanian
• Sarit Kraus

AAAI Conference 2025 Conference Paper

Explaining Decisions of Agents in Mixed-Motive Games

• Maayan Orner
• Oleg Maksimov
• Akiva Kleinerman
• Charles Ortiz
• Sarit Kraus

In recent years, agents have become capable of communicating seamlessly via natural language and navigating in environments that involve cooperation and competition, a fact that can introduce social dilemmas. Due to the interleaving of cooperation and competition, understanding agents' decision-making in such environments is challenging, and humans can benefit from obtaining explanations. However, such environments and scenarios have rarely been explored in the context of explainable AI. While some explanation methods for cooperative environments can be applied in mixed-motive setups, they do not address inter-agent competition, cheap-talk, or implicit communication by actions. In this work, we design explanation methods to address these issues. Then, we proceed to establish generality and demonstrate the applicability of the methods to three games with vastly different properties. Lastly, we demonstrate the effectiveness and usefulness of the methods for humans in two mixed-motive games. The first is a challenging 7-player game called no-press Diplomacy. The second is a 3-player game inspired by the prisoner's dilemma, featuring communication in natural language.

ECAI Conference 2025 Conference Paper

Facilitating Matches on Allocation Platforms

• Yohai Trabelsi
• Abhijin Adiga
• Yonatan Aumann
• Sarit Kraus
• S. S. Ravi

We consider a setting where goods are allocated to agents by way of an allocation platform (e. g. , a matching platform). An “allocation facilitator” aims to increase the overall utility/social-good of the allocation by encouraging (some of the) agents to relax (some of) their restrictions. At the same time, the advice must not hurt agents who would otherwise be better off. Additionally, the facilitator may be constrained by a “bound” (a. k. a. ‘budget’), limiting the number and/or type of restrictions it may seek to relax. We consider the facilitator’s optimization problem of choosing an optimal set of restrictions to request to relax under the aforementioned constraints. Our contributions are three-fold: (i) We provide a formal definition of the problem, including the participation guarantees to which the facilitator should adhere. We define a hierarchy of participation guarantees and also consider several social-good functions. (ii) We provide polynomial algorithms for solving various versions of the associated optimization problems, including one-to-one and many-to-one allocation settings. (iii) We demonstrate the benefits of such facilitation and relaxation, and the implications of the different participation guarantees, using extensive experimentation on three real-world datasets.

AAAI Conference 2025 System Paper

GODDS: The Global Online Deepfake Detection System

• Marco Postiglione
• Julian Baldwin
• Natalia Denisenko
• Luke Fosdick
• Chongyang Gao
• Isabel Gortner
• Chiara Pulice
• Sarit Kraus

Fake audios, videos, and images are now proliferating widely. We developed GODDS, the Global Online Deepfake Detection system, for a specific user community, namely journalists. GODDS leverages an ensemble of deepfake detectors, along with a human in the loop, to provide a deepfake report on each submitted video/image/audio or VIA artifact submitted to the system. To date, VIA artifacts submitted by over 50 journalists from outlets such as the New York Times, Wall Street Journal, CNN, Agence France Press, and others have been run through GODDS. Unlike other deepfake detection systems, GODDS doesn't just focus on the submitted artifact but automatically derives context about the subject of the VIA artifact. Because context is not always available on all subjects, GODDS focuses on alleged deepfakes of high profile individuals, organizations, and events, where there is likely to be considerable contextual information.

AAAI Conference 2025 Conference Paper

Heterogeneous Multi-Robot Graph Coverage with Proximity and Movement Constraints

• Dolev Mutzari
• Yonatan Aumann
• Sarit Kraus

Multi-Robot Coverage problems have been extensively studied in robotics, planning and multi-agent systems. In this work, we consider the coverage problem when there are constraints on the proximity (e.g., maximum distance between the agents, or a blue agent must be adjacent to a red agent) and the movement (e.g., terrain traversability and material load capacity) of the robots. Such constraints naturally arise in many real-world applications, e.g. in search-and-rescue and maintenance operations. Given such a setting, the goal is to compute a covering tour of the graph with a minimum number of steps, and that adheres to the proximity and movement constraints. For this problem, our contributions are four: (i) a formal formulation of the problem, (ii) an exact algorithm that is FPT in parameters ||F||, d and ω - the set of robot formations that encode the proximity constraints, the maximum nodes degree, and the tree-width of the graph, respectively, (iii) for the case that the graph is a tree: a PTAS approximation scheme, that given an ε produces a tour that is within a 1+ ε⋅error(||F||, d)) of the optimal one, and the computation runs in time poly(n) ⋅ h(1/ε, ||F||). (iv) for the case that the graph is a tree, with k=3 robots, and the constraint is that all agents are connected: a PTAS scheme with multiplicative approximation error of 1 + O(ε), independent of d.

AAAI Conference 2025 Conference Paper

Towards Computational Foreseeability

• Sarit Kraus
• Kayla Boggess
• Robert Kim
• Bryan H. Choi
• Lu Feng

This paper addresses the challenges of computational accountability in autonomous systems, particularly in Autonomous Vehicles (AVs), where safety and efficiency often conflict. We begin by examining current approaches such as cost minimization, reward maximization, human-centered approaches, and ethical frameworks, noting their limitations addressing these challenges. Foreseeability is a central concept in tort law that limits the accountability and legal liability of an actor to a reasonable scope. Yet, current data-driven methods to determine foreseeability are rigid, ignore uncertainty, and depend on simulation data. In this work, we advocate for a new computational approach to establish foreseeability of autonomous systems based on the legal “BPL” formula. We provide open research challenges, using fully autonomous vehicles as a motivating example, and call for researchers to help autonomous systems make accountable decisions in safety-critical scenarios.

AAAI Conference 2025 Conference Paper

Voter Priming Campaigns: Strategies, Equilibria, and Algorithms

• Jonathan Shaki
• Yonatan Aumann
• Sarit Kraus

Issue salience is a major determinant in voters' decisions. Candidates and political parties campaign to shift salience to their advantage - a process termed priming. We study the dynamics, strategies and equilibria of campaign spending for voter priming in multi-issue multi-party settings. We consider both parliamentary elections, where parties aim to maximize their share of votes, and various settings for presidential elections, where the winner takes all. For parliamentary elections, we show that pure equilibrium spending always exists and can be computed in time linear in the number of voters. For two parties and all settings, a spending equilibrium exists such that each party invests only in a single issue, and an equilibrium can be computed in time that is polynomial in the number of issues and linear in the number of voters. We also show that in most presidential settings no equilibrium exists. Additional properties of optimal campaign strategies are also studied.

IJCAI Conference 2024 Conference Paper

ADESSE: Advice Explanations in Complex Repeated Decision-Making Environments

• Sören Schleibaum
• Lu Feng
• Sarit Kraus
• JÖRG P. MÜLLER

In the evolving landscape of human-centered AI, fostering a synergistic relationship between humans and AI agents in decision-making processes stands as a paramount challenge. This work considers a problem setup where an intelligent agent comprising a neural network-based prediction component and a deep reinforcement learning component provides advice to a human decision-maker in complex repeated decision-making environments. Whether the human decision-maker would follow the agent's advice depends on their beliefs and trust in the agent and on their understanding of the advice itself. To this end, we developed an approach named ADESSE to generate explanations about the adviser agent to improve human trust and decision-making. Computational experiments on a range of environments with varying model sizes demonstrate the applicability and scalability of ADESSE. Furthermore, an interactive game-based user study shows that participants were significantly more satisfied, achieved a higher reward in the game, and took less time to select an action when presented with explanations generated by ADESSE. These findings illuminate the critical role of tailored, human-centered explanations in AI-assisted decision-making.

ICAPS Conference 2024 Conference Paper

Contrastive Explanations of Centralized Multi-agent Optimization Solutions

• Parisa Zehtabi
• Alberto Pozanco
• Ayala Bolch
• Daniel Borrajo
• Sarit Kraus

In many real-world scenarios, agents are involved in optimization problems. Since most of these scenarios are over-constrained, optimal solutions do not always satisfy all agents. Some agents might be unhappy and ask questions of the form “Why does solution S not satisfy property P? ”. We propose CMAOE, a domain-independent approach to obtain contrastive explanations by: (i) generating a new solution S′ where property P is enforced, while also minimizing the differences between S and S′; and (ii) highlighting the differences between the two solutions, with respect to the features of the objective function of the multi-agent system. Such explanations aim to help agents understanding why the initial solution is better in the context of the multi-agent system than what they expected. We have carried out a computational evaluation that shows that CMAOE can generate contrastive explanations for large multi-agent optimization problems. We have also performed an extensive user study in four different domains that shows that: (i) after being presented with these explanations, humans’ satisfaction with the original solution increases; and (ii) the constrastive explanations generated by CMAOE are preferred or equally preferred by humans over the ones generated by state of the art approaches.

IJCAI Conference 2024 Conference Paper

Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option

• Yohai Trabelsi
• Pan Xu
• Sarit Kraus

Assigning tasks to service providers is a frequent procedure across various applications. Often the tasks arrive dynamically while the service providers remain static. Preventing task rejection caused by service provider overload is of utmost significance. To ensure a positive experience in relevant applications for both service providers and tasks, fairness must be considered. To address the issue, we model the problem as an online matching within a bipartite graph and tackle two minimax problems: one focuses on minimizing the highest waiting time of a task, while the other aims to minimize the highest workload of a service provider. We show that the second problem can be expressed as a linear program and thus solved efficiently while maintaining a reasonable approximation to the objective of the first problem. We developed novel methods that utilize the two minimax problems. We conducted extensive simulation experiments using real data and demonstrated that our novel heuristics, based on the linear program, performed remarkably well.

IJCAI Conference 2024 Conference Paper

Intelligent Agents for Auction-based Federated Learning: A Survey

• Xiaoli Tang
• Han Yu
• Xiaoxiao Li
• Sarit Kraus

Auction-based federated learning (AFL) is an important emerging category of FL incentive mechanism design, due to its ability to fairly and efficiently motivate high-quality data owners to join data consumers' (i. e. , servers') FL training tasks. To enhance the efficiency in AFL decision support for stakeholders (i. e. , data consumers, data owners, and the auctioneer), intelligent agent-based techniques have emerged. However, due to the highly interdisciplinary nature of this field and the lack of a comprehensive survey providing an accessible perspective, it is a challenge for researchers to enter and contribute to this field. This paper bridges this important gap by providing a first-of-its-kind survey on the Intelligent Agents for AFL (IA-AFL) literature. We propose a unique multi-tiered taxonomy that organises existing IA-AFL works according to 1) the stakeholders served, 2) the auction mechanism adopted, and 3) the goals of the agents, to provide readers with a multi-perspective view into this field. In addition, we analyse the limitations of existing approaches, summarise the commonly adopted performance evaluation metrics, and discuss promising future directions leading towards effective and efficient stakeholder-oriented decision support in IA-AFL ecosystems.

AIJ Journal 2024 Journal Article

Negotiation strategies for agents with ordinal preferences: Theoretical analysis and human study

• Noam Hazon
• Sefi Erlich
• Ariel Rosenfeld
• Sarit Kraus

ECAI Conference 2024 Conference Paper

The Complexity of Manipulation of k-Coalitional Games on Graphs

• Hodaya Barr
• Yohai Trabelsi
• Sarit Kraus
• Liam Roditty
• Noam Hazon

In many settings, there is an organizer who would like to divide a set of agents into k coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such k-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.

AAMAS Conference 2024 Conference Paper

Value-based Resource Matching with Fairness Criteria: Application to Agricultural Water Trading

• Abhijin Adiga
• Yohai Trabelsi
• Tanvir Ferdousi
• Madhav Marathe
• S. S. Ravi
• Samarth Swarup
• Anil Kumar Vullikanti
• Mandy L. Wilson

Optimal allocation of agricultural water in the event of droughts is an important global problem. In addressing this problem, many aspects, including the welfare of farmers, the economy, and the environment, must be considered. Under this backdrop, our work focuses on several resource-matching problems accounting for agents with multi-crop portfolios, geographic constraints, and fairness. First, we address a matching problem where the goal is to maximize a welfare function in two-sided markets where buyers’ requirements and sellers’ supplies are represented by value functions that assign prices (or costs) to specified volumes of water. For the setting where the value functions satisfy certain monotonicity properties, we present an efficient algorithm that maximizes a social welfare function. When there are minimum water requirement constraints, we present a randomized algorithm which ensures that the constraints are satisfied in expectation. For a single seller–multiple buyers setting with fairness constraints, we design an efficient algorithm that maximizes the minimum level of satisfaction of any buyer. We also present computational complexity results that highlight the limits on the generalizability of our results. We evaluate the algorithms developed in our work with experiments on both real-world and synthetic data sets with respect to drought severity, value functions, and seniority of agents. ∗Both authors contributed equally to this work. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org).

ICML Conference 2023 Conference Paper

A Coupled Flow Approach to Imitation Learning

• Gideon Joseph Freund
• Elad Sarafian
• Sarit Kraus

In reinforcement learning and imitation learning, an object of central importance is the state distribution induced by the policy. It plays a crucial role in the policy gradient theorem, and references to it–along with the related state-action distribution–can be found all across the literature. Despite its importance, the state distribution is mostly discussed indirectly and theoretically, rather than being modeled explicitly. The reason being an absence of appropriate density estimation tools. In this work, we investigate applications of a normalizing flow based model for the aforementioned distributions. In particular, we use a pair of flows coupled through the optimality point of the Donsker-Varadhan representation of the Kullback-Leibler (KL) divergence, for distribution matching based imitation learning. Our algorithm, Coupled Flow Imitation Learning (CFIL), achieves state-of-the-art performance on benchmark tasks with a single expert trajectory and extends naturally to a variety of other settings, including the subsampled and state-only regimes.

AAMAS Conference 2023 Conference Paper

Allocation Problem in Remote Teleoperation: Online Matching with Offline Reusable Resources and Delayed Assignments

• Osnat Ackerman Viden
• Yohai Trabelsi
• Pan Xu
• Karthik Abinav Sankararaman
• Oleg Maksimov
• Sarit Kraus

Many applications where tasks should be assigned to agents can be modeled as matching in bipartite graphs. In this paper, we consider applications where tasks arrive dynamically and rejection of a task may have significant adverse effects on the requester, therefore performing the task with some delay is preferred over complete rejection. The performance time of a task depends on the task, the agent, and the assignment, and only its distribution is known in advance. The actual time is known only after the task performance when the agent is available for a new assignment. We consider such applications to be one of two arrival types. With the first type, the arrival distribution is known in advance, while there is no assumption about the arrival times and order with the second type. For the first type, we present an LP-based online algorithm with a competitive ratio of 0. 5. For the second type, we show no online algorithm with a constant competitive ratio. We run extensive experiments to evaluate our algorithm in a real-world dataset, demonstrating the advantages of the LP approach.

ECAI Conference 2023 Conference Paper

Cognitive Effects in Large Language Models

• Jonathan Shaki
• Sarit Kraus
• Michael J. Wooldridge

Large Language Models (LLMs) such as ChatGPT have received enormous attention over the past year and are now used by hundreds of millions of people every day. The rapid adoption of this technology naturally raises questions about the possible biases such models might exhibit. In this work, we tested one of these models (GPT-3) on a range of cognitive effects, which are systematic patterns that are usually found in human cognitive tasks. We found that LLMs are indeed prone to several human cognitive effects. Specifically, we show that the priming, distance, SNARC, and size congruity effects were presented with GPT-3, while the anchoring effect is absent. We describe our methodology, and specifically the way we converted real-world experiments to text-based experiments. Finally, we speculate on the possible reasons why GPT-3 exhibits these effects and discuss whether they are imitated or reinvented.

AIJ Journal 2023 Journal Article

Cooperative concurrent games

• Julian Gutierrez
• Szymon Kowara
• Sarit Kraus
• Thomas Steeples
• Michael Wooldridge

AAAI Conference 2023 Conference Paper

Customer Service Combining Human Operators and Virtual Agents: A Call for Multidisciplinary AI Research

• Sarit Kraus
• Yaniv Oshrat
• Yonatan Aumann
• Tal Hollander
• Oleg Maksimov
• Anita Ostroumov
• Natali Shechtman

The use of virtual agents (bots) has become essential for providing online assistance to customers. However, even though a lot of effort has been dedicated to the research, development, and deployment of such virtual agents, customers are frequently frustrated with the interaction with the virtual agent and require a human instead. We suggest that a holistic approach, combining virtual agents and human operators working together, is the path to providing satisfactory service. However, implementing such a holistic customer service system will not, and cannot, be achieved using any single AI technology or branch. Rather, such a system will inevitably require the integration of multiple and diverse AI technologies, including natural language processing, multi-agent systems, machine learning, reinforcement learning, and behavioral cloning; in addition to integration with other disciplines such as psychology, business, sociology, economics, operation research, informatics, computer-human interaction, and more. As such, we believe this customer service application offers a rich domain for experimentation and application of multidisciplinary AI. In this paper, we introduce the holistic customer service application and discuss the key AI technologies and disciplines required for a successful AI solution for this setting. For each of these AI technologies, we outline the key scientific questions and research avenues stemming from this setting. We demonstrate that integrating technologies from different fields can lead to a cost-effective successful customer service center. The challenge is that there is a need for several communities, each with its own language and modeling techniques, different problem-solving methods, and different evaluation methodologies, all of which need to work together. Real cooperation will require the formation of joint methodologies and techniques that could improve the service to customers, but, more importantly, open new directions in cooperation of diverse communities toward solving joint difficult tasks.

IJCAI Conference 2023 Conference Paper

Explainable Multi-Agent Reinforcement Learning for Temporal Queries

• Kayla Boggess
• Sarit Kraus
• Lu Feng

As multi-agent reinforcement learning (MARL) systems are increasingly deployed throughout society, it is imperative yet challenging for users to understand the emergent behaviors of MARL agents in complex environments. This work presents an approach for generating policy-level contrastive explanations for MARL to answer a temporal user query, which specifies a sequence of tasks completed by agents with possible cooperation. The proposed approach encodes the temporal query as a PCTL* logic formula and checks if the query is feasible under a given MARL policy via probabilistic model checking. Such explanations can help reconcile discrepancies between the actual and anticipated multi-agent behaviors. The proposed approach also generates correct and complete explanations to pinpoint reasons that make a user query infeasible. We have successfully applied the proposed approach to four benchmark MARL domains (up to 9 agents in one domain). Moreover, the results of a user study show that the generated explanations significantly improve user performance and satisfaction.

AAMAS Conference 2023 Conference Paper

Resilient Fair Allocation of Indivisible Goods

• Dolev Mutzari
• Yonatan Aumann
• Sarit Kraus

Fair allocation of indivisible goods has been studied extensively. However, the solutions offered to date are not resilient to subsequent changes that may occur after the allocation has been decided and executed, e. g. , agents leaving the system, or additional goods are discovered. Currently, such settings require rerunning the allocation algorithm from scratch, potentially shifting most allocated goods between the agents. This can be cumbersome at best, or impossible at worst. In this paper, we study the notion of resilience, which quantifies the number of changes needed to resolve subsequent changes in the environment. We then apply it to the problem of fair allocation of indivisible goods, focusing on the EF1 and EFX solution concepts. For the EF1 solution concept, we provide constructive and efficient algorithms to restore EF1 after a simultaneous loss of goods, addition of new goods, and resignation of agents. We show that the addition of new agents cannot be resolved efficiently when the agents’ valuation may be arbitrary. When agents have identical valuations, we show how to accept new agents efficiently. For the EFX solution concept, we (mostly) prove negative results, establishing that restoring EFX may be prohibitively costly, even for agents with identical valuations.

AAAI Conference 2023 Conference Paper

Resource Sharing through Multi-Round Matchings

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi
• Daniel J. Rosenkrantz

Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.

EUMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Abstract Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing sknowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

AAMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing structured knowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

IROS Conference 2022 Conference Paper

Analyzing and Overcoming Degradation in Warm-Start Reinforcement Learning

• Benjamin Wexler
• Elad Sarafian
• Sarit Kraus

Reinforcement Learning (RL) for robotic applications can benefit from a warm-start where the agent is initialized with a pretrained behavioral policy. However, when transitioning to RL updates, degradation in performance can occur, which may compromise the robot's safety. This degradation, which constitutes an inability to properly utilize the pretrained policy, is attributed to extrapolation error in the value function, a result of high values being assigned to Out-Of-Distribution actions not present in the behavioral policy's data. We investigate why the magnitude of degradation varies across policies and why the policy fails to quickly return to behavioral performance. We present visual confirmation of our analysis and draw comparisons to the Offline RL setting which suffers from similar difficulties. We propose a novel method, Confidence Constrained Learning (CCL) for Warm-Start RL, that reduces degradation by balancing between the policy gradient and constrained learning according to a confidence measure of the Q-values. For the constrained learning component we propose a novel objective, Positive Q-value Distance (CCL-PQD). We investigate a variety of constraint-based methods that aim to overcome the degradation, and find they constitute solutions for a multi-objective optimization problem between maximimal performance and miniminal degradation. Our results demonstrate that hyperparameter tuning for CCL-PQD produces solutions on the Pareto Front of this multi-objective problem, allowing the user to balance between performance and tolerable compromises to the robot's safety.

AIJ Journal 2022 Journal Article

Defense coordination in security games: Equilibrium analysis and mechanism design

• Jiarui Gan
• Edith Elkind
• Sarit Kraus
• Michael Wooldridge

EUMAS Conference 2022 Conference Paper

Explainability in Mechanism Design: Recent Advances and the Road Ahead

• Sharadhi Alape Suryanarayana
• David Sarne
• Sarit Kraus

Abstract Designing and implementing explainable systems is seen as the next step towards increasing user trust in, acceptance of and reliance on Artificial Intelligence (AI) systems. While explaining choices made by black-box algorithms such as machine learning and deep learning has occupied most of the limelight, systems that attempt to explain decisions (even simple ones) in the context of social choice are steadily catching up. In this paper, we provide a comprehensive survey of explainability in mechanism design, a domain characterized by economically motivated agents and often having no single choice that maximizes all individual utility functions. We discuss the main properties and goals of explainability in mechanism design, distinguishing them from those of Explainable AI in general. This discussion is followed by a thorough review of the challenges one may face when working on Explainable Mechanism Design and propose a few solution concepts to those.

ICAPS Conference 2022 Conference Paper

Explaining Preference-Driven Schedules: The EXPRES Framework

• Alberto Pozanco
• Francesca Mosca
• Parisa Zehtabi
• Daniele Magazzeni
• Sarit Kraus

Scheduling is the task of assigning a set of scarce resources distributed over time to a set of agents, who typically have preferences over the assignments they would like to get. Due to the constrained nature of these problems, satisfying all agents' preferences often turns infeasible, which might lead to some agents not being happy with the resulting schedule. Providing explanations has been shown to increase satisfaction and trust in solutions produced by AI tools. However, explaining schedules poses some particular challenges such as problem interpretability (i. e. , generating explanations from a huge and dense amount of information) and privacy preservation (i. e. , generating explanations respecting the privacy of other agents involved). In this paper we introduce the EXPRES framework, that can explain why a given preference was unsatisfied in a given optimal schedule. The EXPRES framework consists of (i) an explanation generator, that, based on a Mixed-Integer Linear Programming model, finds the best set of reasons that can explain an unsatisfied preference; and (ii) an explanation parser, which translates the generated explanations into human interpretable ones, while preserving agents' privacy. Through simulations, we show that the explanation generator can efficiently scale to large instances. Finally, through a set of user studies within J. P. Morgan, we show that employees preferred the explanations generated by EXPRES over human-generated ones when considering workforce scheduling scenarios.

TIME Conference 2022 Conference Paper

Giving Instructions in Linear Temporal Logic

• Julian Gutierrez 0001
• Sarit Kraus
• Giuseppe Perelli
• Michael J. Wooldridge

Our aim is to develop a formal semantics for giving instructions to taskable agents, to investigate the complexity of decision problems relating to these semantics, and to explore the issues that these semantics raise. In the setting we consider, agents are given instructions in the form of Linear Temporal Logic (LTL) formulae; the intuitive interpretation of such an instruction is that the agent should act in such a way as to ensure the formula is satisfied. At the same time, agents are assumed to have inviolable and immutable background safety requirements, also specified as LTL formulae. Finally, the actions performed by an agent are assumed to have costs, and agents must act within a limited budget. For this setting, we present a range of interpretations of an instruction to achieve an LTL task Υ, intuitively ranging from "try to do this but only if you can do so with everything else remaining unchanged" up to "drop everything and get this done. " For each case we present a formal pre-/post-condition semantics, and investigate the computational issues that they raise.

AAMAS Conference 2022 Conference Paper

Justifying Social-Choice Mechanism Outcome for Improving Participant Satisfaction

• Sharadhi Alape Suryanarayana
• David Sarne
• Sarit Kraus

In many social-choice mechanisms the resulting choice is not the most preferred one for some of the participants, thus the need for methods to justify the choice made in a way that improves the acceptance and satisfaction of said participants. One natural method for providing such explanations is to ask people to provide them, e. g. , through crowdsourcing, and choosing the most convincing arguments among those received. In this paper we propose the use of an alternative approach, one that automatically generates explanations based on desirable mechanism features found in theoretical mechanism design literature. We test the effectiveness of both of the methods through a series of extensive experiments conducted with over 600 participants in ranked voting, a classic social choice mechanism. The analysis of the results reveals that explanations indeed affect both average satisfaction from and acceptance of the outcome in such settings. In particular, explanations are shown to have a positive effect on satisfaction and acceptance when the outcome (the winning candidate in our case) is the least desirable choice for the participant. A comparative analysis reveals that the automatically generated explanations result in similar levels of satisfaction from and acceptance of an outcome as with the more costly alternative of crowdsourced explanations, hence eliminating the need to keep humans in the loop. Furthermore, the automatically generated explanations significantly reduce participants’ belief that a different winner should have been elected compared to crowdsourced explanations.

AAMAS Conference 2022 Conference Paper

Maximizing Resource Allocation Likelihood with Minimum Compromise

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi

Many scenarios where agents with preferences compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have preferences that make them incompatible with some resources. We assume that a Principal chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their preferences within certain limits. The Principal’s goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We develop efficient algorithms for some variants of this budget-constrained maximization problem and establish hardness results for other variants. For the latter variants, we also develop algorithms with performance guarantees. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

EUMAS Conference 2022 Conference Paper

Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi

Abstract Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principal chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principal ’s goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

IJCAI Conference 2022 Conference Paper

Robust Solutions for Multi-Defender Stackelberg Security Games

• Dolev Mutzari
• Yonatan Aumann
• Sarit Kraus

Multi-defender Stackelberg Security Games (MSSG) have recently gained increasing attention in the literature. However, the solutions offered to date are highly sensitive, wherein even small perturbations in the attacker's utility or slight uncertainties thereof can dramatically change the defenders' resulting payoffs and alter the equilibrium. In this paper, we introduce a robust model for MSSGs, which admits solutions that are resistant to small perturbations or uncertainties in the game's parameters. First, we formally define the notion of robustness, as well as the robust MSSG model. Then, for the non-cooperative setting, we prove the existence of a robust approximate equilibrium in any such game, and provide an efficient construction thereof. For the cooperative setting, we show that any such game admits a robust approximate (alpha) core, and provide an efficient construction thereof. Lastly, we show that stronger types of the core may be empty. Interestingly, the robust solutions can substantially increase the defenders' utilities over those of the non-robust ones.

IJCAI Conference 2022 Conference Paper

Toward Policy Explanations for Multi-Agent Reinforcement Learning

• Kayla Boggess
• Sarit Kraus
• Lu Feng

Advances in multi-agent reinforcement learning (MARL) enable sequential decision making for a range of exciting multi-agent applications such as cooperative AI and autonomous driving. Explaining agent decisions is crucial for improving system transparency, increasing user satisfaction, and facilitating human-agent collaboration. However, existing works on explainable reinforcement learning mostly focus on the single-agent setting and are not suitable for addressing challenges posed by multi-agent environments. We present novel methods to generate two types of policy explanations for MARL: (i) policy summarization about the agent cooperation and task sequence, and (ii) language explanations to answer queries about agent behavior. Experimental results on three MARL domains demonstrate the scalability of our methods. A user study shows that the generated explanations significantly improve user performance and increase subjective ratings on metrics such as user satisfaction.

AAAI Conference 2021 Conference Paper

Coalition Formation in Multi-defender Security Games

• Dolev Mutzari
• Jiarui Gan
• Sarit Kraus

We study Stackelberg security game (SSG) with multiple defenders, where heterogeneous defenders need to allocate security resources to protect a set of targets against a strategic attacker. In such games, coordination and cooperation between the defenders can increase their ability to protect their assets, but the heterogeneous preferences of the selfinterested defenders often make such cooperation very difficult. In this paper, we approach the problem from the perspective of cooperative game theory and study coalition formation among the defenders. Our main contribution is a number of algorithmic results for the computation problems that arise in this model. We provide a poly-time algorithm for computing a solution in the core of the game and show that all of the elements in the core are Pareto efficient. We show that the problem of computing the entire core is NP-hard and then delve into a special setting where the size of a coalition is limited up to some threshold. We analyse the parameterized complexity of deciding if a coalition structure is in the core under this special setting, and provide a poly-time algorithm for computing successful deviation strategies for a given coalition.

JAAMAS Journal 2021 Journal Article

Information Design in Affiliate Marketing

• Sharadhi Alape Suryanarayana
• David Sarne
• Sarit Kraus

Abstract The recent massive proliferation of affiliate marketing suggests a new e-commerce paradigm which involves sellers, affiliates and the platforms that connect them. In particular, the fact that prospective buyers may become acquainted with the promotion through more than one affiliate to whom they are connected calls for new mechanisms for compensating affiliates for their promotional efforts. In this paper, we study the problem of a platform that needs to decide on the commission to be awarded to affiliates for promoting a given product or service. Our equilibrium-based analysis, which applies to the case where affiliates are a priori homogeneous and self-interested, enables showing that a minor change in the way the platform discloses information to the affiliates results in a tremendous (positive) effect on the platform’s expected profit. In particular, we show that with the revised mechanism the platform can overcome the multi-equilibria problem that arises in the traditional mechanism and obtain a profit which is at least as high as the maximum profit in any of the equilibria that hold in the latter.

IJCAI Conference 2021 Conference Paper

Manipulation of k-Coalitional Games on Social Networks

• Naftali Waxman
• Sarit Kraus
• Noam Hazon

In many coalition formation games the utility of the agents depends on a social network. In such scenarios there might be a manipulative agent that would like to manipulate his connections in the social network in order to increase his utility. We study a model of coalition formation in which a central organizer, who needs to form k coalitions, obtains information about the social network from the agents. The central organizer has her own objective: she might want to maximize the utilitarian social welfare, maximize the egalitarian social welfare, or only guarantee that every agent will have at least one connection within her coalition. In this paper we study the susceptibility for manipulation of these objectives, given the abilities and information that the manipulator has. Specifically, we show that if the manipulator has very limited information, namely he is only familiar with his immediate neighbours in the network, then a manipulation is almost always impossible. Moreover, if the manipulator is only able to add connections to the social network, then a manipulation is still impossible for some objectives, even if the manipulator has full information on the structure of the network. On the other hand, if the manipulator is able to hide some of his connections, then all objectives are susceptible to manipulation, even if the manipulator has limited information, i. e. , when he is familiar with his immediate neighbours and with their neighbours.

ICML Conference 2021 Conference Paper

Recomposing the Reinforcement Learning Building Blocks with Hypernetworks

• Elad Sarafian
• Shai Keynan
• Sarit Kraus

The Reinforcement Learning (RL) building blocks, i. e. $Q$-functions and policy networks, usually take elements from the cartesian product of two domains as input. In particular, the input of the $Q$-function is both the state and the action, and in multi-task problems (Meta-RL) the policy can take a state and a context. Standard architectures tend to ignore these variables’ underlying interpretations and simply concatenate their features into a single vector. In this work, we argue that this choice may lead to poor gradient estimation in actor-critic algorithms and high variance learning steps in Meta-RL algorithms. To consider the interaction between the input variables, we suggest using a Hypernetwork architecture where a primary network determines the weights of a conditional dynamic network. We show that this approach improves the gradient approximation and reduces the learning step variance, which both accelerates learning and improves the final performance. We demonstrate a consistent improvement across different locomotion tasks and different algorithms both in RL (TD3 and SAC) and in Meta-RL (MAML and PEARL).

AAAI Conference 2020 Conference Paper

Adversarial Fence Patrolling: Non-Uniform Policies for Asymmetric Environments

• Yaniv Oshrat
• Noa Agmon
• Sarit Kraus

Robot teams are very useful in patrol tasks, where the robots are required to repeatedly visit a target area in order to detect an adversary. In this work we examine the Fence Patrol problem, in which the robots must travel back and forth along an open polyline and the adversary is aware of the robots’ patrol strategy. Previous work has suggested nondeterministic patrol schemes, characterized by a uniform policy along the entire area, guaranteeing that the minimal probability of penetration detection throughout the area is maximized. We present a patrol strategy with a non-uniform policy along different points of the fence, based on the location and other properties of the point. We explore this strategy in different kinds of tracks and show that the minimal probability of penetration detection achieved by this non-uniform (variant) policy is higher than former policies. We further consider applying this model in multi-robot scenarios, exploiting robot cooperation to enhance patrol efficiency. We propose novel methods for calculating the variant values, and demonstrate their performance empirically.

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.

IJCAI Conference 2020 Conference Paper

Boolean Games: Inferring Agents' Goals Using Taxation Queries

• Abhijin Adiga
• Sarit Kraus
• Oleg Maksimov
• S. S. Ravi

In Boolean games, each agent controls a set of Boolean variables and has a goal represented by a propositional formula. We study inference problems in Boolean games assuming the presence of a PRINCIPAL who has the ability to control the agents and impose taxation schemes. Previous work used taxation schemes to guide a game towards certain equilibria. We present algorithms that show how taxation schemes can also be used to infer agents' goals. We present experimental results to demonstrate the efficacy our algorithms. We also consider goal inference when only limited information is available in response to a query.

IJCAI Conference 2020 Conference Paper

Constrained Policy Improvement for Efficient Reinforcement Learning

• Elad Sarafian
• Aviv Tamar
• Sarit Kraus

We propose a policy improvement algorithm for Reinforcement Learning (RL) termed Rerouted Behavior Improvement (RBI). RBI is designed to take into account the evaluation errors of the Q-function. Such errors are common in RL when learning the Q-value from finite experience data. Greedy policies or even constrained policy optimization algorithms that ignore these errors may suffer from an improvement penalty (i. e. , a policy impairment). To reduce the penalty, the idea of RBI is to attenuate rapid policy changes to actions that were rarely sampled. This approach is shown to avoid catastrophic performance degradation and reduce regret when learning from a batch of transition samples. Through a two-armed bandit example, we show that it also increases data efficiency when the optimal action has a high variance. We evaluate RBI in two tasks in the Atari Learning Environment: (1) learning from observations of multiple behavior policies and (2) iterative RL. Our results demonstrate the advantage of RBI over greedy policies and other constrained policy optimization algorithms both in learning from observations and in RL tasks.

JAAMAS Journal 2020 Journal Article

Electric vehicle charging strategy study and the application on charging station placement

• Yanhai Xiong
• Bo An
• Sarit Kraus

Abstract Optimal placement of charging stations for electric vehicles (EVs) is critical for providing convenient charging service to EV owners and promoting public acceptance of EVs. There has been a lot of work on EV charging station placement, yet EV drivers’ charging strategy, which plays an important role in deciding charging stations’ performance, is missing. EV drivers make choice among charging stations according to various factors, including the distance, the charging fare and queuing condition in different stations etc. In turn, some factors, like queuing condition, is greatly influenced by EV drivers’ choices. As more EVs visit the same station, longer queuing duration should be expected. This work first proposes a behavior model to capture the decision making of EV drivers in choosing charging stations, based on which an optimal charging station placement model is presented to minimize the social cost (defined as the congestion in charging stations suffered by all EV drivers). Through analyzing EV drivers’ decision-making in the charging process, we propose a k -Level nested Quantal Response Equilibrium charging behavior model inspired by Quantal Response Equilibrium model and level- k thinking model. We then design a set of user studies to simulate charging scenarios and collect data from human players to learn the parameters of different behavior models. Experimental results show that our charging behavior model can better capture the bounded rationality of human players in the charging activity compared with state-of-the-art behavior models. Furthermore, to evaluate the proposed charging behavior model, we formulate the charging station placement problem with it and design an algorithm to solve the problem. It is shown that our approach obtains placement with a significantly better performance to different extent, especially when the budget is limited and relatively low.

ICML Conference 2020 Conference Paper

Explicit Gradient Learning for Black-Box Optimization

• Elad Sarafian
• Mor Sinay
• Yoram Louzoun
• Noa Agmon
• Sarit Kraus

Black-Box Optimization (BBO) methods can find optimal policies for systems that interact with complex environments with no analytical representation. As such, they are of interest in many Artificial Intelligence (AI) domains. Yet classical BBO methods fall short in high-dimensional non-convex problems. They are thus often overlooked in real-world AI tasks. Here we present a BBO method, termed Explicit Gradient Learning (EGL), that is designed to optimize high-dimensional ill-behaved functions. We derive EGL by finding weak spots in methods that fit the objective function with a parametric Neural Network (NN) model and obtain the gradient signal by calculating the parametric gradient. Instead of fitting the function, EGL trains a NN to estimate the objective gradient directly. We prove the convergence of EGL to a stationary point and its robustness in the optimization of integrable functions. We evaluate EGL and achieve state-of-the-art results in two challenging problems: (1) the COCO test suite against an assortment of standard BBO methods; and (2) in a high-dimensional non-convex image generation task.

EAAI Journal 2020 Journal Article

Online prediction of time series with assumed behavior

• Ariel Rosenfeld
• Moshe Cohen
• Sarit Kraus
• Joseph Keshet

AIJ Journal 2020 Journal Article

When security games hit traffic: A deployed optimal traffic enforcement system

• Ariel Rosenfeld
• Oleg Maksimov
• Sarit Kraus

AAMAS Conference 2019 Conference Paper

Complexity and Approximations in Robust Coalition Formation via Max-Min k -Partitioning

• Anisse Ismaili
• Noam Hazon
• Emi Watanabe
• Makoto Yokoo
• Sarit Kraus

Coalition formation is beneficial to multi-agent systems, especially when the value of a coalition depends on the relationship among its members. However, an attack can significantly damage a coalition structure by disabling agents. Therefore, getting prepared in advance for such an attack is particularly important. We study a robust k-coalition formation problem modeled by max-min k-partition of a weighted graph. We show that this problem is ΣP 2 -complete, which holds even for k = 2 and arbitrary weights, or k = 3 and non-negative weights. We also propose the Iterated Best Response (IBR) algorithm which provides a run-time absolute bound for the approximation error and can be generalized to the max-min optimization version of any ΣP 2 -complete problem. We tested IBR on fairly large instances of both synthetic graphs and real life networks, yielding near optimal results in a reasonable time.

RLDM Conference 2019 Conference Abstract

Constrained Policy Improvement for Safe and Efficient Reinforcement Learn- ing

• Elad Sarafian
• Aviv Tamar
• Sarit Kraus

We propose a policy improvement algorithm for Reinforcement Learning (RL) which is called Rerouted Behavior Improvement (RBI). RBI is designed to take into account the evaluation errors of the Q- function. Such errors are common in RL when learning the Q-value from finite past experience data. Greedy policies or even constrained policy optimization algorithms which ignore these errors may suffer from an improvement penalty (i. e. a negative policy improvement). To minimize the improvement penalty, the RBI idea is to attenuate rapid policy changes of low probability actions which were less frequently sampled. This approach is shown to avoid catastrophic performance degradation and reduce regret when learning from a batch of past experience. Through a two-armed bandit with Gaussian distributed rewards example, we show that it also increases data efficiency when the optimal action has a high variance. We evaluate RBI in two tasks in the Atari Learning Environment: (1) learning from observations of multiple behavior policies and (2) iterative RL. Our results demonstrate the advantage of RBI over greedy policies and other constrained policy optimization algorithms as a safe learning approach and as a general data efficient learning algorithm. A Github repository of our RBI implementation is found at https: //github. com/eladsar/rbi/tree/rbi

AAMAS Conference 2019 Conference Paper

Cooperative Concurrent Games

• Julian Gutierrez
• Sarit Kraus
• Michael Wooldridge

In rational verification, one is interested in understanding which temporal logic properties will hold in a concurrent game, under the assumption that players choose strategies that form an equilibrium. Players are assumed to behave rationally in pursuit of individual goals, typically specified as temporal logic formulae. To date, rational verification has only been studied in noncooperative settings. In this paper, we extend the rational verification framework to cooperative games, in which players may form coalitions to collectively achieve their goals. We base our study on the computational model given by concurrent game structures and focus on the core as our basic solution concept. We show the core of a concurrent game can be logically characterised using ATL*, and study the computational complexity of key decision problems associated with the core, which range from problems in PSPACE to problems in 3EXPTIME. We also discuss a number of variants of the main definition of the core, leading to the issue of credible coalition formations, and a possible implementation of the main reasoning framework.

AAAI Conference 2019 Conference Paper

Emergency Department Online Patient-Caregiver Scheduling

• Hanan Rosemarin
• Ariel Rosenfeld
• Sarit Kraus

Emergency Departments (EDs) provide an imperative source of medical care. Central to the ED workflow is the patientcaregiver scheduling, directed at getting the right patient to the right caregiver at the right time. Unfortunately, common ED scheduling practices are based on ad-hoc heuristics which may not be aligned with the complex and partially conflicting ED’s objectives. In this paper, we propose a novel online deep-learning scheduling approach for the automatic assignment and scheduling of medical personnel to arriving patients. Our approach allows for the optimization of explicit, hospital-specific multi-variate objectives and takes advantage of available data, without altering the existing workflow of the ED. In an extensive empirical evaluation, using real-world data, we show that our approach can significantly improve an ED’s performance metrics.

AAAI Conference 2019 Short Paper

Emergency Department Online Patient-Caregiver Scheduling

• Hanan Rosemarin
• Ariel Rosenfeld
• Sarit Kraus

Emergency Departments (EDs) provide an imperative source of medical care. Central to the ED workflow is the patientcaregiver scheduling, directed at getting the right patient to the right caregiver at the right time. Unfortunately, common ED scheduling practices are based on ad-hoc heuristics which may not be aligned with the complex and partially conflicting ED’s objectives. In this paper, we propose a novel online deep-learning scheduling approach for the automatic assignment and scheduling of medical personnel to arriving patients. Our approach allows for the optimization of explicit, hospitalspecific multi-variate objectives and takes advantage of available data, without altering the existing workflow of the ED. In an extensive empirical evaluation, using real-world data, we show that our approach can significantly improve an ED’s performance metrics.

AIJ Journal 2019 Journal Article

Multi-robot adversarial patrolling: Handling sequential attacks

• Efrat Sless Lin
• Noa Agmon
• Sarit Kraus

AAMAS Conference 2018 Conference Paper

Combining Prediction of Human Decisions with ISMCTS in Imperfect Information Games

• Moshe Bitan
• Sarit Kraus

We present agents that perform well against humans in imperfect information games with partially observable actions. We introduce the Semi-Determinized-MCTS (SDMCTS), a variant of the Information Set MCTS algorithm (ISMCTS). SDMCTS generates a predictive model of the unobservable portion of the opponent’s actions from historical behavioral data. Next, SDMCTS performs simulations on an instance of the game where the unobservable portion of the opponent’s actions are determined. Thereby, it facilitates the use of the predictive model in order to decrease uncertainty. We present an implementation of the SDMCTS applied to the Cheat Game. Results from experiments with 120 subjects playing a head-to-head Cheat Game against our SDMCTS agents suggest that SDMCTS performs well against humans, and its performance improves as the predictive model’s accuracy increases.

AIJ Journal 2018 Journal Article

Forming k coalitions and facilitating relationships in social networks

• Liat Sless
• Noam Hazon
• Sarit Kraus
• Michael Wooldridge

KER Journal 2018 Journal Article

Leveraging human knowledge in tabular reinforcement learning: a study of human subjects

• Ariel Rosenfeld
• Moshe Cohen
• Matthew E. Taylor
• Sarit Kraus

Abstract Reinforcement learning (RL) can be extremely effective in solving complex, real-world problems. However, injecting human knowledge into an RL agent may require extensive effort and expertise on the human designer’s part. To date, human factors are generally not considered in the development and evaluation of possible RL approaches. In this article, we set out to investigate how different methods for injecting human knowledge are applied, in practice, by human designers of varying levels of knowledge and skill. We perform the first empirical evaluation of several methods, including a newly proposed method named State Action Similarity Solutions (SASS) which is based on the notion of similarities in the agent’s state–action space. Through this human study, consisting of 51 human participants, we shed new light on the human factors that play a key role in RL. We find that the classical reward shaping technique seems to be the most natural method for most designers, both expert and non-expert, to speed up RL. However, we further find that our proposed method SASS can be effectively and efficiently combined with reward shaping, and provides a beneficial alternative to using only a single-speedup method with minimal human designer effort overhead.

IJCAI Conference 2018 Conference Paper

Negotiation Strategies for Agents with Ordinal Preferences

• Sefi Erlich
• Noam Hazon
• Sarit Kraus

Negotiation is a very common interaction between automated agents. Many common negotiation protocols work with cardinal utilities, even though ordinal preferences, which only rank the outcomes, are easier to elicit from humans. In this work we concentrate on negotiation with ordinal preferences over a finite set of outcomes. We study an intuitive protocol for bilateral negotiation, where the two parties make offers alternately. We analyze the negotiation protocol under different settings. First, we assume that each party has full information about the other party's preference order. We provide elegant strategies that specify a sub-game perfect equilibrium for the agents. We further show how the studied negotiation protocol almost completely implements a known bargaining rule. Finally, we analyze the no information setting. We study several solution concepts that are distribution-free, and analyze both the case where neither party knows the preference order of the other party, and the case where only one party is uninformed.

IJCAI Conference 2018 Conference Paper

Optimal Cruiser-Drone Traffic Enforcement Under Energy Limitation

• Ariel Rosenfeld
• Oleg Maksimov
• Sarit Kraus

Drones can assist in mitigating traffic accidents by deterring reckless drivers, leveraging their flexible mobility. In the real world, drones are fundamentally limited by their battery/fuel capacity and have to be replenished during long operations. In this paper, we propose a novel approach where police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. We propose a binary integer linear program for determining the optimal rendezvous cruiser-drone enforcement policy which guarantees that all drones are replenished on time and minimizes the likelihood of accidents. In an extensive empirical evaluation, we first show that human drivers are expected to react to traffic enforcement drones in a similar fashion to how they react to police cruisers using a first-of-its-kind human study in realistic simulated driving. Then, we show that our proposed approach significantly outperforms the common practice of constructing stationary replenishment installations using both synthetic and real world road networks.

AAMAS Conference 2018 Conference Paper

Scheduling Spare Drones for Persistent Task Performance under Energy Constraints

• Erez Hartuv
• Noa Agmon
• Sarit Kraus

This paper considers the problem of enabling persistent execution of a multi-drone task under energy limitations. The drones are given a set of locations and their task is to ensure that at least one drone will be present, for example for monitoring, over each location at any given time. Because of energy limitations, drones must be replaced from time to time, and fly back home where their batteries can be replaced. Our goals are to identify the minimum number of spare drones needed to accomplish the task while no drone battery drains, and to provide a drone replacement strategy. We present an efficient procedure for calculating whether one spare drone is enough for a given task and provide an optimal replacement strategy. If more than one drone is needed, we aim at finding the minimum number of spare drones required, and extend the replacement strategy to multiple spare drones by introducing a new Bin-Packing variant, named Bin Maximum Item Double Packing (BMIDP). Since the problem is presumably computationally hard, we provide a first fit greedy approximation algorithm for efficiently solving the BMIDP problem. For the offline version, in which all locations are known in advance, we prove an approximation factor upper bound of 1. 5, and for the online version, in which locations are given one by one, we show via extensive simulations, that the approximation yields an average factor of 1. 7.

IROS Conference 2018 Conference Paper

UAV/UGV Search and Capture of Goal-Oriented Uncertain Targets*This research was supported in part by ISF grant #1337/15 and part by a grant from MOST, Israel and the JST Japan

• Mor Sinay
• Noa Agmon
• Oleg Maksimov
• Guy Levy
• Moshe Bitan
• Sarit Kraus

This paper considers a new, complex problem of UAV/UGV collaborative efforts to search and capture attackers under uncertainty. The goal of the defenders (UAV/UGV team) is to stop all attackers as quickly as possible, before they arrive at their selected goal. The uncertainty considered is twofold: the defenders do not know the attackers' location and destination, and there is also uncertainty in the defenders' sensing. We suggest a real-time algorithmic framework for the defenders, combining entropy and stochastic-temporal belief, that aims at optimizing the probability of a quick and successful capture of all of the attackers. We have empirically evaluated the algorithmic framework, and have shown its efficiency and significant performance improvement compared to other solutions.

ICAPS Conference 2017 Conference Paper

Augmenting Decisions of Taxi Drivers through Reinforcement Learning for Improving Revenues

• Tanvi Verma
• Pradeep Varakantham
• Sarit Kraus
• Hoong Chuin Lau

Taxis (which include cars working with car aggregation systems such as Uber, Grab, Lyft etc.) have become a critical component in the urban transportation. While most research and applications in the context of taxis have focused on improving performance from a customer perspective, in this paper, we focus on improving performance from a taxi driver perspective. Higher revenues for taxi drivers can help bring more drivers into the system thereby improving availability for customers in dense urban cities. Typically, when there is no customer on board, taxi drivers will cruise around to find customers either directly (on the street) or indirectly (due to a request from a nearby customer on phone or on aggregation systems). For such cruising taxis, we develop a Reinforcement Learning (RL) based system to learn from real trajectory logs of drivers to advise them on the right locations to find customers which maximize their revenue. There are multiple translational challenges involved in building this RL system based on real data, such as annotating the activities (e. g. , roaming, going to a taxi stand, etc.) observed in trajectory logs, identifying the right features for a state, action space and evaluating against real driver performance observed in the dataset. We also provide a dynamic abstraction mechanism to improve the basic learning mechanism. Finally, we provide a thorough evaluation on a real world data set from a developed Asian city and demonstrate that an RL based system can provide significant benefits to the drivers.

AIJ Journal 2017 Journal Article

Human–computer negotiation in a three player market setting

• Galit Haim
• Ya'akov (Kobi) Gal
• Bo An
• Sarit Kraus

AIJ Journal 2017 Journal Article

Intelligent agent supporting human–multi-robot team collaboration

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

IJCAI Conference 2017 Conference Paper

Leveraging Human Knowledge in Tabular Reinforcement Learning: A Study of Human Subjects

• Ariel Rosenfeld
• Matthew E. Taylor
• Sarit Kraus

Reinforcement Learning (RL) can be extremely effective in solving complex, real-world problems. However, injecting human knowledge into an RL agent may require extensive effort on the human designer's part. To date, human factors are generally not considered in the development and evaluation of possible approaches. In this paper, we propose and evaluate a novel method, based on human psychology literature, which we show to be both effective and efficient, for both expert and non-expert designers, in injecting human knowledge for speeding up tabular RL.

IJCAI Conference 2017 Conference Paper

Maintaining Communication in Multi-Robot Tree Coverage

• Mor Sinay
• Noa Agmon
• Oleg Maksimov
• Sarit Kraus
• David Peleg

Area coverage is an important task for mobile robots, mainly due to its applicability in many domains, such as search and rescue. In this paper we study the problem of multi-robot coverage, in which the robots must obey a strong communication restriction: they should maintain connectivity between teammates throughout the coverage. We formally describe the Multi-Robot Connected Tree Coverage problem, and an algorithm for covering perfect N-ary trees while adhering to the communication requirement. The algorithm is analyzed theoretically, providing guarantees for coverage time by the notion of speedup factor. We enhance the theoretically-proven solution with a dripping heuristic algorithm, and show in extensive simulations that it significantly decreases the coverage time. The algorithm is then adjusted to general (not necessarily perfect) N-ary trees and additional experiments prove its efficiency. Furthermore, we show the use of our solution in a simulated officebuilding scenario. Finally, we deploy our algorithm on real robots in a real office building setting, showing efficient coverage time in practice.

AIJ Journal 2017 Journal Article

Making friends on the fly: Cooperating with new teammates

• Samuel Barrett
• Avi Rosenfeld
• Sarit Kraus
• Peter Stone

AAAI Conference 2017 Conference Paper

Psychologically Based Virtual-Suspect for Interrogative Interview Training

• Moshe Bitan
• Galit Nahari
• Zvi Nisin
• Ariel Roth
• Sarit Kraus

In this paper, we present a Virtual-Suspect system which can be used to train inexperienced law enforcement personnel in interrogation strategies. The system supports different scenario configurations based on historical data. The responses presented by the Virtual-Suspect are selected based on the psychological state of the suspect, which can be configured as well. Furthermore, each interrogator’s statement affects the Virtual-Suspect’s current psychological state, which may lead the interrogation in different directions. In addition, the model takes into account the context in which the statements are made. Experiments with 24 subjects demonstrate that the Virtual-Suspect’s behavior is similar to that of a human who plays the role of the suspect.

AAMAS Conference 2017 Conference Paper

Speeding up Tabular Reinforcement Learning Using State-Action Similarities

• Ariel Rosenfeld
• Matthew E. Taylor
• Sarit Kraus

IJCAI Conference 2017 Conference Paper

When Security Games Hit Traffic: Optimal Traffic Enforcement Under One Sided Uncertainty

• Ariel Rosenfeld
• Sarit Kraus

Efficient traffic enforcement is an essential, yet complex, component in preventing road accidents. In this paper, we present a novel model and an optimizing algorithm for mitigating some of the computational challenges of real-world traffic enforcement allocation in large road networks. Our approach allows for scalable, coupled and non-Markovian optimization of multiple police units and guarantees optimality. In an extensive empirical evaluation we show that our approach favorably compares to several baseline solutions achieving a significant speed-up, using both synthetic and real-world road networks.

AIJ Journal 2016 Journal Article

Diffusion centrality: A paradigm to maximize spread in social networks

• Chanhyun Kang
• Sarit Kraus
• Cristian Molinaro
• Francesca Spezzano
• V.S. Subrahmanian

ECAI Conference 2016 Conference Paper

Online Prediction of Exponential Decay Time Series with Human-Agent Application

• Ariel Rosenfeld
• Joseph Keshet
• Claudia V. Goldman
• Sarit Kraus

Exponential decay time series are prominent in many fields. In some applications, the time series behavior can change over time due to a change in the user's preferences or a change of environment. In this paper we present an innovative online learning algorithm, which we name Exponentron, for the prediction of exponential decay time series. We state a regret bound for our setting, which theoretically compares the performance of our online algorithm relative to the performance of the best batch prediction mechanism, which can be chosen in hindsight from a class of hypotheses after observing the entire time series. In experiments with synthetic and real-world data sets, we found that the proposed algorithm compares favorably with the classic time series prediction methods by providing up to 41% improvement in prediction accuracy. Furthermore, we used the proposed algorithm for the design of a novel automated agent for the improvement of the communication process between a driver and its automotive climate control system. Throughout extensive human study with 24 drivers we show that our agent improves the communication process and increases drivers' satisfaction, exemplifying the Exponentron's applicative benefit.

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.

ECAI Conference 2016 Conference Paper

Strategical Argumentative Agent for Human Persuasion

• Ariel Rosenfeld
• Sarit Kraus

Automated agents should be able to persuade people in the same way people persuade each other - via dialogs. Today, automated persuasion modeling and research use unnatural assumptions regarding persuasive interaction, which creates doubt regarding their applicability for real-world deployment with people. In this work we present a novel methodology for persuading people through argumentative dialogs. Our methodology combines theoretical argumentation modeling, machine learning and Markovian optimization techniques that together result in an innovative agent named SPA. Two extensive field experiments, with more than 100 human subjects, show that SPA is able to persuade people significantly more often than a baseline agent and no worse than people are able to persuade each other.

AAAI Conference 2015 Conference Paper

A Hybrid Approach of Classifier and Clustering for Solving the Missing Node Problem

• Sigal Sina
• Avi Rosenfeld
• Sarit Kraus
• Navot Akiva

An important area of social network research is identifying missing information which is not explicitly represented in the network or is not visible to all. In this paper, we propose a novel Hybrid Approach of Classifier and Clustering, which we refer to as HACC, to solve the missing node identification problem in social networks. HACC utilizes a classifier as a preprocessing step in order to integrate all known information into one similarity measure and then uses a clustering algorithm to identify missing nodes. Specifically, we used the information on the network structure, attributes about known users (nodes) and pictorial information to evaluate HACC and found that it performs significantly better than other missing node algorithms. We also argue that HACC is a general approach and domain independent and can be easily applied to other domains. We support this claim by evaluating HACC on a second authorship identification domain as well.

TARK Conference 2015 Conference Paper

Human-Agent Decision-making: Combining Theory and Practice

• Sarit Kraus

Extensive work has been conducted both in game theory and logic to model strategic interaction. An important question is whether we can use these theories to design agents for interacting with people? On the one hand, they provide a formal design specification for agent strategies. On the other hand, people do not necessarily adhere to playing in accordance with these strategies, and their behavior is affected by a multitude of social and psychological factors. In this paper we will consider the question of whether strategies implied by theories of strategic behavior can be used by automated agents that interact proficiently with people. We will focus on automated agents that we built that need to interact with people in two negotiation settings: bargaining and deliberation. For bargaining we will study game-theory based equilibrium agents and for argumentation we will discuss logic-based argumentation theory. We will also consider security games and persuasion games and will discuss the benefits of using equilibrium based agents.

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.

AAAI Conference 2015 Conference Paper

Intelligent Agents for Rehabilitation and Care of Disabled and Chronic Patients

• Sarit Kraus

The number of people with disabilities is continuously increasing. Providing patients who have disabilities with the rehabilitation and care necessary to allow them good quality of life creates overwhelming demands for health and rehabilitation services. We suggest that advancements in intelligent agent technology provide new opportunities for improving the provided services. We will discuss the challenges of building an agent for the health care domain and present four capabilities that are required for an agent in the health care domain: planning, monitoring, intervention and encouragement. We will discuss the importance of personalizing all of them and the need to facilitate cooperation between the automated agent and the human care givers. We will review recent technology that can be used toward the development of agents that can have these capabilities and their promise in automating services such as physiotherapy, speech therapy and cognitive training.

JAAMAS Journal 2015 Journal Article

NegoChat-A: a chat-based negotiation agent with bounded rationality

• Avi Rosenfeld
• Inon Zuckerman
• Sarit Kraus

Abstract To date, a variety of automated negotiation agents have been created. While each of these agents has been shown to be effective in negotiating with people in specific environments, they typically lack the natural language processing support required to enable real-world types of interactions. To address this limitation, we present NegoChat-A, an agent that incorporates several significant research contributions. First, we found that simply modifying existing agents to include an natural language processing module is insufficient to create these agents. Instead, agents that support natural language must have strategies that allow for partial agreements and issue-by-issue interactions. Second, we present NegoChat-A’s negotiation algorithm. This algorithm is based on bounded rationality, and specifically anchoring and aspiration adaptation theory. The agent begins each negotiation interaction by proposing a full offer, which serves as its anchor. Assuming this offer is not accepted, the agent then proceeds to negotiate via partial agreements, proposing the next issue for negotiation based on people’s typical urgency, or order of importance. We present a rigorous evaluation of NegoChat-A, showing its effectiveness in two different negotiation roles.

AAAI Conference 2015 Conference Paper

Providing Arguments in Discussions Based on the Prediction of Human Argumentative Behavior

• Ariel Rosenfeld
• Sarit Kraus

Argumentative discussion is a highly demanding task. In order to help people in such situations, this paper provides an innovative methodology for developing an agent that can support people in argumentative discussions by proposing possible arguments to them. By analyzing more than 130 human discussions and 140 questionnaires, answered by people, we show that the wellestablished Argumentation Theory is not a good predictor of people’s choice of arguments. Then, we present a model that has 76% accuracy when predicting peoples top three argument choices given a partial deliberation. We present the Predictive and Relevance based Heuristic agent (PRH), which uses this model with a heuristic that estimates the relevance of possible arguments to the last argument given in order to propose possible arguments. Through extensive human studies with over 200 human subjects, we show that peoples satisfaction from the PRH agent is significantly higher than from other agents that propose arguments based on Argumentation Theory, predict arguments without the heuristics or only the heuristics. People also use the PRH agent’s proposed arguments significantly more often than those proposed by the other agents.

JAAMAS Journal 2014 Journal Article

A study of computational and human strategies in revelation games

• Noam Peled
• Ya’akov (Kobi) Gal
• Sarit Kraus

Abstract Many negotiations in the real world are characterized by incomplete information, and participants’ success depends on their ability to reveal information in a way that facilitates agreements without compromising their individual gain. This paper presents an agent-design that is able to negotiate proficiently with people in settings in which agents can choose to truthfully reveal their private information before engaging in multiple rounds of negotiation. Such settings are analogous to real-world situations in which people need to decide whether to disclose information such as when negotiating over health plans and business transactions. The agent combined a decision-theoretic approach with traditional machine-learning techniques to reason about the social factors that affect the players’ revelation decisions on people’s negotiation behavior. It was shown to outperform people as well as agents playing the equilibrium strategy of the game in empirical studies spanning hundreds of subjects. It was also more likely to reach agreement than people or agents playing equilibrium strategies. In addition, it had a positive effect on people’s play, allowing them to reach significantly better performance when compared to people’s play with other people. These results are shown to generalize for two different settings that varied how players depend on each other in the negotiation.

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.

ECAI Conference 2014 Conference Paper

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone 0001

Past research has investigated a number of methods for coordinating teams of agents, but with the growing number of sources of agents, it is likely that agents will encounter teammates that do not share their coordination methods. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. However when teammates do communicate, it can provide a valuable channel for coordination. Therefore, this paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multiarmed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates following unknown behaviors even when its models of these teammates are imperfect.

AAAI Conference 2014 Conference Paper

Generating Content for Scenario-Based Serious-Games Using CrowdSourcing

• Sigal Sina
• Avi Rosenfeld
• Sarit Kraus

Scenario-based serious-games have become an important tool for teaching new skills and capabilities. An important factor in the development of such systems is reducing the time and cost overheads in manually creating content for these scenarios. To address this challenge, we present Scenario- Gen, an automatic method for generating content about everyday activities through combining computer science techniques with the crowd. ScenarioGen uses the crowd in three different ways: to capture a database of scenarios of everyday activities, to generate a database of likely replacements for specific events within that scenario, and to evaluate the resulting scenarios. We evaluated ScenarioGen in 6 different content domains and found that it was consistently rated as coherent and consistent as the originally captured content. We also compared ScenarioGen’s content to that created by traditional planning techniques. We found that both methods were equally effective in generating coherent and consistent scenarios, yet ScenarioGen’s content was found to be more varied and easier to create.

ECAI Conference 2014 Conference Paper

Human-Computer Negotiation in Three-Player Market Settings

• Galit Haim
• Kobi Gal
• Sarit Kraus
• Bo An 0001

This paper studies commitment strategies in three-player negotiation settings comprising human players and computer agents. We defined a new game called the Contract Game which is analogous to real-world market settings in which participants need to reach agreement over contracts in order to succeed. The game comprises three players, two service providers and one customer. The service providers compete to make repeated contract offers to the customer consisting of resource exchanges in the game. We formally analyzed the game and defined sub-game perfect equilibrium strategies for the customer and service providers that involve commitments. We conducted extensive empirical studies of these strategies in three different countries, the U. S. , Israel and China. We ran several configurations in which two human participants played a single agent using the equilibrium strategies in various role configurations in the game (both customer and service providers). Our results showed that the computer agent using equilibrium strategies for the customer role was able to outperform people playing the same role in all three countries. In contrast, the computer agent playing the role of the service provider was not able to outperform people. Analysis reveals this difference in performance is due to the contracts proposed in equilibrium being significantly beneficial to the customer players, as well as irrational behavior taken by human customer players in the game.

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.

IS Journal 2014 Journal Article

The Negotiation Game

• Shaheen Fatima
• Sarit Kraus
• Michael Wooldridge

Here, the authors consider some of the main ideas underpinning attempts to build automated negotiators--computer programs that can effectively negotiate on our behalf.

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

An Agent Design for Repeated Negotiation and Information Revelation with People

• Noam Peled
• Ya'akov Gal
• Sarit Kraus

Many negotiations in the real world are characterized by incomplete information, and participants’ success depends on their ability to reveal information in a way that facilitates agreement without compromising the individual gains of agents. This paper presents a novel agent design for repeated negotiation in incomplete information settings that learns to reveal information strategically during the negotiation process. The agent used classical machine learning techniques to predict how people make and respond to offers during the negotiation, how they reveal information and their response to potential revelation actions by the agent. The agent was evaluated empirically in an extensive empirical study spanning hundreds of human subjects. Results show that the agent was able to outperform people. In particular, it learned (1) to make offers that were beneficial to people while not compromising its own benefit; (2) to incrementally reveal information to people in a way that increased its expected performance. The approach generalizes to new settings without the need to acquire additional data. This work demonstrates the efficacy of combining machine learning with opponent modeling techniques towards the design of computer agents for negotiating with people in settings of incomplete information.

AAMAS Conference 2013 Conference Paper

An Agent Design for Repeated Negotiation and Information Revelation with People

• Noam Peled
• Ya'akov Kobi Gal
• Sarit Kraus

Many negotiations in the real world are characterized by incomplete information, and participants’ success depends on their ability to reveal information in a way that facilitates agreement without compromising the individual gains of agents. This paper presents a novel agent design for repeated negotiation in incomplete information settings that learns to reveal information strategically during the negotiation process. The agent used classical machine learning techniques to predict how people make and respond to offers during the negotiation, how they reveal information and their response to potential revelation actions by the agent. The agent was evaluated empirically in an extensive empirical study spanning hundreds of human subjects. Results show that the agent was able (1) to make offers that were beneficial to people while not compromising its own benefit; (2) to incrementally reveal information to people in a way that increased its expected performance. The agent also had a positive effect on people’s strategy, in that people playing the agent performed significantly higher than people playing other people. This work demonstrates the efficacy of combining machine learning with opponent modeling techniques towards the design of computer agents for negotiating with people in settings of incomplete information.

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.

RLDM Conference 2013 Conference Abstract

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone

Teamwork is central to many tasks, and past research has introduced a number of methods for coordinating teams of agents. However, with the growing number of sources of agents, it is likely that an agent will encounter teammates that do not share its coordination method. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. This paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multi-armed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates not created by the authors even when its models of these teammates are imperfect.

JAAMAS Journal 2013 Journal Article

Efficient bidding strategies for Cliff-Edge problems

• Rina Azoulay
• Ron Katz
• Sarit Kraus

Abstract In this paper, we propose an efficient agent for competing in Cliff-Edge (CE) and simultaneous Cliff-Edge (SCE) situations. In CE interactions, which include common interactions such as sealed-bid auctions, dynamic pricing and the ultimatum game (UG), the probability of success decreases monotonically as the reward for success increases. This trade-off exists also in SCE interactions, which include simultaneous auctions and various multi-player ultimatum games, where the agent has to decide about more than one offer or bid simultaneously. Our agent competes repeatedly in one-shot interactions, each time against different human opponents. The agent learns the general pattern of the population’s behavior, and its performance is evaluated based on all of the interactions in which it participates. We propose a generic approach which may help the agent compete against unknown opponents in different environments where CE and SCE interactions exist, where the agent has a relatively large number of alternatives and where its achievements in the first several dozen interactions are important. The underlying mechanism we propose for CE interactions is a new meta-algorithm, deviated virtual learning (DVL), which extends existing methods to efficiently cope with environments comprising a large number of alternative decisions at each decision point. Another competitive approach is the Bayesian approach, which learns the opponents’ statistical distribution, given prior knowledge about the type of distribution. For the SCE, we propose the simultaneous deviated virtual reinforcement learning algorithm (SDVRL), the segmentation meta-algorithm as a method for extending different basic algorithms, and a heuristic called fixed success probabilities (FSP). Experiments comparing the performance of the proposed algorithms with algorithms taken from the literature, as well as other intuitive meta-algorithms, reveal superiority of the proposed algorithms in average payoff and stability as well as in accuracy in converging to the optimal action, both in CE and SCE problems.

AIJ Journal 2013 Journal Article

Evaluating practical negotiating agents: Results and analysis of the 2011 international competition

• Tim Baarslag
• Katsuhide Fujita
• Enrico H. Gerding
• Koen Hindriks
• Takayuki Ito
• Nicholas R. Jennings
• Catholijn Jonker
• Sarit Kraus

IJCAI Conference 2013 Conference Paper

How to Change a Group's Collective Decision?

• Noam Hazon
• Raz Lin
• Sarit Kraus

Persuasion is a common social and economic activity. It usually arises when conflicting interests among agents exist, and one of the agents wishes to sway the opinions of others. This paper considers the problem of an automated agent that needs to influence the decision of a group of self-interested agents that must reach an agreement on a joint action. For example, consider an automated agent that aims to reduce the energy consumption of a nonresidential building, by convincing a group of people who share an office to agree on an economy mode of the air-conditioning and low light intensity. In this paper we present four problems that address issues of minimality and safety of the persuasion process. We discuss the relationships to similar problems from social choice, and show that if the agents are using Plurality or Veto as their voting rule all of our problems are in P. We also show that with K-Approval, Bucklin and Borda voting rules some problems become intractable. We thus present heuristics for efficient persuasion with Borda, and evaluate them through simulations.

AIJ Journal 2013 Journal Article

Incentive engineering for Boolean games

• Michael Wooldridge
• Ulle Endriss
• Sarit Kraus
• Jérôme Lang

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.

AIJ Journal 2013 Journal Article

Physical search problems with probabilistic knowledge

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• David Sarne

IJCAI Conference 2013 Conference Paper

Predicting Human Strategic Decisions Using Facial Expressions

• Noam Peled
• Moshe Bitan
• Joseph Keshet
• Sarit Kraus

People’s facial expressions, whether made consciously or subconsciously, continuously reveal their state of mind. This work proposes a method for predicting people’s strategic decisions based on their facial expressions. We designed a new version of the centipede game that intorduces an incentive for the human participant to hide her facial expressions. We recorded on video participants who played several games of our centipede version, and concurrently logged their decisions throughout the games. The video snippet of the participants’ faces prior to their decisions is represented as a fixed-size vector by estimating the covariance matrix of key facial points which change over time. This vector serves as input to a classifier that is trained to predict the participant’s decision. We compare several training techniques, all of which are designed to work with the imbalanced decisions typically made by the players of the game. Furthermore, we investigate adaptation of the trained model to each player individually, while taking into account the player’s facial expressions in the previous games. The results show that our method outperforms standard SVM as well as humans in predicting subjects’ strategic decisions. To the best of our knowledge, this is the first study to present a methodology for predicting people’s strategic decisions when there is an incentive to hide facial expressions.

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.

AIJ Journal 2013 Journal Article

Teaching and leading an ad hoc teammate: Collaboration without pre-coordination

• Peter Stone
• Gal A. Kaminka
• Sarit Kraus
• Jeffrey S. Rosenschein
• Noa Agmon

AAAI Conference 2013 Conference Paper

Teamwork with Limited Knowledge of Teammates

• Samuel Barrett
• Peter Stone
• Sarit Kraus
• Avi Rosenfeld

While great strides have been made in multiagent teamwork, existing approaches typically assume extensive information exists about teammates and how to coordinate actions. This paper addresses how robust teamwork can still be created even if limited or no information exists about a specific group of teammates, as in the ad hoc teamwork scenario. The main contribution of this paper is the first empirical evaluation of an agent cooperating with teammates not created by the authors, where the agent is not provided expert knowledge of its teammates. For this purpose, we develop a generalpurpose teammate modeling method and test the resulting ad hoc team agent’s ability to collaborate with more than 40 unknown teams of agents to accomplish a benchmark task. These agents were designed by people other than the authors without these designers planning for the ad hoc teamwork setting. A secondary contribution of the paper is a new transfer learning algorithm, TwoStageTransfer, that can improve results when the ad hoc team agent does have some limited observations of its current teammates.

AAMAS Conference 2012 Conference Paper

A Cultural Sensitive Agent for Human-Computer Negotiation

• Galit Haim
• Ya'akov (Kobi) Gal
• Sarit Kraus
• Michele Gelfand

People's cultural background has been shown to affect how they reach agreement in negotiation and how they fulfil these agreements. This paper presents a novel agent design for negotiating with people from different cultures. Our setting involved an alternating-offer protocol that allowed parties to choose the extent to which they kept each of their agreements during the negotiation. A challenge to designing agents for such setting is to predict how people reciprocate their actions over time despite the scarcity of prior data of their behavior across different cultures. Our methodology addresses this challenge by combining a decision theoretic model with classical machine learning techniques to predict how people respond to offers, and the extent to which they fulfill agreements. This agent was evaluated empirically by playing with 157 people in three countries--Lebanon, the U. S. , and Israel---in which people are known to vary widely in their negotiation behavior. The agent was able to outperform people in all countries under conditions that varied how parties depended on each other at the onset of the negotiation. This is the first work to show that a computer agent can learn to outperform people when negotiating in three countries representing different cultures.

AAMAS Conference 2012 Conference Paper

A Robust Approach to Addressing Human Adversaries in Security Games

• James Pita
• Richard John
• Rajiv Maheswaran
• Milind Tambe
• Rong Yang
• Sarit Kraus

While game-theoretic approaches have been proposed for addressing complex security resource allocation problems, many of the standard game-theoretic assumptions fail to address human adversaries who security forces will likely face. To that end, approaches have been proposed that attempt to incorporate better models of human decision-making in these security settings. We take a new approach where instead of trying to create a model of human decisionmaking, we leverage ideas from robust optimization techniques. In addition, we extend our approach and the previous best performing approach to also address human anchoring biases under limited observation conditions. To evaluate our approach, we perform a comprehensive examination comparing the performance of our new approach against the current leading approaches to addressing human adversaries. Finally, in our experiments we take the first ever analysis of some demographic information and personality measures that may influence decision making in security games.

ECAI Conference 2012 Conference Paper

A Robust Approach to Addressing Human Adversaries in Security Games

• James Pita
• Richard John
• Rajiv T. Maheswaran
• Milind Tambe
• Sarit Kraus

Game-theoretic approaches have been proposed for addressing the complex problem of assigning limited security resources to protect a critical set of targets. However, many of the standard assumptions fail to address human adversaries who security forces will likely face. To address this challenge, previous research has attempted to integrate models of human decision-making into the game-theoretic algorithms for security settings. The current leading approach, based on experimental evaluation, is derived from a well-founded solution concept known as quantal response and is known as BRQR. One critical difficulty with opponent modeling in general is that, in security domains, information about potential adversaries is often sparse or noisy and furthermore, the games themselves are highly complex and large in scale. Thus, we chose to examine a completely new approach to addressing human adversaries that avoids the complex task of modeling human decision-making. We leverage and modify robust optimization techniques to create a new type of optimization where the defender's loss for a potential deviation by the attacker is bounded by the distance of that deviation from the expected-value-maximizing strategy. To demonstrate the advantages of our approach, we introduce a systematic way to generate meaningful reward structures and compare our approach with BRQR in the most comprehensive investigation to date involving 104 security settings where previous work has tested only up to 10 security settings. Our experimental analysis reveals our approach performing as well as or outperforming BRQR in over 90% of the security settings tested and we demonstrate significant runtime benefits. These results are in favor of utilizing an approach based on robust optimization in these complex domains to avoid the difficulties of opponent modeling.

AAMAS Conference 2012 Conference Paper

Agent-human Coordination with Communication Costs under Uncertainty

• Asaf Frieder
• Raz Lin
• Sarit Kraus

As agents’ technology becomes increasing more prevalent, coordination in mixed agent-human environments becomes a key issue. Agent-human coordination is becoming even more important in real life situations, where uncertainty and incomplete information exists and communication is costly. While abundant research has focused on aspects of computerized teamwork, little attention has been given to the issues raised in teams that consist of both computerized agents and people. In this paper we focus on teamwork between an agent and a human counterpart and present a novel agent designed to interact proficiently with people. In extensive simulations we matched our agent with people and compared it with another state-of-the-art agent. Our results demonstrate the significant improvement in coordination when our agent is involved.

AAAI Conference 2012 Conference Paper

Agent-Human Coordination with Communication Costs Under Uncertainty

• Asaf Frieder
• Raz Lin
• Sarit Kraus

Coordination in mixed agent-human environments is an important, yet not a simple, problem. Little attention has been given to the issues raised in teams that consist of both computerized agents and people. In such situations different considerations are in order, as people tend to make mistakes and they are affected by cognitive, social and cultural factors. In this paper we present a novel agent designed to proficiently coordinate with a human counterpart. The agent uses a neural network model that is based on a pre-existing knowledge base which allows it to achieve an efficient modeling of a human’s decisions and predict their behavior. A novel communication mechanism which takes into account the expected effect of communication on the other member will allow communication costs to be minimized. In extensive simulations involving more than 200 people we investigated our approach and showed that our agent achieves better coordination when involved, compared to settings in which only humans or another state-of-the-art agent are involved.

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.

ECAI Conference 2012 Conference Paper

Delegating Decisions in Strategic Settings

• Sarit Kraus
• Michael J. Wooldridge

We formalise and investigate the following problem. A principal must delegate a number of decisions to a collection of agents. Once the decisions are delegated, the agents to whom the decisions are delegated will act selfishly, rationally, and independently in pursuit of their own preferences. The principal himself is assumed to be self-interested, and has some goal that he desires to be achieved. The delegation problem is then, given such a setting, is it possible for the principal to delegate decisions in such a way that, if all the agents to whom decisions have been delegated then make decisions rationally, the principal's goal will be achieved in equilibrium. We formalise this problem using Boolean games, which provides a very natural framework within which to capture the delegation problem: decisions are directly represented as Boolean variables, which the principal assigns to agents. After motivating and formally defining the delegation problem, we investigate the computational complexity of the problem, and some issues surrounding it.

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.

ECAI Conference 2012 Conference Paper

Guiding User Choice During Discussion by Silence, Examples and Justifications

• Maier Fenster
• Inon Zuckerman
• Sarit Kraus

This paper describes an approach for guiding human choice-making by a computerized agent, in a conversational setting, where both user and agent provide meaningful input. In the proposed approach, the agent attempts to convince a person by providing examples for the person to emulate or by providing justifications for the person to internalize and build or change her preferences accordingly. The agent can take into account examples and justifications provided by the person. In a series of experiments where the task was selecting a location for a school, a computer agent interacted with subjects using a textual chat-type interface, with different agent designs being used in different experiments. The results show that the example-providing agent outperformed the justification providing agent and both, surprisingly, outperformed an agent which pre sented the subject with both examples and justifications. In addition, it was demonstrated that in some cases the best strategy for the agent is to keep silent.

AIJ Journal 2012 Journal Article

On the evaluation of election outcomes under uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

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.

AAMAS Conference 2011 Conference Paper

A Study of Computational and Human Strategies in Revelation Games

• Noam Peled
• Ya'akov (Kobi) Gal
• Sarit Kraus

Revelation games are bilateral bargaining games in which agents may choose to truthfully reveal their private information before engaging in multiple rounds of negotiation. They are analogous to real-world situations in which people need to decide whether to disclose information such as medical records or university transcripts when negotiating over health plans and business transactions. This paper presents an agent-design that is able to negotiate proficiently with people in a revelation game with different dependencies that hold between players. The agent modeled the social factors that affect the players' revelation decisions on people's negotiation behavior. It was empirically shown to outperform people in empirical evaluations as well as agents playing equilibrium strategies. It was also more likely to reach agreement than people or equilibrium agents.

TIST Journal 2011 Journal Article

An Adaptive Agent for Negotiating with People in Different Cultures

• Ya’akov Gal
• Sarit Kraus
• Michele Gelfand
• Hilal Khashan
• Elizabeth Salmon

The rapid dissemination of technology such as the Internet across geographical and ethnic lines is opening up opportunities for computer agents to negotiate with people of diverse cultural and organizational affiliations. To negotiate proficiently with people in different cultures, agents need to be able to adapt to the way behavioral traits of other participants change over time. This article describes a new agent for repeated bilateral negotiation that was designed to model and adapt its behavior to the individual traits exhibited by its negotiation partner. The agent’s decision-making model combined a social utility function that represented the behavioral traits of the other participant, as well as a rule-based mechanism that used the utility function to make decisions in the negotiation process. The agent was deployed in a strategic setting in which both participants needed to complete their individual tasks by reaching agreements and exchanging resources, the number of negotiation rounds was not fixed in advance and agreements were not binding. The agent negotiated with human subjects in the United States and Lebanon in situations that varied the dependency relationships between participants at the onset of negotiation. There was no prior data available about the way people would respond to different negotiation strategies in these two countries. Results showed that the agent was able to adopt a different negotiation strategy to each country. Its average performance across both countries was equal to that of people. However, the agent outperformed people in the United States, because it learned to make offers that were likely to be accepted by people, while being more beneficial to the agent than to people. In contrast, the agent was outperformed by people in Lebanon, because it adopted a high reliability measure which allowed people to take advantage of it. These results provide insight for human-computer agent designers in the types of multicultural settings that we considered, showing that adaptation is a viable approach towards the design of computer agents to negotiate with people when there is no prior data of their behavior.

JAAMAS Journal 2011 Journal Article

AutoMed: an automated mediator for multi-issue bilateral negotiations

• Michal Chalamish
• Sarit Kraus

Abstract In this paper, we present AutoMed, an automated mediator for multi-issue bilateral negotiation under time constraints. AutoMed elicits the negotiators preferences and analyzes them. It monitors the negotiations and proposes possible solutions for resolving the conflict. We conducted experiments in a simulated environment. The results show that negotiations mediated by AutoMed are concluded significantly faster than non-mediated ones and without any of the negotiators opting out. Furthermore, the subjects in the mediated negotiations are more satisfied with the resolutions than the subjects in the non-mediated negotiations.

IS Journal 2011 Journal Article

Bridging the Gap: Face-to-Face Negotiations with an Automated Mediator

• Raz Lin
• Yehoshua Gev
• Sarit Kraus

The automated, animated mediator AniMed* aims to increase the social welfare of people in bilateral negotiations, utilizing a generic strategy mechanism and the ability to propose partial solutions.

AAAI Conference 2011 Conference Paper

Comparing Agents’ Success against People in Security Domains

• Raz Lin
• Sarit Kraus
• Noa Agmon
• Samuel Barrett
• Peter Stone

The interaction of people with autonomous agents has become increasingly prevalent. Some of these settings include security domains, where people can be characterized as uncooperative, hostile, manipulative, and tending to take advantage of the situation for their own needs. This makes it challenging to design proficient agents to interact with people in such environments. Evaluating the success of the agents automatically before evaluating them with people or deploying them could alleviate this challenge and result in better designed agents. In this paper we show how Peer Designed Agents (PDAs) – computer agents developed by human subjects – can be used as a method for evaluating autonomous agents in security domains. Such evaluation can reduce the effort and costs involved in evaluating autonomous agents interacting with people to validate their efficacy. Our experiments included more than 70 human subjects and 40 PDAs developed by students. The study provides empirical support that PDAs can be used to compare the proficiency of autonomous agents when matched with people in security domains.

AAMAS Conference 2011 Conference Paper

Designing Incentives for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

Boolean games are a natural, compact, and expressive class of logic-based games, in which each player exercises unique control over some set of Boolean variables, and has some logical goal formula that it desires to be achieved. A player's strategy set is the set of all possible valuations that may be made to its variables. A player's goal formula may contain variables controlled by other agents, and in this case, it must reason strategically about how best to assign values to its variables. In the present paper, we consider the possibility of overlaying Boolean games with taxation schemes. A taxation scheme imposes a cost on every possible assignment an agent can make. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the agents within a society, so that agents are rationally incentivised to choose some socially desirable equilibrium that would not otherwise be chosen, or incentivised to rule out some socially undesirable equilibria. After formally presenting the model, we explore some issues surrounding it (e. g. , the complexity of finding a taxation scheme that implements some socially desirable outcome), and then discuss possible desirable properties of taxation schemes.

AAMAS Conference 2011 Conference Paper

Empirical Evaluation of Ad Hoc Teamwork in the Pursuit Domain

• Samuel Barrett
• Peter Stone
• Sarit Kraus

The concept of creating autonomous agents capable of exhibiting ad hoc teamwork was recently introduced as a challenge to the AI, and specifically to the multiagent systems community. An agent capable of ad hoc teamwork is one that can effectively cooperate with multiple potential teammates on a set of collaborative tasks. Previous research has investigated theoretically optimal ad hoc teamwork strategies in restrictive settings. This paper presents the first empirical study of ad hoc teamwork in a more open, complex teamwork domain. Specifically, we evaluate a range of effective algorithms for on-line behavior generation on the part of a single ad hoc team agent that must collaborate with a range of possible teammates in the pursuit domain.

AAAI Conference 2011 Conference Paper

Identifying Missing Node Information in Social Networks

• Ron Eyal
• Sarit Kraus
• Avi Rosenfeld

In recent years, social networks have surged in popularity as one of the main applications of the Internet. This has generated great interest in researching these networks by various fields in the scientific community. One key aspect of social network research is identifying important missing information which is not explicitly represented in the network, or is not visible to all. To date, this line of research typically focused on what connections were missing between nodes, or what is termed the "Missing Link Problem". This paper introduces a new Missing Nodes Identification problem where missing members in the social network structure must be identified. Towards solving this problem, we present an approach based on clustering algorithms combined with measures from missing link research. We show that this approach has beneficial results in the missing nodes identification process and we measure its performance in several different scenarios.

IJCAI Conference 2011 Conference Paper

Incentive Engineering for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

We investigate the problem of influencing the preferences of players within a Boolean game so that, if all players act rationally, certain desirable outcomes will result. The way in which we influence preferences is by overlaying games with taxation schemes. In a Boolean game, each player has unique control of a set of Boolean variables, and the choices available to the player correspond to the possible assignments that may be made to these variables. Each player also has a goal, represented by a Boolean formula, that they desire to see satisfied. Whether or not a player's goal is satisfied will depend both on their own choices and on the choices of others, which gives Boolean games their strategic charac- ter. We extend this basic framework by introducing an external principal who is able to levy a taxation scheme on the game, which imposes a cost on every possible action that a player can choose. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the players, so that they are incentivised to choose some equilibrium that would not otherwise be chosen. After motivating and formally presenting our model, we explore some issues surrounding it, including the complexity of finding a taxation scheme that implements some socially desirable outcome, and then discuss desirable properties of taxation schemes.

IJCAI Conference 2011 Conference Paper

Manipulating Boolean Games through Communication

• John Grant
• Sarit Kraus
• Michael Wooldridge
• Inon Zuckerman

We address the issue of manipulating games through communication. In the specific setting we consider (a variation of Boolean games), we assume there is some set of environment variables, the value of which is not directly accessible to players; each player has their own beliefs about these variables, and makes decisions about what actions to perform based on these beliefs. The communication we consider takes the form of (truthful) announcements about the value of some environment variables; the effect of an announcement about some variable is to modify the beliefs of the players who hear the announcement so that they accurately reflect the value of the announced variables. By choosing announcements appropriately, it is possible to perturb the game away from certain rational outcomes and towards others. We specifically focus on the issue of stabilisation: making announcements that transform a game from having no stable states to one that has stable configurations.

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.

AAMAS Conference 2011 Conference Paper

Using Aspiration Adaptation Theory to Improve Learning

• Avi Rosenfeld
• Sarit Kraus

Creating agents that properly simulate and interact with people is critical for many applications. Towards creating these agents, models are needed that quickly and accurately predict how people behave in a variety of domains and problems. This paper explores how one bounded rationality theory, Aspiration Adaptation Theory (AAT), can be used to aid in this task. We extensively studied two types of problems - a relatively simple optimization problem and two complex negotiation problems. We compared the predictive capabilities of traditional learning methods with those where we added key elements of AAT and other optimal and bounded rationality models. Within the extensive empirical studies we conducted, we found that machine learning models combined with AAT were most effective in quickly and accurately predicting people's behavior.

AAMAS Conference 2010 Conference Paper

A Graph-Theoretic Approach to Protect Static and Moving Targets from Adversaries

• John Dickerson
• Gerardo Simari
• V. S. Subrahmanian
• Sarit Kraus

The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e. g. , a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge-cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.

AAAI Conference 2010 Conference Paper

Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination

• Peter Stone
• Gal Kaminka
• Sarit Kraus
• Jeffrey Rosenschein

As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This paper challenges the AI community to develop theory and to implement prototypes of ad hoc team agents. It defines the concept of ad hoc team agents, specifies an evaluation paradigm, and provides examples of possible theoretical and empirical approaches to challenge. The goal is to encourage progress towards this ambitious, newly realistic, and increasingly important research goal.

ICRA Conference 2010 Conference Paper

Adaptive multi-robot coordination: A game-theoretic perspective

• Gal A. Kaminka
• Dan Erusalimchik
• Sarit Kraus

Multi-robot systems researchers have been investigating adaptive coordination methods for improving spatial coordination in teams. Such methods adapt the coordination method to the dynamic changes in density of the robots. Unfortunately, while their empirical success is evident, none of these methods has been understood in the context of existing formal work on multi-robot learning. This paper presents a reinforcement-learning approach to coordination algorithm selection, which is not only shown to work well in experiments, but is also analytically grounded. We present a reward function (Effectiveness Index, EI), that reduces time and resources spent coordinating, and maximizes the time between conflicts that require coordination. It does this by measuring the resource-spending velocity. We empirically show its success in simulations of multi-robot foraging. In addition, we analytically explore the reasons that EI works well. We show that under some assumptions, spatial coordination opportunities can be modeled as matrix games in which the payoffs are directly a function of EI estimates. The use of reinforcement learning leads to robots maximizing their EI rewards in equilibrium. This work is a step towards bridging the gap between the theoretical study of interactions, and their use in multi-robot coordination.

AIJ Journal 2010 Journal Article

Agent decision-making in open mixed networks

• Ya'akov Gal
• Barbara Grosz
• Sarit Kraus
• Avi Pfeffer
• Stuart Shieber

AAAI Conference 2010 Conference Paper

Facilitating the Evaluation of Automated Negotiators using Peer Designed Agents

• Raz Lin
• Sarit Kraus
• Yinon Oshrat
• Ya'akov (Kobi) Gal

Computer agents are increasingly deployed in settings in which they make decisions with people, such as electronic commerce, collaborative interfaces, and cognitive assistants. However, the scientific evaluation of computational strategies for human-computer decision-making is a costly process, involving time, effort and personnel. This paper investigates the use of Peer Designed Agents (PDA)—computer agents developed by human subjects—as a tool for facilitating the evaluation process of automatic negotiators that were developed by researchers. It compares the performance between automatic negotiators that interacted with PDAs to automatic negotiators that interacted with actual people in different domains. The experiments included more than 300 human subjects and 50 PDAs developed by students. Results showed that the automatic negotiators outperformed PDAs in the same situations in which they outperformed people, and that on average, they exhibited the same measure of generosity towards their negotiation partners. These patterns occurred for all types of domains, and for all types of automated negotiators, despite the fact that there were individual differences between the behavior of PDAs and people. The study thus provides an empirical proof that PDAs can alleviate the evaluation process of automatic negotiators, and facilitate their design.

AAAI Conference 2010 Conference Paper

Intentions in Equilibrium

• John Grant
• Sarit Kraus
• Michael Wooldridge

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multiagent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

JAAMAS Journal 2010 Journal Article

Modeling agents based on aspiration adaptation theory

• Avi Rosenfeld
• Sarit Kraus

Abstract Creating agents that realistically simulate and interact with people is an important problem. In this paper we present strong empirical evidence that such agents should be based on bounded rationality, and specifically on key elements from Aspiration Adaptation Theory (AAT). First, we analyzed the strategies people described they would use to solve two relatively basic optimization problems involving one and two parameters. Second, we studied the agents a different group of people wrote to solve these same problems. We then studied two realistic negotiation problems involving five and six parameters. Again, first we studied the negotiation strategies people used when interacting with other people. Then we studied two state of the art automated negotiation agents and negotiation sessions between these agents and people. We found that in both the optimizing and negotiation problems the overwhelming majority of automated agents and people used key elements from AAT, even when optimal solutions, machine learning techniques for solving multiple parameters, or bounded techniques other than AAT could have been implemented. We discuss the implications of our findings including suggestions for designing more effective agents for game and simulation environments.

AAMAS Conference 2010 Conference Paper

On Agent Types in Coalition Formation Problems

• Tammar Shrot
• Yonatan Aumann
• Sarit Kraus

Coalitions and cooperation are key topics in multi–agent systems (MAS). They enable agents to achieve goals that theymay not have been able to achieve independently. A rangeof previous studies have found that many problems in coalitional games tend to be computationally intractable - thatis, the computational complexity grows rapidly as a functionof the number of participating agents. However, these hardness results generally require that each agent is of a differenttype. Here, we observe that in many mas settings, while thenumber of agents may grow, the number of different types ofagents remains small. We formally define the notion of agenttypes in cooperative games. We then re-examine the computational complexity of the different coalition formationproblems when assuming that the number of agent typesis fixed. We show that most of the previously hard problems become polynomial when the number of agent typesis fixed. We consider multiple different game formulationsand representations (characteristic function with subadditive utilities, crg, and graphical representations) and several different computational problems (including stability, core-emptiness, and Shapley value).

JAAMAS Journal 2010 Journal Article

Practical voting rules with partial information

• Meir Kalech
• Sarit Kraus
• Claudia V. Goldman

Abstract Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous work has typically assumed that voters send their complete set of preferences for computation, and in fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send a complete set of preferences due to communication limitations and willingness to keep as much information private as possible. The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly, we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments with simulated and real-world data show that this algorithm results in an average of 35% savings in communications, while guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in practice, close approximations are obtained.

AIJ Journal 2010 Journal Article

Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition

• James Pita
• Manish Jain
• Milind Tambe
• Fernando Ordóñez
• Sarit Kraus

AIJ Journal 2010 Journal Article

Solving coalitional resource games

• Paul E. Dunne
• Sarit Kraus
• Efrat Manisterski
• Michael Wooldridge

JAAMAS Journal 2010 Journal Article

The adversarial activity model for bounded rational agents

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein

Abstract Multiagent research provides an extensive literature on formal Beliefs-Desires-Intentions (BDI) based models describing the notion of teamwork and cooperation. However, multiagent environments are often not cooperative nor collaborative; in many cases, agents have conflicting interests, leading to adversarial interactions. This form of interaction has not yet been formally defined in terms of the agents mental states, beliefs, desires and intentions. This paper presents the Adversarial Activity model, a formal Beliefs-Desires-Intentions (BDI) based model for bounded rational agents operating in a zero-sum environment. In complex environments, attempts to use classical utility-based search methods with bounded rational agents can raise a variety of difficulties (e. g. implicitly modeling the opponent as an omniscient utility maximizer, rather than leveraging a more nuanced, explicit opponent model). We define the Adversarial Activity by describing the mental states of an agent situated in such environment. We then present behavioral axioms that are intended to serve as design principles for building such adversarial agents. We illustrate the advantages of using the model as an architectural guideline by building agents for two adversarial environments: the Connect Four game and the Risk strategic board game. In addition, we explore the application of our approach by analyzing log files of completed Connect Four games, and gain additional insights on the axioms’ appropriateness.

AAMAS Conference 2010 Conference Paper

To Teach or not to Teach? Decision Making Under Uncertainty in Ad Hoc Teams

• Peter Stone
• Sarit Kraus

In typical multiagent \emph{teamwork} settings, the teammates are either programmed together, or are otherwise provided with standard communication languages and coordination protocols. In contrast, this paper presents an \emph{ad hoc team} setting in which the teammates are not pre-coordinated, yet still must work together in order to achieve their common goal(s). We represent a specific instance of this scenario, in which a teammate has limited action capabilities and a fixed and known behavior, as a multiagent cooperative $k$-armed bandit. In addition to motivating and studying this novel ad hoc teamwork scenario, the paper contributes to the $k$-armed bandits literature by characterizing the conditions under which certain actions are potentially optimal, and by presenting a polynomial dynamic programming algorithm that solves for the optimal action when the arm payoffs come from a discrete distribution.

JAAMAS Journal 2010 Journal Article

Using focal point learning to improve human–machine tacit coordination

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein

Abstract We consider an automated agent that needs to coordinate with a human partner when communication between them is not possible or is undesirable ( tacit coordination games ). Specifically, we examine situations where an agent and human attempt to coordinate their choices among several alternatives with equivalent utilities. We use machine learning algorithms to help the agent predict human choices in these tacit coordination domains. Experiments have shown that humans are often able to coordinate with one another in communication-free games, by using focal points, “prominent” solutions to coordination problems. We integrate focal point rules into the machine learning process, by transforming raw domain data into a new hypothesis space. We present extensive empirical results from three different tacit coordination domains. The Focal Point Learning approach results in classifiers with a 40–80% higher correct classification rate, and shorter training time, than when using regular classifiers, and a 35% higher correct classification rate than classical focal point techniques without learning. In addition, the integration of focal points into learning algorithms results in agents that are more robust to changes in the environment. We also present several results describing various biases that might arise in Focal Point based coordination.

IJCAI Conference 2009 Conference Paper

• Inon Zuckerman
• Ariel Felner
• Sarit Kraus

There are two basic approaches to generalize the propagation mechanism of the two-player Minimax search algorithm to multi-player (3 or more) games: the MaxN algorithm and the Paranoid algorithm. The main shortcoming of these approaches is that their strategy is fixed. In this paper we suggest a new approach (called MP- Mix) that dynamically changes the propagation strategy based on the players’ relative strengths between MaxN, Paranoid and a newly presented offensive strategy. In addition, we introduce the Opponent Impact factor for multi-player games, which measures the players’ ability to impact their opponents’ score, and show its relation to the relative performance of our new MP-Mix strategy. Experimental results show that MP-Mix outperforms all other approaches under most circumstances.

IJCAI Conference 2009 Conference Paper

• Avi Rosenfeld
• Sarit Kraus

Effectively modeling an agent’s cognitive model is an important problem in many domains. In this paper, we explore the agents people wrote to operate within optimization problems. We claim that the overwhelming majority of these agents used strategies based on bounded rationality, even when optimal solutions could have been implemented. Particularly, we believe that many elements from Aspiration Adaptation Theory (AAT) are useful in quantifying these strategies. To support these claims, we present extensive empirical results from over a hundred agents programmed to perform in optimization problems involving solving for one and two variables.

IJCAI Conference 2009 Conference Paper

• Noa Agmon
• Sarit Kraus
• Gal A. Kaminka
• Vladimir Sadov

We study the problem of multi-robot perimeter patrol in adversarial environments, under uncertainty of adversarial behavior. The robots patrol around a closed area using a nondeterministic patrol algorithm. The adversary’s choice of penetration point depends on the knowledge it obtained on the patrolling algorithm and its weakness points. Previous work investigated full knowledge and zero knowledge adversaries, and the impact of their knowledge on the optimal algorithm for the robots. However, realistically the knowledge obtained by the adversary is neither zero nor full, and therefore it will have uncertainty in its choice of penetration points. This paper considers these cases, and offers several approaches to bounding the level of uncertainty of the adversary, and its influence on the optimal patrol algorithm. We provide theoretical results that justify these approaches, and empirical results that show the performance of the derived algorithms used by simulated robots working against humans playing the role of the adversary is several different settings.

IJCAI Conference 2009 Conference Paper

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus

This paper considers the setting wherein a group of agents (e. g. , robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e. g. , battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, apriori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e. g. , rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For noncommunicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities.

AIJ Journal 2009 Journal Article

Computing the fault tolerance of multi-agent deployment

• Yingqian Zhang
• Efrat Manisterski
• Sarit Kraus
• V.S. Subrahmanian
• David Peleg

AAMAS Conference 2009 Conference Paper

Easy and Hard Coalition Resource Game Formation Problems - A Parameterized Complexity Analysis

• Tammar Shrot
• Yonatan Aumann
• Sarit Kraus

Coalition formation is a key topic in multi–agent systems (mas). Coalitions enable agents to achieve goals that they may not have been able to achieve independently, and encourages resource sharing among agents with different goals. A range of previous studies have found that problems in coalitional games tend to be computationally complex. However, such hardness results consider the entire input as one, ignoring any structural information on the instances. In the case of coalition formation problems, this bundles together several distinct elements of the input, e. g. the agent set, the goal set, the resources, etc. In this paper we reexamine the complexity of coalition formation problems in the coalition resources game model, as a function of their distinct input elements, using the theory of parameterized complexity. The analysis shows that not all parts of the input are created equal, and that many instances of the problem are actually tractable. We show that the problems are FPT in the number of goals, implying that if the number of goals is bounded then an efficient algorithm is available. Similarly, the problems are FPT in the combination of the number of agents and resources, again implying that if these parameters are bounded, then an efficient algorithm is available. On the other hand, the problems are para-NP hard in the number of resources, implying that even if we bound the number of resources the problems (probably) remain hard. Additionally, we show that most problems are W[1]-hard in the size of the coalition of interest, indicating that there is (probably) no algorithm polynomial in all but the coalition size. The exact definitions of the parameterized complexity notions FPT, Para-NP and W[1] are provided herein.

AAMAS Conference 2009 Conference Paper

Effective Solutions for Real-World Stackelberg Games: When Agents Must Deal with Human Uncertainties

• James Pita
• Manish Jain
• Fernando Ordóñez
• Milind Tambe
• Sarit Kraus
• Reuma Magori-Cohen

How do we build multiagent algorithms for agent interactions with human adversaries? Stackelberg games are natural models for many important applications that involve human interaction, such as oligopolistic markets and security domains. In Stackelberg games, one player, the leader, commits to a strategy and the follower makes their decision with knowledge of the leader’s commitment. Existing algorithms for Stackelberg games efficiently find optimal solutions (leader strategy), but they critically assume that the follower plays optimally. Unfortunately, in real-world applications, agents face human followers (adversaries) who — because of their bounded rationality and limited observation of the leader strategy — may deviate from their expected optimal response. Not taking into account these likely deviations when dealing with human adversaries can cause an unacceptable degradation in the leader’s reward, particularly in security applications where these algorithms have seen real-world deployment. To address this crucial problem, this paper introduces three new mixed-integer linear programs (MILPs) for Stackelberg games to consider human adversaries, incorporating: (i) novel anchoring theories on human perception of probability distributions and (ii) robustness approaches for MILPs to address human imprecision. Since these new approaches consider human adversaries, traditional proofs of correctness or optimality are insufficient; instead, it is necessary to rely on empirical validation. To that end, this paper considers two settings based on real deployed security systems, and compares 6 different approaches (three new with three previous approaches), in 4 different observability conditions, involving 98 human subjects playing 1360 games in total. The final conclusion was that a model which incorporates both the ideas of robustness and anchoring achieves statistically significant better rewards and also maintains equivalent or faster solution speeds compared to existing approaches. General Terms Algorithms, Experimentation, Security, Human Factors

AAMAS Conference 2009 Conference Paper

Facing the Challenge of Human-Agent Negotiations via Effective General Opponent Modeling

• Yinon Oshrat
• Raz Lin
• Sarit Kraus

Automated negotiation agents capable of negotiating efficiently with people must deal with the fact that people are diverse in their behavior and each individual might negotiate in a different manner. Thus, automated agents must rely on a good opponent modeling component to model their counterpart and adapt their behavior to their partner. In this paper we present the KBAgent. The KBAgent is an automated negotiator that negotiates with each person only once, and uses past negotiation sessions of others as a knowledge base for general opponent modeling. The database is used to extract the likelihood of acceptance and proposals that may be offered by the opposite side. Experiments conducted with people show that the KBAgent negotiates efficiently with people and even achieves better utility values than another automated negotiator, shown to be efficient in negotiations with people. Moreover, the KBAgent achieves significantly better agreements, in terms of individual utility, than the human counterparts playing the same role.

AAMAS Conference 2009 Conference Paper

Investigating the Benefits of Automated Negotiations in Enhancing People's Negotiation Skills

• Raz Lin
• Yinon Oshrat
• Sarit Kraus

Negotiation surrounds our day-to-day lives. Research in the field of automated negotiations has suggested the design and use of automated negotiators, on one hand to allow facilitation of the negotiation process by human negotiators and, on the other hand to provide automated agents that can negotiate on behalf of humans. Many papers present innovative agents and evaluate their efficacy in negotiations with other automated agents or people. Others focus on building negotiation support systems with the purpose of helping negotiators reach an agreement. Yet, the question still remains whether these systems or agents have the potential of improving people’s negotiation skills. In this paper we attempt to shed more light on this topic. By means of extensive simulations with human negotiators we examine and compare several training methods and their implications on the improvement of negotiation skills of human negotiators.

JAAMAS Journal 2009 Journal Article

Multi-goal economic search using dynamic search structures

• David Sarne
• Efrat Manisterski
• Sarit Kraus

Abstract This paper investigates cooperative search strategies for agents engaged in costly search in a complex environment. Searching cooperatively, several search goals can be satisfied within a single search effort. Given the searchers’ preferences, the goal is to conduct a search in a way that the expected overall utility out of the set of opportunities found (e. g. , products when operating in a market) minus the costs associated with finding that set is maximized. This search scheme, given in the context of a group search, applies also to scenarios where a single agent has to search for a set of items for satisfying several different goals. The uniqueness of the proposed mechanism is in the ability to partition the group of agents/goals into sub-groups where the search continues for each group autonomously. As we show throughout the paper, this strategy is favorable as it weakly dominates (i. e. , can improve but never worsen) cooperative and autonomous search techniques. The paper presents a comprehensive analysis of the new search method and highlights the specific characteristics of the optimal search strategy. Furthermore, we introduce innovative algorithms for extracting the optimal search strategy in a range of common environments, that eliminates the computational overhead associated with the use of the partitioning technique.

AIJ Journal 2008 Journal Article

A study of mechanisms for improving robotic group performance

• Avi Rosenfeld
• Gal A. Kaminka
• Sarit Kraus
• Onn Shehory

ECAI Conference 2008 Conference Paper

An Empirical Investigation of the Adversarial Activity Model

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein

Multiagent research provides an extensive literature on formal Belief-Desire-Intention (BDI) based models describing the notions of teamwork and cooperation, but adversarial and competitive relationships have received very little formal BDI treatment. Moreover, one of the main roles of such models is to serve as design guide-lines for the creation of agents, and while there is work illustrating that role in cooperative interaction, there has been no empirical work done to validate competitive BDI models.

AAMAS Conference 2008 Conference Paper

Cooperative Boolean Games

• Paul Dunne
• Sarit Kraus
• Wiebe van der Hoek
• Michael Wooldridge

We present and formally investigate Cooperative Boolean Games, a new, natural family of coalitional games that are both compact and expressive. In such a game, an agent’s primary aim is to achieve its individual goal, which is represented as a propositional logic formula over some set of Boolean variables. Each agent is assumed to exercise unique control over some subset of the overall set of Boolean variables, and the set of valuations for these variables corresponds to the set of actions the agent can take. However, the actions available to an agent are assumed to have some cost, and an agent’s secondary aim is to minimise its costs. Typically, an agent must cooperate with others because it does not have sufficient control to ensure its goal is satisfied. However, the desire to minimise costs leads to preferences over possible coalitions, and hence to strategic behaviour. Following an introduction to the formal framework of Cooperative Boolean Games, we investigate solution concepts of the core and stable sets for them. In each case, we characterise the complexity of the associated solution concept, and discuss the surrounding issues. Finally, we present a bargaining protocol for cooperation in Boolean games, and characterise the strategies in equilibrium for this protocol.

AAMAS Conference 2008 Conference Paper

Deployed ARMOR Protection: The Application of a Game Theoretic Model for Security at the Los Angeles International Airport

• James Pita
• Manish Jain
• Janusz Marecki
• Fernando Ord
• oacute;
• ntilde; ez
• Christopher Portway
• Milind Tambe

Security at major locations of economic or political importance is a key concern around the world, particularly given the threat of terrorism. Limited security resources prevent full security coverage at all times, which allows adversaries to observe and exploit patterns in selective patrolling or monitoring, e. g. they can plan an attack avoiding existing patrols. Hence, randomized patrolling or monitoring is important, but randomization must provide distinct weights to different actions based on their complex costs and benefits. To this end, this paper describes a promising transition of the latest in multi-agent algorithms – in fact, an algorithm that represents a culmination of research presented at AAMAS – into a deployed application. In particular, it describes a software assistant agent called ARMOR (Assistant for Randomized Monitoring over Routes) that casts this patrolling/monitoring problem as a Bayesian Stackelberg game, allowing the agent to appropriately weigh the different actions in randomization, as well as uncertainty over adversary types. ARMOR combines three key features: (i) It uses the fastest known solver for Bayesian Stackelberg games called DOBSS, where the dominant mixed strategies enable randomization; (ii) Its mixed-initiative based interface allows users to occasionally adjust or override the automated schedule based on their local constraints; (iii) It alerts the users if mixed-initiative overrides appear to degrade the overall desired randomization. ARMOR has been successfully deployed since August 2007 at the Los Angeles International Airport (LAX) to randomize checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals. This paper examines the information, design choices, challenges, and evaluation that went into designing ARMOR.

AAMAS Conference 2008 Conference Paper

Efficiently Determining the Appropriate Mix of Personal Interaction and Reputation Information in Partner Choice

• Shulamit Reches
• Philip Hendrix
• Barbara Grosz
• Sarit Kraus

Many multi-agent settings require that agents identify appropriate partners or teammates with whom to work on tasks. When selecting potential partners, agents may benefit from obtaining information about alternative possibilities through gossip (i. e. , by consulting others) or using a reputation system (a centralized repository of information about past behavior). This paper defines a statistical model, the “Information-Acquisition Source Utility model" (IASU) by which agents operating in an uncertain world can determine the amount of information to collect about potential partners before choosing one and which information sources they should consult (gossip, reputation system, or additional personal interaction with the agent). The IASU model explicitly represents the cost of information, which may vary by information source. To maximize the expected gain from a choice, it estimates the utility of choosing a partner by iteratively estimating the benefit of additional information. The paper reports empirical studies that compare the effectiveness of the IASU model with a baseline in which only prior experience with a potential partner is used as the basis of the decision and with a model that determines in advance both the amount of information and its allocation among the different sources. Two different application domains are used in these empirical studies, the Surrogate Venture Game model, which concerns choosing an optimal partner for a business venture, and a restaurant domain. The results of the experiments show that the use of the model significantly increases the agents’ overall utility.

AAMAS Conference 2008 Conference Paper

Evaluation of Election Outcomes under Uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

We investigate the extent to which it is possible to evaluate the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings – we do not know which of these orderings actually represents the voters’ preferences, but we know for each one the probability that it does. We give a polynomial algorithm to solve the problem of computing the probability that a given candidate will win when the number of candidates is a constant. However, when the number of candidates is not bounded, we prove that the problem becomes #P-Hard for the Plurality, Borda, and Copeland voting protocols. We further show that even evaluating if a candidate has any chance to win is NP-Complete for the Plurality voting protocol, in the weighted voters case. We give a polynomial algorithm for this problem when the voters’ weights are equal.

AAMAS Conference 2008 Conference Paper

How Automated Agents Treat Humans and Other Automated Agents in Situations of Inequity: An Experimental Study

• Ron Katz
• Sarit Kraus

This paper explores the question of how agent designers perceive and treat their agent’s opponents. In particular, it examines the influence of the opponent’s identity (human vs. automated agent) in negotiations. We empirically demonstrate that when people interact spontaneously they treat human opponents differently than automated agents in the context of equity and fairness considerations. However, these difference vanish when people design and implement agents that will interact on their behalf. Nevertheless, the commitment of the agents to honor agreements with people is higher than their commitment to other agents. In the experiments, which comprised 147 computer science students, we used the Colored Trails game as the negotiation environment. We suggest possible explanations for the relationships among online players, agent designers, human opponents and automated opponents.

AIJ Journal 2008 Journal Article

Managing parallel inquiries in agents' two-sided search

• David Sarne
• Sarit Kraus

ICRA Conference 2008 Conference Paper

Multi-robot perimeter patrol in adversarial settings

• Noa Agmon
• Sarit Kraus
• Gal A. Kaminka

This paper considers the problem of multi-robot patrol around a closed area with the existence of an adversary attempting to penetrate into the area. In case the adversary knows the patrol scheme of the robots and the robots use a deterministic patrol algorithm, then in many cases it is possible to penetrate with probability 1. Therefore this paper considers a non-deterministic patrol scheme for the robots, such that their movement is characterized by a probability p. This patrol scheme allows reducing the probability of penetration, even under an assumption of a strong opponent that knows the patrol scheme. We offer an optimal polynomial-time algorithm for finding the probability p such that the minimal probability of penetration detection throughout the perimeter is maximized. We describe three robotic motion models, defined by the movement characteristics of the robots. The algorithm described herein is suitable for all three models.

AIJ Journal 2008 Journal Article

Negotiating with bounded rational agents in environments with incomplete information using an automated agent

• Raz Lin
• Sarit Kraus
• Jonathan Wilkenfeld
• James Barry

AAAI Conference 2008 Conference Paper

Physical Search Problems Applying Economic Search Models

• Yonatan Aumann
• Sarit Kraus

This paper considers the problem of an agent searching for a resource or a tangible good in a physical environment, where at each stage of its search it observes one source where this good can be found. The cost of acquiring the resource or good at a given source is uncertain (a-priori), and the agent can observe its true value only when physically arriving at the source. Sample applications involving this type of search include agents in exploration and patrol missions (e. g. , an agent seeking to find the best location to deploy sensing equipment along its path). The uniqueness of these settings is that the expense of observing the source on each step of the process derives from the last source the agent explored. We analyze three variants of the problem, differing in their objective: minimizing the total expected cost, maximizing the success probability given an initial budget, and minimizing the budget necessary to obtain a given success probability. For each variant, we first introduce and analyze the problem with a single agent, either providing a polynomial solution to the problem or proving it is NP-Complete. We also introduce an innovative fully polynomial time approximation scheme algorithm for the minimum budget variant. Finally, the results for the single agent case are generalized to multi-agent settings.

AAMAS Conference 2008 Conference Paper

Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Games

• Praveen Paruchuri
• Jonathan Pearce
• Janusz Marecki
• Milind Tambe
• Fernando Ordonez
• Sarit Kraus

In a class of games known as Stackelberg games, one agent (the leader) must commit to a strategy that can be observed by the other agent (the follower or adversary) before the adversary chooses its own strategy. We consider Bayesian Stackelberg games, in which the leader is uncertain about the types of adversary it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and a robber (follower) has a chance to observe this strategy over time before choosing its own strategy of where to attack. This paper presents an efficient exact algorithm for finding the optimal strategy for the leader to commit to in these games. This algorithm, DOBSS, is based on a novel and compact mixed-integer linear programming formulation. Compared to the most efficient algorithm known previously for this problem, DOBSS is not only faster, but also leads to higher quality solutions, and does not suffer from problems of infeasibility that were faced by this previous algorithm. Note that DOBSS is at the heart of the ARMOR system that is currently being tested for security scheduling at the Los Angeles International Airport.

AAMAS Conference 2008 Conference Paper

Programming Agents as a Means of Capturing Self-Strategy

• Michal Chalamish
• David Sarne
• Sarit Kraus

In this paper we report results of an extensive evaluation of people’s ability to reproduce the strategies they use in simple real-life settings. Having the ability to reliably capture people’s strategies in different environments is highly desirable in Multi-Agent Systems (MAS). However, as trivial and daily as these strategies are, the process is not straightforward and people often have a different belief of how they act. We describe our experiments in this area, based on the participation of a pool of subjects in four different games with variable complexity and characteristics. The main measure used for determining the closeness between the two types of strategies used is the level of similarity between the actions taken by the participants and those taken by agents they programmed in identical world states. Our results indicate that generally people have the ability to reproduce their game strategies for the class of games we consider. However, this process should be handled carefully as some individuals tend to exhibit a behavior different from the one they program into their agents. The paper evaluates one possible method for enhancing the process of strategy reproduction.

KR Conference 2008 Conference Paper

Promises Kept, Promises Broken: An Axiomatic and Quantitative Treatment of Fulfillment

• Gerardo I. Simari
• Matthias Broecheler
• V. S. Subrahmanian
• Sarit Kraus

In this paper, we propose a theoretical framework within which to evaluate the reliability of promises that an agent makes, based on past performance of the agent. Our framework does not just propose one such measure, but defines axioms that govern the choice of measure. The framework is able to account for partial fulfillment of promises, late fulfillment of promises, fulfillment of variants of promises, and the like. Within this framework, we propose some specific measures to evaluate promises made by agents and develop algorithms to compute these efficiently. We tested our methods on a real world data set of airline flight information and show that our methods are both accurate and quickly computable, even on large data sets.

AIJ Journal 2008 Journal Article

Resolving crises through automated bilateral negotiations

• Sarit Kraus
• Penina Hoz-Weiss
• Jonathan Wilkenfeld
• David R. Andersen
• Amy Pate

AAMAS Conference 2008 Conference Paper

Synthesis of Strategies from Interaction Traces

• Tsz-Chiu Au
• Dana Nau
• Sarit Kraus

We describe how to take a set of interaction traces produced by different pairs of players in a two-player repeated game, and combine them into a composite strategy. We provide an algorithm that, in polynomial time, can generate the best such composite strategy. We describe how to incorporate the composite strategy into an existing agent, as an enhancement of the agent’s original strategy. We provide experimental results using interaction traces from 126 agents (most of them written by students as class projects) for the Iterated Prisoner’s Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes. We compared each agent with the enhanced version of that agent produced by our algorithm. The enhancements improved the agents’ scores by about 5% in the IPD, 11% in the ICG, and 26% in the IBS, and improved their rank by about 12% in the IPD, 38% in the ICG, and 33% in the IBS.

AAMAS Conference 2008 Conference Paper

The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol

• Noa Agmon
• Vladimir Sadov
• Sarit Kraus
• Gal Kaminka

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a “lower bound” to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots. This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent—a different extreme—and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the Combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

AAMAS Conference 2008 Conference Paper

Towards Bidirectional Distributed Matchmaking

• Victor Shafran
• Gal Kaminka
• Sarit Kraus
• Claudia Goldman

Matchmaking is the process of introducing two or more agents to each other. Current matchmaking techniques are unidirectional and fail to address large-scale and highly dynamic systems with time constraints. We propose a new distributed technique which scales well, and still maintains relatively low matchmaking time and communication overhead. Our technique introduces very low storage and computational overhead to the agents. We suggest using a matching cache which can take advantage of the multidirectional nature of the matchmaking problem. We empirically evaluate the proposed technique on bilateral matchmaking and show that it outperforms the existing techniques.

AAMAS Conference 2008 Conference Paper

Understanding How People Design Trading Agents over Time

• Efrat Manistersky
• Raz Lin
• Sarit Kraus

As computerized agents are becoming more and more common, e-commerce becomes a major candidate for incorporation of automated agents. Thus, it is vital to understand how people design agents for online markets and how their design changes over time. This, in turn, will enable better design of agents for these environments. We focus on the design of trading agents for bilateral negotiations with unenforceable agreements. In order to simulate this environment we conducted an experiment with human subjects who were asked to design agents for a resource allocation game. The subjects’ agents participated in several tournaments against each other and were given the opportunity to improve their agents based on their performance in previous tournaments. Our results show that, indeed, most subjects modified their agents’ strategic behavior with the prospect of improving the performance of their agents, yet their average score significantly decreased throughout the tournaments and became closer to the equilibrium agents’ score. In particular, the subjects modified their agents to break more agreements throughout the tournaments. In addition, the subjects increased their means of protection against deceiving agents.

IJCAI Conference 2007 Conference Paper

• Efrat Manisterski
• David Sarne
• Sarit Kraus

In this paper we present new search strategies for agents with diverse preferences searching cooperatively in complex environments with search costs. The uniqueness of our proposed mechanism is in the integration of the coalition's ability to partition itself into sub-coalitions, which continue the search autonomously, into the search strategy (a capability that was neglected in earlier cooperative search models). As we show throughout the paper, this strategy is always favorable in comparison to currently known cooperative and autonomous search techniques: it has the potential to significantly improve the searchers' performance in various environments and in any case guarantees reaching at least as good a performance as that of other known methods. Furthermore, for many common environments we manage to significantly eliminate the consequential added computational complexity associated with the partitioning option, by introducing innovative efficient algorithms for extracting the coalition's optimal search strategy. We illustrate the advantages of the proposed model over currently known cooperative and individual search techniques, using an environment based on authentic settings.

IJCAI Conference 2007 Conference Paper

• Efrat Manisterski
• Ron Katz
• Sarit Kraus

This paper presents a novel approach for providing automated trading agents to a population, focusing on bilateral negotiation with unenforceable agreements. A new type of agents, called semi-cooperative (SC) agents is proposed for this environment. When these agents negotiate with each other they reach a pareto-optimal solution that is mutually beneficial. Through extensive experiments we demonstrate the superiority of providing such agents for humans over supplying equilibrium agents or letting people design their own agents. These results are based on our observation that most people do not modify SC agents even though they are not in equilibrium. Our findings introduce a new factor ---human response to provided agents --- that should be taken into consideration when developing agents that are provided to a population.

IJCAI Conference 2007 Conference Paper

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein

We consider an automated agent that needs to coordinate with a human partner when communication between them is not possible or is undesirable (tactic coordination games). Specifically, we examine situations where an agent and human attempt to coordinate their choices among several alternatives with equivalent utilities. We use machine learning algorithms to help the agent predict human choices in these tactic coordination domains.

AAMAS Conference 2007 Conference Paper

A Statistical Decision-making Model for Choosing among Multiple Alternatives

• Shulamit Reches
• Shavit Talman
• Sarit Kraus

AAMAS Conference 2007 Conference Paper

An Adversarial Environment Model for Bounded Rational Agents in Zero-Sum Interactions

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein
• Gal Kaminka

Multiagent environments are often not cooperative nor collaborative; in many cases, agents have conflicting interests, leading to adversarial interactions. This paper presents a formal Adversarial Environment model for bounded rational agents operating in a zero-sum environment. In such environments, attempts to use classical utility-based search methods can raise a variety of difficulties (e. g. , implicitly modeling the opponent as an omniscient utility maximizer, rather than leveraging a more nuanced, explicit opponent model).

AAMAS Conference 2007 Conference Paper

An Efficient Heuristic Approach for Security Against Multiple Adversaries

• Praveen Paruchuri
• Jonathan P. Pearce
• Milind Tambe
• Fernando Ordonez
• Sarit Kraus

In adversarial multiagent domains, security, commonly defined as the ability to deal with intentional threats from other agents, is a critical issue. This paper focuses on domains where these threats come from unknown adversaries. These domains can be modeled as Bayesian games; much work has been done on finding equilibria for such games. However, it is often the case in multiagent security domains that one agent can commit to a mixed strategy which its adversaries observe before choosing their own strategies. In this case, the agent can maximize reward by finding an optimal strategy, without requiring equilibrium. Previous work has shown this problem of optimal strategy selection to be NP-hard. Therefore, we present a heuristic called ASAP, with three key advantages to address the problem. First, ASAP searches for the highest-reward strategy, rather than a Bayes-Nash equilibrium, allowing it to find feasible strategies that exploit the natural first-mover advantage of the game. Second, it provides strategies which are simple to understand, represent, and implement. Third, it operates directly on the compact, Bayesian game representation, without requiring conversion to normal form. We provide an efficient Mixed Integer Linear Program (MILP) implementation for ASAP, along with experimental results illustrating significant speedups and higher rewards over other approaches.

AAMAS Conference 2007 Conference Paper

AutoMed - An Automated Mediator for Bilateral Negotiations Under Time Constraints

• Michal Chalamish
• Sarit Kraus

AAMAS Conference 2007 Conference Paper

Mass Programmed Agents for Simulating Human Strategies in Large Scale Systems

• Michal Chalamish
• David Sarne
• Sarit Kraus

AAMAS Conference 2007 Conference Paper

On the Benefits of Cheating by Self-Interested Agents in Vehicular Networks

• Raz Lin
• Sarit Kraus
• Yuval Shavitt

As more and more cars are equipped with GPS and Wi-Fi transmitters, it becomes easier to design systems that will allow cars to interact autonomously with each other, e. g. , regarding traffic on the roads. Indeed, car manufacturers are already equipping their cars with such devices. Though, currently these systems are a proprietary, we envision a nat- ural evolution where agent applications will be developed for vehicular systems, e. g. , to improve car routing in dense urban areas. Nonetheless, this new technology and agent ap- plications may lead to the emergence of self-interested car owners, who will care more about their own welfare than the social welfare of their peers. These car owners will try to manipulate their agents such that they transmit false data to their peers. Using a simulation environment, which mod- els a real transportation network in a large city, we demon- strate the benefits achieved by self-interested agents if no counter-measures are implemented.

AAMAS Conference 2007 Conference Paper

Scaling-Up Shopbots - a Dynamic Allocation-Based Approach

• David Sarne
• Sarit Kraus
• Takayuki Ito

In this paper we consider the problem of eCommerce comparison shopping agents (shopbots) that are limited by capacity constraints. In light of the phenomenal increase both in demand for price comparison services over the internet and in the number of opportunities available in electronic markets, shopbots are nowadays required to improve the utilization of their finite set of querying resources. In this paper we introduce PlanBot, an innovative shopbot which uniquely integrates concepts from production management and economic search theory. PlanBot aims to maximize its efficiency by dynamically re-planning the allocation of its querying resources according to the results of formerly executed queries and new arriving requests. We detail the design principles that drive the PlanBot 's operation and illustrate its improved performance (in comparison to the traditional shopbots' First-Come-First-Served (FCFS) query execution mechanisms) using a simulated environment which is based on price datasets collected over the internet. Our encouraging results suggest that the design principles we apply have the potential of being used as an infrastructure for various implementations of future comparison shopping agents.

ECAI Conference 2006 Conference Paper

An Automated Agent for Bilateral Negotiation with Bounded Rational Agents with Incomplete Information

• Raz Lin
• Sarit Kraus
• Jonathan Wilkenfeld
• James Barry

Many day-to-day tasks require negotiation, mostly under conditions of incomplete information. In particular, the opponent's exact tradeoff between different offers is usually unknown. We propose a model of an automated negotiation agent capable of negotiating with a bounded rational agent (and in particular, against humans) under conditions of incomplete information. Although we test our agent in one specific domain, the agent's architecture is generic; thus it can be adapted to any domain as long as the negotiators' preferences can be expressed in additive utilities. Our results indicate that the agent played significantly better, including reaching a higher proportion of agreements, than human counterparts when playing one of the sides, while when playing the other side there was no significant difference between the results of the agent and the human players.

AAMAS Conference 2006 Conference Paper

Efficient agents for Cliff Edge environments with a large set of decision options

• Ron Katz
• Sarit Kraus

AAMAS Conference 2006 Conference Paper

Forming Efficient Agent Groups for Completing Complex Tasks

• Efrat Manisterski
• Esther David
• Sarit Kraus
• NICK JENNINGS

AAMAS Conference 2006 Conference Paper

Integrating Parallel Interactions into Cooperative Search

• Efrat Manisterski
• David Sarne
• Sarit Kraus

AAMAS Conference 2006 Conference Paper

MLBP: MAS for Large-Scale Biometric Pattern Recognition

• Ram Meshulam
• Shulamit Reces
• Aner Yarden
• Sarit Kraus

AAMAS Conference 2006 Conference Paper

Security in multiagent systems by policy randomization

• Praveen Paruchuri
• Milind Tambe
• Fernando Ordonez
• Sarit Kraus

AIJ Journal 2005 Journal Article

A logic-based model of intention formation and action for multi-agent subcontracting

• John Grant
• Sarit Kraus
• Donald Perlis

AAMAS Conference 2005 Conference Paper

Buyer's Coalition for Optimal Search

• David Sarne
• Sarit Kraus

AAMAS Conference 2005 Conference Paper

Utility-Based Multi-Agent System for Performing Repeated Navigation Tasks

• Ram Meshulam
• Ariel Felner
• Sarit Kraus

ECAI Conference 2004 Conference Paper

Adaptive Robot Coordination Using Interference Metrics

• Avi Rosenfeld
• Gal A. Kaminka
• Sarit Kraus

ECAI Conference 2004 Conference Paper

Equilibrium Strategies for Task Allocation in Dynamic Multi-Agent Systems

• David Sarne
• Meirav Hadad
• Sarit Kraus

AIJ Journal 2004 Journal Article

Stable repeated strategies for information exchange between two autonomous agents

• Rina Azoulay-Schwartz
• Sarit Kraus

AAMAS Conference 2004 Conference Paper

The Advantages of Compromising in Coalition Formation with Incomplete Information

• Sarit Kraus
• Onn Shehory
• Gilad Taase

AAMAS Conference 2004 Conference Paper

The Influence of Social Dependencies on Decision-Making: Initial Investigations with a New Game

• Barbara Grosz
• Sarit Kraus
• Shavit Talman
• Boaz Stossel
• Moti Havlin

AAMAS Conference 2004 Conference Paper

Time-Variant Distributed Agent Matching Applications

• David Sarne
• Sarit Kraus

AAMAS Conference 2004 Conference Paper

Towards a formalization of teamwork with resource constraints

• Praveen Paruchuri
• Milind Tambe
• Fernando Ordonez
• Sarit Kraus

AAMAS Conference 2003 Conference Paper

Bidders` strategy for Multi-Attribute sequential English auction with a deadline

• Esther David
• Rina Azulay-Schwartz
• Sarit Kraus

AAMAS Conference 2003 Conference Paper

Coalition Formation with Uncertain Heterogeneous Information

• Sarit Kraus
• Onn Shehory
• Gilad Tasse

IJCAI Conference 2003 Conference Paper

Probabilistically Survivable MASs

• Sarit Kraus
• V. S. Subrahmanian
• N. Cihan Tas

Muhiagent systems (MAS) can "go down" for a large number of reasons, ranging from system malfunctions and power failures to malicious attacks. The placement of agents on nodes is called a deployment of the MAS. We develop a probabilistic model of survivability of a deployed MAS and provide two algorithms to compute the probability of survival of a deployed MAS. Our probabilistic model docs not make independence assumptions though such assumptions can be added if so desired. An optimal deployment of a MAS is one that maximizes its survival probability. We provide a mathematical answerto this question, an algorithm that computes an exact solution to this problem, as well as several algorithms that quickly compute approximate solutions to the problem. We have implemented our algorithms - our implementation demonstrates that computing deployments can be done scalably.

AAMAS Conference 2002 Conference Paper

Agents dealing with Time and Uncertainty

• Juergen Dix
• Sarit Kraus
• VS Subrahmanian

AIJ Journal 2002 Journal Article

Editorial

• Ed Durfee
• Sarit Kraus
• Hideyuki Nakashima
• Milind Tambe

AAMAS Conference 2002 Conference Paper

Finding Optimal Path in Unknown Physical Environments

• Ariel Felner
• Roni Stern
• Sarit Kraus

AAMAS Conference 2002 Conference Paper

Protocols and Strategies for Automated Multi Attributes Auctions

• Esther David
• Rina Azulay
• Sarit Kraus

AIJ Journal 2002 Journal Article

The influence of social norms and social consciousness on intention reconciliation

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

AIJ Journal 2001 Journal Article

Temporal agent programs

• Jürgen Dix
• Sarit Kraus
• V.S. Subrahmanian

TCS Journal 2000 Journal Article

Algorithms of distributed task allocation for cooperative agents

• Sarit Kraus
• Tatjana Plotkin

AIJ Journal 1999 Journal Article

Emergent cooperative goal-satisfaction in large-scale automated-agent systems

• Onn Shehory
• Sarit Kraus
• Osher Yadgar

AIJ Journal 1998 Journal Article

Methods for task allocation via agent coalition formation

• Onn Shehory
• Sarit Kraus

AIJ Journal 1998 Journal Article

Reaching agreements through argumentation: a logical model and implementation

• Sarit Kraus
• Katia Sycara
• Amir Evenchik

AIJ Journal 1998 Journal Article

Syntactical treatments of propositional attitudes

• Michael Morreau
• Sarit Kraus

AIJ Journal 1998 Journal Article

Utility-based on-line exploration for repeated navigation in an embedded graph

• Shlomo Argamon-Engelson
• Sarit Kraus
• Sigalit Sina

AIJ Journal 1997 Journal Article

Negotiation and cooperation in multi-agent environments

• Sarit Kraus

AIJ Journal 1996 Journal Article

An overview of incentive contracting

• Sarit Kraus

AIJ Journal 1996 Journal Article

Collaborative plans for complex group action

• Barbara J. Grosz
• Sarit Kraus

ECAI Conference 1996 Conference Paper

Cooperative Goal-satisfaction without Communication in Large-scale Agent-Systems

• Onn Shehory
• Sarit Kraus

AIJ Journal 1995 Journal Article

Multiagent negotiation under time constraints

• Sarit Kraus
• Jonathan Wilkenfeld
• Gilad Zlotkin

IJCAI Conference 1995 Conference Paper

Task allocation via coalition formation among autonomous agents

• Onn Shehory
• Sarit Kraus

Autonomous agents working in multi-agent environments may need to cooperate in order to fulfill tasks. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents which will perform the task. The allocation of tasks to groups of agents is necessary when tasks cannot be performed by a single agent. It may also be useful to assign groups of agents to tasks when the group's performance is more efficient than the performance of single agents. In this paper we give an efficient solution to the problem of task allocation among autonomous agents, and suggest that the agents will form coalitions in order to perform tasks or improve the efficiency. We present a distributed algorithm with a low ratio bound and with a low computational complexity. Our algorithm is an any-time algorithm, it is simple, efficient and easy to implement.

ECAI Conference 1994 Conference Paper

Interaction and Collaboration in Multi-agent Systems

• Sarit Kraus

AAAI Conference 1993 Conference Paper

Agents Contracting Tasks in Non-Collaborative Environments

• Sarit Kraus

Agents may sub-contract some of their tasks to other agent(s) even when they don’ t share a common goal. An agent tries to contract some of its tasks that it can’ t perform by itself, or when the task may be performed more efficiently or better by other agents. A “selfish” agent may convince another “selfish” agent to help it with its task, even if the agents are not assumed to be benevolent, by promises of rewards. We propose techniques that provide efficient ways to reach subcontracting in varied situations: the agents have full information about the environment and each other vs. subcontracting when the agents don’ t know the exact state of the world. We consider situations of repeated encounters, cases of asymmetric information, situations where the agents lack information about each other, and cases where an agent subcontracts a task to a group of agents. We also consider situations where there is a competition either among contracted agents or contracting agents. In all situations we would like the contracted agent to carry out the task efficiently without the need of close supervision by the contracting agent. The contracts that are reached are simple, Pareto-optimal and stable.

IJCAI Conference 1993 Conference Paper

Collaborative Plans for Group Activities

• Barbara Grosz
• Sarit Kraus

IJCAI Conference 1991 Conference Paper

Negotiations Over Time in a Multi-Agent Environment: Preliminary Report

• Sarit Kraus
• Jonathan

AIJ Journal 1991 Journal Article

Nonmonotonicity and the scope of reasoning

• David W. Etherington
• Sarit Kraus
• Donald Perlis

AAAI Conference 1991 Conference Paper

The Function of Time in Cooperative Negotiations

• Sarit Kraus

Work in distributed artificial intelligence (DAI) has, since its earliest years, been concerned with negotiation strategies. which can be used in building agents that are able to communicate to reach mutually beneficial agreements. In this paper we suggest a strategic model of negotiation that takes the passage of time during the negotiation process itself into consideration. Changes in the agent’ s preferences over time will change their strategies in the negotiation and, as a result the agreements they are willing to reach. We will show that in this model the delay in reaching agreements can be avoided.

AIJ Journal 1990 Journal Article

Nonmonotonic reasoning, preferential models and cumulative logics

• Sarit Kraus
• Daniel Lehmann
• Menachem Magidor

TCS Journal 1988 Journal Article

Knowledge, belief and time

• Sarit Kraus
• Daniel Lehmann

FOCS Conference 1983 Conference Paper

Decision Procedures for Time and Chance (Extended Abstract)

• Sarit Kraus
• Daniel Lehmann 0001

Decision procedures are provided for checking the satisfiability of a formula in each of the three systems TCg. TCb and TCf defined in [LS]. The procedures for TCg and TCf run in non-deterministic time 22on where n is the size of the formula and c is a constant. The procedure for TCb runs in non-deterministic time 22on2. A deterministic exponential lower bound is proved for the three systems. All three systems are also shown to be PSPACE-hard using results of [SC]. Those decision procedures are not as efficient as the deterministic (one or two)- exponential time procedures proposed in [BMP] and [EH1] for different logics of branching time that are weaker than ours in expressive power. No elementary decision procedure is known for a logic of branching time that is as expressive as ours. The decision procedures of the probabilistic logics of [HS] run in deterministic exponential time but their language is essentially less expressive than ours.