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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Teleoperation of autonomous vehicles has been gaining a lot of attention recently and is expected to play an important role in helping autonomous vehicles handle difficult situations which they cannot handle on their own. In such cases, a remote driver located in a teleoperation center can remotely drive the vehicle until the situation is resolved. However, teledriving is a challenging task and requires many cognitive resources from the teleoperator. Our goal is to assist the remote driver in some complex situations by giving the driver appropriate advice. The advice is displayed on the driver’s screen to help her make the right decision. To this end, we introduce the TeleOperator Advisor (TOA), an adaptive agent that provides assisting advice to a remote driver. We evaluate the TOA in a simulation-based setting in two scenarios: overtaking a slow vehicle and passing through a traffic light. Results indicate that our advice helps to reduce the cognitive load of the remote driver and improve driving performance.

Advertisements (ads) are an innate part of search engine business models. To promote sales, advertisers are willing to pay search engines to promote their content to a prominent position in the search result page (SERP). This raises concerns about the search engine manipulation effect (SEME): the opinions of users can be influenced by the way search results are presented

In rational verification , the aim is to verify which temporal logic properties will obtain in a multi-agent system, under the assumption that agents (“players”) in the system choose strategies for acting that form a game theoretic equilibrium. Preferences are typically defined by assuming that agents act in pursuit of individual goals, specified as temporal logic formulae. To date, rational verification has been studied using non-cooperative solution concepts—Nash equilibrium and refinements thereof. Such non-cooperative solution concepts assume that there is no possibility of agents forming binding agreements to cooperate, and as such they are restricted in their applicability. In this article, we extend rational verification to cooperative solution concepts, as studied in the field of cooperative game theory . We focus on the core , as this is the most fundamental (and most widely studied) cooperative solution concept. We begin by presenting a variant of the core that seems well-suited to the concurrent game setting, and we show that this version of the core can be characterised using ATL ⁎ . We then study the computational complexity of key decision problems associated with the core, which range from problems in PSpace to problems in 3ExpTime . We also investigate conditions that are sufficient to ensure that the core is non-empty, and explore when it is invariant under bisimilarity. We then introduce and study a number of variants of the main definition of the core, leading to the issue of credible deviations, and to stronger notions of collective stable behaviour. Finally, we study cooperative rational verification using an alternative model of preferences, in which players seek to maximise the mean-payoff they obtain over an infinite play in games where quantitative information is allowed.

Without measures of the lethality of terrorist networks, it is very difficult to assess if capturing or killing a terrorist is effective. We present the predictive lethality analysis of terrorist organization () algorithm, which merges machine learning with techniques from graph theory and social network analysis to predict the number of attacks that a terrorist network will carry out based on a network structure alone. We show that is highly accurate on two novel datasets, which cover Al Qaeda (AQ) and the Islamic State (ISIS). Using both machine learning and statistical methods, we show that the most significant macrofeatures for predicting AQ’s lethality are related to their public communications (PCs) and logistical subnetworks, while the leadership and operational subnetworks are most impactful for predicting ISISs lethality. Across both groups, the average degree and the diameters of the strongly connected components (SCCs) within these networks are strongly linked with lethality.

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.

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.

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.

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.

Real-world security scenarios sometimes involve multiple defenders: security agencies of two or more countries might patrol the same border areas, and domestic security agencies might also operate in the same locations when their areas of jurisdiction overlap. Motivated by these scenarios and the observation that uncoordinated movements of the defenders may lead to an inefficient defense, we introduce a model of multi-defender security games and explore the possibility of improving efficiency by coordinating the defenders — specifically, by pooling the defenders' resources and allocating them jointly. The model generalizes the standard model of Stackelberg security games, where a defender (now a group of defenders) allocates security resources to protect a set of targets, and an attacker picks the best target to attack. In particular, we are interested in the situation with heterogeneous defenders, who may value the same target differently. Our task is twofold. First, we need to develop a good understanding of the uncoordinated situation, as the baseline to be improved. To this end we formulate a new equilibrium concept, and prove that an equilibrium under this concept always exists and can be computed efficiently. Second, to coordinate the heterogeneous defenders we take a mechanism design perspective and aim to find a mechanism to generate joint resource allocation strategies. We seek a mechanism that improves the defenders' utilities upon the uncoordinated baseline, achieves Pareto efficiency, and incentivizes the defenders to report their true incentives and execute the recommended strategies. Our analysis establishes several impossibility results, which indicate the intrinsic difficulties of defense coordination. Specifically, we show that even the basic properties listed above are in conflict with each other: no mechanism can simultaneously satisfy them all, or even some proper subsets of them. In terms of positive results, we present mechanisms that satisfy all combinations of the properties that are not ruled out by our impossibility results, thereby providing a comprehensive profile of the mechanism design problem with respect to the properties considered.

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 self-interested 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.

