Kobi Gal

AAMAS Conference 2025 Conference Paper

Beyond the Echo Chamber: Modelling Open-Mindedness in Citizens' Assemblies

• Jake Barrett
• Kobi Gal
• Loizos Michael
• Dan Vilenchik

A Citizens’ Assembly (CA) is a democratic innovation tool where a randomly selected group of citizens deliberate a topic over multiple rounds to generate, and then vote upon, policy recommendations. Despite growing popularity, little work exists on understanding how CA inputs, such as the expert selection process and the mixing method used for discussion groups, affect results, and therefore on how to systematically set such parameters to optimize the process. In this work, we model CA deliberation and opinion change as a Multi-Agent Systems problem. We introduce and formalise a set of criteria for evaluating successful CAs using insight from previous CA trials and theoretical results. Although real-world trials meet these criteria, we show that finding a model that does so is nontrivial; through simulations and theoretical arguments, we show that established opinion change models fail at least one of these criteria. This is an extended abstract of a JAAMAS article [2].

ECAI Conference 2025 Conference Paper

Detecting Struggling Student Programmers Using Proficiency Taxonomies

• Noga Schwartz
• Roy Fairstein
• Avi Segal
• Kobi Gal

Early detection of struggling student programmers is crucial for providing them with personalized support. While multiple AI-based approaches have been proposed for this problem, they do not explicitly reason about students’ programming skills in the model. This study addresses this gap by developing in collaboration with educators a taxonomy of proficiencies that categorizes how students solve coding tasks and is embedded in the detection model. Our model, termed the Proficiency Taxonomy Model (PTM), simultaneously learns the student’s coding skills based on their coding history and predicts whether they will struggle on a new task. We extensively evaluated the effectiveness of the PTM model on two separate datasets from introductory Java and Python courses for beginner programmers. Experimental results demonstrate that PTM outperforms state-of-the-art models in predicting struggling students. The paper showcases the potential of combining structured insights from teachers for early identification of those needing assistance in learning to code.

JAAMAS Journal 2024 Journal Article

Beyond the echo chamber: modelling open-mindedness in citizens’ assemblies

• Jake Barrett
• Kobi Gal
• Dan Vilenchik

Abstract A Citizens’ assembly (CA) is a democratic innovation tool where a randomly selected group of citizens deliberate a topic over multiple rounds to generate, and then vote upon, policy recommendations. Despite growing popularity, little work exists on understanding how CA inputs, such as the expert selection process and the mixing method used for discussion groups, affect results. In this work, we model CA deliberation and opinion change as a multi-agent systems problem. We introduce and formalise a set of criteria for evaluating successful CAs using insight from previous CA trials and theoretical results. Although real-world trials meet these criteria, we show that finding a model that does so is non-trivial; through simulations and theoretical arguments, we show that established opinion change models fail at least one of these criteria. We therefore propose an augmented opinion change model with a latent ‘open-mindedness’ variable, which sufficiently captures people’s propensity to change opinion. We show that data from the CA of Scotland indicates a latent variable both exists and resembles the concept of open-mindedness in the literature. We calibrate parameters against real CA data, demonstrating our model’s ecological validity, before running simulations across a range of realistic global parameters, with each simulation satisfying our criteria. Specifically, simulations meet criteria regardless of expert selection, expert ordering, participant extremism, and sub-optimal participant grouping, which has ramifications for optimised algorithmic approaches in the computational CA space.

AAAI Conference 2023 Conference Paper

Now We’re Talking: Better Deliberation Groups through Submodular Optimization

• Jake Barrett
• Kobi Gal
• Paul Gölz
• Rose M. Hong
• Ariel D. Procaccia

Citizens’ assemblies are groups of randomly selected constituents who are tasked with providing recommendations on policy questions. Assembly members form their recommendations through a sequence of discussions in small groups (deliberation), in which group members exchange arguments and experiences. We seek to support this process through optimization, by studying how to assign participants to discussion groups over multiple sessions, in a way that maximizes interaction between participants and satisfies diversity constraints within each group. Since repeated meetings between a given pair of participants have diminishing marginal returns, we capture interaction through a submodular function, which is approximately optimized by a greedy algorithm making calls to an ILP solver. This framework supports different submodular objective functions, and we identify sensible options, but we also show it is not necessary to commit to a particular choice: Our main theoretical result is a (practically efficient) algorithm that simultaneously approximates every possible objective function of the form we are interested in. Experiments with data from real citizens' assemblies demonstrate that our approach substantially outperforms the heuristic algorithm currently used by practitioners.

