Author name cluster
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.
AAMAS Conference 2025 Conference Paper
In this work we present the idea of partitioning contestants into disjoint groups, each competing in an independent contest, with its own prize. We focus on binary contests, wherein contestants choose whether or not to participate, and show that such contest partitioning can benefit the organizer running the contest when partitioning entails a cost.
JAAMAS Journal 2024 Journal Article
Abstract In this work we explore the opportunities presented by partitioning contestants in contest into disjoint groups, each competing in an independent contest, with its own prize. This, as opposed to most literature on contest design, which focuses on the setting of a single “grand” (possibly multi-stage) contest, wherein all potential contestants ultimately compete for the same prize(s), with few exceptions that do consider contest partitioning, yet with conflicting preference results concerning the optimal structure to be used. Focusing on binary contests, wherein the quality of contestants’ submissions are endogenously determined, we show that contest partitioning is indeed beneficial under some condition, e. g. , whenever the number of contestants, or the prize amount, are “sufficiently large”, where the exact size requirements are a function of the partitioning cost. When partitioning does not entail any cost, we show that it is either a dominating or weakly dominating strategy, depending on the way the organizer’s expected benefit is determined. The analysis is further extended to consider partitioning where some of the sub-contests used contain a single contestant (a singleton). We conclude that contest partitioning is an avenue that contest designers can and should consider, when aiming to maximize their profit.
AAAI Conference 2024 Conference Paper
This paper focuses in the inherent anchoring bias present in sequential reviews-sentiment corpora annotation processes. It proposes employing a limited subset of meticulously chosen reviews at the outset of the process, as a means of calibration, effectively mitigating the phenomenon. Through extensive experimentation we validate the phenomenon of sentiment bias in the annotation process and show that its magnitude can be influenced by pre-calibration. Furthermore, we show that the choice of the calibration set matters, hence the need for effective guidelines for choosing the reviews to be included in it. A comparison of annotators performance with the proposed calibration to annotation processes that do not use calibration or use a randomly-picked calibration set, reveals that indeed the calibration set picked is highly effective---it manages to substantially reduce the average absolute error compared to the other cases. Furthermore, the proposed selection guidelines are found to be highly robust in picking an effective calibration set also for domains different than the one based on which these rules were extracted.
ECAI Conference 2023 Conference Paper
In recent years, autonomous agents have been increasingly handling decision tasks on behalf of their human users. One such type of task with much potential to be carried out by an assisting autonomous agent is optimal stopping (e. g. , in costly search). In such case, when it is the agent’s responsibility to decide when to terminate search, the challenge of maximizing user satisfaction with the process becomes acute. This paper provides evidence for the loose correlation between agent performance, profit-wise, and user satisfaction in this application domain, ruling out the use of the profit-maximizing strategy. As an alternative, it proposes a strategy relying on behavioral features. An extensive comparative evaluation of the proposed strategy, as well as the profit-maximizing strategy and the highest ranked strategy elicited through crowdsourcing reveals that the average satisfaction with the first is substantially greater than when experiencing with the others. The analysis of the results also reveals several important insights related to people’s ability to estimate the effectiveness of search strategies, satisfaction-wise, or propose such strategies themselves, contributing to the study of how human beings deal with optimal stopping problems in practice.
EUMAS Conference 2022 Conference Paper
Abstract Designing and implementing explainable systems is seen as the next step towards increasing user trust in, acceptance of and reliance on Artificial Intelligence (AI) systems. While explaining choices made by black-box algorithms such as machine learning and deep learning has occupied most of the limelight, systems that attempt to explain decisions (even simple ones) in the context of social choice are steadily catching up. In this paper, we provide a comprehensive survey of explainability in mechanism design, a domain characterized by economically motivated agents and often having no single choice that maximizes all individual utility functions. We discuss the main properties and goals of explainability in mechanism design, distinguishing them from those of Explainable AI in general. This discussion is followed by a thorough review of the challenges one may face when working on Explainable Mechanism Design and propose a few solution concepts to those.
AAMAS Conference 2022 Conference Paper
In many social-choice mechanisms the resulting choice is not the most preferred one for some of the participants, thus the need for methods to justify the choice made in a way that improves the acceptance and satisfaction of said participants. One natural method for providing such explanations is to ask people to provide them, e. g. , through crowdsourcing, and choosing the most convincing arguments among those received. In this paper we propose the use of an alternative approach, one that automatically generates explanations based on desirable mechanism features found in theoretical mechanism design literature. We test the effectiveness of both of the methods through a series of extensive experiments conducted with over 600 participants in ranked voting, a classic social choice mechanism. The analysis of the results reveals that explanations indeed affect both average satisfaction from and acceptance of the outcome in such settings. In particular, explanations are shown to have a positive effect on satisfaction and acceptance when the outcome (the winning candidate in our case) is the least desirable choice for the participant. A comparative analysis reveals that the automatically generated explanations result in similar levels of satisfaction from and acceptance of an outcome as with the more costly alternative of crowdsourced explanations, hence eliminating the need to keep humans in the loop. Furthermore, the automatically generated explanations significantly reduce participants’ belief that a different winner should have been elected compared to crowdsourced explanations.
JAAMAS Journal 2021 Journal Article
Abstract The recent massive proliferation of affiliate marketing suggests a new e-commerce paradigm which involves sellers, affiliates and the platforms that connect them. In particular, the fact that prospective buyers may become acquainted with the promotion through more than one affiliate to whom they are connected calls for new mechanisms for compensating affiliates for their promotional efforts. In this paper, we study the problem of a platform that needs to decide on the commission to be awarded to affiliates for promoting a given product or service. Our equilibrium-based analysis, which applies to the case where affiliates are a priori homogeneous and self-interested, enables showing that a minor change in the way the platform discloses information to the affiliates results in a tremendous (positive) effect on the platform’s expected profit. In particular, we show that with the revised mechanism the platform can overcome the multi-equilibria problem that arises in the traditional mechanism and obtain a profit which is at least as high as the maximum profit in any of the equilibria that hold in the latter.
IJCAI Conference 2020 Conference Paper
This paper suggests a new paradigm for the design of collaborative autonomous agents engaged in executing a joint task alongside a human user. In particular, we focus on the way an agent's failures should affect its decision making, as far as user satisfaction measures are concerned. Unlike the common practice that considers agent (and more broadly, system) failures solely in the prism of their influence over the agent's contribution to the execution of the joint task, we argue that there is an additional, direct, influence which cannot be fully captured by the above measure. Through two series of large-scale controlled experiments with 450 human subjects, recruited through Amazon Mechanical Turk, we show that, indeed, such direct influence holds. Furthermore, we show that the use of a simple agent design that takes into account the direct influence of failures in its decision making yields considerably better user satisfaction, compared to an agent that focuses exclusively on maximizing its absolute contribution to the joint task.
IJCAI Conference 2020 Conference Paper
This paper suggests a new paradigm for the design of collaborative autonomous agents engaged in executing a joint task alongside a human user. In particular, we focus on the way an agent's failures should affect its decision making, as far as user satisfaction measures are concerned. Unlike the common practice that considers agent (and more broadly, system) failures solely in the prism of their influence over the agent's contribution to the execution of the joint task, we argue that there is an additional, direct, influence which cannot be fully captured by the above measure. Through two series of large-scale controlled experiments with 450 human subjects, recruited through Amazon Mechanical Turk, we show that, indeed, such direct influence holds. Furthermore, we show that the use of a simple agent design that takes into account the direct influence of failures in its decision making yields considerably better user satisfaction, compared to an agent that focuses exclusively on maximizing its absolute contribution to the joint task.
JAAMAS Journal 2020 Journal Article
Abstract A principal needs to elicit the true value of an object she owns from an agent who has a unique ability to compute this information. The principal cannot verify the correctness of the information, so she must incentivize the agent to report truthfully. Previous works coped with this unverifiability by employing two or more information agents and awarding them according to the correlation between their reports. We show that, in a common value setting, the principal can elicit the true information even from a single information agent, and even when computing the value is costly for the agent. Moreover, the principal’s expense is only slightly higher than the cost of computing the value. For this purpose we provide three alternative mechanisms, all providing the same above guarantee, highlighting the advantages and disadvantages in each. Extensions of the basic mechanism include adaptations for cases such as when the principal and the agent value the object differently, when the object is divisible and when the agent’s cost of computation is unknown. Finally, we deal with the case where delivering the information to the principal incurs a cost. Here we show that substantial savings can be obtained in a multi-object setting.
AAMAS Conference 2019 Conference Paper
AAAI Conference 2019 Conference Paper
Information plays a key role in many decision situations. The rapid advancement in communication technologies makes information providers more accessible, and various information providing platforms can be found nowadays, most of which are strategic in the sense that their goal is to maximize the providers’ expected profit. In this paper, we consider the common problem of a strategic information provider offering prospective buyers information which can disambiguate uncertainties the buyers have, which can be valuable for their decision making. Unlike prior work, we do not limit the information provider’s strategy to price setting but rather enable her flexibility over the way information is sold, specifically enabling querying about specific outcomes and the elimination of a subset of non-true world states alongside the traditional approach of disclosing the true world state. We prove that for the case where the buyer is self-interested (and the information provider does not know the true world state beforehand) all three methods (i. e. , disclosing the true worldstate value, offering to check a specific value, and eliminating a random value) are equivalent, yielding the same expected profit to the information provider. For the case where buyers are human subjects, using an extensive set of experiments we show that the methods result in substantially different outcomes. Furthermore, using standard machine learning techniques the information provider can rather accurately predict the performance of the different methods for new problem settings, hence substantially increase profit.
AAMAS Conference 2019 Conference Paper
AAMAS Conference 2019 Conference Paper
IJCAI Conference 2019 Conference Paper
This paper studies the benefit in using signaling by an information seller holding information that can completely disambiguate some uncertainty concerning the state of the world for the information buyer. We show that a necessary condition for having the information seller benefit from signaling in this model is having some ``seed of truth" in the signaling scheme used. We then introduce two natural signaling mechanisms that adhere to this condition, one where the seller pre-commits to the signaling scheme to be used and the other where she commits to use a signaling scheme that contains a ``seed of truth". Finally, we analyze the equilibrium resulting from each and show that, somehow counter-intuitively, despite the inherent differences between the two mechanisms, they are equivalent in the sense that for any equilibrium associated with the maximum revenue in one there is an equilibrium offering the seller the same revenue in the other.
JAAMAS Journal 2019 Journal Article
Abstract Intelligent agents and AI-based systems are becoming increasingly prevalent. They support people in different ways, such as providing users with advice, working with them to achieve goals or acting on users’ behalf. One key capability missing in such systems is the ability to present their users with an effective summary of their strategy and expected behaviors under different conditions and scenarios. This capability, which we see as complementary to those currently under development in the context of “interpretable machine learning” and “explainable AI”, is critical in various settings. In particular, it is likely to play a key role when a user needs to collaborate with an agent, when having to choose between different available agents to act on her behalf, or when requested to determine the level of autonomy to be granted to an agent or approve its strategy. In this paper, we pose the challenge of developing capabilities for strategy summarization, which is not addressed by current theories and methods in the field. We propose a conceptual framework for strategy summarization, which we envision as a collaborative process that involves both agents and people. Last, we suggest possible testbeds that could be used to evaluate progress in research on strategy summarization.
IJCAI Conference 2019 Conference Paper
We study temporal information design in contests, wherein the organizer may, possibly incrementally, disclose information about the participation and performance of some contestants to other (later) contestants. We show that such incremental disclosure can increase the organizer's profit. The expected profit, however, depends on the exact information disclosure structure, and the optimal structure depends on the parameters of the problem. We provide a game-theoretic analysis of such information disclosure schemes as they apply to two common models of contests: (a) simple contests, wherein contestants' decisions concern only their participation; and (b) Tullock contests, wherein contestants choose the effort levels to expend. For each of these we analyze and characterize the equilibrium strategy, and exhibit the potential benefits of information design.
AAMAS Conference 2018 Conference Paper
Intelligent agents and AI-based systems are becoming increasingly prevalent. They support people in different ways, such as providing users with advice, working with them to achieve goals or acting on users’ behalf. One key capability missing in such systems is the ability to present their users with an effective summary of their strategy and expected behaviors under different conditions and scenarios. This capability, which we see as complimentary to those currently under development in the context of “interpretable machine learning” and “explainable AI”, is critical in various settings. In particular, it is likely to play a key role whenever a user needs to understand the strategy of an agent she is working along with, when having to choose between different available agents to act on her behalf, or when requested to determine the level of autonomy to be granted to the agent or approve its strategy. In this paper, we pose the challenge of developing capabilities for strategy summarization, which is not addressed by current theories and methods in the field. We propose a conceptual framework for strategy summarization, which we envision as a collaborative process that involves both agents and people. Last, we suggest possible testbeds that could be used to evaluate progress in research on strategy summarization.
AAMAS Conference 2018 Conference Paper
AAMAS Conference 2018 Conference Paper
In this paper we introduce and experimentally evaluate a new suboptimal decision-making design to be used by autonomous agents acting on behalf of a user in repeated tasks, whenever the agent’s autonomy level is continuously controlled by the user. This mode of operation is common and can be found whenever user’s perception of the agent’s competence is affected by the nature of the outcomes resulting from the agent’s decisions rather than the optimality of the decisions made, e. g. , in spam filtering, CV filtering, poker agents, and robotic vacuum cleaners as well as in newly arriving systems such as autonomous cars. Our proposed design relies on choosing the action that offers the best tradeoff between decision optimality and the influence over future allowed autonomy, where the latter is predicted using standard machine learning techniques. The design is found to be highly effective compared to following the theoreticoptimal decision rule, over various measures, through extensive experimentation with a virtual investment agent, making virtual investments on behalf of 679 subjects using Amazon Mechanical Turk.
AAMAS Conference 2018 Conference Paper
IJCAI Conference 2018 Conference Paper
Much of the work on multi-agent contests is focused on determining the equilibrium behavior of contestants. This capability is essential for the principal for choosing the optimal parameters for the contest (e. g. prize amount). As it turns out, many contests exhibit not one, but many possible equilibria, hence precluding contest design optimization and contestants behavior prediction. In this paper we examine a variation of the classic contest that alleviates this problem by having contestants make the decisions sequentially rather than in parallel. We study this model in the setting of a simple contest, wherein contestants only choose whether or not to participate, while their performance level is exogenously set. We show that by switching to the revised mechanism the principal can not only force her most desired pure-strategies based equilibrium to emerge, but also, at times, end up with an equilibrium offering a greater expected profit. Further, we show that in the modified contest the optimal prize can be effectively computed. The theoretical analysis is complemented by comprehensive experiments with people over Amazon Mechanical Turk. Here, we find that the modified mechanism offers great benefit for the principal, both in terms of an increased over-participation in the contest (compared to theoretical expectations) and increased average profit.
AAAI Conference 2018 Conference Paper
One key motivation for using contests in real-life is the substantial evidence reported in empirical contest-design literature for people’s tendency to act more competitively in contests than predicted by the Nash Equilibrium. This phenomenon has been traditionally explained by people’s eagerness to win and maximize their relative (rather than absolute) payoffs. In this paper we make use of “simple contests”, where contestants only need to strategize on whether to participate in the contest or not, as an infrastructure for studying whether indeed more effort is exerted in contests due to competitiveness, or perhaps this can be attributed to other factors that hold also in non-competitive settings. The experimental methodology we use compares contestants’ participation decisions in eight contest settings differing in the nature of the contest used, the number of contestants used and the theoretical participation predictions to those obtained (whenever applicable) by subjects facing equivalent non-competitive decision situations in the form of a lottery. We show that indeed people tend to over-participate in contests compared to the theoretical predictions, yet the same phenomenon holds (to a similar extent) also in the equivalent non-competitive settings. Meaning that many of the contests used nowadays as a means for inducing extra human effort, that are often complex to organize and manage, can be replaced by a simpler non-competitive mechanism that uses probabilistic prizes.
IJCAI Conference 2017 Conference Paper
This paper studies the problem of designing contests for settings where a principal seeks to optimize the quality of the best performance obtained, and potential contestants only strategize about whether to participate in the contest, as participation incurs some cost. This type of contest can be mapped to various real-life settings (e. g. , an audition, a beauty pageant, technology crowdsourcing). The paper provides a comparative game-theoretic based solution to two variants of the above underlying model: parallel and sequential contest, enabling a characterization of the equilibrium strategies in each. Special emphasis is placed on the case where the contestants are homogeneous which is often the case in real-life whenever the contestants are basically alike and their ranking in the contest is mostly influenced by some probabilistic factors (e. g. , luck). Here, several (somehow counter-intuitive) properties of the equilibrium are proved, in particular for the sequential contest, leading to a comprehensive characterization of the principal preference between the two.
IJCAI Conference 2017 Conference Paper
This paper presents methods for improving the attention span of workers in tasks that heavily rely on their attention to the occurrence of rare events. The underlying idea in our approach is to dynamically augment the task with some dummy (artificial) events at different times throughout the task, rewarding the worker upon identifying and reporting them. The proposed approach is an alternative to the traditional approach of exclusively relying on rewarding the worker for successfully identifying the event of interest itself. We propose three methods for timing the dummy events throughout the task. Two of these methods are static and determine the timing of the dummy events at random or uniformly throughout the task. The third method is dynamic and uses the identification (or misidentification) of dummy events as a signal for the worker's attention to the task, adjusting the rate of dummy events generation accordingly.
AAAI Conference 2017 Conference Paper
This paper studies a criteria-based mechanism for nurturing and enhancing agents’ group-benefiting individual efforts whenever the agents are self-interested. The idea is that only those agents that meet the criteria get to benefit from the group effort, giving an incentive to contribute even when it is otherwise individually irrational. Specifically, the paper provides a comprehensive equilibrium analysis of a thresholdbased criteria mechanism for the common cooperative information gathering application, where the criteria is set such that only those whose contribution to the group is above some pre-specified threshold can benefit from the contributions of others. The analysis results in a closed form solution for the strategies to be used in equilibrium and facilitates the numerical investigation of different model properties as well as a comparison to the dual mechanism according to only an agent whose contribution is below the specified threshold gets to benefit from the contributions of others. One important contribution enabled through the analysis provided is in showing that, counter-intuitively, for some settings the use of the above-threshold criteria is outperformed by the use of the below-threshold criteria as far as collective and individual performance is concerned.
JAAMAS Journal 2017 Journal Article
Abstract This paper studies the strategic behavior of platforms that provide agents easier access to the type of opportunities in which they are interested (e. g. , eCommerce platforms, used cars bulletins and dating web-sites). We show that under four common service schemes, a platform can benefit from not necessarily listing all the opportunities with which it is familiar, even if there is no marginal cost for listing any additional opportunity. The main implication of this result is that platforms should take the subset of opportunities to be included in their listings as a decision variable, alongside the fees set for the service in their expected-profit “maximizing” optimization problem. We show that none of the four schemes generally dominates any of the others or is dominated by any. For the case of homogeneous preferences, however, several dominance relationships can be proved. Furthermore, the analysis provides a game-theoretic search-based explanation for a possible preference of buyers to pay for the service rather than receive it for free (e. g. , when the service is sponsored by ads). The paper shows that this preference can hold both for the users and the platform simultaneously in a given setting, even if both sides are fully strategic. Finally, the paper analyzes the potential improvement in the platform’s expected profit that can be achieved by considering hybrid service schemes that combine the basic ones. In particular, we focus in the Two-Part Tariff scheme that combines the two commonly used subscription and pay-per-click schemes.
AAAI Conference 2017 Conference Paper
With the increasing interest in the role information providers play in multi-agent systems, much effort has been dedicated to analyzing strategic information disclosure and signaling by such agents. This paper analyzes the problem in the context of auctions (specifically for second-price auctions). It provides an equilibrium analysis to the case where the information provider can use signaling according to some precommitted scheme before introducing its regular (costly) information selling offering. The signal provided, publicly discloses (for free) some of the information held by the information provider. Providing the signaling is thus somehow counter intuitive as the information provider ultimately attempts to maximize her gain from selling the information she holds. Still, we show that such signaling capability can be highly beneficial for the information provider and even improve social welfare. Furthermore, the examples provided demonstrate various possible other beneficial behaviors available to the different players as well as to a market designer, such as paying the information provider to leave the system or commit to a specific signaling scheme. Finally, the paper provides an extension of the underlying model, related to the use of mixed signaling strategies.
AAAI Conference 2017 Conference Paper
This paper studies the benefit for information providers in free public information disclosure in settings where the prospective information buyers are people. The underlying model, which applies to numerous real-life situations, considers a standard decision making setting where the decision maker is uncertain about the outcomes of her decision. The information provider can fully disambiguate this uncertainty and wish to maximize her profit from selling such information. We use a series of AMT-based experiments with people to test the benefit for the information provider from reducing some of the uncertainty associated with the decision maker’s problem, for free. Free information disclosure of this kind can be proved to be ineffective when the buyer is a fullyrational agent. Yet, when it comes to people we manage to demonstrate that a substantial improvement in the information provider’s profit can be achieved with such an approach. The analysis of the results reveals that the primary reason for this phenomena is people’s failure to consider the strategic nature of the interaction with the information provider. Peoples’ inability to properly calculate the value of information is found to be secondary in its influence.
JAAMAS Journal 2016 Journal Article
Abstract The plethora of comparison shopping agents (CSAs) in today’s markets enables buyers to query more than a single CSA when shopping, thus expanding the list of sellers whose prices they obtain. This potentially decreases the chance of a purchase within any single interaction between a buyer and a CSA, and consequently decreases each CSAs’ expected revenue per-query. Obviously, a CSA can improve its competence in such settings by acquiring more sellers’ prices, potentially resulting in a more attractive “best price”. In this paper we suggest a complementary approach that improves the attractiveness of the best result returned based on intelligently controlling the order according to which they are presented to the user, in a way that utilizes several known cognitive-biases of human buyers. The advantage of this approach is in its ability to affect the buyer’s tendency to terminate her search for a better price, hence avoid querying further CSAs, without spending valuable resources on finding additional prices to present. The effectiveness of our method is demonstrated using real data, collected from four CSAs for five products. Our experiments confirm that the suggested method effectively influence people in a way that is highly advantageous to the CSA compared to the common method for presenting the prices. Furthermore, we experimentally show that all of the components of our method are essential to its success.
AAAI Conference 2016 Conference Paper
This paper studies two suboptimal advice provisioning methods (“advisors”) as an alternative to providing optimal advice in repeated advising settings. Providing users with suboptimal advice has been reported to be highly advantageous whenever the optimal advice is non-intuitive, hence might not be accepted by the user. Alas, prior methods that rely on suboptimal advice generation were designed primarily for a single-shot advice provisioning setting, hence their performance in repeated settings is questionable. Our methods, on the other hand, are tailored to the repeated interaction case. Comprehensive evaluation of the proposed methods, involving hundreds of human participants, reveals that both methods meet their primary design goal (either an increased user profit or an increased user satisfaction from the advisor), while performing at least as good with the alternative goal, compared to having people perform with: (a) no advisor at all; (b) an advisor providing the theoretic-optimal advice; and (c) an effective suboptimal-advice-based advisor designed for the non-repeated variant of our experimental framework.
JAAMAS Journal 2015 Journal Article
Abstract This paper studies to what extent agent development changes one’s own strategy. While this question has many general implications it is of special interest to the study of peer designed agents (PDAs), which are computer agents developed by non-experts. This latter emerging technology, has been widely advocated in recent literature for the purpose of replacing people in simulations and investigating human behavior. Its main premise is that strategies programmed into these agents reliably reflect, to some extent, the behavior used by their programmers in real life. We show that PDA development has an important side effect that has not been addressed to date—the process that merely attempts to capture one’s strategy is also likely to affect the developer’s strategy. This result has many implications concerning the appropriate design of PDA-based simulations as well as the validity of using PDAs for studying individual decision making. The phenomenon is demonstrated experimentally, using two very different application domains and several performance measures. Our findings suggest that the effects on one’s strategy arise both in situations where it is potentially possible for people to reason about the optimal strategy (in which case PDA development will enhance the use of an optimal strategy) and in those where calculating the optimal strategy is computationally challenging (in which case PDA development will push people to use more effective strategies, on average). Since in our experiments PDA development actually improved the developer’s strategy, PDA development can be suggested as a means for improving people’s problem solving skills. Finally, we show that the improvement achieved in people’s strategies through agent development is not attributed to the expressive aspect of agent development per-se but rather there is a crucial additional gain in the process of designing and programming ones strategy into an agent.
JAIR Journal 2015 Journal Article
This paper considers the problem of cooperation between self-interested agents in acquiring better information regarding the nature of the different options and opportunities available to them. By sharing individual findings with others, the agents can potentially achieve a substantial improvement in overall and individual expected benefits. Unfortunately, it is well known that with self-interested agents equilibrium considerations often dictate solutions that are far from the fully cooperative ones, hence the agents do not manage to fully exploit the potential benefits encapsulated in such cooperation. In this paper we introduce, analyze and demonstrate the benefit of five methods aiming to improve cooperative information gathering. Common to all five that they constrain and limit the information sharing process. Nevertheless, the decrease in benefit due to the limited sharing is outweighed by the resulting substantial improvement in the equilibrium individual information gathering strategies. The equilibrium analysis given in the paper, which, in itself is an important contribution to the study of cooperation between self-interested agents, enables demonstrating that for a wide range of settings an improved individual expected benefit is achieved for all agents when applying each of the five methods.
JAAMAS Journal 2015 Journal Article
Abstract When two parties need to split some reward between them, negotiation theory can predict what offers the parties will make and how the reward will be split. When a single party needs to evaluate several alternatives and choose the best among them, optimal-stopping-rule theories guide it as to how to perform the exploration, what to explore next and when to stop. We consider a model in which party A needs to choose one alternative, but has no information and no means of acquiring information on the value of each alternative. Party B, on the other hand, has no interest in what party A chooses, but can perform (costly) exploration to learn about the different alternatives. As both negotiation and exploration take time, the common deadline and discounting factor further tie the processes together. We study the combined model, providing a comprehensive game theoretic based analysis, enabling the extraction of the payments that need to be made between agents A and B, and the social welfare. Special emphasis is placed on studying the effect of interleaving negotiation and exploration, and when is this method preferred over separating the two. In addition to exploring the basic questions, we also consider the case in which one of the parties has some control over the parameters of the problem (e. g. the negotiation protocol), and show how it increases the utility of this party but decreases the overall welfare.
AAAI Conference 2015 Conference Paper
We present a credit-based matching mechanism for dynamic barter markets—and kidney exchange in particular—that is both strategy proof and efficient, that is, it guarantees truthful disclosure of donor-patient pairs from the transplant centers and results in the maximum global matching. Furthermore, the mechanism is individually rational in the sense that, in the long run, it guarantees each transplant center more matches than the center could have achieved alone. The mechanism does not require assumptions about the underlying distribution of compatibility graphs—a nuance that has previously produced conflicting results in other aspects of theoretical kidney exchange. Our results apply not only to matching via 2-cycles: the matchings can also include cycles of any length and altruist-initiated chains, which is important at least in kidney exchanges. The mechanism can also be adjusted to guarantee immediate individual rationality at the expense of economic efficiency, while preserving strategy proofness via the credits. This circumvents a well-known impossibility result in static kidney exchange concerning the existence of an individually rational, strategy-proof, and maximal mechanism. We show empirically that the mechanism results in significant gains on data from a national kidney exchange that includes 59% of all US transplant centers.
AAAI Conference 2015 Conference Paper
This paper represents a paradigm shift in what advice agents should provide people. Contrary to what was previously thought, we empirically show that agents that dispense optimal advice will not necessary facilitate the best improvement in people’s strategies. Instead, we claim that agents should at times suboptimally advise. We provide results demonstrating the effectiveness of a suboptimal advising approach in extensive experiments in two canonical mixed agent-human advice-giving domains. Our proposed guideline for suboptimal advising is to rely on the level of intuitiveness of the optimal advice as a measure for how much the suboptimal advice presented to the user should drift from the optimal value.
IROS Conference 2014 Conference Paper
Human operators play a key role in robotic exploration and search missions, as the interpretation of camera images typically requires the visual perception skills of humans. Thus one the key challenges in building effective robotic systems for such missions lies in developing good operator interfaces. In this paper, we present a novel asynchronous user-guided interface for human operators of robotic search of an unknown area. Enabled by efficient methods to store and retrieve recorded images (and meta information) in real-time, our interface allows the operator to click on any point of interest. The operator is then presented with highly-relevant images that cover the point, without occlusion. This, in contrast with system-guided approaches, where an automated system selects areas and images for inspection. Experiments with 32 human subjects in two different-size maps favor the user-guided approach we present over the system-guided approach. Additional experiments with human subjects provide an explanation as to the environment characteristics that favor our approach.
AAAI Conference 2014 Conference Paper
Peer Designed Agents (PDAs), computer agents developed by non-experts, is an emerging technology, widely advocated in recent literature for the purpose of replacing people in simulations and investigating human behavior. Its main premise is that strategies programmed into these agents reliably reflect, to some extent, the behavior used by their programmers in real life. In this paper we show that PDA development has an important side effect that has not been addressed to date — the process that merely attempts to capture one’s strategy is also likely to affect the developer’s strategy. The phenomenon is demonstrated experimentally, using several performance measures. This result has many implications concerning the appropriate design of PDA-based simulations, and the validity of using PDAs for studying individual decision making. Furthermore, we obtain that PDA development actually improved the developer’s strategy according to all performance measures. Therefore, PDA development can be suggested as a means for improving people’s problem solving skills.
AIJ Journal 2014 Journal Article
This paper considers the problem of autonomous agents that need to pick one of several options, all plausible however differ in their value, which is a priori uncertain and can be revealed for a cost. The agents thus need to weigh the benefits of revealing further values against the associated costs. The paper addresses the problem in its multi-agent joint form, such that not a single but rather a group of agents may benefit from the fruits of the search. The paper formally introduces and analyzes the joint search problem, when carried out fully distributedly, and determines the strategies to be used by the agents both when fully cooperative and when self-interested. The analysis is used to demonstrate that elements that can easily be proved to be beneficial with fully cooperative agents' search (e. g. , extension of the search horizon, increase in the number of cooperating agents) can actually degrade individual and overall expected utility in the self-interested case. The analysis contributes to the advancement of joint search theories, and offers important insights for system designers, enabling them to determine the mechanisms that should be included in the markets and systems they design.
AIJ Journal 2014 Journal Article
This paper introduces a game-theoretic analysis of auction settings where bidders' private values depend on an uncertain common value, and the auctioneer has the option to purchase information that can eliminate that uncertainty. Therefore the auctioneer needs to decide whether to purchase the information, and if so, whether to disclose it to the bidders. Unlike prior work, the model assumes that bidders are aware of the auctioneer's option to purchase the external information but are not necessarily aware of her decision. The modeling of the problem as a Stackelberg game, where the auctioneer is the leader, is complicated by the fact that in cases where the auctioneer decides not to disclose the information, the situation is actually modeled as a version of Stackelberg game where the follower has potentially imperfect information about the leader's actions. Our analysis of the individual expected-benefit-maximizing strategies results in the characterization of the pure-strategy perfect Bayesian Nash equilibrium and proof of its existence for any setting. In addition, we introduce an algorithm for extracting the equilibrium as a function of the information cost, which is of great importance when the information is provided by a strategic information-provider. The analysis is also extended to deal with mixed-strategy perfect Bayesian Nash equilibrium and with noisy information. Overall, the analysis enables the demonstration of various model characteristics, including many non-intuitive properties related to the benefits of competition, the benefits in having the option of the auctioneer to purchase such information and the benefits encapsulated in the bidders' awareness of such an option.
AAAI Conference 2014 Conference Paper
The popularity of online shopping has contributed to the development of comparison shopping agents (CSAs) aiming to facilitate buyers’ ability to compare prices of online stores for any desired product. Furthermore, the plethora of CSAs in today’s markets enables buyers to query more than a single CSA when shopping, thus expanding even further the list of sellers whose prices they obtain. This potentially decreases the chance of a purchase based on the prices outputted as a result of any single query, and consequently decreases each CSAs’ expected revenue per-query. Obviously, a CSA can improve its competence in such settings by acquiring more sellers’ prices, potentially resulting in a more attractive “best price”. In this paper we suggest a complementary approach that improves the attractiveness of a CSA by presenting the prices to the user in a specific intelligent manner, which is based on known cognitive-biases. The advantage of this approach is its ability to affect the buyer’s tendency to terminate her search for a better price, hence avoid querying further CSAs, without having the CSA spend any of its resources on finding better prices to present. The effectiveness of our method is demonstrated using real data, collected from four CSAs for five products. Our experiments with people confirm that the suggested method effectively influence people in a way that is highly advantageous to the CSA.
JAAMAS Journal 2014 Journal Article
Abstract This paper proposes the use of restructuring information about choices to improve the performance of computer agents on recurring sequentially dependent decisions. The intended situations of use for the restructuring methods it defines are website platforms such as electronic marketplaces in which agents typically engage in sequentially dependent decisions. With the proposed methods, such platforms can improve agents’ experience, thus attracting more customers to their sites. In sequentially-dependent-decisions settings, decisions made at one time may affect decisions made later; hence, the best choice at any point depends not only on the options at that point, but also on future conditions and the decisions made in them. This “problem restructuring” approach was tested on sequential economic search, which is a common type of recurring sequentially dependent decision-making problem that arises in a broad range of areas. The paper introduces four heuristics for restructuring the choices that are available to decision makers in economic search applications. Three of these heuristics are based on characteristics of the choices, not of the decision maker. The fourth heuristic requires information about a decision-makers prior decision-making, which it uses to classify the decision-maker. The classification type is used to choose the best of the three other heuristics. The heuristics were extensively tested on a large number of agents designed by different people with skills similar to those of a typical agent developer. The results demonstrate that the problem-restructuring approach is a promising one for improving the performance of agents on sequentially dependent decisions. Although there was a minor degradation in performance for a small portion of the agents, the overall and average individual performance improved substantially. Complementary experimentation with people demonstrated that the methods carry over, to some extent, also to human decision makers. Interestingly, the heuristic that adapts based on a decision-maker’s history achieved the best results for computer agents, but not for people.
JAAMAS Journal 2014 Journal Article
Abstract In this paper we study distributed agent matching in environments characterized by uncertain signals, costly exploration, and the presence of an information broker. Each agent receives information about the potential value of matching with others. This information signal may, however, be noisy, and the agent incurs some cost in receiving it. If all candidate agents agree to the matching the team is formed and each agent receives the true unknown utility of the matching, and leaves the market. We consider the effect of the presence of information brokers, or experts, on the outcomes of such matching processes. Experts can, upon payment of either a fee or a commission, perform the service of disambiguating noisy signals and revealing the true value of a match to any agent. We analyze equilibrium behavior given the fee set by a monopolist expert and use this analysis to derive the revenue maximizing strategy for the expert as the first mover in a Stackelberg game. Interestingly, we find that better information can hurt: the presence of the expert, even if the use of her services is optional, can degrade both individual agents’ utilities and overall social welfare. While in one-sided search the presence of the expert can only help, in two-sided (and general \(k\) -sided) search the externality imposed by the fact that others are consulting the expert can lead to a situation where the equilibrium outcome is that everyone consults the expert, even though all agents would be better off if the expert were not present. As an antidote, we show how market designers can enhance welfare by compensating the expert to change the price at which she offers her services.
JAAMAS Journal 2013 Journal Article
Abstract This paper addresses the problem of computing the value of information in settings in which the people using an autonomous-agent system have access to information not directly available to the system itself. To know whether to interrupt a user for this information, the agent needs to determine its value. The fact that the agent typically does not know the exact information the user has and so must evaluate several alternative possibilities significantly increases the complexity of the value-of-information calculation. The paper addresses this problem as it arises in multi-agent task planning and scheduling with architectures in which information about the task schedule resides in a separate “scheduler” module. For such systems, calculating the value to overall agent performance of potential new information requires that the system component that interacts with the user query the scheduler. The cost of this querying and inter-module communication itself substantially affects system performance and must be taken into account. The paper provides a decision-theoretic algorithm for determining the value of information the system might acquire, query-reduction methods that decrease the number of queries the algorithm makes to the scheduler, and methods for ordering the queries to enable faster decision-making. These methods were evaluated in the context of a collaborative interface for an automated scheduling agent. Experimental results demonstrate the significant decrease achieved by using the query-reduction methods in the number of queries needed for reasoning about the value of information. They also show the ordering methods substantially increase the rate of value accumulation, enabling faster determination of whether to interrupt the user.
AIJ Journal 2013 Journal Article
This paper investigates agent search for the agent with the best value in a multi-agent system, according to some value assignment. In the type of setting considered, agent values are independent of one another. Under this condition, classic state-space search methods are not very suitable solutions since they must probe the values of all agents in order to determine who the best-valued agent is. The method considered in this paper refines the number of agents that need to be probed by iteratively publishing thresholds on acceptable agent values. This kind of agent search is applicable to various domains, including auctions, first responders, and sensor networks. In the model considered, there is a fixed cost for publishing the thresholds and a variable cost for obtaining agent values that increases with the number of values obtained. By transforming the threshold-based sequence to a probability-based one, the sequence with minimum expected cost is proven to consist of either a single search round or an infinite sequence of increasing thresholds. This leads to a simplified characterization of the optimal thresholds sequence from which the sequence can be derived. The analysis is extended to the case of search for multiple agents. One important implication of this method is that it improves the performance of legacy economic-search methods that are commonly used in “search theory”. Within this context, we show how a threshold-based search can be used to augment existing economic search techniques or as an economic search technique itself. The effectiveness of the methods for both best-value search and economic-search is demonstrated numerically using a synthetic environment.
AAAI Conference 2013 Conference Paper
This paper studies distributed cooperative multi-agent exploration methods in settings where the exploration is costly and the overall performance measure is determined by the minimum performance achieved by any of the individual agents. Such an exploration setting is applicable to various multi-agent systems, e. g. , in Dynamic Spectrum Access exploration. The goal in such problems is to optimize the process as a whole, considering the tradeoffs between the quality of the solution obtained and the cost associated with the exploration and coordination between the agents. Through the analysis of the two extreme cases where coordination is completely free and when entirely disabled, we manage to extract the solution for the general case where coordination is taken to be costly, modeled as a fee that needs to be paid for each additional coordinated agent. The strategy structure for the general case is shown to be threshold-based, and the thresholds which are analytically derived in this paper can be calculated offline, resulting in a very low online computational load.
AIJ Journal 2013 Journal Article
This paper considers the problem of an agent or a team of agents searching for a resource or tangible good in a physical environment, where the resource or good may possibly be obtained at one of several locations. The cost of acquiring the resource or good at a given location is uncertain (a priori), and the agents can observe the true cost only when physically arriving at this location. Sample applications include agents in exploration and patrol missions (e. g. , an agent seeking to find the best location to deploy sensing equipment along its path). The uniqueness of these settings is in that the cost of observing a new location is determined by distance from the current one, impacting the consideration for the optimal search order. Although this model captures many real world scenarios, it has not been investigated so far. We analyze three variants of the problem, differing in their objective: minimizing the total expected cost, maximizing the success probability given an initial budget, and minimizing the budget necessary to obtain a given success probability. For each variant, we first introduce and analyze the problem with a single agent, either providing a polynomial solution to the problem or proving it is NP-complete. We also introduce a fully polynomial time approximation scheme algorithm for the minimum budget variant. In the multi-agent case, we analyze two models for managing resources, shared and private budget models. We present polynomial algorithms that work for any fixed number of agents, in the shared or private budget model. For non-communicating agents in the private budget model, we present a polynomial algorithm that is suitable for any number of agents. We also analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities. Finally, we define our problem in an environment with self-interested agents. We show how to find a Nash equilibrium in polynomial time, and prove that the bound on the performance of our algorithms, with respect to the social welfare, is tight.
AAAI Conference 2013 Conference Paper
The blooming of comparison shopping agents (CSAs) in recent years enables buyers in today’s markets to query more than a single CSA while shopping, thus substantially expanding the list of sellers whose prices they obtain. From the individual CSA point of view, however, the multi-CSAs querying is definitely non-favorable as most of today’s CSAs benefit depends on payments they receive from sellers upon transferring buyers to their websites (and making a purchase). The most straightforward way for the CSA to improve its competence is through spending more resources on getting more sellers’ prices, potentially resulting in a more attractive “best price”. In this paper we suggest a complementary approach that improves the attractiveness of the best price returned to the buyer without having to extend the CSAs’ price database. This approach, which we term “selective price disclosure” relies on removing some of the prices known to the CSA from the list of results returned to the buyer. The advantage of this approach is in the ability to affect the buyer’s beliefs regarding the probability of obtaining more attractive prices if querying additional CSAs. The paper presents two methods for choosing the subset of prices to be presented to a fully-rational buyer, attempting to overcome the computational complexity associated with evaluating all possible subsets. The effectiveness and efficiency of the methods are demonstrated using real data, collected from five CSAs for four products. Furthermore, since people are known to have an inherently bounded rationality, the two methods are also evaluated with human buyers, demonstrating that selective price-disclosing can be highly effective with people, however the subset of prices that needs to be used should be extracted in a different (and more simplistic) manner.
ECAI Conference 2012 Conference Paper
The paper studies distributed cooperative multi-agent exploration methods in settings where the overall benefit of an opportunity is the minimum of individual findings and the exploration is costly. The primary motivation for the model is the multi-channel cooperative sensing problem which draws from the inter-vehicular cognitive offload paradigm. Here, vehicles try to coordinate an offload channel through a dedicated common control channel, and the resulting quality of the channel eventually selected is constrained by the individual qualities. Similar settings may arise in other multi-agent settings where the exploration needs to be coordinated. The goal in such problems concerns the optimization of the process as a whole, considering the tradeoff between the quality of the solution obtained for the shared goal and the cost associated with the exploration and coordination process. The methods considered in this paper make use of parallel and sequential exploration. The first approach is more latency-efficient, and the latter is shown to be more cost-effective. The strategy structure in both schemes is threshold-based, and the thresholds which are analytically derived in this paper can be calculated offline, resulting in a very low online computational load. A comparative illustration of the methods' performance is given using a synthetic environment, emphasizing the cost-latency tradeoff.
AAMAS Conference 2012 Conference Paper
AAAI Conference 2012 Conference Paper
This paper studies repetitive negotiation over the execution of an exploration process between two selfinterested, fully rational agents in a full information environment with side payments. A key aspect of the protocol is that the exploration’s execution may interleave with the negotiation itself, inflicting some degradation on the exploration’s flexibility. The advantage of this form of negotiation is in enabling the agents supervising that the exploration’s execution takes place in its agreed form as negotiated. We show that in many cases, much of the computational complexity of the new protocol can be eliminated by solving an alternative negotiation scheme according to which the parties first negotiate the exploration terms as a whole and then execute it. As demonstrated in the paper, the solution characteristics of the new protocol are somehow different from those of legacy negotiation protocols where the execution of the agreement reached through the negotiation is completely separated from the negotiation process. Furthermore, if the agents are given the option to control some of the negotiation protocol parameters, the resulting exploration may be suboptimal. In particular we show that the increase in an agent’s expected utility in such cases is unbounded and so is the resulting decrease in the social welfare. Surprisingly, we show that further increasing one of the agents’ level of control in some of the negotiation parameters enables bounding the resulting decrease in the social welfare.
AAMAS Conference 2012 Conference Paper
AAMAS Conference 2012 Conference Paper
AAMAS Conference 2011 Conference Paper
Increasingly in both traditional, and especially Internet-based marketplaces, knowledge is becoming a traded commodity. This paper considers the impact of the presence of knowledge-brokers, or experts, on search-based markets with noisy signals. For example, consider a consumer looking for a used car on a large Internet marketplace. She sees noisy signals of the true value of any car she looks at the advertisement for, and can disambiguate this signal by paying for the services of an expert (for example, getting a Carfax report, or taking the car to a mechanic for an inspection). Both the consumer and the expert are rational, self-interested agents. We present a model for such search environments, and analyze several aspects of the model, making three main contributions: (1) We derive the consumer's optimal search strategy in environments with noisy signals, with and without the option of consulting an expert; (2) We find the optimal strategy for maximizing the expert's profit; (3) We study the option of market designers to subsidize search in a way that improves overall social welfare. We illustrate our results in the context of a plausible distribution of signals and values.
AAMAS Conference 2011 Conference Paper
In many settings and for various reasons, people fail to make optimal decisions. These factors also influence the agents people design to act on their behalf in such virtual environments as eCommerce and distributed operating systems, so that the agents also act sub-optimally despite their greater computational capabilities. In some decision-making situations it is theoretically possible to supply the optimal strategy to people or their agents, but this optimal strategy may be non-intuitive, and providing a convincing explanation of optimality may be complex. This paper explores an alternative approach to improving the performance of a decision-maker in such settings: the data on choices is manipulated to guide searchers to a strategy that is closer to optimal. This approach was tested for sequential search, which is a classical sequential decision-making problem with broad areas of applicability (e. g. , product search, partnership search). The paper introduces three heuristics for manipulating choices, including one for settings in which repeated interaction or access to a decision-maker's past history is available. The heuristics were evaluated on a large population of computer agents, each of which embodies a search strategy programmed by a different person. Extensive tests on thousands of search settings demonstrate the promise of the problem-restructuring approach: despite a minor degradation in performance for a small portion of the population, the overall and average individual performance improve substantially. The heuristic that adapts based on a decision-maker's history achieved the best results.
AAAI Conference 2010 Conference Paper
This paper investigates search techniques for multi-agent settings in which the most suitable agent, according to given criteria, needs to be found. In particular, it considers the case where the searching agent incurs a cost for learning the value of an agent and the goal is to minimize the expected overall cost of search by iteratively increasing the extent of search. This kind of search is applicable to various domains, including auctions, first responders, and sensor networks. Using an innovative transformation of the extents-based sequence to a probability-based one, the optimal sequence is proved to consist of either a single search iteration or an infinite sequence of increasing search extents. This leads to a simplified characterization of the the optimal search sequence from which it can be derived. This method is also highly useful for legacy economic-search applications, where all agents are considered suitable candidates and the goal is to optimize the search process as a whole. The effectiveness of the method for both best-valued search and economic search is demonstrated numerically using a synthetic environment.
AAMAS Conference 2010 Conference Paper
This paper investigates search techniques for multi-agentsettings in which the most suitable agent needs to be foundand the goal is to minimize the expected cost of search. Given the ability to vary the extent of search, a search strategy is a sequence of search iterations of varying extent.
JAAMAS Journal 2009 Journal Article
Abstract This paper investigates cooperative search strategies for agents engaged in costly search in a complex environment. Searching cooperatively, several search goals can be satisfied within a single search effort. Given the searchers’ preferences, the goal is to conduct a search in a way that the expected overall utility out of the set of opportunities found (e. g. , products when operating in a market) minus the costs associated with finding that set is maximized. This search scheme, given in the context of a group search, applies also to scenarios where a single agent has to search for a set of items for satisfying several different goals. The uniqueness of the proposed mechanism is in the ability to partition the group of agents/goals into sub-groups where the search continues for each group autonomously. As we show throughout the paper, this strategy is favorable as it weakly dominates (i. e. , can improve but never worsen) cooperative and autonomous search techniques. The paper presents a comprehensive analysis of the new search method and highlights the specific characteristics of the optimal search strategy. Furthermore, we introduce innovative algorithms for extracting the optimal search strategy in a range of common environments, that eliminates the computational overhead associated with the use of the partitioning technique.
ICAPS Conference 2008 Conference Paper
This paper addresses the problem of deciding effectively whether to interrupt a teammate who may have information that is valuable for solving a collaborative scheduling problem. Two characteristics of multi-agent scheduling complicate the determination of the value of the teammate's information, and hence whether it exceeds the costs of an interruption. First, in many scheduling contexts, task and scheduling knowledge reside in a scheduler module which is external to the agent, and the agent must query that module to estimate the value to the solution of knowing a specific piece of information. Second, the agent does not know the specific information its teammate has, resulting in the need for it to repeatedly query the scheduler. Choosing the right sequence of queries to the scheduler may enable the agent to make an interruption decision sooner, thus saving query time and computational load for both the agent and the external system. This paper defines two new sequencing heuristics which enhance the efficiency of the querying process. It also introduces three metrics for measuring the efficiency of a query sequence. It presents extensive simulation-based evidence that the new heuristics significantly outperform previously proposed methods for determining the value of information a teammate has.
AIJ Journal 2008 Journal Article
In this paper we address the problem of agents engaged in a distributed costly two-sided search for pairwise partnerships in Multi-Agent Systems (MAS). While traditional two-sided search mechanisms are based on a purely sequential search of all searchers, our mechanism integrates an ability of some of the agents to maintain several search efforts in parallel at each search stage. We show that in many environments the transition to the new mechanism is inevitable since the adoption of the parallel-interactions based search suggests a greater utility for the searching agents. By exploring the appropriate model equations, we present the new dynamics that drive the equilibrium when using such a mechanism in MAS environments. Complementary algorithms are offered, based on the unique equilibria characteristics found, for facilitating the extraction of the agents' strategies. The analysis methodology used supplies a comprehensive solution to a self contained model, and also offers a great value for future work concerning distributed two-sided mechanisms for MAS. Towards the end of the paper we review two of these important models that can benefit from the proposed analysis.
AAMAS Conference 2008 Conference Paper
In this paper we report results of an extensive evaluation of people’s ability to reproduce the strategies they use in simple real-life settings. Having the ability to reliably capture people’s strategies in different environments is highly desirable in Multi-Agent Systems (MAS). However, as trivial and daily as these strategies are, the process is not straightforward and people often have a different belief of how they act. We describe our experiments in this area, based on the participation of a pool of subjects in four different games with variable complexity and characteristics. The main measure used for determining the closeness between the two types of strategies used is the level of similarity between the actions taken by the participants and those taken by agents they programmed in identical world states. Our results indicate that generally people have the ability to reproduce their game strategies for the class of games we consider. However, this process should be handled carefully as some individuals tend to exhibit a behavior different from the one they program into their agents. The paper evaluates one possible method for enhancing the process of strategy reproduction.
IJCAI Conference 2007 Conference Paper
In this paper we present new search strategies for agents with diverse preferences searching cooperatively in complex environments with search costs. The uniqueness of our proposed mechanism is in the integration of the coalition's ability to partition itself into sub-coalitions, which continue the search autonomously, into the search strategy (a capability that was neglected in earlier cooperative search models). As we show throughout the paper, this strategy is always favorable in comparison to currently known cooperative and autonomous search techniques: it has the potential to significantly improve the searchers' performance in various environments and in any case guarantees reaching at least as good a performance as that of other known methods. Furthermore, for many common environments we manage to significantly eliminate the consequential added computational complexity associated with the partitioning option, by introducing innovative efficient algorithms for extracting the coalition's optimal search strategy. We illustrate the advantages of the proposed model over currently known cooperative and individual search techniques, using an environment based on authentic settings.
AAMAS Conference 2007 Conference Paper
This paper addresses the problem of identifying the value of information held by a teammate on a distributed, multi-agent team. It focuses on a distributed scheduling task in which computer agents support people who are carrying out complex tasks in a dynamic environment. The paper presents a decision-theoretic algorithm for determining the value of information that is potentially relevant to schedule revisions, but is directly available only to the person and not the computer agent. The design of a "coordination autonomy" (CA) module within a coordination-manager system provided the empirical setting for this work. By design, the CA module depends on an external scheduler module to determine the specific effect of additional information on overall system performance. The paper describes two methods for reducing the number of queries the CA issues to the scheduler, enabling it to satisfy computational resource constraints placed on it. Experimental results indicate the algorithm improves system performance and establish the exceptional efficiency–measured in terms of the number of queries required for estimating the value of information-that can be achieved by the query–reducing methods.
AAMAS Conference 2007 Conference Paper
AAMAS Conference 2007 Conference Paper
In this paper we consider the problem of eCommerce comparison shopping agents (shopbots) that are limited by capacity constraints. In light of the phenomenal increase both in demand for price comparison services over the internet and in the number of opportunities available in electronic markets, shopbots are nowadays required to improve the utilization of their finite set of querying resources. In this paper we introduce PlanBot, an innovative shopbot which uniquely integrates concepts from production management and economic search theory. PlanBot aims to maximize its efficiency by dynamically re-planning the allocation of its querying resources according to the results of formerly executed queries and new arriving requests. We detail the design principles that drive the PlanBot 's operation and illustrate its improved performance (in comparison to the traditional shopbots' First-Come-First-Served (FCFS) query execution mechanisms) using a simulated environment which is based on price datasets collected over the internet. Our encouraging results suggest that the design principles we apply have the potential of being used as an infrastructure for various implementations of future comparison shopping agents.
AAMAS Conference 2007 Conference Paper
This paper presents a two-sided economic search model in which agents are searching for beneficial pairwise partnerships. In each search stage, each of the agents is randomly matched with several other agents in parallel, and makes a decision whether to accept a potential partnership with one of them. The distinguishing feature of the proposed model is that the agents are not restricted to maintaining a synchronized (instantaneous) decision protocol and can sequentially accept and reject partnerships within the same search stage. We analyze the dynamics which drive the agents' strategies towards a stable equilibrium in the new model and show that the proposed search strategy weakly dominates the one currently in use for the two-sided parallel economic search model. By identifying several unique characteristics of the equilibrium we manage to efficiently bound the strategy space that needs to be explored by the agents and propose an efficient means for extracting the distributed equilibrium strategies in common environments.
AAMAS Conference 2007 Conference Paper
This paper investigates the problem of estimating the value of probabilistic parameters needed for decision making in environments in which an agent, operating within a multi-agent system, has no a priori information about the structure of the distribution of parameter values. The agent must be able to produce estimations even when it may have made only a small number of direct observations, and thus it must be able to operate with sparse data. The paper describes a mechanism that enables the agent to significantly improve its estimation by augmenting its direct observations with those obtained by other agents with which it is coordinating. To avoid undesirable bias in relatively heterogeneous environments while effectively using relevant data to improve its estimations, the mechanism weighs the contributions of other agents' observations based on a real-time estimation of the level of similarity between each of these agents and itself. The "coordination autonomy" module of a coordination-manager system provided an empirical setting for evaluation. Simulation-based evaluations demonstrated that the proposed mechanism outperforms estimations based exclusively on an agent's own observations as well as estimations based on an unweighted aggregate of all other agents' observations.
AAMAS Conference 2006 Conference Paper
AAAI Conference 2005 Conference Paper
In this paper we study search strategies of agents that represent buyer agents’ coalitions in electronic marketplaces. The representative agents operate in environments where numerous potential complex opportunities can be found. Each opportunity is associated with several different terms and conditions thus differing from other opportunities by its value for the coalition. Given a search cost, the goal of the representative agent is to find the best set of opportunities which fulfills the coalition’s demands with the maximum overall utility, to be divided among the coalition members. Given the option of side-payments, this strategy will always be preferred by all coalition members (thus no conflict of interests), regardless of the coalition’s payoff division protocol. We analyze the incentive to form such coalitions and extract the optimal search strategy for their representative agents, with a distinction between operating in B2C and C2C markets. Based on our findings we suggest efficient algorithms to be used by the representative agents for calculating a strategy that maximizes their expected utilities. A computational-based example is given, illustrating the achieved performance as a function of the coalition’s members’ heterogeneity level.
AAAI Conference 2005 Conference Paper
In this paper we analyze the process of allocating tasks to self-interested agents in uncertain changing open environments. The allocator in our model is responsible for the performance of dynamically arriving tasks using a second price reverse auction as the allocation protocol. Since the agents are self-interested (i. e. each agent attempts to maximize its own revenue), previous models concerning cooperative agents aiming for a joint goal are not applicable. Thus the main challenge is to identify a set of equilibrium strategies - a stable solution where no agent can benefit from changing its strategy given the other agents’ strategies - for any specific environmental settings. We formulate the model and discuss the difficulty in extracting the agents’ equilibrium strategies directly from the model’s equations. Consequently we propose an efficient algorithm to accurately approximate the agents’ equilibrium strategies. A comparative illustration through simulation of the system performance in a closed and open environments is given, emphasizing the advantage of the allocator operating in the latter environment, reaching results close to those obtained by a central enforceable allocation.
ECAI Conference 2004 Conference Paper
AAMAS Conference 2004 Conference Paper