Arrow Research search

Author name cluster

Sandip Sen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

69 papers
2 author rows

Possible papers

69

EUMAS Conference 2024 Conference Paper

Influence of Language Warmth on User Adoption of Agent Recommendations for Multi-arm Bandits

  • Selim Karaoglu
  • Marina Katoh
  • Titash Majumdar
  • Ethan Beaird
  • Feyza Merve Hafizoglu
  • Sandip Sen

Abstract This research investigates the influence of language warmth on the user adoption of agent recommendations and satisfaction by/of the users in the multi-armed bandit scenarios. Prior work has identified that agent recommendations can, under certain situations, improve user selection of options to maximize utility given a limited number of pulls on a multi-armed bandit problem. We posit that appropriate explanations associated with agent recommendations can further increase user adoption of potentially higher utility arms and thereby increase cumulative utility obtained by the user from a finite number of arm pulls. Furthermore, we investigate the effect of “warmth” of explanations on recommendation adoption by the user and concomitant cumulative utility realized. We design an experimentation platform for the agent-assisted user selection from multi-armed bandits. Experiments are run with workers recruited from an online crowdsourcing platform. The results reveal that explanations do result in improved cumulative utility obtained. Most importantly, we suggest that agent designers should configure the warmth level of agent explanations depending on the interaction type, i. e. , warm language can be more effective in some problems while cold language works in others.

Details

AAMAS Conference 2024 Conference Paper

Team Performance and User Satisfaction in Mixed Human-Agent Teams

  • Sami Abuhaimed
  • Sandip Sen

Human-agent teams, consisting of at least one human and one agent teaming together to achieve a common objective, are increasingly prevalent and effective in both social and industrial spheres. Associated changes in human preferences and expectations from autonomous teammates will continue to shape and alter collaboration opportunities and dynamics within human-agent teams. New environments are emerging, including Ad Hoc teams where teammates collaborate without pre-coordination or prior knowledge of other teammates capabilities. Team members in ad hoc human-agent teams have to collaborate to find tasks allocations to effectively leverage teammate capabilities to improve team performance and human satisfaction. In this paper, we investigate ad hoc team dynamics under different team compositions, including those comprised of only humans or of human and agent team members, as well as teams consisting of more than two members. Experiments are run with MTurk workers and several hypotheses are evaluated on the effects of teammate type and team size on team performance and human satisfaction using a collaborative Human- Agent Taskboard (CHATboard) platform where teams repeatedly collaborate to complete assigned tasks.

PDF

EUMAS Conference 2024 Conference Paper

Using Agent Interventions to Reduce User Procrastination Tendencies

  • Ethan Beaird
  • Feyza Merve Hafizoglu
  • Sandip Sen

Abstract Procrastination, i. e. , irrational delay, seriously and increasingly affects people’s daily and professional lives in today’s society where social media and easy access to entertainment options are plentiful. Psychology literature offers various types of interventions developed to reduce an individual’s level of procrastination; however, only a limited number of people experiencing procrastination have access to such interventions. Leveraging agent technology as even a partial remedy to this widespread problem can be highly beneficial due to its ubiquitous nature. In this study, we develop a model of procrastination on task completion and levels of agent-based interventions to assist individuals in overcoming procrastination. The effects of agent interventions on procrastination are evaluated through an extensive set of controlled experiments with participants recruited from Amazon Mechanical Turk. The agent engages the user using instances of given task types to develop a shared awareness of user preferences and capabilities. This preference model is then used both to choose effective interventions as well as measure and reward subsequent user performance. This model can also be leveraged to explain agent interventions to the user. We collect and use both task completion metric data and survey data to assess individuals’ perceptions of procrastination, task completion satisfaction, and the usefulness of agent support. Our data analysis indicates that using agent-based interventions can effectively help people reduce procrastination.

Details

KER Journal 2020 Journal Article

Effects of parity, sympathy and reciprocity in increasing social welfare

  • Sandip Sen
  • Chad Crawford
  • Adam Dees
  • Rachna Nanda Kumar
  • James Hale

Abstract We are interested in understanding how socially desirable traits like sympathy, reciprocity, and fairness can survive in environments that include aggressive and exploitative agents. Social scientists have long theorized about ingrained motivational factors as explanations for departures from self-seeking behaviors by human subjects. Some of these factors, namely reciprocity, have also been studied extensively in the context of agent systems as tools for promoting cooperation and improving social welfare in stable societies. In this paper, we evaluate how other factors like sympathy and parity can be used by agents to seek out cooperation possibilities while avoiding exploitation traps in more dynamic societies. We evaluate the relative effectiveness of agents influenced by different social considerations when they can change who they interact with in their environment using both an experimental framework and a predictive analysis. Such rewiring of social networks not only allows possibly vulnerable agents to avoid exploitation but also allows them to form gainful coalitions to leverage mutually beneficial cooperation, thereby significantly increasing social welfare.

Details DOI

AAMAS Conference 2018 Conference Paper

Agents for Social (Media) Change: Blue Sky Ideas Track

  • Sandip Sen
  • Zenefa Rahaman
  • Chad Crawford
  • Osman Yü cel