Automated vehicles promise a future where drivers can engage in non-driving tasks without hands on the steering wheels for a prolonged period. Nevertheless, automated vehicles may still need to occasionally hand the control back to drivers due to technology limitations and legal requirements. While some systems determine the need for driver takeover using driver context and road condition to initiate a takeover request, studies show that the driver may not react to it. We present DeepTake, a novel deep neural network-based framework that predicts multiple aspects of takeover behavior to ensure that the driver is able to safely take over the control when engaged in non-driving tasks. Using features from vehicle data, driver biometrics, and subjective measurements, DeepTake predicts the driver’s intention, time, and quality of takeover. We evaluate DeepTake performance using multiple evaluation metrics. Results show that DeepTake reliably predicts the takeover intention, time, and quality, with an accuracy of 96%, 93%, and 83%, respectively. Results also indicate that DeepTake outperforms previous state-of-the-art methods on predicting driver takeover time and quality. Our findings have implications for the algorithm development of driver monitoring and state detection.

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).

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.

Search engines are perceived as a reliable source for general information needs. However, finding the answer to medical questions using search engines can be challenging for an ordinary user. Content can be biased and results may present different opinions. In addition, interpreting medically related content can be difficult for users with no medical background. All of these can lead users to incorrect conclusions regarding health related questions.

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.

The successful integration of automation in systems that affect human experiences requires the user acceptance of those automated functionalities. For example, the human comfort felt during a ride is affected by the automated control behavior of the vehicle. The challenge presented in this paper is how to develop an intelligent agent that learns its users? driving preferences and adjusts the vehicle control in real time, accordingly, minimizing the number of otherwise required manual interventions. This is a hard problem since users? preferences can be complex, context dependent and do not necessarily translate to the language of machines in a simple and straightforward manner. Our solution includes (1) a simulation test bed, (2) an adaptive intelligent interface and (3) an adaptive agent that learns to predict user's driving discomfort and it also learns to compute corrective actions that maximize user acceptance of automated driving. Overall, we conducted three user studies with 94 subjects in simulated driving scenarios. Our results show that our intelligent agent learned to successfully predict how to adjust the automated driving style to increase user? acceptance by decreasing the number of user manual interventions.

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.

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.

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.

Although most game theory models assume that payoff matrices are provided as input, getting payoff matrices in strategic games (e.g., corporate negotiations and counter-terrorism operations) has proven difficult. To tackle this challenge, we propose a payoff inference engine (PIE) that finds payoffs assuming that players in a game follow a myopic best response or a regret minimization heuristic. This assumption yields a set of constraints (possibly nonlinear) on the payoffs with a multiplicity of solutions. PIE finds payoffs by considering solutions of these constraints and their variants via three heuristics. First, we approximately compute a centroid of the resulting polytope of the constraints. Second, we use a soft constraint approach that allows violation of constraints by penalizing violations in the objective function. Third, we develop a novel approach to payoff inference based on support vector machines (SVMs). Unlike past work on payoff inference, PIE has the following advantages. PIE supports reasoning about multiplayer games, not just one or two players, it can use short histories, not long ones which may not be available in many real-world situations, it does not require all players to be fully rational, and it is one to two orders of magnitude more scalable than past work. We run experiments on a synthetic data set where we generate payoff functions for the players and see how well our algorithms can learn them, a real-world coarse-grained counter-terrorism data set about a set of different terrorist groups, and a real-world fine-grained data set about a specific terrorist group. As the ground truth about payoffs for the terrorist groups cannot be tested directly, we test PIE by using the payoffs to make predictions about the actions of the groups and corresponding governments (even though this is not the purpose of this article). We show that compared with recent work on payoff inference, PIE has both higher accuracy and much shorter runtime.

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.

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.

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 can obtain a profit which is at least as high as the maximum profit in any of the equilibria that hold in the latter.

Automated agents that interact proficiently with people can be useful in supporting, training or replacing people in complex tasks. The inclusion of people presents novel problems for the design of automated agents' strategies. People do not necessarily adhere to the optimal, monolithic strategies that can be derived analytically. Their behavior is affected by a multitude of social and psychological factors. In this talk I will show how combining machine learning techniques for human modeling, human behavioral models, formal decision-making and game theory approaches enables agents to interact well with people. Applications include intelligent agents that help drivers reduce energy consumption, agents that support rehabilitation, employer-employee negotiation and agents that support a human operator in managing a team of low-cost mobile robots in search and rescue tasks.

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.

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.

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.

Online platforms which assist people in finding a suitable partner or match, such as online dating and job recruiting environments, have become increasingly popular in the last decade. Many of these platforms include recommender systems which aim at helping users discover other people who will also be interested in them. These recommender systems benefit from contemplating the interest of both sides of the recommended match, however the question of how to optimally balance the interest and the response of both sides remains open. In this study we present a novel recommendation method for recommending people to people. For each user receiving a recommendation, our method finds the optimal balance of two criteria: a) the likelihood of the user accepting the recommendation; and b) the likelihood of the recommended user positively responding. We extensively evaluate our recommendation method in a group of active users of an operational online dating site. We find that our method is significantly more effective in increasing the number of successful interactions compared to a state-of-the-art recommendation method.