ECAI Conference 2023 Conference Paper

Online Evaluation of Tail Project Boosting in Citizen Science

• Amit Sultan
• Avi Segal
• Guy Shani
• Darlene Cavalier
• Kobi Gal

In citizen science, regular people provide invaluable information by contributing to scientific projects. Citizen science platforms, such as SciStarter, provide easy access to numerous such projects. Often, users contribute mainly to a relatively small set of popular projects, while it is difficult for many projects to draw the attention of users. Thus, increasing the contribution of users to such low-popularity projects may increase scientific and societal impact. In this paper, we explore the power of a recommender system to draw attention to less popular projects. Standard use of recommendation systems often leads to limited exposure of less popular (tail) projects. We thus propose a re-ranking approach based on “lift boosting, ” which uses the statistical lift measure to enhance the exposure of tail projects. By combining lift and traditional relevance measures, our method re-ranks the recommendation list to emphasize projects that are both relevant to the user while also have a high lift value. We implement our approach on SciStarter, one of the biggest citizen science platforms on the web. We conduct an online experiment involving over 2000 real users. Our results show a positive shift towards less popular projects without compromising overall contribution rates. This work demonstrates the potential of our lift-boosting method for promoting the discovery of tail projects in citizen science platforms, thereby fostering a more diverse range of scientific contributions.

AAAI Conference 2023 Conference Paper

Participatory Budgeting Designs for the Real World

• Roy Fairstein
• Gerdus Benadè
• Kobi Gal

Participatory budgeting engages the public in the process of allocating public money to different types of projects. PB designs differ in how voters are asked to express their preferences over candidate projects and how these preferences are aggregated to determine which projects to fund. This paper studies two fundamental questions in PB design. Which voting format and aggregation method to use, and how to evaluate the outcomes of these design decisions? We conduct an extensive empirical study in which 1 800 participants vote in four participatory budgeting elections in a controlled setting to evaluate the practical effects of the choice of voting format and aggregation rule.We find that k-approval leads to the best user experience. With respect to the aggregation rule, greedy aggregation leads to outcomes that are highly sensitive to the input format used and the fraction of the population that participates. The method of equal shares, in contrast, leads to outcomes that are not sensitive to the type of voting format used, and these outcomes are remarkably stable even when the majority of the population does not participate in the election. These results carry valuable insights for PB practitioners and social choice researchers.

AAAI Conference 2022 Conference Paper

MultiplexNet: Towards Fully Satisfied Logical Constraints in Neural Networks

• Nick Hoernle
• Rafael Michael Karampatsis
• Vaishak Belle
• Kobi Gal

We propose a novel way to incorporate expert knowledge into the training of deep neural networks. Many approaches encode domain constraints directly into the network architecture, requiring non-trivial or domain-specific engineering. In contrast, our approach, called MultiplexNet, represents domain knowledge as a quantifier-free logical formula in disjunctive normal form (DNF) which is easy to encode and to elicit from human experts. It introduces a latent Categorical variable that learns to choose which constraint term optimizes the error function of the network and it compiles the constraints directly into the output of existing learning algorithms. We demonstrate the efficacy of this approach empirically on several classical deep learning tasks, such as density estimation and classification in both supervised and unsupervised settings where prior knowledge about the domains was expressed as logical constraints. Our results show that the MultiplexNet approach learned to approximate unknown distributions well, often requiring fewer data samples than the alternative approaches. In some cases, MultiplexNet finds better solutions than the baselines; or solutions that could not be achieved with the alternative approaches. Our contribution is in encoding domain knowledge in a way that facilitates inference. We specifically focus on quantifier-free logical formulae that are specified over the output domain of a network. We show that this approach is both efficient and general; and critically, our approach guarantees 100% constraint satisfaction in a network’s output.

AAMAS Conference 2022 Conference Paper

Welfare vs. Representation in Participatory Budgeting

• Roy Fairstein
• Dan Vilenchik
• Reshef Meir
• Kobi Gal