We are addicted to the Internet and spend a significant portion of our waking hours engaged to that virtual world through the "window" of our electronic devices. A large majority of these interactions occur on online social media. From advertising campaigns to political debates and from trending news topics to communications from family and social circles, social media platforms and services have become invaluable and irreplaceable tools for most of us. Our beliefs and preferences are increasingly shaped and defined by what we see and experience on social media. With this increased reliance also comes the uneasy realization that information and knowledge of value to us is being drowned out in the deluge of forwarded messages and targeted communication from paid advertisers on various social media platforms. This paper seeks to highlight the research challenges underlying the potential for intelligent agents to help stem the tide, to help us deliberate, prioritize and process information of value to us and to our communities, as well as help us reach out, connect to, share and disseminate mutually interesting knowledge with other users. We posit an agent-based ecosystem, where both individual users and organizations see the value and creative possibilities of agent-based solutions to critical problems of connectivity, relevance, varying interest profiles, context, etc.

PDF

KER Journal 2018 Journal Article

Language independent recommender agent

  • Osman Yucel
  • Sandip Sen

Abstract This paper presents a new ‘Language Independent Recommender Agent’ (LIRA), using information distributed over any text-source pair on the Web about candidate items. While existing review-based recommendation systems learn the features of candidate items and users’ preferences, they do not handle varying perspectives of users on those features. LIRA constructs agents for each user, which run regression algorithms on texts from different sources and builds trust relations. The key advantages of LIRA can be listed as: LIRA does not require reviews from target users, LIRA calculates trust values based on prediction accuracy instead of social connections or rating similarity, LIRA does not require the reviews to come from the same community or peer user group. Since ratings of the reviewers are not necessary for LIRA, we can collect and use reviews from different sources (web pages, professional critiques), as long as we know the corresponding item and source of that text. Since LIRA does not combine text from different sources, texts from different sources are not required to be in the same language. LIRA can utilize text from multiple languages, as long as sources are consistent with their language usage.

Details DOI

AAMAS Conference 2018 Conference Paper

Resisting Exploitation Through Rewiring in Social Networks: Social Welfare Increase using Parity, Sympathy and Reciprocity

  • Chad Crawford
  • Rachna Nanda Kumar
  • Sandip Sen

We seek to understand how socially desirable traits like sympathy, reciprocity and fairness can survive in environments that include aggressive and exploitative agents. Social scientists have long observed and theorized about ingrained motivational factors as explanations for departures from self-seeking behaviors by human subjects. Some of these factors, namely reciprocity, have also been studied extensively in the context of agent systems as tools for promoting cooperation and improving social welfare in stable societies. In this paper, we investigate how other factors like sympathy and parity can be used by agents to leverage cooperation possibilities while avoiding exploitation traps in more dynamic societies. We evaluate the relative effectiveness of agents using different social considerations when they can change who they interact with in their environment. Such rewiring of social networks not only allows possibly vulnerable agents to avoid exploitation but also allows them to form gainful coalitions to leverage mutually beneficial cooperation, thereby significantly improving social welfare.

PDF

AAMAS Conference 2018 Conference Paper

The Dynamics of Opinion Evolution in Gossiper-Media Model with WoLS-CALA Learning

  • Chengwei Zhang
  • Xiaohong Li
  • Jianye Hao
  • Sandip Sen
  • Wanli Xue
  • Zhiyong Feng

In social networks, media outlets such as TV, newspapers, blogs adjust their opinions to cater to the public’s interest to increase the number of followers. Meanwhile, the evolution of the public’s opinions are affected by both the media and the peers they interact with. In this work, we investigate how the interactions between mainstream media affect the dynamics of the public’s opinions in social networks. We propose a reinforcement learning framework to model the interactions between the public (aka gossipers) and the media agents. We model each gossiper as an individually rational agent, which updates its opinion using the Bounded Confidence Model (BCM). Each media agent is interested in maximizing the number of following gossipers competitively, and an adaptive WoLS-CALA (Win or Learn Slow Continuous Action Learning Automaton) algorithm is proposed to achieve that goal. We theoretically prove that WoLS-CALA can learn to Nash equilibria for two-agent games with continuous action space. Besides, the opinion dynamics of both gossipers and media are theoretically analyzed. Extensive empirical simulation reveals the opinion dynamics of our framework facilitates the consensus of opinions and confirms the theoretical analysis.

PDF

AAMAS Conference 2018 Conference Paper

The Effects of Past Experience on Trust in Repeated Human-Agent Teamwork

  • Feyza Merve Hafizoglu
  • Sandip Sen

For human-agent virtual ad hoc teams to be effective, humans must be able to trust their agent counterparts. To earn the human’s trust, agents need to quickly develop an understanding of the expectation of human team members and adapt accordingly. This study empirically investigates the impact of past experience on human trust in and behavior towards agent teammates. To do so, we developed a repeated team coordination game, the Game of Trust (GoT), in which two players repeatedly cooperate to complete team tasks without prior assignment of subtasks. The effects of past experience on human trust are evaluated by performing an extensive set of controlled experiments with participants recruited from Amazon Mechanical Turk, a crowdsourcing marketplace. We collect both teamwork performance data as well as surveys to gauge participants’ trust in their agent teammates. The results show that positive (negative) past experience increases (decreases) human trust in agent teammates and past experience can affect three antecedents of trust: emotional state, game expertise, and expectation. These findings provide clear and significant evidence of the influence of key factors on human trust in virtual agent teammates and enhance our understanding of the changes in human trust in peer-level agent teammates with respect to past experience.

PDF

AAMAS Conference 2017 Conference Paper

Gesture-Based Control of Autonomous UAVs

  • Jonathon Bolin
  • Chad Crawford
  • William Macke
  • Jon Hoffman
  • Sam Beckmann
  • Sandip Sen