Automated platforms which support users in finding a mutually beneficial match, such as online dating and job recruitment sites, are becoming increasingly popular. These platforms often include recommender systems that assist users in finding a suitable match. While recommender systems which provide explanations for their recommendations have shown many benefits, explanation methods have yet to be adapted and tested in recommending suitable matches. In this paper, we introduce and extensively evaluate the use of "reciprocal explanations" - explanations which provide reasoning as to why both parties are expected to benefit from the match. Through an extensive empirical evaluation, in both simulated and real-world dating platforms with 287 human participants, we find that when the acceptance of a recommendation involves a significant cost (e.g., monetary or emotional), reciprocal explanations outperform standard explanation methods, which consider the recommendation receiver alone. However, contrary to what one may expect, when the cost of accepting a recommendation is negligible, reciprocal explanations are shown to be less effective than the traditional explanation methods.

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.

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.

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.

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. %We present a game 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.

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.

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.

Argumentative discussion is a highly demanding task. In order to help people in such discussions, this article provides an innovative methodology for developing agents that can support people in argumentative discussions by proposing possible arguments. By gathering and analyzing human argumentative behavior from more than 1000 human study participants, we show that the prediction of human argumentative behavior using Machine Learning (ML) is possible and useful in designing argument provision agents. This paper first demonstrates that ML techniques can achieve up to 76% accuracy when predicting people’s top three argument choices given a partial discussion. We further show that well-established Argumentation Theory is not a good predictor of people’s choice of arguments. Then, we present 9 argument provision agents, which we empirically evaluate using hundreds of human study participants. We show that the Predictive and Relevance-Based Heuristic agent (PRH), which uses ML prediction with a heuristic that estimates the relevance of possible arguments to the current state of the discussion, results in significantly higher levels of satisfaction among study participants compared with the other evaluated agents. These other agents propose arguments based on Argumentation Theory; propose predicted arguments without the heuristics or with only the heuristics; or use Transfer Learning methods. Our findings also show that people use the PRH agents proposed arguments significantly more often than those proposed by the other agents.

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 needto 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.

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 well-established Argumentation Theory is not a good predictor of people's choice of arguments. Then, we present a model that has 76% accuracy when predicting people’s 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 people’s 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.

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,a 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.

Extensive use of computerized forums and chat-rooms provides a modern venue for deception. We propose introducing an agent to assist in detecting and incriminating a deceptive participant. We designed a game, where deception in a text based discussion environment occurs. In this game several participants attempt to collectively detect a deceptive member. We compose an automated agent which participates in this game as a regular player. The goal of the agent is to detect the deceptive participant and alert other members, without raising suspicion itself. We use machine learning on the data collected from human players to design this agent. Extensive evaluation of our agent shows that it succeeds in raising the players collective success rate in catching the deceptive player.

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.

Reducing energy consumption of climate control systems is important in order to reduce human environmental footprint. The need to save energy becomes even greater when considering an electric car, since heavy use of the climate control system may exhaust the battery. In this paper we consider a method for an automated agent to provide advice to drivers which will motivate them to reduce the energy consumption of their climate control unit. Our approach takes into account both the energy consumption of the climate control system and the expected comfort level of the driver. We therefore build two models, one for assessing the energy consumption of the climate control system as a function of the system’s settings, and the other, models human comfort level as a function of the climate control system’s settings. Using these models, the agent provides advice to the driver considering how to set the climate control system. The agent advises settings which try to preserve a high level of comfort while consuming as little energy as possible. We empirically show that drivers equipped with our agent which provides them with advice significantly save energy as compared to drivers not equipped with our agent.

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.

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 ScenarioGen, 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.

Interruptions can have a significant impact on users working to complete a task. When people are collaborating, either with other users or with systems, coordinating interruptions is an important factor in maintaining efficiency and preventing information overload. Computer systems can observe user behavior, model it, and use this to optimize the interruptions to minimize disruption. However, current techniques often require long training periods that make them unsuitable for online collaborative environments where new users frequently participate.

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.

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.

The design of automated negotiators has been the focus of abundant research in recent years. However, due to difficulties involved in creating generalized agents that can negotiate in several domains and against human counterparts, many automated negotiators are domain specific and their behavior cannot be generalized for other domains. Some of these difficulties arise from the differences inherent within the domains, the need to understand and learn negotiators’ diverse preferences concerning issues of the domain, and the different strategies negotiators can undertake. In this paper we present a system that enables alleviation of the difficulties in the design process of general automated negotiators termed Genius, a General Environment for Negotiation with Intelligent multi‐purpose Usage Simulation. With the constant introduction of new domains, e‐commerce and other applications, which require automated negotiations, generic automated negotiators encompass many benefits and advantages over agents that are designed for a specific domain. Based on experiments conducted with automated agents designed by human subjects using Genius we provide both quantitative and qualitative results to illustrate its efficacy. Finally, we also analyze a recent automated bilateral negotiators competition that was based on Genius. Our results show the advantages and underlying benefits of using Genius and how it can facilitate the design of general automated negotiators.

