Effective online mental health counseling is a complex, theory-driven process requiring the simultaneous integration of psychological frameworks, real-time distress signals, and strategic intervention planning. This level of clinical reasoning is critical for safety and therapeutic effectiveness but is often missing in general-purpose Large Language Models (LLMs). We introduce SAGE (Strategy-Aware Graph-Enhanced Generation Framework), a novel framework designed to bridge the gap between structured clinical knowledge and generative AI. SAGE constructs a heterogeneous graph that unifies conversational dynamics with a psychologically grounded layer, explicitly anchoring interactions in a theory-driven lexicon. Our architecture first employs a Next Strategy Classifier to identify the optimal therapeutic intervention. Subsequently, a Graph-Aware Attention mechanism projects graph-derived structural signals into soft prompts, conditioning the LLM to generate responses that maintain clinical depth. Validated through both automated metrics and expert human evaluation, SAGE outperforms baselines in strategy prediction and recommended response quality. By providing actionable intervention recommendations, SAGE serves as a cutting-edge decision-support tool designed to augment human expertise in high-stakes online crisis counseling.

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.

Modelling student performance is an increasingly popular goal in the learning analytics community. A common method for this task is Bayesian Knowledge Tracing (BKT), which predicts student performance and topic mastery using the student’s answer history. While BKT has strong qualities and good empirical performance, like many machine learning approaches it can be prone to bias. In this study we demonstrate an inherent bias in BKT with respect to students’ income support levels and gender, using publicly available data. We find that this bias is likely a result of the model’s ‘slip’ parameter disregarding answer speed when deciding if a student has lost mastery status. We propose a new BKT model variation that directly considers answer speed, resulting in a significant fairness increase without sacrificing model performance. We discuss the role of answer speed as a potential cause of BKT model bias, as well as a method to minimise bias in future implementations.

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.

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.

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.

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.

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.

With the increased awareness of situations of mental crisis and their societal impact, online services providing emergency support are becoming commonplace in many countries. Computational models, trained on discussions between help-seekers and providers, can support suicide prevention by identifying at-risk individuals. However, the lack of domain-specific models, especially in low-resource languages, poses a significant challenge for the automatic detection of suicide risk. We propose a model that combines pre-trained language models (PLM) with a fixed set of manually crafted (and clinically approved) set of suicidal cues, followed by a two-stage fine-tuning process. Our model achieves 0.91 ROC-AUC and an F2-score of 0.55, significantly outperforming an array of strong baselines even early on in the conversation, which is critical for real-time detection in the field. Moreover, the model performs well across genders and age groups.

Citizen science projects promise to increase scientific productivity while also connecting science with the general public. They create scientific value for researchers and provide pedagogical and social benefits to volunteers. Given the astounding number of available citizen science projects, volunteers find it difficult to find the projects that best fit their interests. This difficulty can be alleviated by providing personalized project recommendations to users. This paper studies whether combining project recommendations with explanations improves users’ contribution levels and satisfaction. We generate post-hoc explanations to users by learning from their past interactions as well as project content (e.g., location, topics). We provide an algorithm for clustering recommended projects to groups based on their predicted relevance to the user. We demonstrated the efficacy of our approach in offline studies as well as in an online study in SciStarter that included hundreds of users. The vast majority of users highly preferred receiving explanations about why projects were recommended to them, and receiving such explanations did not impede on the contribution levels of users, when compared to other users who received project recommendations without explanations. Our approach is now fully integrated in SciStarter.