Unmanned Aerial Vehicles (UAVs) have been traditionally controlled via remote control or by software, which require skill using the remote or expert programming skills. Our goal is to develop a natural mode of directing a drone’s actions, akin to the forms of expression one finds between a person and a pet and hence accessible to almost any person without specialized training or expertise in using electronic gadgets. We build on prior work on analyzing video streams to use the video from the drone’s on-board camera to enable gesture-based control. Our approach uses a pre-trained convolutional neural network for pose extraction, Haar cascades to identify regions of interest within the UAV’s field of view, and a finite state machine to select the drone’s action. CCS Concepts •Human-centered computing → Collaborative interaction; Gestural input; Human computer interaction (HCI); Interface design prototyping;

PDF

ECAI Conference 2016 Conference Paper

Accelerating Norm Emergence Through Hierarchical Heuristic Learning

  • Tianpei Yang
  • Zhaopeng Meng
  • Jianye Hao
  • Sandip Sen
  • Chao Yu 0004

Social norms serve as an important mechanism to regulate the behaviours of agents and to facilitate coordination among them in multiagent systems. One important research question is how a norm can rapidly emerge through repeated local interaction within agent societies under different environments when their coordination space becomes large. To address this problem, we propose a hierarchically heuristic learning strategy (HHLS) under the hierarchical social learning framework. Subordinate agents report their information to their supervisors, while supervisors can generate instructions (rules and suggestions) based on the information collected from their subordinates. Subordinate agents heuristically update their strategies based on both their own experience and the instructions from their supervisors. Extensive experiment evaluations show that HHLS can support the emergence of desirable social norms more efficiently and can be applicable in a much wider range of multiagent interaction scenarios compared with previous work. The influence of key related factors (e. g. , different topologies, population, neighbourhood and action space size, cluster size) are also investigated and new insights are obtained as well.

Details

AAMAS Conference 2016 Conference Paper

An Adaptive Learning Framework for Efficient Emergence of Social Norms (Extended Abstract)

  • Chao Yu
  • Hongtao Lv
  • Sandip Sen
  • Jianye Hao
  • Fenghui Ren
  • Rui Liu

This paper investigates how norm emergence can be facilitated by agents’ adaptive learning behaviors. A general learning framework is proposed, in which agents can dynamically adapt their learning behaviors through social learning of their individual learning experience. Experimental results indicate that the proposed framework outperforms the static learning framework in various comparison criteria.

PDF

JAAMAS Journal 2015 Journal Article

A simulation framework for measuring robustness of incentive mechanisms and its implementation in reputation systems

  • Yuan Liu
  • Jie Zhang
  • Sandip Sen

Abstract In game theoretical analysis of incentive mechanisms, all players are assumed to be rational. Since it is likely that mechanism participants in the real world may not be fully rational, such mechanisms may not work as effectively as in the idealized settings for which they were designed. Therefore, it is important to evaluate the robustness of incentive mechanisms against various types of agents with bounded rational behaviors. Such evaluations would provide us with the information needed to choose mechanisms with desired properties in real environments. In this article, we first propose a general robustness measure, inspired by research in evolutionary game theory, as the maximal percentage of invaders taking non-equilibrium strategies such that the agents sustain the desired equilibrium strategy. We then propose a simulation framework based on evolutionary dynamics to empirically evaluate the equilibrium robustness. The proposed simulation framework is validated by comparing the simulated results with the analytical predictions based on a modified simplex analysis approach. Finally, we implement the proposed simulation framework for evaluating the robustness of incentive mechanisms in reputation systems for electronic marketplaces. The results from the implementation show that the evaluated mechanisms have high robustness against a certain non-equilibrium strategy, but is vulnerable to another strategy, indicating the need for designing more robust incentive mechanisms for reputation management in e-marketplaces.

Details DOI

JAAMAS Journal 2013 Journal Article

Emergence of conventions through social learning

  • Stéphane Airiau
  • Sandip Sen
  • Daniel Villatoro

Abstract Societal norms or conventions help identify one of many appropriate behaviors during an interaction between agents. The offline study of norms is an active research area where one can reason about normative systems and include research on designing and enforcing appropriate norms at specification time. In our work, we consider the problem of the emergence of conventions in a society through distributed adaptation by agents from their online experiences at run time. The agents are connected to each other within a fixed network topology and interact over time only with their neighbours in the network. Agents recognize a social situation involving two agents that must choose one available action from multiple ones. No default behavior is specified. We study the emergence of system-wide conventions via the process of social learning where an agent learns to choose one of several available behaviors by interacting repeatedly with randomly chosen neighbors without considering the identity of the interacting agent in any particular interaction. While multiagent learning literature has primarily focused on developing learning mechanisms that produce desired behavior when two agents repeatedly interact with each other, relatively little work exists in understanding and characterizing the dynamics and emergence of conventions through social learning. We experimentally show that social learning always produces conventions for random, fully connected and ring networks and study the effect of population size, number of behavior options, different learning algorithms for behavior adoption, and influence of fixed agents on the speed of convention emergence. We also observe and explain the formation of stable, distinct subconventions and hence the lack of emergence of a global convention when agents are connected in a scale-free network.

Details DOI

AAMAS Conference 2013 Conference Paper

Opposites Repel: The Effect of Incorporating Repulsion on Opinion Dynamics in the Bounded Confidence Model

  • Chad Crawford
  • Logan Brooks
  • Sandip Sen