Attacker-Defender Stackelberg security games (SSGs) have emerged as an important research area in multi-agent systems. However, existing SSGs models yield fixed, static, schedules which fail in dynamic domains where defenders face execution uncertainty, i.e., in domains where defenders may face unanticipated disruptions of their schedules. A concrete example is an application involving checking fares on trains, where a defender's schedule is frequently interrupted by fare evaders, making static schedules useless. To address this shortcoming, this paper provides four main contributions. First, we present a novel general Bayesian Stackelberg game model for security resource allocation in dynamic uncertain domains. In this new model, execution uncertainty is handled by using a Markov decision process (MDP) for generating defender policies. Second, we study the problem of computing a Stackelberg equilibrium for this game and exploit problem structure to reduce it to a polynomial-sized optimization problem. Shifting to evaluation, our third contribution shows, in simulation, that our MDP-based policies overcome the failures of previous SSG algorithms. In so doing, we can now build a complete system, that enables handling of schedule interruptions and, consequently, to conduct some of the first controlled experiments on SSGs in the field. Hence, as our final contribution, we present results from a real-world experiment on Metro trains in Los Angeles validating our MDP-based model, and most importantly, concretely measuring the benefits of SSGs for security resource allocation.

The problem of insider threat is receiving increasing attention both within the computer science community as well as government and industry. This paper starts by presenting a broad, multidisciplinary survey of insider threat capturing contributions from computer scientists, psychologists, criminologists, and security practitioners. Subsequently, we present the behavioral analysis of insider threat (BAIT) framework, in which we conduct a detailed experiment involving 795 subjects on Amazon Mechanical Turk (AMT) in order to gauge the behaviors that real human subjects follow when attempting to exfiltrate data from within an organization. In the real world, the number of actual insiders found is very small, so supervised machine-learning methods encounter a challenge. Unlike past works, we develop bootstrapping algorithms that learn from highly imbalanced data, mostly unlabeled, and almost no history of user behavior from an insider threat perspective. We develop and evaluate seven algorithms using BAIT and show that they can produce a realistic (and acceptable) balance of precision and recall.

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.

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.

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 general-purpose 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.

Despite committees and elections being widespread in thereal-world, the design of agents for operating in humancomputer committees has received far less attention than thetheoretical analysis of voting strategies. We address this gapby providing an agent design that outperforms other voters ingroups comprising both people and computer agents. In oursetting 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 studyin which hundreds of people participated in repeated votingrounds with other people as well as computer agents that differed in how they employ strategic reasoning in their votingbehavior. Our results show that over time, people learn todeviate from truthful voting strategies, and use heuristics toguide their play, such as repeating their vote from the previous round. We show that a computer agent using a bestresponse voting strategy was able to outperform people in thegame. Our study has implication for agent designers, highlighting the types of strategies that enable agents to succeedin committees comprising both human and computer participants. This is the first work to study the role of computeragents in voting settings involving both human and agent participants.

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.

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.

An important area of social networks research is identifying missing information which is not explicitly represented in the network, or is not visible to all. Recently, the Missing Node Identification problem was introduced where missing members in the social network structure must be identified. However, previous works did not consider the possibility that information about specific users (nodes) within the network could be useful in solving this problem. In this paper, we present two algorithms: SAMI--A and SAMI--N. Both of these algorithms use the known nodes' specific information, such as demographic information and the nodes' historical behavior in the network. We found that both SAMI--A and SAMI--N perform significantly better than other missing node algorithms. However, as each of these algorithms and the parameters within these algorithms often perform better in specific problem instances, a mechanism is needed to select the best algorithm and the best variation within that algorithm. Towards this challenge, we also present OASCA, a novel online selection algorithm. We present results that detail the success of the algorithms presented within this paper.

Traditional recommender systems minimize prediction error with respect to users' choices. Recent studies have shown that recommender systems have a positive effect on the provider's revenue.

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 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 and satisfaction.

In recent years, social networks have surged in popularity. One key aspect of social network research is identifying important missing information that is not explicitly represented in the network, or is not visible to all. To date, this line of research typically focused on finding the connections that are missing between nodes, a challenge typically termed as the link prediction problem . This article introduces the missing node identification problem, where missing members in the social network structure must be identified. In this problem, indications of missing nodes are assumed to exist. Given these indications and a partial network, we must assess which indications originate from the same missing node and determine the full network structure. Toward solving this problem, we present the missing node identification by spectral clustering algorithm (MISC), an approach based on a spectral clustering algorithm, combined with nodes’ pairwise affinity measures that were adopted from link prediction research. We evaluate the performance of our approach in different problem settings and scenarios, using real-life data from Facebook. The results show that our approach has beneficial results and can be effective in solving the missing node identification problem. In addition, this article also presents R-MISC, which uses a sparse matrix representation, efficient algorithms for calculating the nodes’ pairwise affinity, and a proprietary dimension reduction technique to enable scaling the MISC algorithm to large networks of more than 100,000 nodes. Last, we consider problem settings where some of the indications are unknown. Two algorithms are suggested for this problem: speculative MISC, based on MISC, and missing link completion, based on classical link prediction literature. We show that speculative MISC outperforms missing link completion.

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.

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 epsilon-greedy 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.

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.

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.