Abstract Virtual rewards, such as badges, are commonly used in online platforms as incentives for promoting contributions from a userbase. It is widely accepted that such rewards “steer” people’s behaviour towards increasing their rate of contributions before obtaining the reward. This paper provides a new probabilistic model of user behaviour in the presence of threshold rewards, such a badges. We find, surprisingly, that while steering does affect a minority of the population, the majority of users do not change their behaviour around the achievement of these virtual rewards. In particular, we find that only approximately 5–30% of Stack Overflow users who achieve the rewards appear to respond to the incentives. This result is based on the analysis of thousands of users’ activity patterns before and after they achieve the reward. Our conclusion is that the phenomenon of steering is less common than has previously been claimed. We identify a statistical phenomenon, termed “Phantom Steering”, that can account for the interaction data of the users who do not respond to the reward. The presence of phantom steering may have contributed to some previous conclusions about the ubiquity of steering. We conduct a qualitative survey of the users on Stack Overflow which supports our results, suggesting that the motivating factors behind user behaviour are complex, and that some of the online incentives used in Stack Overflow may not be solely responsible for changes in users’ contribution rates.

A new approach to online discussion, which situates student discussions in the margins of the course content, can enhance student engagement with course materials. However, in high-enrollment classes, the large number of comments can overwhelm and intimidate students. Some become frustrated by the volume of potential online interactions and by a perceived lack of immediate relevance to their studies. Likewise, instructors are disappointed when outstanding discussions, that they deem valuable for all to see, get lost in the clutter. To address these challenges, we propose visual spotlighting mechanisms for increasing the saliency of selected comments. We piloted and deployed multiple designs in two high-enrollment biology courses at a large public university in the United States. Interviews, surveys, and a controlled experiment show that spotlighting relevant comments in heavily annotated texts positively affects students' engagement, measured in terms of their attention to comments, and their reported sense of validation and pride. Students also reported their preferences for certain spotlighting designs.

Citizen science refers to scientific 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 non-personalized 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.

Online forums are an integral part of modern day courses, but motivating students to participate in educationally beneficial discussions can be challenging. Our proposed solution is to initialize (or “seed”) a new course forum with comments from past instances of the same course that are intended to trigger discussion that is beneficial to learning. In this work, we develop methods for selecting high-quality seeds and evaluate their impact over one course instance of a 186-student biology class. We designed a scale for measuring the “seeding suitability” score of a given thread (an opening comment and its ensuing discussion). We then constructed a supervised machine learning (ML) model for predicting the seeding suitability score of a given thread. This model was evaluated in two ways: first, by comparing its performance to the expert opinion of the course instructors on test/holdout data; and second, by embedding it in a live course, where it was actively used to facilitate seeding by the course instructors. For each reading assignment in the course, we presented a ranked list of seeding recommendations to the course instructors, who could review the list and filter out seeds with inconsistent or malformed content. We then ran a randomized controlled study, in which one group of students was shown seeds that were recommended by the ML model, and another group was shown seeds that were recommended by an alternative model that ranked seeds purely by the length of discussion that was generated in previous course instances. We found that the group of students that received posts from either seeding model generated more discussion than a control group in the course that did not get seeded posts. Furthermore, students who received seeds selected by the ML-based model showed higher levels of engagement, as well as greater learning gains, than those who received seeds ranked by length of discussion.

Abstract Badges are endemic to online interaction sites, from question and answer (Q&A) websites to ride sharing, as systems for rewarding participants for their contributions. This article studies how badge design affects people's contributions and behavior over time. Past work has shown that badges “steer” people's behavior toward substantially increasing the amount of contributions before obtaining the badge, and immediately decreasing their contributions thereafter, returning to their baseline contribution levels. In contrast, we find that the steering effect depends on the type of user, as modeled by the rate and intensity of the user's contributions. We use these measures to distinguish between different groups of user activity, including users who are not affected by the badge system despite being significant contributors to the site. We provide a predictive model of how users change their activity group over the course of their lifetime in the system. We demonstrate our approach empirically in three different Q&A sites on Stack Exchange with hundreds of thousands of users, for two types of activities (editing and voting on posts).