Various computer and analytical models have been studied that analyze population dynamics of opinions of agents in societies under various assumptions of interaction restrictions and influences. Of particular interest to us are societal models based on Self-categorization Theory which addresses how agent opinions are affected based on interactions with other agents. The Bounded Confidence model, for example posits that two agents whose opinions are not too similar influence each other and are more likely to change their opinions towards each other after an interaction. Several extensions have also been proposed to such models that include interaction restrictions based on group memberships and the possibility of agents shifting their opinions away from each other after an interaction. We are motivated to study more realistic repulsion models where agents with extreme opinions will tend to further polarize after an interaction. We develop, simulate, and analyze several repulsion schemes within the Bounded Confidence Model of interaction and show interesting emergent phenomena that have been observed in real-life scenarios. We also present analytical models that are able to predict major features and timings of emergent opinion patterns in such interacting populations.

PDF

AAMAS Conference 2013 Conference Paper

Predicting Migration and Opinion Adoption Patterns in Agent Communities

  • Sreerupa Chatterjee
  • Feyza Merve Hafizoğlu
  • Sandip Sen

This paper presents an analytical model of a more realistic version of migration behavior and opinion adoption in communities, experimentally evaluated in [1]. The formal model is developed to predict the variation of community sizes over time and the final opinion distributions of agents having binary opinions distributed in communities. We derive and verify predictions from the formal model about the population dynamics using different combinations of each of three migration and adoption tendencies: eager, moderate, and conservative.

PDF

TAAS Journal 2013 Journal Article

Robust convention emergence in social networks through self-reinforcing structures dissolution

  • Daniel Villatoro
  • Jordi Sabater-Mir
  • Sandip Sen

Convention emergence solves the problem of choosing, in a decentralized way and among all equally beneficial conventions, the same convention for the entire population in the system for their own benefit. Our previous work has shown that reaching 100% agreement is not as straighforward as assumed by previous researchers, that, in order to save computational resources fixed the convergence rate to 90% (measuring the time it takes for 90% of the population to coordinate on the same action). In this article we present the notion of social instruments as a set of mechanisms that facilitate and accelerate the emergence of norms from repeated interactions between members of a society, only accessing local and public information and thus ensuring agents' privacy and anonymity. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions while effectively addressing coordination and learning problems, paying special attention to dissolving metastable subconventions. The first experimental results show that even with the usage of the proposed instruments, convergence is not accelerated or even obtained in irregular networks. This result leads us to perform an exhaustive analysis of irregular networks discovering what we have defined as Self-Reinforcing Structures (SRS). The SRS are topological configurations of nodes that promote the establishment and persistence of subconventions by producing a continuous reinforcing effect on the frontier agents. Finally, we propose a more sophisticated composed social instrument (observation + rewiring) for robust resolution of subconventions, which works by the dissolution of the stable frontiers caused by the Self-Reinforcing Substructures (SRS) within the social network.

Details DOI

AAMAS Conference 2012 Conference Paper

Opinion Convergence in Agent Networks

  • Sreerupa Chatterjee
  • Alexander Ruff
  • Sandip Sen

We empirically investigated the dynamics of opinion adaption on random networks, scale-free networks and regular lattice structures where agents adopt the opinion held by the majority of their direct neighbors only if the fraction of these exceed a certain laggard threshold [1]. We observed that either due to initial random distribution of opinion to agents or through opinion adaptation in the first few iterations, isolated pockets of agents with a different opinion than those of the surrounding population form and are sustained. Such population configurations thereafter converge to mixed or heterogeneous states. For certain values of the laggard threshold, we also observe a phase of uncertain convergence: for identical system parameters, the population will converge to homogeneous opinions whose value may be different for different random initializations. We identify the regions of consistent homogeneous convergence, heterogeneous convergence and uncertain homogeneous convergence for different values of the laggard threshold.

PDF

AAMAS Conference 2012 Conference Paper

Patterns of Migration and Adoption of Choices By Agents in Communities

  • Feyza Hafizoğlu
  • Sandip Sen

We study the migration and behavior adoption patterns of agents situated in geographically distributed communities. We consider agents with two types of states or opinions, binary and continuous. Agents either probabilistically adopt the predominant state in their community or migrate to another community more supportive of their state. We observe an interesting range of emerging population patterns based on different migration and adoption biases.

PDF

IJCAI Conference 2011 Conference Paper

Modeling the Emergence and Convergence of Norms

  • Logan Brooks
  • Wayne Iba
  • Sandip Sen

In many multi-agent systems, the emergence of norms is the primary factor that determines overall behavior and utility. Agent simulations can be used to predict and study the development of these norms. However, a large number of simulations is usually required to provide an accurate depiction of the agents' behavior, and some rare contingencies may still be overlooked completely. The cost and risk involvedwith agent simulations can be reduced by analyzing a system theoretically and producing models of its behavior. We use such a theoretical approach to examine the dynamics of a population of agents playing a coordination game to determine all the norms to which the society can converge, and develop a system of linear recurrence relations that predict how frequently each of these norms will be reached, as well as the average convergence time. This analysis produces certain guarantees about system behavior that canot be provided by a purely empirical approach, and can be used to make predictions about the emergence of norms that numerically match those obtained through large-scale simulations.

PDF Details DOI

AAMAS Conference 2011 Conference Paper

Modeling the Emergence of Norms

  • Logan Brooks
  • Wayne Iba
  • Sandip Sen

Norms or conventions can be used as external correlating signals to promote coordination between rational agents and hence have merited in-depth study of the evolution and economics of norms both in the social sciences and in multi-agent systems. While agent simulations can be used to gain a cursory idea of when and what norms can evolve, the estimations obtained by running simulations can be costly to obtain, provide no guarantees about the behavior of the system, and may overlook some rare occurrences. We use a theoretical approach to analyze a system of agents playing a convergence game and develop models that predict (a) how the system's behavior will change over time, (b) how much time it will take for it to converge to a stable state, and (c) how often the system will converge to a particular norm.