Though centrality of vertices in social networks has been extensively studied, all past efforts assume that centrality of a vertex solely depends on the structural properties of graphs. However, with the emergence of online "semantic" social networks where vertices have properties (e.g. gender, age, and other demographic data) and edges are labeled with relationships (e.g. friend, follows) and weights (measuring the strength of a relationship), it is essential that we take semantics into account when measuring centrality. Moreover, the centrality of a vertex should be tied to a diffusive property in the network - a Twitter vertex may have high centrality w.r.t. jazz, but low centrality w.r.t. Republican politics. In this paper, we propose a new notion of diffusion centrality (DC) in which semantic aspects of the graph, as well as a diffusion model of how a diffusive property p is spreading, are used to characterize the centrality of vertices. We present a hyper graph based algorithm to compute DC and report on a prototype implementation and experiments showing how we can compute DCs (using real YouTube data) on social networks in a reasonable amount of time. We compare DC with classical centrality measures like degree, closeness, betweenness, eigenvector and stress centrality and show that in all cases, DC produces higher quality results. DC is also often faster to compute than both betweenness, closeness and stress centrality, but slower than degree and eigenvector centrality.

Adaptive Cruise Control (ACC) is a technology that allows a vehicle to automatically adjust its speed to maintain a preset distance from the vehicle in front of it based on the driver’s preferences. Individual drivers have different driving styles and preferences. Current systems do not distinguish among the users. We introduce a method to combine machine learning algorithms with demographic information and expert advice into existing automated assistive systems. This method can save on the interactions between drivers and automated systems by adjusting parameters relevant to the operation of these systems based on their specific drivers and context of drive. We also learn when users tend to engage and disengage the automated system. This method sheds light on the kinds of dynamics that users develop while interacting with automation and can teach us how to improve these systems for the benefit of their users. While accepted packages such as Weka were successful in learning drivers’ behavior, we found that improved learning models could be developed by adding information on drivers’ demographics and a previously developed model about different driver types. We present the general methodology of our learning procedure and suggest applications of our approach to other domains as well.

This work provides a game theoretic framework through which one can study the different trust and mitigation strategies a decision maker can employ when soliciting advice or input from a potentially self-interested third-party. The framework supports a single decision maker's interacting with an arbitrary number of either honest or malicious (and malicious in varying ways) advisors. We include some preliminary results on the analysis of this framework in some constrained instances and propose several avenues of future work.

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.

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.

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.

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 character. 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.

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.

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multi-agent 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.

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 compared 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 were significant 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.

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.

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.

In this paper we consider the problem of allocating personal TV advertisements when the viewers' viewing capacities are uncertain. We focus on the Mobile TV medium as a personal platform taking into account special constraints that are motivated by the TV medium. Since the problem is NP-Hard, we present a sequential solution procedure and propose several heuristic algorithms for solving it. Through computational experiments on different scenarios of uncertainty, the performances of these heuristics were compared to the performance in the deterministic case where the actual viewing capacities are known in advance. The performance of these heuristics was close to that of the deterministic even for scenarios where uncertainty was very high while the CombinedRatingRobust algorithm seems to be the best for most scenarios. In general, the heuristic algorithms that consider uncertainty in advance seem to be preferable over those that only adapt to it after it has been discovered. Though this paper is oriented for Mobile TV, the proposed algorithms are suitable for other personal push-advertisement methods such as SMS (Short Message Service) and MMS (Multimedia Messaging Service).

We present an approach for learning models that obtain accurate classification of large scale data objects, collected in spatiotemporal domains. The model generation is structured in three phases: pixel selection (spatial dimension reduction), spatiotemporal features extraction and feature selection. Novel techniques for the first two phases are presented, with two alternatives for the middle phase. Model generation based on the combinations of techniques from each phase is explored. The introduced methodology is applied on datasets from the Voltage-Sensitive Dye Imaging (VSDI) domain, where the generated classification models successfully decode neuronal population responses in the visual cortex of behaving animals. VSDI currently is the best technique enabling simultaneous high spatial (10,000 points) and temporal (10 ms or less) resolution imaging from neuronal population in the cortex. We demonstrate that not only our approach is scalable enough to handle computationally challenging data, but it also contributes to the neuroimaging field of study with its decoding abilities.

