Bar-Ilan University


Comparing Plan Recognition Algorithms through Standard Libraries

AAAI Conferences

Plan recognition is one of the fundamental problems of AI, applicable to many domains, from user interfaces to cyber security. We focus on a class of algorithms that use plan libraries as input to the recognition process. Despite the prevalence of these approaches, they lack a standard representation, and have not been compared to each other on common testbed. This paper directly addresses this gap by providing a standard plan library representation and evaluation criteria to consider. Our representation is comprehensive enough to describe a variety of known plan recognition problems, yet it can be easily applied to existing algorithms, which can be evaluated using our defined criteria. We demonstrate this technique on two known algorithms, SBR and PHATT. We provide meaningful insights both about the differences and abilities of the algorithms. We show that SBR is superior to PHATT both in terms of computation time and space, but at the expense of functionality and compact representation. We also show that depth is the single feature of a plan library that increases the complexity of the recognition, regardless of the algorithm used.


MUDA: A Truthful Multi-Unit Double-Auction Mechanism

AAAI Conferences

In a seminal paper, McAfee (1992) presented a truthful mechanism for double auctions, attaining asymptotically-optimal gain-from-trade without any prior information on the valuations of the traders. McAfee's mechanism handles single-parametric agents, allowing each seller to sell a single unit and each buyer to buy a single unit. This paper presents a double-auction mechanism that handles multi-parametric agents and allows multiple units per trader, as long as the valuation functions of all traders have decreasing marginal returns. The mechanism is prior-free, ex-post individually-rational, dominant-strategy truthful and strongly-budget-balanced. Its gain-from-trade approaches the optimum when the market size is sufficiently large.


Approximating Bribery in Scoring Rules

AAAI Conferences

The classic bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win.We find an approximate solution for this problem for a broad family of scoring rules (which includes Borda and t-approval), in the following sense: if there is a strategy which requires bribing k voters, we efficiently find a strategy which requires bribing at most k + Õ(√ k ) voters. Our algorithm is based on a randomized reduction from bribery to coalitional manipulation (UCM). To solve the UCM problem, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding the optimal solution in the truncated search space yields a new algorithm for UCM, which is of independent interest.


Augmenting Decisions of Taxi Drivers through Reinforcement Learning for Improving Revenues

AAAI Conferences

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


Strategic Signaling and Free Information Disclosure in Auctions

AAAI Conferences

With the increasing interest in the role information providers play in multi-agent systems, much effort has been dedicated to analyzing strategic information disclosure and signaling by such agents. This paper analyzes the problem in the context of auctions (specifically for second-price auctions). It provides an equilibrium analysis to the case where the information provider can use signaling according to some pre-committed scheme before introducing its regular (costly) information selling offering. The signal provided, publicly discloses (for free) some of the information held by the information provider. Providing the signaling is thus somehow counter intuitive as the information provider ultimately attempts to maximize her gain from selling the information she holds. Still, we show that such signaling capability can be highly beneficial for the information provider and even improve social welfare. Furthermore, the examples provided demonstrate various possible other beneficial behaviors available to the different players as well as to a market designer, such as paying the information provider to leave the system or commit to a specific signaling scheme. Finally, the paper provides an extension of the underlying model, related to the use of mixed signaling strategies.


Nurturing Group-Beneficial Information-Gathering Behaviors Through Above-Threshold Criteria Setting

AAAI Conferences

This paper studies a criteria-based mechanism for nurturing and enhancing agents' group-benefiting individual efforts whenever the agents are self-interested. The idea is that only those agents that meet the criteria get to benefit from the group effort, giving an incentive to contribute even when it is otherwise individually irrational. Specifically, the paper provides a comprehensive equilibrium analysis of a threshold-based criteria mechanism for the common cooperative information gathering application, where the criteria is set such that only those whose contribution to the group is above some pre-specified threshold can benefit from the contributions of others. The analysis results in a closed form solution for the strategies to be used in equilibrium and facilitates the numerical investigation of different model properties as well as a comparison to the dual mechanism according to only an agent whose contribution is below the specified threshold gets to benefit from the contributions of others. One important contribution enabled through the analysis provided is in showing that, counter-intuitively, for some settings the use of the above-threshold criteria is outperformed by the use of the below-threshold criteria as far as collective and individual performance is concerned.


The Benefit in Free Information Disclosure When Selling Information to People

AAAI Conferences

This paper studies the benefit for information providers in free public information disclosure in settings where the prospective information buyers are people. The underlying model, which applies to numerous real-life situations, considers a standard decision making setting where the decision maker is uncertain about the outcomes of her decision. The information provider can fully disambiguate this uncertainty and wish to maximize her profit from selling such information. We use a series of AMT-based experiments with people to test the benefit for the information provider from reducing some of the uncertainty associated with the decision maker's problem, for free. Free information disclosure of this kind can be proved to be ineffective when the buyer is a fully-rational agent. Yet, when it comes to people we manage to demonstrate that a substantial improvement in the information provider's profit can be achieved with such an approach. The analysis of the results reveals that the primary reason for this phenomena is people's failure to consider the strategic nature of the interaction with the information provider. Peoples' inability to properly calculate the value of information is found to be secondary in its influence.


Advice Provision for Energy Saving in Automobile Climate-Control System

AI Magazine

Reducing energy consumption of climate control systems is important in order to reduce human environmental footprint. 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.


Advice Provision for Energy Saving in Automobile Climate-Control System

AI Magazine

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


Automated Agents for Advice Provision

AAAI Conferences

In this thesis, we focus on automated advising agents. The advice given is a form of relating recommendations or guidance from an automated agent to its human user. Providing the right advice at the right time is extremely complex, and requires a good adaptation to human desires and changing environments. We propose a novel methodology for designing automated advising agents and evaluate it in three real world environments. Our intelligent advising agents were evaluated through extensive field trials, with hundreds of human subjects. A significant increase in human performance as well as a high level of user satisfaction was recorded when they were equipped with our agents.