PDF

AAMAS Conference 2011 Conference Paper

Social Instruments for Convention Emergence

  • Daniel Villatoro
  • Jordi Sabater-Mir
  • Sandip Sen

In this paper we present the notion of Social Instruments as a set of mechanisms that facilitate the emergence of norms from repeated interactions between members of a society. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions when effectively addressing coordination and learning problems, paying special attention to dissolving metastable subconventions. Finally, we present a more sophisticated social instrument (observation + rewiring) for robust resolution of subconventions, which works dissolving SelfReinforcing Substructures (SRS) in the social network.

PDF

IJCAI Conference 2011 Conference Paper

Social Instruments for Robust Convention Emergence

  • Daniel Villatoro
  • Jordi Sabater-Mir
  • Sandip Sen

We present the notion of Social Instruments as mechanisms that facilitate the emergence of conventions from repeated interactions between members of a society. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions when effectively addressing coordination and learning problems, paying special attention to dissolving meta-stable subconventions. Initial experiments throw some light on how Self-Reinforcing Substructures (SRS) in the network prevent full convergence, resulting in reduced convergence rates. The use of an effective composed social instrument (observation + rewiring) allow agents to eliminate the subconventions that otherwise remained meta-stable.

PDF Details DOI

AAMAS Conference 2010 Conference Paper

Comprehensive Trust Management

  • Sandip Sen
  • Kuheli Chakraborty

Trust has been viewed as an integral component of agent decision making in the context of multiagent systems (MASs). Various formal and semi-formal trust schemes, motivatedby diverse considerations and influenced by various fields ofstudy, have been proposed, implemented, and evaluated. Webelieve that there still exists a pressing need for developinga comprehensive trust management scheme that addressesmost, if not all, issues underlying trust development, maintenance, and use. To facilitate the discussion of a generaland comprehensive trust management scheme, we provideour own operational definition of trust motivated by uncertainty management and utility optimization. We identifythe various components required of a comprehensive trustmanagement scheme and their roles in determining agentperformance in a competitive, open MAS.

PDF

ECAI Conference 2010 Conference Paper

On the stability of an Optimal Coalition Structure

  • Stéphane Airiau
  • Sandip Sen

The two main questions in coalition games are 1) what coalitions should form and 2) how to distribute the value of each coalition between its members. When a game is not superadditive, other coalition structures (CSs) may be more attractive than the grand coalition. For example, if the agents care about the total payoff generated by the entire society, CSs that maximize utilitarian social welfare are of interest. The search for such optimal CSs has been a very active area of research. Stability concepts have been defined for games with coalition structure, under the assumption that the agents agree first on a CS, and then the members of each coalition decide on how to share the value of their coalition. An agent can refer to the values of coalitions with agents outside of its current coalition to argue for a larger share of the coalition payoff. To use this approach, one can find the CS s ★ with optimal value and use one of these stability concepts for the game with s ★. However, it may not be fair for some agents to form s ★, e. g. , for those that form a singleton coalition and cannot benefit from collaboration with other agents. We explore the possibility of allowing side-payments across coalitions to improve the stability of an optimal CS. We adapt existing stability concepts and prove that some of them are non-empty under our proposed scheme.

Details

IJCAI Conference 2009 Conference Paper

  • Anil Gürsel
  • Sandip Sen

The popularity of social networks have burgeoned in recent years. Users share and access large volumes of information on social networking sites like Facebook, Flickr, del. icio. us, etc. Whereas a few of these sites have generic, impersonal searching mechanisms, we have developed an agent-based framework that mines the social network of a user to improve search results. Our Social Networkbased Item Search (SNIS) system uses agents that utilize the connections of a user in the social network to facilitate the search for items of interest. Our approach generates targeted search results that can improve the precision of the result returned from a user’s query. We have implemented the SNIS agent-based framework in Flickr, a photosharing social network, for searching for photos by using tag lists as search queries. We discuss the architecture of SNIS, motivate the searching scheme used, and demonstrate the effectiveness of the SNIS approach by presenting results. We also show how SNIS can be utilized for expertise location.

PDF Details

AAMAS Conference 2009 Conference Paper

Comparing Trust Mechanisms for Monitoring Aggregator Nodes in Sensor Networks

  • Oly Mistry
  • Anıl Gürsel
  • Sandip Sen

Sensor nodes are often used to collect data from locations inaccessible or hazardous for humans. As they are not under normal supervision, these nodes are particularly susceptible to physical damage or remote tampering. Generally, a hierarchical data collection scheme is used by the sensors to report data to the base station. It is difficult to precisely identify and eliminate a tampered node in such a data collecting hierarchy. Most security schemes for sensor networks focuses on developing mechanism for nodes located higher in the hierarchy to monitor those located at lower levels. We propose a complementary mechanism with which the nodes at lower levels can monitor their parents in the hierarchy to detect malicious behavior. Every node maintains a reputation value of its parent and updates this at the end of every data reporting cycle. We propose a novel combination of statistical testing techniques and existing reputation management and reinforcement learning schemes to manage the reputation of a parent node. The probability that the parent node is malicious is calculated using various combination of the Q-learning algorithm and the β-Reputation scheme. The input to the β-Reputation scheme is a history of boolean events consisting of correct or erroneous data reporting events by the parent node. The boolean events are generated at each data reporting period using statistical tests. Our approach can be viewed as a mechanism composed of different modules for the detection of a malicious event, interpretation of the malicious event and updating node reputation value based on the interpretation. We have created different versions of our system by varying these components. We compared the effectiveness of these alternative designs in detecting different types of malicious behavior in sensor networks.