Participatory budgeting (PB) is a democratic process for allocating funds to projects based on the votes of members of the community. Different rules have been used to aggregate participants’ votes. A recent paper by Lackner and Skowron [12] studied the tradeoff between notions of social welfare and representation in the multi-winner voting, which is a special case of participatory budgeting with identical project costs. But there is little understanding of this trade-off in the more general PB setting. This paper provides a theoretical and empirical study of the worst-case guarantees of several common rules to better understand the trade-off between social welfare and representation. We show that many of the guarantees from the multi-winner setting do not generalize to the PB setting, and that the introduction of costs leads to substantially worse guarantees, thereby exacerbating the welfare-representation trade-off. We further study how the requirement of proportionality over voting rules effects the guarantees on social welfare and representation. We study the latter point also empirically, both on real and synthetic datasets. We show that variants of the recently suggested voting rule Rule-X (which satisfies proportionality) do very well in practice both with respect to social welfare and representation.

AAAI Conference 2021 Conference Paper

Improving the Performance-Compatibility Tradeoff with Personalized Objective Functions

• Jonathan Martinez
• Kobi Gal
• Ece Kamar
• Levi H. S. Lelis

AI-systems that model and interact with their users can update their models over time to reflect new information and changes in the environment. Although these updates may improve the overall performance of the AI-system, they may actually hurt the performance with respect to individual users. Prior work has studied the tradeoff between improving the system’s performance following an update and the compatibility of the updated system with prior user experience. The more the model is forced to be compatible with a prior version, the higher loss in performance it will incur. This paper challenges this assumption by showing that by personalizing the loss function to specific users, it is possible to increase the prediction performance of the AI-system while sacrificing less compatibility for these users. Our approach updates the sample weights to reflect their contribution to the compatibility of the model for a particular user following the update. We construct a portfolio of different models that vary in how they personalize the loss function for a user. We select the best model to use for a target user based on a validation set. We apply this approach to three supervised learning tasks commonly used in the human-computer decision-making literature. We show that using our approach leads to significant improvements in the performance-compatibility tradeoff over the non-personalized approach of Bansal et al. , achieving up to 300% improvement for certain users. We present several use cases that illustrate the difference between the personalized and non-personalized approach for two of our domains.

AAAI Conference 2021 Conference Paper

Intelligent Recommendations for Citizen Science

• Daniel Ben Zaken
• Kobi Gal
• Guy Shani
• Avi Segal
• Darlene Cavalier

Citizen science refers to scientKobiific research that is carried out by volunteers, often in collaboration with professional scientists. The spread of the internet has allowed volunteers to contribute to citizen science projects in dramatically new ways while creating scientific value and gaining pedagogical and social benefits. Given the sheer size of available projects, finding the right project, which best suits the user preferences and capabilities, has become a major challenge and is essential for keeping volunteers motivated and active contributors. We address this challenge by developing a system for personalizing project recommendations which was fully deployed in the wild. We adapted several recommendation algorithms to the citizen science domain from the literature based on memory-based and model-based collaborative filtering approaches. The algorithms were trained on historical data of users’ interactions in the SciStarter platform - a leading citizen science site - as well as their contributions to different projects. The trained algorithms were evaluated in SciStarter and involved hundreds of users who were provided with personalized recommendations for new projects they had not contributed to before. The results show that using the new recommendation system led people to increased participation in new SciStarter projects when compared to groups that were recommended projects using nonpersonalized recommendation approaches, and compared to behavior before recommendations. In particular, the group of volunteers receiving recommendations created by an SVD algorithm (matrix factorization) exhibited the highest levels of contributions to new projects, when compared to the other cohorts. A follow-up survey conducted with the SciStarter community confirmed that users felt that the recommendations matched their personal interests and goals. Based on these results, our recommendation system is now fully integrated into the SciStarter portal, positively affecting hundreds of users each week, and leading to social and educational benefits.

TIST Journal 2020 Journal Article

Human-computer Coalition Formation in Weighted Voting Games

• Moshe Mash
• Roy Fairstein
• Yoram Bachrach
• Kobi Gal
• Yair Zick

This article proposes a negotiation game, based on the weighted voting paradigm in cooperative game theory, where agents need to form coalitions and agree on how to share the gains. Despite the prevalence of weighted voting in the real world, there has been little work studying people’s behavior in such settings. This work addresses this gap by combining game-theoretic solution concepts with machine learning models for predicting human behavior in such domains. We present a five-player online version of a weighted voting game in which people negotiate to create coalitions. We provide an equilibrium analysis of this game and collect hundreds of instances of people’s play in the game. We show that a machine learning model with features based on solution concepts from cooperative game theory (in particular, an extension of the Deegan-Packel Index) provide a good prediction of people’s decisions to join coalitions in the game. We designed an agent that uses the prediction model to make offers to people in this game and was able to outperform other people in an extensive empirical study. These results demonstrate the benefit of incorporating concepts from cooperative game theory in the design of agents that interact with people in group decision-making settings.