Badges are commonly used in online platforms as incentives for promoting contributions. It is widely accepted that badges “steer” people's behavior toward increasing their rate of contributions before obtaining the badge. This paper provides a new probabilistic model of user behavior in the presence of badges. By applying the model to data from thousands of users on the Q&A site Stack Overflow, we find that steering is not as widely applicable as was previously understood. Rather, the majority of users remain apathetic toward badges, while still providing a substantial number of contributions to the site. An interesting statistical phenomenon, termed “Phantom Steering,” accounts for the interaction data of these users and this may have contributed to some previous conclusions about steering. Our results suggest that a small population, approximately 20%, of users respond to the badge incentives. Moreover, we conduct a qualitative survey of the users on Stack Overflow which provides further evidence that the insights from the model reflect the true behavior of the community. We argue that while badges might contribute toward a suite of effective rewards in an online system, research into other aspects of reward systems, such as Stack Overflow's reputation points, should become a focus of the community.

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.

Students' confusion is a barrier for learning, contributing to loss of motivation and to disengagement with course materials. However, detecting students' confusion in large-scale courses is both time and resource intensive. This paper provides a new approach for confusion detection in online forums that is based on harnessing the power of students' self-reported affective states (reported using a set of pre-defined hashtags). It presents a rule for labeling confusion, based on students' hashtags in their posts, that is shown to align with teachers' judgement. We use this labeling rule to inform the design of an automated classifier for confusion detection for the case when there are no self-reported hashtags present in the test set. We demonstrate this approach in a large scale Biology course using the Nota Bene annotation platform. This work lays the foundation to empower teachers with better support tools for detecting and alleviating confusion in online courses.

This paper explores the use of data analytics for identifying creativity in visual programming. Visual programming environments are increasingly included in the schools curriculum. Their potential for promoting creative thinking in students is an important factor in their adoption. However, there does not exist a standard approach for detecting creativity in students' programming behavior, and analyzing programs manually requires human expertise and is time consuming. This work provides a computational tool for measuring creativity in visual programming that combines theory from the literature with data mining approaches. It adapts classical dimensions of creative processes to our setting, and considers new aspects such as visual elements of the visual programming projects. We apply our approach to the Scratch programming environment, measuring the creativity score of hundreds of projects. We show a preliminary comparison between our metrics and teacher ratings.

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.

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.

Badges are endemic to online interaction sites, from Question and Answer (Q&A) websites to ride sharing, as systems for rewarding participants for their contributions. This paper studies how badge design affects people's contributions and behavior over time. Past work has shown that badges "steer'' people's behavior toward substantially increasing the amount of contributions before obtaining the badge, and immediately decreasing their contributions thereafter, returning to their baseline contribution levels. In contrast, we find that the steering effect depends on the type of user, as modeled by the rate and intensity of the user's contributions. We use these measures to distinguish between different groups of user activity, including users who are not affected by the badge system despite being significant contributors to the site. We provide a predictive model of how users change their activity group over the course of their lifetime in the system. We demonstrate our approach empirically in three different Q&A sites on Stack Exchange with hundreds of thousands of users, and we discuss the implications for system designers.

Real-time strategy (RTS) games are a challenging application for artificial intelligence (AI) methods. This is because they involve simultaneous play and adversarial reasoning that is conducted in real time in large state spaces. Many AI methods for playing RTS games rely on hard-coded strategies designed by human experts. The drawback of using such strategies is that they are often unable to adapt to new scenarios during gameplay. The contribution of this paper is a new approach, called strategy creation via voting (SCV), that uses a voting method to generate a large set of novel strategies from existing expert-based ones. Then, SCV uses an opponent modeling scheme during the game to choose which strategy from the generated pool of possibilities to use. By repeatedly choosing which strategy to use, SCV is able to adapt to different scenarios that might arise during the game. We implemented SCV as a bot for μRTS, a recognized RTS testbed. The results of a detailed empirical study show that SCV outperforms all approaches tested in matches played on large maps and is competitive in matches played on smaller maps.

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.

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.

Reading material has been part of course teaching for centuries, but until recently students' engagement with that reading, and its effect on their learning, has been difficult for teachers to assess. In this article, we explore the idea of examining cognitive engagement---a measure of how deeply a student is thinking about course material, which has been shown to correlate with learning gains---as it varies over different sections of the course reading material. We show that a combination of automatic classification and visualization of cognitive engagement anchored in the text can give teachers---and not only researchers---valuable insight into their students' thinking, suggesting ways to modify their lectures and their course readings to improve learning. We demonstrate this approach with analyzing students' comments in two different courses (Physics and Biology) using the Nota Bene annotation platform.