Personal advertisements are the next-generation in the world of advertisement. In this article we consider the personal advertisement allocation problem with constraints that are motivated by the TV and Mobile advertisement worlds. This problem is a version of the Generalized Multi-Assignment Problem, defined as an extension of GAP with assignment restrictions and all-or-nothing constraints. We present an Integer Programming (IP) model of the problem, prove that it is an NP-hard problem, and propose heuristic algorithms to solve it. Through computational experiments, we compare the performance of these heuristics to solutions obtained with IP solvers. We show that the Backtrack Heuristic outperforms the others and on average it attains 98% of the possible revenue. Though this paper is Mobile TV oriented, the results suit any other personal advertisement "push" method in the mobile market such as SMS (Short Message Service) and MMS (Multimedia Messaging Service).

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.

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.

In this paper we show how taking advantage of autonomous agents' capability to maintain parallel interactions with others, and incorporating it into the cooperative economic search model results in a new search strategy which outperforms current strategies in use. As a framework for our analysis we use the electronic marketplace, where buyer agents have the incentive to search cooperatively. The new search technique is quite intuitive, however its analysis and the process of extracting the optimal search strategy are associated with several significant complexities. These difficulties are derived mainly from the unbounded search space and simultaneous dual affects of decisions taken along the search. We provide a comprehensive analysis of the model, highlighting, demonstrating and proving important characteristics of the optimal search strategy. Consequently, we manage to come up with an efficient modular algorithm for extracting the optimal cooperative search strategy for any given environment. A computational based comparative illustration of the system performance using the new search technique versus the traditional methods is given, emphasizing the main differences in the optimal strategy's structure and the advantage of using the proposed model.

This article considers a canonical auction protocol that forms the basis of nearly all current online auctions. Such discrete bid auctions require that the bidders submit bids at predetermined discrete bid levels, and thus, there exists a minimal increment by which the bid price may be raised. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions. As a result, there is little practical guidance as to how an auctioneer, seeking to maximize its revenue, should determine the number and value of these discrete bid levels, and it is this omission that is addressed here. To this end, a model of an ascending price English auction with discrete bid levels is considered. An expression for the expected revenue of this auction is derived and used to determine numerical and analytical solutions for the optimal bid levels in the case of uniform and exponential bidder's valuation distributions. Finally, in order to develop an intuitive understanding of how these optimal bid levels are distributed, the limiting case where the number of discrete bid levels is large is considered, and an analytical expression for their distribution is derived.

This paper describes a novel programmatic approach to efficiently distribute resources in a dynamic cellular network, using local negotiations. Our proposed mechanism is reactive and facilitates parallel self-adaptation efforts, leading to dynamics that improve overall network performance. The local nature of the negotiations being performed as part of the adaptation process enables frequent changes in the network's parameters with a negligible coordination overhead. The results of our experiments suggest rapid adjustment to changes and overall improvement over time in the number of users served by the network. We evaluate our algorithm based on the service level index, measured by the number of covered handsets. Nevertheless, the proposed algorithm supports any set of parameters and any combination of performance measures supplied by service providers.

To date, there has been no work on temporal probabilistic agent reasoning on top of heterogeneous legacy databases and software modules. We will define the concept of aheterogeneous temporal probabilistic(HTP) agent. Such agents can be built on top of existing databases, data structures, and software code bases without explicitly accessing the internal code of those systems and can take actions compatible with a policy or operating principles specified by an agent developer. We will develop a formal semantics for such agents through the notion of a feasible temporal probabilistic status interpretation (FTPSI for short). Intuitively, an FTPSI specifies what all an HTP agent is permitted/forbidden/obliged to do at various timest. As changes occur in the environment, the HTP agent must compute a new FTPSI. HTP agents continuously compute FTPSIs in order to determine what they should do and, hence, the problem of computing FTPSIs is very important. We give a sound and complete algorithm to compute FTPSIs for a very large class of HTP agents calledstrictHTP agents. In a given state, many FTPSIs may exist. These represent alternative courses of action that the HTP agent can take. We provide a notion of anoptimalFTPSI that selects an FTPSI optimizing an objective function and give a sound and complete algorithm to compute an optimal FTPSI.

In this paper we consider a common form of the English auction that is widely used in online Internet auctions. This discrete bid auction requires that the bidders may only submit bids which meet some predetermined discrete bid levels and, thus, there exists a minimal increment with which a bidder may raise the current price. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions, and, as a result, there is little practical guidance as to how an auctioneer, who is seeking to maximise his revenue, should determine the number and value of these discrete bid levels. Consequently, in current online auctions, a fixed bid increment is commonly implemented, despite this having been shown to be optimal in only limited cases.Given this background, in this paper, our aim is to provide the optimal auction design for an English auction with discrete bid levels. To this end, we derive an expression that relates the expected revenue of the auction, to the actual discrete bid levels im-plemented, the number of bidders participating, and the distribution from which the bidders draw their private independent valuations. We use this expression to derive numerical and analytical solutions for the optimal bid levels in the general case. To compare these results with previous work, we apply these solutions to an example, where bidders' valuations are drawn from a uniform distribution. In this case, we prove that when there are more than two bidders, a decreasing bid increment is optimal and we show that the optimal reserve price of the auction increases as the number of bidders increases. Finally, we compare the properties of an auction in which optimal bid levels are used, to the standard auction approach which implements a fixed bid increment. In so doing, we show that the optimal bid levels result in improvements in the revenue, duration and allocative efficiency of the auction.

