Abstract: Plan recognition algorithms need to maintain all candidate hypotheses which are consistent with the observations, even though there is only a single hypothesis that is the correct one. Unfortunately, the number of possible hypotheses can be exponentially large in practice. This paper addresses the problem of how to disambiguate between many possible hypotheses that are all consistent with the actions of the observed agent. One way to reduce the number of hypotheses is to consult a domain expert or the acting agent directly about its intentions. This process can be performed sequentially, updating the set of hypotheses during the recognition process. The paper specifically addresses the problem of how to minimize the number of queries made that are required to find the correct hypothesis. It adapts a number of probing techniques for choosing which plan to query, such as maximal information gain and maximum likelihood. These approaches were evaluated on a domain from the literature using a well known plan recognition algorithm. The results showed that the information gain approach was able to find the correct plan using significantly fewer queries than the maximum likelihood approach as well as a baseline approach choosing random plans. Our technique can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.

Citation: Reuth Mirsky, Ya’akov Gal, Roni Stern, Meir Kalech. Sequential Plan Recognition. International Joint Conference on Artificial Intelligence (IJCAI), New York, USA, July 2016.

Download: http://bit.ly/2iR3wLf

Abstract: Plan Recognition algorithms require to recognize a complete hierarchy explaining the agent’s actions and goals. While the output of such algorithms is informative to the recognizer, the cost of its calculation is high in run-time, space, and completeness. Moreover, performing plan recognition on-line requires the observing agent to reason about future actions that have not yet been seen and maintain a set of hypotheses to support all possible options. This paper presents a new and efficient algorithm for online plan recognition called SLIM (Semi-Lazy Inference Mechanism). It combines both a bottom-up and top-down parsing processes, which allow it to commit only to the minimum necessary actions in real-time, but still provide complete hypotheses post factum. We show both theoretically and empirically that although the computational cost of this process is still exponential, there is a significant improvement in run-time when compared to a state of the art of plan recognition algorithm.

Citation: Reuth Mirsky, Ya’akov Gal. SLIM: Semi-Lazy Inference Mechanism for Plan Recognition. International Joint Conference on Artificial Intelligence (IJCAI), New York, USA, July 2016.

Download: http://bit.ly/2jh7HTZ

Abstract: Volunteer-based crowdsourcing depend critically on maintaining the engagement of participants. We explore a methodology for extending engagement in citizen science by combining machine learning with intervention design. We first present a platform for using real-time predictions about forthcoming disengagement to guide interventions. Then we discuss a set of experiments with delivering different messages to users based on the proximity to the predicted time of disengagement. The messages address motivational factors that were found in prior studies to influence users’ engagements. We evaluate this approach on Galaxy Zoo, one of the largest citizen science application on the web, where we traced the behavior and contributions of thousands of users who received intervention messages over a period of a few months. We found sensitivity of the amount of user contributions to both the timing and nature of the message. Specifically, we found that a message emphasizing the helpfulness of individual users significantly increased users’ contributions when delivered according to predicted times of disengagement, but not when delivered at random times. The influence of the message on users’ contributions was more pronounced as additional user data was collected and made available to the classifier.

Citation: Avi Segal, Ya’akov Gal, Ece Kamar, Eric Horvitz, Alex Bower, Grant Miller. Intervention Strategies for Increasing Engagement in Volunteer-Based Crowdsourcing. International Joint Conference on Artificial Intelligence (IJCAI), New York, USA, July 2016.

Download: http://bit.ly/2jh9fgG

Abstract: What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.

Citation: Ya’akov Gal, Moshe Mash, Ariel D. Procaccia, Yair Zick. Which Is the Fairest (Rent Division) of Them All? ACM Conference on Economics and Computation (EC), July, Maasticht, The Netherlands. Best Paper Award.

Download: http://bit.ly/2iQYwGz

Abstract: The recent media focus on Smart City services, particularly ride sharing, that provide ordinary users with the ability to advertise their resources has highlighted society’s need for transparent and accountable systems. Current systems offer little transparency behind their processes that claim to provide accountability to and for their users. To address such a concern, some applications provide a static, textual description of the automated algorithms used, with a view to promote transparency. However, this is not sufficient to inform users exactly how information is derived. These descriptions can be enhanced by explaining the actual execution of the algorithm, the data it operated on, and the parameters it was configured with. Such descriptions about a system’s execution and its information flow can be expressed using PROV, a standardised provenance data model. However, given its generic and domain-agnostic nature, PROV only provides limited information about the relationship between provenance elements. Combined with semantic information, a PROV instance becomes a rich resource, which can be exploited to provide users with understandable accounts of automated processes, thereby promoting transparency and accountability. Thus, this paper contributes, a vocabulary for Smart City resource sharing applications, an architecture for accountable systems, and a set of use cases that demonstrate and quantify how the semantics enrich an account in a ride share scenario.