A key challenge in procedural content generation is to automatically evaluate whether the generated content has good quality. In this paper, we describe an approach that uses nonexpert workers to evaluate small portions of levels generated by an off-the-shelf generation system for the game ofInfinite Mario Bros. Several such evaluated portions are then combined to form full levels of the game using a mathematical progression arc model. The composition of the small portions into full levels is done by accounting for the human-annotated information. We evaluated the approach using computational metrics as well as surveying human subjects playing the levels. The results show that the human computation approach is able to generate levels that are perceived by people to have better visual aesthetics and to be more enjoyable to play than existing approaches. Another contribution of our paper is a dataset of the small annotated levels that can be used in future research for learning models for evaluating machine-generated content.

Goal Recognition Design (GRD) is the problem of designing a domain in a way that will allow easy identification of agents' goals. This work extends the original GRD problem to the Plan Recognition Design (PRD) problem which is the task of designing a domain using plan libraries in order to facilitate fast identification of an agent's plan. While GRD can help to explain faster which goal the agent is trying to achieve, PRD can help in faster understanding of how the agent is going to achieve its goal. We define a new measure that quantifies the worst-case distinctiveness of a given planning domain, propose a method to reduce it in a given domain and show the reduction of this new measure in three domains from the literature.

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.

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.

“Mirror, mirror, on the wall, who is the fairest of them all?” The Evil Queen 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.

In exploratory domains, agents’ behaviors include switching between activities, extraneous actions, and mistakes. Such settings are prevalent in real world applications such as interaction with open-ended software, collaborative office assistants, and integrated development environments. Despite the prevalence of such settings in the real world, there is scarce work in formalizing the connection between high-level goals and low-level behavior and inferring the former from the latter in these settings. We present a formal grammar for describing users’ activities in such domains. We describe a new top-down plan recognition algorithm called CRADLE (Cumulative Recognition of Activities and Decreasing Load of Explanations) that uses this grammar to recognize agents’ interactions in exploratory domains. We compare the performance of CRADLE with state-of-the-art plan recognition algorithms in several experimental settings consisting of real and simulated data. Our results show that CRADLE was able to output plans exponentially more quickly than the state-of-the-art without compromising its correctness, as determined by domain experts. Our approach can form the basis of future systems that use plan recognition to provide real-time support to users in a growing class of interesting and challenging domains.

Despite the prevalence of e-learning systems in schools, most of today's systems do not personalize educational data to the individual needs of each student. This paper proposes a new algorithm for sequencing questions to students that is empirically shown to lead to better performance and engagement in real schools when compared to a baseline approach. It is based on using knowledge tracing to model students' skill acquisition over time, and to select questions that advance the student's learning within the range of the student's capabilities, as determined by the model. The algorithm is based on a Bayesian Knowledge Tracing (BKT) model that incorporates partial credit scores, reasoning about multiple attempts to solve problems, and integrating item difficulty. This model is shown to outperform other BKT models that do not reason about (or reason about some but not all) of these features. The model was incorporated into a sequencing algorithm and deployed in two classes in different schools where it was compared to a baseline sequencing algorithm that was designed by pedagogical experts. In both classes, students using the BKT sequencing approach solved more difficult questions and attributed higher performance than did students who used the expert-based approach. Students were also more engaged using the BKT approach, as determined by their interaction time and number of log-ins to the system, as well as their reported opinion. We expect our approach to inform the design of better methods for sequencing and personalizing educational content to students that will meet their individual learning needs.

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.