We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.

In this article, we propose a strategic negotiation model that enables self‐motivated rational agents to share resources. The strategic negotiation model takes the passage of time during the negotiation process itself into account. The model considers bilateral negotiations in situations characterized by complete information, in which one agent loses over time whereas the other gains over time. Using this negotiation mechanism, autonomous agents apply simple and stable negotiation strategies that result in efficient agreements without delay, even when there are dynamic changes in the environment. Simulation results show that our mechanism performs as well as a centralized scheduler and also has the property of balancing the resources' usage.

Cooperating and sharing resources by creating coalitions of agents are important ways for autonomous agents to execute tasks and to maximize payoff. Such coalitions will form only if each member of a coalition gains more by joining the coalition than it could gain otherwise. There are several ways of creating such coalitions and dividing the joint payoff among the members. In this paper we present algorithms for coalition formation and payoff distribution in nonsuperadditive environments. We focus on a low‐complexity kernel‐oriented coalition formation algorithm. The properties of this algorithm were examined via simulations. These have shown that the model increases the benefits of the agents within a reasonable time period, and more coalition formations provide more benefits to the agents.

In this paper, we address the tradeoff between exploration and exploitation for agents which need to learn more about the structure of their environment in order to perform more effectively. For example, a software agent operating on the World Wide Web may need to learn which sites on the net are most useful, and the most efficient routes to those sites. We compare exploration strategies for a repeated task, where the agent is given some particular task to perform some number of times. Tasks are modeled as navigation on a partially known (deterministic) graph. This paper describes a new utility-based exploration algorithm for repeated tasks which interleaves exploration with task performance. The method takes into account both the costs and the potential benefits (for future task repetitions) of different exploratory actions. Exploration is performed in a greedy fashion, with the locally optimal exploratory action performed during repetition of each task. We experimentally evaluated our utility-based interleaved exploration algorithm against a heuristic search algorithm for exploration before task performance (a priori exploration) as well as a randomized interleaved exploration algorithm. We found that for a single repeated task, utility-based interleaved exploration consistently outperforms the alternatives, unless the number of task repetitions is very high. In addition, we extended the algorithms for the case of multiple repeated tasks, where the agent has a different, randomly-chosen task (from a known subset of possible tasks) to perform each time. Here too, we found that utility-based interleaved exploration is clear in most cases.

In this paper, a model which combines relational databases with self-processing networks is proposed in order to improve the performance of very large databases. The proposed model uses an approach which is radically different from all other distributed database models, where each computer processes a portion of the database. In the self-processing network model, the network structure which consists of nodes and connections, captures the data and the relationships by assigning them unique, connected control, and data nodes. The network activity is the mechanism that performs the relational algebra operations. No data transmission is needed, and since data nodes are common to all the relations, integrity and elimination of data redundancy are achieved. An extension of the model, by interconnecting the data nodes via weighted links, provides us with properties that are embedded in neural networks, such as fuzziness and learning.

In planning situations involving tight deadlines, a commonsense reasoner may spend a substantial amount of the available time in reasoning towards and about the formulation of the (partial) plan. This reasoning involves, but is not limited to (partial) plan formulation, asking decisions about available and conceivable alternatives, plan sequecing, and also plan failure and revision. However, the time taken in reasoning about a plan brings the deadline closer. The reasoner should therefore take account of the passage of time during that same reasoning, and this accounting must continously affect every decision under time-pressure. Step-logics were introduced as a mechanism for reasoning situated in time. We employ an extension of them here, called ‘active logics’, to create a logic-based planner that lets a time-situated reasoner keep track of a approaching deadline as he/she makes (and enacts) his/her plan, thereby treatilng all facets of planning (including plan-formation and its simultaneous of subsequent execution) as deadline-coupled. While an agent under severe time-pressure may spend a substantial amount of the available time in reasoning towards and about a plan of action, in a realistic setting the same agent must also measure up to two other crucial resource limitations as well, namely space and computation bounds. We address these concerns and offer some solution by introducing a limited short-term memory combined with a primitive relevance mechanism, and a limited-capacity inference engine. We propose heuristics to maximize an agent's chances of meeting a dedline within these additional realistic constraints. We give examples from commonsense planning, including ones we have solved and implemented in Prolog.

Negotiations are very important in a multiagenl environment, particularly, in an environment where there are conflicts between the agents, and cooperation would be beneficial. We have developed a general structure for a Negotiating Automated Agent that consists of five modules: a Prime Minister, a Ministry of Defense, a Foreign Office, a Headquarters and Intelligence. These modules are implemented using a dynamic set of local agents belonging to the different modules. We used this structure to develop a Diplomacy player. Diplomat. Playing Diplomacy involves a certain amount of technical skills as in other board games, but the capacity to negotiate, explain, convince, promise, keep promises or break them, is an essential ingredient in good play. Diplomat was evaluated and consistently played better than human players.