PDF

AAMAS Conference 2009 Conference Paper

Effective Tag Mechanisms for Evolving Cooperation

  • Matt Matlock
  • Sandip Sen

Certain observable features (tags), shared by a group of similar agents, can be used to signal intentions and can be effectively used to infer unobservable properties. Such inference will enable the formulation of appropriate behaviors for interaction with those agents. Tags have been previously shown to be successful in social dilemma situations such as the prisoner’s dilemma, and more recently have been shown to be applicable to other games by augmenting the standard tag mechanisms. We examine these more general tag mechanisms, and explain previously reported results by more thoroughly examining their fundamental designs. We show that these new tag mechanisms, along with some adjustments and augmentations, can be effective in enabling stable, socially optimal, and fair cooperative outcomes to emerge in general sum games. We focus, in particular, on general-sum conflicted games, where socially optimal outcomes do not necessarily yield the best results for individual agents. We argue that the improvements and understanding of these mechanisms expands the usability of tag mechanisms for facilitating coordination in multiagent systems. We argue that they allow agents to effectively reuse knowledge learned form interactions with one agent when interacting with other agents sharing the same features.

PDF

AAMAS Conference 2009 Conference Paper

Producing Timely Recommendations From Social Networks Through Targeted Search

  • Anıl Gürsel
  • Sandip Sen

There has been a significant increase in interest and participation in social networking websites recently. For many users, social networks are indispensable tools for sharing personal information and keeping abreast with updates by their acquaintances. While there has been research on understanding the structure and effects of social networks, research on using social networks for developing targeted referral systems are few even though this can be valuable because of the abundance of information about user preferences, activities and choices. The goal of this research is to develop agent-based referral systems that learn user preferences based on past rating activities and caters to an individual user’s interests by selectively searching the contributions posted by other users in close proximity in this user’s social network. In particular, we are interested in fast notification of relevant activities in the social network that will enhance user awareness, satisfaction, and currency. In this paper, we propose keeping different trust values for a friend on different topics of interest and emphasize its importance with empirical results. We have developed an online photo referral system that identifies photos of possible interest to a user based on meta-data and comments on the pages of linked users on a popular photo sharing social website (flickr. com). We develop a probabilistic category determination mechanism that allows us to identify the possible categories an item belongs to by examining its tags. We use comments as an indirect measure of user preference for a photo. Empirical results show that our Social Network-based Item Recommendation (SNIR) system outperforms a content-based approach as well as the current recommendation schemes.

PDF

AAMAS Conference 2008 Conference Paper

Learning Task-Specific Trust Decisions

  • Ikpeme Erete
  • Erin Ferguson
  • Sandip Sen

We study the problem of agents locating other agents that are both capable and willing to help complete assigned tasks. An agent incurs a fixed cost for each help request it sends out. To minimize this cost, the performance metric used in our work, an agent should learn based on past interactions to identify agents likely to help on a given task. We compare three trust mechanisms: success-based, learning-based, and random. We also consider different agent social attitudes: selfish, reciprocative, and helpful. We evaluate the performance of these social attitudes with both homogeneous and mixed societies. Our results show that learning-based trust decisions consistently performed better than other schemes. We also observed that the success rate is significantly better for reciprocative agents over selfish agents.

PDF

AAMAS Conference 2008 Conference Paper

MB-AIM-FSI: A Model Based Framework for exploiting gradient ascent MultiAgent Learners in Strategic

  • Doran Chakraborty
  • Sandip Sen

Future agent applications will increasingly represent human users autonomously or semi-autonomously in strategic interactions with similar entities. Hence, there is a growing need to develop algorithmic approaches that can learn to recognize commonalities in opponent strategies and exploit such commonalities to improve strategic response. Recently a framework [9] has been proposed that aims for targeted optimality against a set of finite memory opponents. We propose an approach that aims for targeted optimality against the set of all possible multiagent learning algorithms that perform gradient search to select a single stage Nash Equilibria of a repeated game. Such opponents induce a Markov Decision Process as the learning environment and appropriate responses to such environments are learned by assuming a generative model of the environment. In the absence of a generative model, we present a framework, MB- AIM-FSI, that models the opponent online based on interactions, solves the model off-line when sufficient information has been gathered, stores the strategy in the repository and finally uses it judiciously when playing against the same or similar opponent at a later time.

PDF

AAMAS Conference 2008 Conference Paper

Norm Emergence Under Constrained Interactions in Diverse Societies

  • Partha Mukherjee
  • Stephane Airiau
  • Sandip Sen

Effective norms, emerging from sustained individual interactions over time, can complement societal rules and significantly enhance performance of individual agents and agent societies. Researchers have used a model that supports the emergence of social norms via learning from interaction experiences where each interaction is viewed as a stage game. In this social learning model, which is distinct from an agent learning from repeated interactions against the same player, an agent learns a policy to play the game from repeated interactions with multiple learning agents. The key research question is to characterize when and how the entire population of homogeneous learners converge to a consistent norm when multiple action combinations yield the same optimal payoff. In this paper we study two extensions to the social learning model that significantly enhances its applicability. We first explore the effects of heterogeneous populations where different agents may be using different learning algorithms. We also investigate norm emergence when agent interactions are physically constrained. We consider agents located on a grid where an agent is more likely to interact with other agents situated closer to it than those that are situated afar. The key new results include the surprising acceleration in learning with limited interaction ranges. We also study the effects of pure-strategy players, i. e. , nonlearners in the environment.

PDF