Active honeytokens are fake digital data objects planted among real data objects and used in an attempt to detect data misuse by insiders. In this article, we are interested in understanding how users (e.g., employees) behave when interacting with honeytokens, specifically addressing the following questions: Can users distinguish genuine data objects from honeytokens? And, how does the user's behavior and tendency to misuse data change when he or she is aware of the use of honeytokens? First, we present an automated and generic method for generating the honeytokens that are used in the subsequent behavioral studies. The results of the first study indicate that it is possible to automatically generate honeytokens that are difficult for users to distinguish from real tokens. The results of the second study unexpectedly show that users did not behave differently when informed in advance that honeytokens were planted in the database and that these honeytokens would be monitored to detect illegitimate behavior. These results can inform security system designers about the type of environmental variables that affect people's data misuse behavior and how to generate honeytokens that evade detection.

This article presents novel methods for representing and analyzing a special class of multiagent bargaining settings that feature multiple players, large action spaces, and a relationship among players’ goals, tasks, and resources. We show how to reduce these interactions to a set of bilateral normal-form games in which the strategy space is significantly smaller than the original settings while still preserving much of their structural relationship. The method is demonstrated using the Colored Trails (CT) framework, which encompasses a broad family of games and has been used in many past studies. We define a set of heuristics (metastrategies) in multiplayer CT games that make varying assumptions about players’ strategies, such as boundedly rational play and social preferences. We show how these CT settings can be decomposed into canonical bilateral games such as the Prisoners’ Dilemma, Stag Hunt, and Ultimatum games in a way that significantly facilitates their analysis. We demonstrate the feasibility of this approach in separate CT settings involving one-shot and repeated bargaining scenarios, which are subsequently analyzed using evolutionary game-theoretic techniques. We provide a set of necessary conditions for CT games for allowing this decomposition. Our results have significance for multiagent systems researchers in mapping large multiplayer CT task settings to smaller, well-known bilateral normal-form games while preserving some of the structure of the original setting.

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.

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.

Exploratory Learning Environments (ELE) are open-ended and flexible software, supporting interaction styles that include exogenous actions and trial-and-error. This paper shows that using AI techniques to visualize worked examples in ELEs improves students' generalization of mathematical concepts across problems, as measured by their performance. Students were exposed to a worked example of a problem solution using an ELE for statistics education. One group in the study was presented with a hierarchical plan of relevant activities that emphasized the sub-goals and the structure relating to the solution. This visualization used an AI algorithm to match a log of activities in the ELEs to ideal solutions. We measured students' performance when using the ELE to solve new problems that required generalization of concepts introduced in the example solution. The results showed that students who were shown the plan visualization significantly outperformed other students who were presented with a step-by-step list of actions in the software used to generate the same solution to the example problem. Analysis of students' explanations of the problem solution shows that the students in the former condition also demonstrated deeper understanding of the solution process. These results demonstrate the benefit to students when using AI technology to visualize worked examples in ELEs and suggests future applications of this approach to actively support students' learning and teachers' understanding of students' activities.

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.

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.

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.

Modern pedagogical software is open-ended and flexible, allowing students to solve problems through exploration and trial-and-error. Such exploratory settings provide for a rich educational environment for students, but they challenge teachers to keep track of students’ progress and to assess their performance. This article presents techniques for recognizing students’ activities in such pedagogical software and visualizing these activities to teachers. It describes a new plan recognition algorithm that uses a recursive grammar that takes into account repetition and interleaving of activities. This algorithm was evaluated empirically using an exploratory environment for teaching chemistry used by thousands of students in several countries. It was always able to correctly infer students’ plans when the appropriate grammar was available. We designed two methods for visualizing students’ activities for teachers: one that visualizes students’ inferred plans, and one that visualizes students’ interactions over a timeline. Both of these visualization methods were preferred to and found more helpful than a baseline method which showed a movie of students’ interactions. These results demonstrate the benefit of combining novel AI techniques and visualization methods for the purpose of designing collaborative systems that support students in their problem solving and teachers in their understanding of students’ performance.

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.

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.

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.

This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents' beliefs and decision-making processes. NIDs are graphical structures in which agents' mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents' optimal strategies, and how they actually behave in reality.