Formal real-time imagination is a term that may curiously describe the activities of a commonsense agent in a real-time setting in general, and in a tight deadline situation in particular. We briefly describe an ‘active-logic’ mechanism that fits this description. Temporal projection is an essential component of realtime planning. We draw a parallel between imagination as we understand it in human context and the capacity of the automated agent to formulate mental images of possible scenarios and plans of action in the course of its reasoning. We outline a treatment of temporal issues of significance to a time-situated reasoning mechanism in a dynamic setting with deadlines. The Yale shooting problem is a benchmark problem in temporal reasoning. We demonstrate how the active-logic planning mechanism successfully handles some interesting real-time variants of the Yale shooting problem. The solutions to each of these illustrate the agent’s ability to form contexts within which to reason, to project in each context thus formed by applying default inferences, and to revise and extend its conclusions within each context by applying time-sensitive inference rules, and most importantly, to account for all the time spent in the process.

Any agent interacting with the real world must be able to reason about uncertainty in the world, about the actions that may occur in the world (either due to the agent or those initiated by other agents), about the (probabilistic) beliefs of other agents, and how these (probabilistic) beliefs are changing over time. In this article, we develop a family of logics that a reasoning agent may use to perform successively more sophisticated types of reasoning in such environments. We also characterize different types of agents. Furthermore, we provide a logic that enables a systems designer (who may have populated an environment with a collection of such autonomous agents) to reason about the system of agents as a whole. © 1995 John Wiley & Sons, Inc.

We develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called "yes-no" dialogs, and "yes-no-don't know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time-hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don't know dialogs.>

During the past decade, it has become increasingly clear that the future generation of large-scale knowledge bases will consist, not of one single isolated knowledge base, but a multiplicity of specialized knowledge bases that contain knowledge about different domains of expertise. These knowledge bases will work cooperatively, pooling together their varied bodies of knowledge, so as to be able to solve complex problems that no single knowledge base, by itself, would have been able to address successfully. In any such situation, inconsistencies are bound to arise. In this paper, we address the question: "Suppose we have a set of knowledge bases, KB1, …, KBn, each of which uses default logic as the formalism for knowledge representation, and a set of integrity constraints IC. What knowledge base constitutes an acceptable combination of KB1, …, KBn?"

The area of automated negotiation has been of particular interest in AI due to the important role negotiations play in facilitating understanding and the achievement of cooperation among entities with differing interests, whether they be individuals, organizations, governments, or automated agents. A strategic model for negotiation of alternative offers is presented with specific application to international crises. In the model, both players can opt out, and while one loses over time, the other gains (up to a point). Specific issues are: conflicting objectives and utility functions of parties and the impact of time on bargaining behavior in crises. The general model has relevance to the hostage crisis from which it was built, and subsequent applicability in building an automated negotiation agent for experimental and training purposes.>

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process ofcombiningthe knowledge of these different experts is an important and nontrivial problem. We study this problem here when the expert systems are considered to be first‐order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.

As part of our work on agent-oriented programming,1 we are developing an agent description language. We describe an agent's “mental state” in terms of its knowledge, beliefs, desires, commitments, and abilities. Our goal is not to specify human knowledge, beliefs, etc., but rather to devise a more limited, precise language to facilitate programming agents and interagent communication. We believe that borrowing from our intuition about these commonsense terms will simplify the human designer's job. This article describes a preliminary version of our language. We define a temporal language with modal operators representing knowledge, belief, desire, commitment, and ability. This is a propositional language with quantification over time points and agents only.

The area of automated negotiation has been of particular interest in artificial intelligence due to the important role negotiation plays in facilitating understanding and achieving co-operation among entities with differing interests. These entities may be individuals, organizations, governments, or automated agents. This paper presents methods for solving different aspects of automated negotiation: with whom to negotiate, evaluation of suggestions and the way to offer suggestions. These methods were successfully used to develop the system Diplomat, that may be one of the players in a board game, Diplomacy. This game is characterized by intense negotiation, a very large set of possible strategies and the absence of a trusted intermediary. Although Diplomacy players may break their promises, close co-operation is needed for a success.

Combining knowledge present in multiple knowledge base systems into a single knowledge base is discussed. A knowledge based system can be considered an extension of a deductive database in that it permits function symbols as part of the theory. Alternative knowledge bases that deal with the same subject matter are considered. The authors define the concept of combining knowledge present in a set of knowledge bases and present algorithms to maximally combine them so that the combination is consistent with respect to the integrity constraints associated with the knowledge bases. For this, the authors define the concept of maximality and prove that the algorithms presented combine the knowledge bases to generate a maximal theory. The authors also discuss the relationships between combining multiple knowledge bases and the view update problem.>

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.