IJCAI Conference 2020 Conference Paper

Interpretable Models for Understanding Immersive Simulations

• Nicholas Hoernle
• Kobi Gal
• Barbara Grosz
• Leilah Lyons
• Ada Ren
• Andee Rubin

This paper describes methods for comparative evaluation of the interpretability of models of high dimensional time series data inferred by unsupervised machine learning algorithms. The time series data used in this investigation were logs from an immersive simulation like those commonly used in education and healthcare training. The structures learnt by the models provide representations of participants' activities in the simulation which are intended to be meaningful to people's interpretation. To choose the model that induces the best representation, we designed two interpretability tests, each of which evaluates the extent to which a model’s output aligns with people’s expectations or intuitions of what has occurred in the simulation. We compared the performance of the models on these interpretability tests to their performance on statistical information criteria. We show that the models that optimize interpretability quality differ from those that optimize (statistical) information theoretic criteria. Furthermore, we found that a model using a fully Bayesian approach performed well on both the statistical and human-interpretability measures. The Bayesian approach is a good candidate for fully automated model selection, i. e. , when direct empirical investigations of interpretability are costly or infeasible.

JAAMAS Journal 2020 Journal Article

Strategic voting in the lab: compromise and leader bias behavior

• Reshef Meir
• Kobi Gal
• Maor Tal

Abstract Plurality voting is perhaps the most commonly used way to aggregate the preferences of multiple voters. Yet, there is no consensus on how people vote strategically, even in very simple settings. The purpose of this paper is to provide a comprehensive study of people’s voting behavior in various online settings under the plurality rule. We implemented voting games that replicate two common real-world voting scenarios in controlled experiments. In the first, a single voter votes once after seeing a pre-election poll. In the second game, a group of voters play an iterative game, and change their vote as the game progresses (as in online voting). The winning candidate in each game (and hence the subject’s payment) is determined using the plurality rule. For each of these settings we generated hundreds of game instances, varying conditions such as the number of voters, subjects’ preferences over candidates and the poll information that was made available to the subjects prior to voting. We show that people can be classified into several groups, one of which is not engaged in any strategic behavior, while the largest group demonstrates both a tendency for strategic compromise, and a bias toward voting for the leader in the poll. We provide a detailed analysis of this group behavior for both settings, and how it depends on the poll information. Our study has insight for multi-agent system designers in uncovering patterns that provide reasonable predictions of voters’ behaviors, which may facilitate the design of agents that support people or act autonomously in voting systems.

AIJ Journal 2019 Journal Article

Corrigendum to “Sequential plan recognition: An iterative approach to disambiguating between hypotheses” [Artif. Intell. 260 (2018) 51–73]

• Reuth Mirsky
• Roni Stern
• Kobi Gal
• Meir Kalech

TIST Journal 2019 Journal Article

Goal and Plan Recognition Design for Plan Libraries

• Reuth Mirsky
• Kobi Gal
• Roni Stern
• Meir Kalech

This article provides new techniques for optimizing domain design for goal and plan recognition using plan libraries. We define two new problems: Goal Recognition Design for Plan Libraries (GRD-PL) and Plan Recognition Design (PRD). Solving the GRD-PL helps to infer which goal the agent is trying to achieve, while solving PRD can help to infer how the agent is going to achieve its goal. For each problem, we define a worst-case distinctiveness measure that is an upper bound on the number of observations that are necessary to unambiguously recognize the agent’s goal or plan. This article studies the relationship between these measures, showing that the worst-case distinctiveness of GRD-PL is a lower bound of the worst-case plan distinctiveness of PRD and that they are equal under certain conditions. We provide two complete algorithms for minimizing the worst-case distinctiveness of plan libraries without reducing the agent’s ability to complete its goals: One is a brute-force search over all possible plans and one is a constraint-based search that identifies plans that are most difficult to distinguish in the domain. These algorithms are evaluated in three hierarchical plan recognition settings from the literature. We were able to reduce the worst-case distinctiveness of the domains using our approach, in some cases reaching 100% improvement within a predesignated time window. Our iterative algorithm outperforms the brute-force approach by an order of magnitude in terms of runtime.

AAMAS Conference 2019 Conference Paper