Citation: Heather Packer, Dimitris Diochnos, Michael Rovatsos, Ya’akov Gal, Luc Moreau, Semantics and Provenance for Accountable Smart City Applications, The Role of Semantics in Smart Cities, Semantic Web Journal special issue, 2014.

Download: http://bit.ly/2jcTK9B

Abstract: Corruption frequently occurs in many aspects of multi-party interaction between private agencies and government employees. Past works studying corruption in a lab context have explicitly included covert or illegal activities in participants’ strategy space or have relied on surveys like the Corruption Perception Index (CPI). This paper studies corruption in ecologically realistic settings in which corruption is not suggested to the players a priori but evolves during repeated interaction. We ran studies involving hundreds of subjects in three countries: China, Israel, and the United States. Subjects interacted using a four-player board game in which three bidders compete to win contracts by submitting bids in repeated auctions, and a single auctioneer determines the winner of each auction. The winning bid was paid to an external “government” entity, and was not distributed among the players. The game logs were analyzed posthoc for cases in which the auctioneer was bribed to choose a bidder who did not submit the highest bid. We found that although China exhibited the highest corruption level of the three countries, there were surprisingly more cases of corruption in the U.S. than in Israel, despite the higher PCI in Israel as compared to the U.S. We also found that bribes in the U.S. were at times excessively high, resulting in bribing players not being able to complete their winning contracts. We were able to predict the occurrence of corruption in the game using machine learning. The significance of this work is in providing a novel paradigm for investigating covert activities in the lab without priming subjects, and it represents a first step in the design of intelligent agents for detecting and reducing corruption activities in such settings.

Citation: Ya’akov Gal, Avi Rosenfeld, Sarit Kraus, Michele Gelfand, Bo An and Jun Lin. A new paradigm for the study of corruption across cultures. International Conference on Social Computing, Behavioral-Cultural Modeling, & Prediction (SBP), Maryland, MD, April 2014.

Download: http://bit.ly/2ijGQCm

A preliminary of this work was presented at HAIDM 2014. The 2014 workshop on Human-Agent Interaction Design and Models was co-organised by SmartSociety.

This work was the winner of the “Best Student Paper Award” at the Seventh International Conference on Educational Data Mining (EDM 2014).

Abstract: The growing prevalence of e-learning systems and on-line courses has made educational material widely accessible to students of varying abilities, backgrounds and styles. There is thus a growing need to accommodate for individual differences in such e-learning systems. This paper presents a new algorithm for personalizing educational content to students that combines collaborative filtering algorithms with social choice theory. The algorithm constructs a “difficulty” ranking over questions for a target student by aggregating the ranking of similar students, as measured by different aspects of their performance on common past questions, such as grades, number of retries, and time spent solving questions. It infers a difficulty ranking directly over the questions for a target student, rather than ordering them according to predicted performance, which is prone to error. The algorithm was tested on two large real world data sets containing tens of thousands of students and a million records. Its performance was compared to a variety of personalization methods as well as a non-personalized method that relied on a domain expert. It was able to significantly outperform all of these approaches according to standard information retrieval metrics. Our approach can potentially be used to support teachers in tailoring problem sets and exams to individual students and students in informing them about areas they may need to strengthen..

Citation: EduRank: A Collaborative Filtering Approach to Personalization in E-learning Avi Segal, Ziv Katzir, Ya’akov Gal, Guy Shani and Bracha Shapira. EduRank: A Collaborative Filtering Approach to Personalization in E-learning. Seventh International Conference on Educational Data Mining (EDM 2014), London, England, July 2014.

Download: http://bit.ly/1WzaWlY

Abstract. A popular use of crowdsourcing is to collect and aggregate individual worker responses to problems to reach a correct answer. This paper studies the relationship between the computation complexity class of problems, and the ability of a group to agree on a correct solution. We hypothesized that for NP-Complete (NPC) problems, groups would be able to reach a majority-based correct solution once it was suggested by a group member and presented to the other members, due to the “easy to verify” (i.e., verification in polynomial time) characteristic of this complexity class. In contrast, when posed with PSPACE-Complete (PSC) “hard to verify” problems (i.e., verification in exponential time), groups will not necessarily be able to choose a correct solution even if such a solution has been presented. Consequently, increasing the size of the group is expected to facilitate the ability of the group to converge on a correct solution when solving NPC problems, but not when solving PSC problems. To test this hypothesis we conducted preliminary experiments in which we evaluated people’s ability to solve an analytical problem and their ability to recognize a correct solution. In our experiments, participants were significantly more likely to recognize correct and incorrect solutions for NPC problems than for PSC problems, even for problems of similar difficulties (as measured by the percentage of participants who solved the problem). This is a first step towards formalizing a relationship between the computationally complexity of a problem and the crowd’s ability to converge to a correct solution to the problem.

Citation: Ofra Amir, Yuval Shahar, Ya’akov Gal and Litan Ilany. On the Verification Complexity of Group Decision-Making Tasks. Conference on Human Computation and Crowdsourcing, Palm Springs, CA, November 2013.

Download: http://bit.ly/1MBhsqn