IJCAI Conference 2007 Conference Paper

  • Sandip Sen
  • St
  • eacute; phane Airiau

Behavioral norms are key ingredients that allow agent coordination where societal laws do not sufficiently constrain agent behaviors. Whereas social laws need to be enforced in a top-down manner, norms evolve in a bottom-up manner and are typically more self-enforcing. While effective norms can significantly enhance performance of individual agents and agent societies, there has been little work in multiagent systems on the formation of social norms. We propose a model that supports the emergence of social norms via learning from interaction experiences. In our model, individual agents repeatedly interact with other agents in the society over instances of a given scenario. Each interaction is framed as a stage game. An agent learns its policy to play the game over repeated interactions with multiple agents. We term this mode of learning social learning, which is distinct from an agent learning from repeated interactions against the same player. We are particularly interested in situations where multiple action combinations yield the same optimal payoff. The key research question is to find out if the entire population learns to converge to a consistent norm. In addition to studying such emergence of social norms among homogeneous learners via social learning, we study the effects of heterogeneous learners, population size, multiple social groups, etc.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Teddy Candale
  • Sandip Sen

Bidding for multi-items in simultaneous auctions raises challenging problems. In multi-auction settings, the determination of optimal bids by potential buyers requires combinatorial calculations. While an optimal bidding strategy is known when bidding in sequential auctions, only suboptimal strategies are available when bidding for items being sold in simultaneous auctions. We investigate a multi-dimensional bid improvement scheme, motivated by optimization techniques, to derive optimal bids for item bundles in simultaneous auctions. Given a vector of initial bids, the proposed scheme systematically improves bids for each item. Such multi-dimensional improvements result in locally optimal bid vectors. Globally optimal bid vectors are guaranteed in the limit for infinite restarts. For ease of presentation we use two-item scenarios to explain the working of the algorithm. Experimental results show polynomial complexity of variants of this algorithm under different types of bidder valuations for item bundles.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Sabyasachi Saha
  • Sandip Sen

We study the problem of autonomous agents negotiating the allocation of multiple indivisible resources. It is difficult to reach optimal outcomes in bilateral or multi-lateral negotiations over multiple resources when the agents' preferences for the resources are not common knowledge. Self-interested agents often end up negotiating inefficient agreements in such situations. We present a protocol for negotiation over multiple indivisible resources which can be used by rational agents to reach efficient outcomes. Our proposed protocol enables the negotiating agents to identify efficient solutions using systematic distributed search that visits only a subspace of the whole solution space.

PDF Details

AAMAS Conference 2007 Conference Paper

Computing effective communication policies in multiagent systems

  • Doran Chakraborty
  • Sandip Sen

Communication is a key tool for facilitating multiagent coordination in cooperative and uncertain domains. We focus on a class of multiagent problems modeled as Decentralized Markov Decision Processes with Communication (DEC-MDP-COM) with local observability. The planning problem for computing the optimal communication strategy in such domains is often formulated with the assumption of the knowledge of optimal domain-level policy. Computing the optimal communication policy is NP-complete. There is a need, then, for heuristic solutions that trade-off performance with efficiency. We present a decision theoretic approach for computing optimal communication policies in stochastic environments which uses a branching future representation and evaluates only those decisions that an agent is likely to encounter. The communication strategy computed off-line is used in the more probable scenarios that the agent would face in future. Our approach also allows agents to compute communication policies at run-time in the unlikely event of the agents facing scenarios that were discarded while computing the off-line policy.

PDF

AAMAS Conference 2007 Conference Paper

Distributed Intrusion Detection in Partially Observable Markov Decision Processes

  • Doran Chakraborty
  • Sandip Sen

The problem of decentralized control occurs frequently in realistic domains where agents have to cooperate to achieve a universal goal. Planning for domain-level joint strategy takes into account the uncertainty of the underlying environment in computing near-optimal joint-strategies that can handle the intrinsic domain uncertainty. However, uncertainty related to agents deviating from the recommended joint-policy is not taken into consideration. We focus on hostile domains, where the goal is to quickly identify deviations from planned behavior by any compromised agents. There is a growing need to develop techniques that enable the system to recognize and recover from such deviations. We discuss the problem from the intruder's perspective and then present a distributed intrusion detection scheme that can detect a particular type of attack.

PDF

AAMAS Conference 2007 Conference Paper

Effective Tag Mechanisms for Evolving Coordination

  • Matthew Matlock
  • Sandip Sen

Tags or observable features shared by a group of similar agents are effectively used in real and artificial societies to signal intentions and can be used to infer unobservable properties and choose appropriate behaviors. Use of tags to select partners has been shown to produce stable cooperation in agent populations playing the Prisoner's Dilemma game. Existing tag mechanisms, however, can promote cooperation only if that requires identical actions from all group members. We propose a more general tag-based interaction scheme that facilitates and supports significantly richer coordination between agents. Our work is motivated by previous research that showed the ineffectiveness of current tag schemes for solving games requiring divergent actions. The mechanisms proposed here not only solves those problems but are effective for other general-sum games. We argue that these general-purpose tag mechanisms allow new application possibilities of multiagent learning algorithms as they allow an agent to reuse its learned knowledge about one agent when interacting with other agents sharing the same observable features.

PDF

JAAMAS Journal 2007 Journal Article

Reaching pareto-optimality in prisoner’s dilemma using conditional joint action learning

  • Dipyaman Banerjee
  • Sandip Sen