Modeling People's Voting Behavior with Poll Information

• Roy Fairstein
• Adam Lauz
• Reshef Meir
• Kobi Gal

Despite the prevalence of voting systems in the real world there is no consensus among researchers of how people vote strategically, even in simple voting settings. This paper addresses this gap by comparing different approaches that have been used to model strategic voting, including expected utility maximization, heuristic decisionmaking, and bounded rationality models. The models are applied to data collected from hundreds of people in controlled voting experiments, where people vote after observing non-binding poll information. We introduce a new voting model, the Attainability- Utility (AU) heuristic, which weighs the popularity of a candidate according to the poll, with the utility of the candidate to the voter. We argue that the AU model is cognitively plausible, and show that it is able to predict people’s voting behavior significantly better than other models from the literature. It was almost at par with (and sometimes better than) a machine learning algorithm that uses substantially more information. Our results provide new insights into the strategic considerations of voters, that undermine the prevalent assumptions of much theoretical work in social choice.

AAAI Conference 2018 Conference Paper

Optimizing Interventions via Offline Policy Evaluation: Studies in Citizen Science

• Avi Segal
• Kobi Gal
• Ece Kamar
• Eric Horvitz
• Grant Miller

Volunteers who help with online crowdsourcing such as citizen science tasks typically make only a few contributions before exiting. We propose a computational approach for increasing users’ engagement in such settings that is based on optimizing policies for displaying motivational messages to users. The approach, which we refer to as Trajectory Corrected Intervention (TCI), reasons about the tradeoff between the long-term influence of engagement messages on participants’ contributions and the potential risk of disrupting their current work. We combine model-based reinforcement learning with off-line policy evaluation to generate intervention policies, without relying on a fixed representation of the domain. TCI works iteratively to learn the best representation from a set of random intervention trials and to generate candidate intervention policies. It is able to refine selected policies off-line by exploiting the fact that users can only be interrupted once per session. We implemented TCI in the wild with Galaxy Zoo, one of the largest citizen science platforms on the web. We found that TCI was able to outperform the state-of-the-art intervention policy for this domain, and significantly increased the contributions of thousands of users. This work demonstrates the benefit of combining traditional AI planning with off-line policy methods to generate intelligent intervention strategies.

AIJ Journal 2018 Journal Article

Sequential plan recognition: An iterative approach to disambiguating between hypotheses

• Reuth Mirsky
• Roni Stern
• Kobi Gal
• Meir Kalech

Plan recognition algorithms output hypotheses about an agent's plans from its observed actions. Due to imperfect knowledge about the agent's behavior and the environment, it is often the case that there are multiple hypotheses about an agent's plans that are consistent with the observations, though only one of these hypotheses is correct. This paper addresses the problem of how to disambiguate between hypotheses during the recognition process, by querying the acting agent about whether a given plan is part of the correct hypothesis. The main contribution is a sound and complete process for reducing the set of possible hypotheses called Sequential Plan Recognition (SPR). SPR iteratively queries the user and revises the set of possible hypotheses according to the outcome of the query. Several policies are provided for choosing which plans to query the agent. These policies address the problem of how to reduce the number of hypotheses during the recognition process using a minimal number of queries. The proposed policies include policies that use maximum likelihood and information gain measures. The paper provides a complexity analysis of the SPR process and the proposed query policies. It demonstrate its efficiency on two known domains from the literature, describing how performance and runtime are affected by features in the domain. Our results can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.

IJCAI Conference 2017 Conference Paper

How to Form Winning Coalitions in Mixed Human-Computer Settings

• Yair Zick
• Kobi Gal
• Yoram Bachrach
• Moshe Mash

Despite the prevalence of weighted voting in the real world, there has been relatively little work studying real people's behavior in such settings. This paper proposes a new negotiation game, based on the weighted voting paradigm in cooperative games, where players need to form coalitions and agree on how to share the gains. We show that solution concepts from cooperative game theory (in particular, an extension of the Deegan-Packel Index) provide a good prediction of people's decisions to join a given coalition. With this insight in mind, we design an agent that combines predictive analytics with decision theory to make offers to people in the game. We show that the agent was able to obtain higher shares from coalitions than did people playing other people, without reducing the acceptance rate of its offers. These results demonstrate the potential of incorporating concepts from cooperative game theory in the design of negotiating agents.

ECAI Conference 2014 Conference Paper

Human-Computer Negotiation in Three-Player Market Settings

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

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