Abstract We consider the learning problem faced by two self-interested agents repeatedly playing a general-sum stage game. We assume that the players can observe each other’s actions but not the payoffs received by the other player. The concept of Nash Equilibrium in repeated games provides an individually rational solution for playing such games and can be achieved by playing the Nash Equilibrium strategy for the single-shot game in every iteration. Such a strategy, however can sometimes lead to a Pareto-Dominated outcome for games like Prisoner’s Dilemma. So we prefer learning strategies that converge to a Pareto-Optimal outcome that also produces a Nash Equilibrium payoff for repeated two-player, n-action general-sum games. The Folk Theorem enable us to identify such outcomes. In this paper, we introduce the Conditional Joint Action Learner (CJAL) which learns the conditional probability of an action taken by the opponent given its own actions and uses it to decide its next course of action. We empirically show that under self-play and if the payoff structure of the Prisoner’s Dilemma game satisfies certain conditions, a CJAL learner, using a random exploration strategy followed by a completely greedy exploitation technique, will learn to converge to a Pareto-Optimal solution. We also show that such learning will generate Pareto-Optimal payoffs in a large majority of other two-player general sum games. We compare the performance of CJAL with that of existing algorithms such as WOLF-PHC and JAL on all structurally distinct two-player conflict games with ordinal payoffs.

Details DOI

AAMAS Conference 2007 Conference Paper

Reciprocal Negotiation Over Shared Resources in Agent Societies

  • Sabyasachi Saha
  • Sandip Sen

We are interested in domains where an agent repeatedly negotiates with other agents over shared resources where the demand or utility to the agent for the shared resources vary over time. We propose a protocol that will maximize social welfare if agents reveal their true preferences in every negotiation. The protocol, however, is not truth-revealing and selfish agents have the incentive to artificially inflate preferences. We use a probabilistic reciprocative behavior that discourages the reporting of false preferences. This reciprocative behavior promotes cooperation in repeated negotiations and improves both individual and group longterm payoff. We characterize environmental conditions under which agents can develop and sustain mutually beneficial relationships with similar agents and avoid exploitation by different types of selfish agents.

PDF

AAAI Conference 2005 Conference Paper

Profit Sharing Auction

  • Sandip Sen

Auctions are a class of multi-party negotiation protocols. Classical auctions try to maximize social welfare by selecting the highest bidder as the winner. If bidders are rational, this ensures that the sum of profits for all bidders and the seller is maximized. In all such auctions, however, only the winner and the seller make any profit. We believe that “social welfare distribution” is a desired goal of any multi-party protocol. In the context of auctions, this goal translates into a rather radical proposal of profit sharing between all bidders and the seller. We propose a Profit Sharing Auction (PSA) where a part of the selling price paid by the winner is paid back to the bidders. The obvious criticism of this mechanism is the incentive for the seller to share its profit with nonwinning bidders. We claim that this loss can be compensated by attracting more bidders to such an auction, resulting in an associated increase in selling price. We run several sets of experiments where equivalent items are concurrently sold at a First Price Sealed Bid, a Vickrey, and a PSA auction. A population of learning bidders repeatedly choose to go to one of these auctions based on their valuation for the good being auctioned and their learned estimates of profits from these auctions. Results show that sellers make more or equivalent profits by using PSA as compared to the classical auctions. Additionally, PSA always attracts more bidders, which might create auxiliary revenue streams, and a desirable lower variability in selling prices. Interestingly then, a rational seller has the incentive to share profits and offer an auction like PSA which maximizes and distributes social welfare.

PDF Details

AAAI Conference 2004 Short Paper

A Bayes Net Approach to Argumentation

  • Sabyasachi Saha
  • Sandip Sen

Argumentation-based negotiation approaches have been proposed to present realistic negotiation contexts. This paper presents a novel Bayesian network based argumentation and decision making framework that allows agents to utilize models of other agents. Our goal is to use Bayesian networks to capture the opponent model through an incremental learning process and use the model to generate more effective arguments to convince the opponent to accept favorable contracts.

PDF Details

IJCAI Conference 1995 Conference Paper

A genetic prototype learner

  • Sandip Sen
  • Leslie Knight

Supervised classification problems have received considerable attention from the machine learning community. We propose a novel genetic algorithm based prototype learning system, PLEASE, for this class of problems. Given a set of prototypes for each of the possible classes, the class of an input instance is determined by the prototype nearest to this instance. We assume ordinal attributes and prototypes are represented as sets of feature-value pairs. A genetic algorithm is used to evolve the number of prototypes per class and their positions on the input space as determined by corresponding feature-value pairs. Comparisons with C4. 5 on a set of artificial problems of controlled complexity demonstrate the effectiveness of the proposed system.

PDF

AAAI Conference 1994 Conference Paper

Learning to Coordinate without Sharing Information

  • Sandip Sen

Researchers in the field of Distributed Artificial Intelligence (DAI) h ave been developing efficient mechanisms to coordinate the activities of multiple autonomous agents. The need for coordination arises because agents have to share resources and expertise required to achieve their goals. Previous work in the area includes using sophisticated information exchange protocols, investigating heuristics for negotiation, and developing formal models of possibilities of conflict and cooperation among agent interests. In order to handle the changing requirements of continuous and dynamic environments, we propose learning as a means to provide additional possibilities for effective coordination. We use reinforcement learning techniques on a block pushing problem to show that agents can learn complimentary policies to follow a desired path without any knowledge about each other. We theoretically analyze and experimentally verify the effects of learning rate on system convergence, and demonstrate benefits of using learned coordination knowledge on similar problems. Reinforcement learning based coordination can be achieved in both cooperative and non-cooperative domains, and in domains with noisy communication channels and other stochastic characteristics that present a formidable challenge to using other coordination schemes.

PDF Details