Noam Hazon

AAMAS Conference 2026 Conference Paper

Does Calibration Affect Human Actions?

• Meir Nizri
• Amos Azaria
• Chirag Gupta
• Noam Hazon

Calibration has been proposed as a way to enhance the reliability and adoption of machine learning classifiers. We study a particular aspect of this proposal: how does calibrating a classification model affect the decisions made by non-expert humans consuming the model’s predictions? We performed a Human–Computer Interaction (HCI) experiment to assess the effect of calibration on (i) trust in the model and (ii) the correlation between decisions and predictions. Wealsoproposefurthercorrectionstothereportedcalibrated scores based on Kahneman and Tversky’s prospect theory from behavioral economics, and study the effect of these corrections on trust and decision-making. We found that calibration alone was not sufficient: applying the prospect-theory–based correction is crucial for increasing the correlation between human decisions and the model predictions. While this increased correlation suggests higher trust in the model, responses to “Do you trust the model more? ” are unaffected by the method used. For the full paper, see: https: //arxiv. org/abs/2508. 18317

AAMAS Conference 2026 Conference Paper

Identifying the Source of Information Spread in Networks via Markov Chains

• Yael Sabato
• Amos Azaria
• Noam Hazon

Nowadays, the diffusion of information through social networks is a powerful phenomenon. One common way to model diffusions in social networks is the Independent Cascade (IC) model. Given a set of infected nodes according to the IC model, a natural problem is the source detection problem, in which the goal is to identify the unique node that has started the diffusion. Maximum Likelihood Estimation (MLE) is a common approach for tackling the source detection problem, but it is computationally hard. In this work, we propose an efficient method for the source detection problem under the MLE approach, which is based on computing the stationary distribution of a Markov chain. Using simulations, we demonstrate the effectiveness of our method compared to other state-of-the-art methods from the literature, both on random and real-world networks.

AAMAS Conference 2024 Conference Paper

Coalition Formation with Bounded Coalition Size

• Chaya Levinger
• Noam Hazon
• Sofia Simola
• Amos Azaria

In many situations when people are assigned to coalitions, the utility of each person depends on the friends in her coalition. Additionally, in many situations, the size of each coalition should be bounded. This paper studies such coalition formation scenarios in both weighted and unweighted settings. Since finding a partition that maximizes the utilitarian social welfare is computationally hard, we provide a polynomial-time approximation algorithm. We also investigate the existence and the complexity of finding stable partitions. Namely, we show that the Contractual Strict Core (CSC) is never empty, but the Strict Core (SC) of some games is empty. Finding partitions that are in the CSC is computationally easy, but even deciding whether an SC of a given game exists is NP-hard. The analysis of the core is more involved. In the unweighted setting, we show that when the coalition size is bounded by 3 the core is never empty, and we present a polynomial time algorithm for finding a member of the core. However, for the weighted setting, the core may be empty, and we prove that deciding whether there exists a core is NP-hard.

AIJ Journal 2024 Journal Article

Negotiation strategies for agents with ordinal preferences: Theoretical analysis and human study

• Noam Hazon
• Sefi Erlich
• Ariel Rosenfeld
• Sarit Kraus

Negotiation is a very common interaction between agents. Many common negotiation protocols work with cardinal utilities, even though ordinal preferences, which only rank the outcomes, are easier to elicit from humans. In this work, we focus on negotiation with ordinal preferences over a finite set of outcomes. We study an intuitive protocol for bilateral negotiations, where the two parties make offers alternately. We analyze the negotiation protocol under two settings: First, we consider the full information setting, where each party is fully aware of the other party's preference order. For this case, we provide elegant strategies that specify a sub-game perfect equilibrium. In addition, we show how the studied negotiation protocol almost completely implements a known bargaining rule. Second, we analyze the complementary no-information setting where neither party knows the preference order of the other party. For this case, we provide a Maxmin strategy and show that every pair of Maxmin strategies specifies a robust-optimization equilibrium. Finally, through a human study ( N = 150 ), we empirically study the practical relevance of our full information analysis to people engaging in negotiations with each other and/or with an automated agent using the studied protocol. Surprisingly, our results indicate that people tend to arrive at the equilibrium outcomes despite frequently departing from the proposed strategies. In addition, in contrast to commonly held beliefs, we find that an equilibrium-following agent performs very well with people.

AAMAS Conference 2024 Conference Paper

Source Detection in Networks using the Stationary Distribution of a Markov Chain

• Yael Sabato
• Amos Azaria
• Noam Hazon

Nowadays, the diffusion of information through social networks is a powerful phenomenon. One common way to model diffusions in social networks is the Independent Cascade (IC) model. Given a set of infected nodes according to the IC model, a natural problem is the source detection problem, in which the goal is to identify the unique node that has started the diffusion. Maximum Likelihood Estimation (MLE) is a common approach for tackling the source detection problem, but it is computationally hard. In this work, we propose an efficient method for the source detection problem under the MLE approach, which is based on computing the stationary distribution of a Markov chain. Using simulations, we demonstrate the effectiveness of our method compared to other state-of-the-art methods from the literature, both on random and real-world networks.

ECAI Conference 2024 Conference Paper

The Complexity of Manipulation of k-Coalitional Games on Graphs

• Hodaya Barr
• Yohai Trabelsi
• Sarit Kraus
• Liam Roditty
• Noam Hazon

In many settings, there is an organizer who would like to divide a set of agents into k coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such k-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.

AAMAS Conference 2023 Conference Paper

Efficient Nearly-Fair Division with Capacity Constraints

• Hila Shoshan
• Noam Hazon
• Erel Segal-Halevi

We consider the problem of fairly and efficiently allocating indivisible items (goods or bads) under capacity constraints. In this setting, we are given a set of categorized items. Each category has a capacity constraint (the same for all agents), that is an upper bound on the number of items an agent can receive from each category. Our main result is a polynomial-time algorithm that solves the problem for two agents with additive utilities over the items. When each category contains items that are all goods (positively evaluated) or all chores (negatively evaluated) for each of the agents, our algorithm finds a feasible allocation of the items, which is both Pareto-optimal and envy-free up to one item. In the general case, when each item can be a good or a chore arbitrarily, our algorithm finds an allocation that is Pareto-optimal and envy-free up to one good and one chore. Full version is available at arXiv [36].

AAMAS Conference 2023 Conference Paper

Social Aware Coalition Formation with Bounded Coalition Size

• Chaya Levinger
• Amos Azaria
• Noam Hazon

In many situations when people are assigned to coalitions the assignment must be social aware, i. e, the utility of each person is the number of friends in her coalition. Additionally, in many situations the size of each coalition should be bounded. This paper initiates the study of such coalition formation scenarios. We show that finding a partition that maximizes the utilitarian social welfare is computationally hard, and provide a polynomial-time approximation algorithm. We also investigate the existence and the complexity of finding stable partitions. Namely, we show that there always exists a Nash Stable (NS) partition and the Contractual Strict Core (CSC) is never empty, but the Strict Core (SC) of some games is empty. Finding partitions that are NS or in the CSC is computationally easy, but finding partitions that are in the SC is hard. The analysis of the core is more involved. When the coalition size is bounded by 3 the core is never empty, and we present a polynomial time algorithm for finding a member of the core. In all other cases, we provide additive and multiplicative approximations of the core. In addition, we show in simulation over 100 million games that a simple heuristic always finds a partition that is in the core.

ECAI Conference 2023 Conference Paper

The Leximin Approach for a Sequence of Collective Decisions

• Ido Kahana
• Noam Hazon

In many situations, several agents need to make a sequence of decisions. For example, a group of workers that needs to decide where their weekly meeting should take place. In such situations, a decision-making mechanism must consider fairness notions. In this paper, we analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. We consider both offline and online settings, and concentrate on the fairness notion of proportionality and its relaxations. Specifically, in the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome, even if such an outcome exists. We thus introduce a new fairness property that captures this requirement, and show that a variant of the leximin mechanism satisfies the new fairness property. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations. We thus consider a natural restriction on the agents’ preferences, and show that the leximin mechanism guarantees the best possible additive approximation to proportionality and satisfies all the relaxations of proportionality.

AAAI Conference 2022 Short Paper

Explainable Shapley-Based Allocation (Student Abstract)

• Meir Nizri
• Noam Hazon
• Amos Azaria

The Shapley value is one of the most important normative division scheme in cooperative game theory, satisfying basic axioms. However, some allocation according to the Shapley value may seem unfair to humans. In this paper, we develop an automatic method that generates intuitive explanations for a Shapley-based payoff allocation, which utilizes the basic axioms. Given a coalitional game, our method decomposes it to sub-games, for which it is easy to generate verbal explanations, and shows that the given game is composed of the sub-games. Since the payoff allocation for each sub-game is perceived as fair, the Shapley-based payoff allocation for the given game should seem fair as well. We run an experiment with 210 human participants and show that when applying our method, humans perceive Shapley-based payoff allocation as significantly more fair than when using a general standard explanation.

AAAI Conference 2022 Short Paper

Social Aware Assignment of Passengers in Ridesharing (Student Abstract)

• Chaya Levinger
• Noam Hazon
• Amos Azaria

We analyze the assignment of passengers in a shared ride, which considers the social relationship among the passengers. Namely, there is a fixed number of passengers in each vehicle, and the goal is to recommend an assignment of the passengers such that the number of friendship relations is maximized. We show that the problem is computationally hard, and we provide an approximation algorithm.

EUMAS Conference 2021 Conference Paper

Explaining Ridesharing: Selection of Explanations for Increasing User Satisfaction

• David Zar
• Noam Hazon
• Amos Azaria

Abstract Transportation services play a crucial part in the development of modern smart cities. In particular, on-demand ridesharing services, which group together passengers with similar itineraries, are already operating in several metropolitan areas. These services can be of significant social and environmental benefit, by reducing travel costs, road congestion and \(CO_2\) emissions. Unfortunately, despite their advantages, not many people opt to use these ridesharing services. We believe that increasing the user satisfaction from the service will cause more people to utilize it, which, in turn, will improve the quality of the service, such as the waiting time, cost, travel time, and service availability. One possible way for increasing user satisfaction is by providing appropriate explanations comparing the alternative modes of transportation, such as a private taxi ride and public transportation. For example, a passenger may be more satisfied from a shared-ride if she is told that a private taxi ride would have cost her 50% more. Therefore, the problem is to develop an agent that provides explanations that will increase the user satisfaction. We model our environment as a signaling game and show that a rational agent, which follows the perfect Bayesian equilibrium, must reveal all of the information regarding the possible alternatives to the passenger. In addition, we develop a machine learning based agent that, when given a shared-ride along with its possible alternatives, selects the explanations that are most likely to increase user satisfaction. Using feedback from humans we show that our machine learning based agent outperforms the rational agent and an agent that randomly chooses explanations, in terms of user satisfaction.

IJCAI Conference 2021 Conference Paper

Manipulation of k-Coalitional Games on Social Networks

• Naftali Waxman
• Sarit Kraus
• Noam Hazon

In many coalition formation games the utility of the agents depends on a social network. In such scenarios there might be a manipulative agent that would like to manipulate his connections in the social network in order to increase his utility. We study a model of coalition formation in which a central organizer, who needs to form k coalitions, obtains information about the social network from the agents. The central organizer has her own objective: she might want to maximize the utilitarian social welfare, maximize the egalitarian social welfare, or only guarantee that every agent will have at least one connection within her coalition. In this paper we study the susceptibility for manipulation of these objectives, given the abilities and information that the manipulator has. Specifically, we show that if the manipulator has very limited information, namely he is only familiar with his immediate neighbours in the network, then a manipulation is almost always impossible. Moreover, if the manipulator is only able to add connections to the social network, then a manipulation is still impossible for some objectives, even if the manipulator has full information on the structure of the network. On the other hand, if the manipulator is able to hide some of his connections, then all objectives are susceptible to manipulation, even if the manipulator has limited information, i. e. , when he is familiar with his immediate neighbours and with their neighbours.

AAAI Conference 2021 Conference Paper

Targeted Negative Campaigning: Complexity and Approximations

• ‪Avishai Zagoury‬‏
• Orgad Keller
• Avinatan Hassidim
• Noam Hazon

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a computational perspective. To this end, we present a model where elections can be manipulated by convincing voters to demote specific non-favored candidates, and study its properties in the classic setting of scoring rules. When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for t-approval and Borda. We also provide a t-factor approximation for tapproval for every fixed t, and a 3-factor approximation algorithm for Borda. Interestingly enough—following recent trends in political science that show that the effectiveness of negative campaigning depends on the type of candidate and demographic—when assigning varying prices to different possible demotion operations, we are able to provide inapproximability results. When the goal is destructive (making the leading opponent lose), we show that the problem is easy for a broad class of scoring rules.

AAAI Conference 2020 Conference Paper

AI for Explaining Decisions in Multi-Agent Environments

• Sarit Kraus
• Amos Azaria
• Jelena Fiosina
• Maike Greve
• Noam Hazon
• Lutz Kolbe
• Tim-Benjamin Lembcke
• Jorg P. Muller

Explanation is necessary for humans to understand and accept decisions made by an AI system when the system’s goal is known. It is even more important when the AI system makes decisions in multi-agent environments where the human does not know the systems’ goals since they may depend on other agents’ preferences. In such situations, explanations should aim to increase user satisfaction, taking into account the system’s decision, the user’s and the other agents’ preferences, the environment settings and properties such as fairness, envy and privacy. Generating explanations that will increase user satisfaction is very challenging; to this end, we propose a new research direction: Explainable decisions in Multi-Agent Environments (xMASE). We then review the state of the art and discuss research directions towards efficient methodologies and algorithms for generating explanations that will increase users’ satisfaction from AI systems’ decisions in multi-agent environments.

JAIR Journal 2019 Journal Article

Approximating Weighted and Priced Bribery in Scoring Rules

• Orgad Keller
• Avinatan Hassidim
• Noam Hazon

The classic Bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win. Its important generalizations consider voters who are weighted and also have different prices. We provide an approximate solution for these problems for a broad family of scoring rules (which includes Borda, t-approval, and Dowdall).Our algorithm is based on a randomized reduction from these Bribery generalizations to weighted coalitional manipulation (WCM). To solve this WCM instance, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding a solution in the truncated search space yields a new algorithm for WCM, which is of independent interest.

AAMAS Conference 2019 Conference Paper

Complexity and Approximations in Robust Coalition Formation via Max-Min k -Partitioning

• Anisse Ismaili
• Noam Hazon
• Emi Watanabe
• Makoto Yokoo
• Sarit Kraus

Coalition formation is beneficial to multi-agent systems, especially when the value of a coalition depends on the relationship among its members. However, an attack can significantly damage a coalition structure by disabling agents. Therefore, getting prepared in advance for such an attack is particularly important. We study a robust k-coalition formation problem modeled by max-min k-partition of a weighted graph. We show that this problem is ΣP 2 -complete, which holds even for k = 2 and arbitrary weights, or k = 3 and non-negative weights. We also propose the Iterated Best Response (IBR) algorithm which provides a run-time absolute bound for the approximation error and can be generalized to the max-min optimization version of any ΣP 2 -complete problem. We tested IBR on fairly large instances of both synthetic graphs and real life networks, yielding near optimal results in a reasonable time.

JAIR Journal 2019 Journal Article

New Approximations for Coalitional Manipulation in Scoring Rules

• Orgad Keller
• Avinatan Hassidim
• Noam Hazon

We study the problem of coalitional manipulation---where k manipulators try to manipulate an election on m candidates---for any scoring rule, with focus on the Borda protocol. We do so in both the weighted and unweighted settings. For these problems, recent approximation approaches have tried to minimize k, the number of manipulators needed to make some preferred candidate p win (thus assuming that the number of manipulators is not limited in advance). In contrast, we focus on minimizing the score margin of p which is the difference between the maximum score of a candidate and the score of p. We provide algorithms that approximate the optimum score margin, which are applicable to any scoring rule. For the specific case of the Borda protocol in the unweighted setting, our algorithm provides a superior approximation factor for lower values of k.Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle. We believe that such methods could be beneficial in other social choice settings as well.

JAAMAS Journal 2019 Journal Article

Probabilistic physical search on general graphs: approximations and heuristics

• Noam Hazon
• Mira Gonen

Abstract We consider an agent seeking to obtain an item, potentially available at different locations in a physical environment. The traveling costs between locations are known in advance, but there is only probabilistic knowledge regarding the possible prices of the item at any given location. Given such a setting, the problem is to find a plan that maximizes the probability of acquiring the good while minimizing both travel and purchase costs. Sample applications include agents in search-and-rescue or exploration missions, e. g. , a rover on Mars seeking to mine a specific mineral. These probabilistic physical search problems have been previously studied, but we present the first approximation and heuristic algorithms for solving such problems on general graphs. We establish an interesting connection between these problems and classical graph-search problems, which led us to provide the approximation algorithms and hardness of approximation results for our settings. We further suggest several heuristics for practical use, and demonstrate their effectiveness with simulation on a real graph structure.

AAAI Conference 2018 Conference Paper

Approximating Bribery in Scoring Rules

• Orgad Keller
• Avinatan Hassidim
• Noam Hazon

The classic bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win. We find an approximate solution for this problem for a broad family of scoring rules (which includes Borda and t-approval), in the following sense: if there is a strategy which requires bribing k voters, we efficiently find a strategy which requires bribing at most k + O( √ k) voters. Our algorithm is based on a randomized reduction from bribery to coalitional manipulation (UCM). To solve the UCM problem, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding the optimal solution in the truncated search space yields a new algorithm for UCM, which is of independent interest.

AIJ Journal 2018 Journal Article

Forming k coalitions and facilitating relationships in social networks

• Liat Sless
• Noam Hazon
• Sarit Kraus
• Michael Wooldridge

In this paper we relax two common assumptions that are made when studying coalition formation. The first is that any number of coalitions can be formed; the second is that any possible coalition can be formed. We study a model of coalition formation where the value depends on a social network and exactly k coalitions must be formed. Additionally, in this context we present a new problem for an organizer that would like to introduce members of the social network to each other in order to increase the social welfare or to stabilize a coalition structure. We show that, when the number of coalitions, k, is fixed and there are not many negative edges, it is possible to find the coalition structure that maximizes the social welfare in polynomial time. Furthermore, an organizer can efficiently find the optimal set of edges to add to the network, and we experimentally demonstrate the effectiveness of this approach. In addition, we show that in our setting even when k is fixed and there are not many negative edges, finding a member of the core is intractable. However, we provide a heuristic for efficiently finding a member of the core that also guarantees a social welfare within a factor of 1/2 of the optimal social welfare. We also show that checking whether a given coalition structure is a member of the core can be done in polynomial time. Finally, we consider the problem faced by an organizer who would like to add edges to the network in order to stabilize a specific coalition structure core: we show that this problem is intractable.

IJCAI Conference 2018 Conference Paper

Negotiation Strategies for Agents with Ordinal Preferences

• Sefi Erlich
• Noam Hazon
• Sarit Kraus

Negotiation is a very common interaction between automated agents. Many common negotiation protocols work with cardinal utilities, even though ordinal preferences, which only rank the outcomes, are easier to elicit from humans. In this work we concentrate on negotiation with ordinal preferences over a finite set of outcomes. We study an intuitive protocol for bilateral negotiation, where the two parties make offers alternately. We analyze the negotiation protocol under different settings. First, we assume that each party has full information about the other party's preference order. We provide elegant strategies that specify a sub-game perfect equilibrium for the agents. We further show how the studied negotiation protocol almost completely implements a known bargaining rule. Finally, we analyze the no information setting. We study several solution concepts that are distribution-free, and analyze both the case where neither party knows the preference order of the other party, and the case where only one party is uninformed.

AIJ Journal 2018 Journal Article

Optimal defense against election control by deleting voter groups

• Yue Yin
• Yevgeniy Vorobeychik
• Bo An
• Noam Hazon

Election control encompasses attempts from an external agent to alter the structure of an election in order to change its outcome. This problem is both a fundamental theoretical problem in social choice, and a major practical concern for democratic institutions. Consequently, this issue has received considerable attention, particularly as it pertains to different voting rules. In contrast, the problem of how election control can be prevented or deterred has been largely ignored. We introduce the problem of optimal defense against election control, including destructive and constructive control, where manipulation is allowed at the granularity of groups of voters (e. g. , voting locations) through a denial-of-service attack, and the defender allocates limited protection resources to prevent control. We consider plurality voting, and show that it is computationally hard to prevent both types of control, though destructive control itself can be performed in polynomial time. For defense against destructive control, we present a double-oracle framework for computing an optimal prevention strategy. We show that both defender and attacker best response subproblems are NP-complete, and develop exact mixed-integer linear programming approaches for solving these, as well as fast heuristic methods. We then extend this general approach to develop effective algorithmic solutions for defense against constructive control. Finally, we generalize the model and algorithmic approaches to consider uncertainty about voter preferences. Experiments conducted on both synthetic and real data demonstrate that the proposed computational framework can scale to realistic problem instances. 1

AAMAS Conference 2017 Conference Paper

New Approximation for Borda Coalitional Manipulation

• Orgad Keller
• Avinatan Hassidim
• Noam Hazon

We study the problem of Borda Unweighted Coalitional Manipulation, where k manipulators try to manipulate an election on m candidates under the Borda protocol. This problem is known to be NP-hard. While most recent approaches to approximation tried to minimize k, the number of manipulators needed to make the preferred candidate win (thus assuming that the number of manipulators is not limited in advance), we focus instead on minimizing the maximum score obtainable by a non-preferred candidate. We provide a randomized, additive O(k √ m log m) approximation to this value; in other words, if there exists a strategy enabling the preferred candidate to win by an Ω(k √ m log m) margin, our method, with high probability, will find a strategy enabling her to win (albeit with a possibly smaller margin). It thus provides a somewhat stronger guarantee compared to the previous methods, where the addition of an extra manipulator implied (with respect to the original k) a strategy that provides an Ω(m)-additive approximation to a runnerup’s score: when k is o( p m/ log m), our strategy provides a stronger approximation. Our algorithm can also be viewed as a (1 + o(1))-multiplicative approximation since the value we approximate has a natural Ω(km) lower bound. Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentiallylarge configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle. We believe that such methods could be beneficial in approximating coalitional manipulation in other election protocols as well. CCS Concepts •Computing methodologies → Multi-agent systems;

JAAMAS Journal 2016 Journal Article

Enhancing comparison shopping agents through ordering and gradual information disclosure

• Chen Hajaj
• Noam Hazon
• David Sarne

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.

IJCAI Conference 2016 Conference Paper

Optimally Protecting Elections

• Yue Yin
• Yevgeniy Vorobeychik
• Bo An
• Noam Hazon

Election control encompasses attempts from an external agent to alter the structure of an election in order to change its outcome. This problem is both a fundamental theoretical problem in social choice, and a major practical concern for democratic institutions. Consequently, this issue has received considerable attention, particularly as it pertains to different voting rules. In contrast, the problem of how election control can be prevented or deterred has been largely ignored. We introduce the problem of optimal protection against election control, where manipulation is allowed at the granularity of groups of voters (e. g. , voting locations), through a denial-of-service attack, and the defender allocates limited protection resources to prevent control. We show that for plurality voting, election control through group deletion to prevent a candidate from winning is in P, while it is NP-Hard to prevent such control. We then present a double-oracle framework for computing an optimal prevention strategy, developing exact mixed-integer linear programming for mulations for both the defender and attacker oracles (both of these subproblems we show to be NP-Hard), as well as heuristic oracles. Experiments conducted on both synthetic and real data demonstrate that the proposed computational framework can scale to realistic problem instances.

ECAI Conference 2014 Conference Paper

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone 0001

Past research has investigated a number of methods for coordinating teams of agents, but with the growing number of sources of agents, it is likely that agents will encounter teammates that do not share their coordination methods. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. However when teammates do communicate, it can provide a valuable channel for coordination. Therefore, this paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multiarmed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates following unknown behaviors even when its models of these teammates are imperfect.

AAAI Conference 2014 Conference Paper

Ordering Effects and Belief Adjustment in the Use of Comparison Shopping Agents

• Chen Hajaj
• Noam Hazon
• David Sarne

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.

RLDM Conference 2013 Conference Abstract

Communicating with Unknown Teammates

• Samuel Barrett
• Noa Agmon
• Noam Hazon
• Sarit Kraus
• Peter Stone

Teamwork is central to many tasks, and past research has introduced a number of methods for coordinating teams of agents. However, with the growing number of sources of agents, it is likely that an agent will encounter teammates that do not share its coordination method. Therefore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork research has focused on cases where the agents do not directly communicate. This paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multi-armed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates not created by the authors even when its models of these teammates are imperfect.

IJCAI Conference 2013 Conference Paper

How to Change a Group's Collective Decision?

• Noam Hazon
• Raz Lin
• Sarit Kraus

Persuasion is a common social and economic activity. It usually arises when conflicting interests among agents exist, and one of the agents wishes to sway the opinions of others. This paper considers the problem of an automated agent that needs to influence the decision of a group of self-interested agents that must reach an agreement on a joint action. For example, consider an automated agent that aims to reduce the energy consumption of a nonresidential building, by convincing a group of people who share an office to agree on an economy mode of the air-conditioning and low light intensity. In this paper we present four problems that address issues of minimality and safety of the persuasion process. We discuss the relationships to similar problems from social choice, and show that if the agents are using Plurality or Veto as their voting rule all of our problems are in P. We also show that with K-Approval, Bucklin and Borda voting rules some problems become intractable. We thus present heuristics for efficient persuasion with Borda, and evaluate them through simulations.

AIJ Journal 2013 Journal Article

Physical search problems with probabilistic knowledge

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• David Sarne

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

Search More, Disclose Less

• Chen Hajaj
• Noam Hazon
• David Sarne
• Avshalom Elmalech

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.

AIJ Journal 2012 Journal Article

On the evaluation of election outcomes under uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

We investigate the extent to which it is possible to compute the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings – we do not know which of these orderings actually represents the preferences of the voter, but for each ordering, we know the probability that it does. For the case where the number of candidates is a constant, we are able to give a polynomial time algorithm to compute the probability that a given candidate will win. We present experimental results obtained with an implementation of the algorithm, illustrating how the algorithmʼs performance in practice is better than its predicted theoretical bound. However, when the number of candidates is not bounded, we prove that the problem becomes #P-hard for the Plurality, k-approval, Borda, Copeland, and Bucklin voting rules. We further show that even evaluating if a candidate has any chance of winning is NP-complete for the Plurality voting rule in the case where voters may have different weights. With unweighted voters, we give a polynomial algorithm for Plurality, and show that the problem is hard for many other voting rules. Finally, we give a Monte Carlo approximation algorithm for computing the probability of a candidate winning in any settings, with an error that is as small as desired.

AAMAS Conference 2012 Conference Paper

Solving Non-Zero Sum Multiagent Network Flow Security Games with Attack Costs

• Steven Okamoto
• Noam Hazon
• Katia Sycara

Moving assets through a transportation network is a crucial challenge in hostile environments such as future battlefields where malicious adversaries have strong incentives to attack vulnerable patrols and supply convoys. Intelligent agents must balance network costs with the harm that can be inflicted by adversaries who are in turn acting rationally to maximize harm while trading off against their own costs to attack. Furthermore, agents must choose their strategies even without full knowledge of their adversaries' capabilities, costs, or incentives. In this paper we model this problem as a non-zero sum game between two players, a sender who chooses flows through the network and an adversary who chooses attacks on the network. We advance the state of the art by: (1) moving beyond the zero-sum games previously considered to non-zero sum games where the adversary incurs attack costs that are not incorporated into the payoff of the sender; (2) introducing a refinement of the Stackelberg equilibrium that is more appropriate to network security games than previous solution concepts; and (3) using Bayesian games where the sender is uncertain of the capabilities, payoffs, and costs of the adversary. We provide polynomial time algorithms for finding equilibria in each of these cases. We also show how our approach can be applied to games where there are multiple adversaries.

AAMAS Conference 2011 Conference Paper

Ties Matter: Complexity of Voting Manipulation Revisited

• Svetlana Obraztsova
• Edith Elkind
• Noam Hazon

In their groundbreaking paper, Bartholdi, Tovey and Trick argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator's goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator's preferred candidate. In this paper, we examine the role of this assumption in the easiness results of Bartholdi et al. We observe that the algorithm presented in Bartholdi et al extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator's utility function that is inspired by the original model of Bartholdi et al. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in Bartholdi et al, and for a large class of scoring rules.

IJCAI Conference 2011 Conference Paper

Ties Matter: Complexity of Voting Manipulation Revisited

• Svetlana Obraztsova
• Edith Elkind
• Noam Hazon

In their groundbreaking paper, Bartholdi, Tovey and Trick [1989] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator's goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator's preferred candidate. In this paper, we examine the role of this assumption in the easiness results of [Bartholdi et al. , 1989]. We observe that the algorithm presented in [Bartholdi et al. , 1989] extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator's utility function that is inspired by the original model of [Bartholdi et al. , 1989]. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in [Bartholdi et al. , 1989], and for a large class of scoring rules.

IJCAI Conference 2009 Conference Paper

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus

This paper considers the setting wherein a group of agents (e. g. , robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e. g. , battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, apriori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e. g. , rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For noncommunicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities.

AAMAS Conference 2008 Conference Paper

Evaluation of Election Outcomes under Uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

We investigate the extent to which it is possible to evaluate the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings – we do not know which of these orderings actually represents the voters’ preferences, but we know for each one the probability that it does. We give a polynomial algorithm to solve the problem of computing the probability that a given candidate will win when the number of candidates is a constant. However, when the number of candidates is not bounded, we prove that the problem becomes #P-Hard for the Plurality, Borda, and Copeland voting protocols. We further show that even evaluating if a candidate has any chance to win is NP-Complete for the Plurality voting protocol, in the weighted voters case. We give a polynomial algorithm for this problem when the voters’ weights are equal.

AAAI Conference 2008 Short Paper

Social Interaction under Uncertainty in Multi Agent Systems

• Noam Hazon

ICRA Conference 2006 Conference Paper

Constructing Spanning Trees for Efficient Multi-robot Coverage

• Noa Agmon
• Noam Hazon
• Gal A. Kaminka

This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multirobot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method, underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. Current studies assume that the spanning tree is given, and try to make the most out of the given configuration. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper tackles the open challenge of constructing a coverage spanning tree that minimizes the time to complete coverage. We argue that the choice of the initial spanning tree has far reaching consequences concerning the coverage time, and if the tree is constructed appropriately, it could considerably reduce the coverage time of the terrain. Therefore the problem studied here is finding spanning trees that would decrease the coverage time of the terrain when used as base for multi-robot coverage algorithms. The main contributions of this paper are twofold. First, it provides initial sound discussion and results concerning the construction of the tree as a crucial base for any efficient coverage algorithm. Second, it describes a polynomial-time tree construction algorithm that, as shown in extensive simulations, dramatically improves the coverage time even when used as a basis for a simple, inefficient, coverage algorithm

ICRA Conference 2006 Conference Paper

Towards Robust on-line Multi-robot Coverage

• Noam Hazon
• Fabrizio Mieli
• Gal A. Kaminka

Area coverage is an important task for mobile robots, with many real-world applications. In many cases, the coverage has to be completed without the use of a map or any a priori knowledge about the area, a process referred-to as on-line coverage. Previous investigations of multi-robot on-line coverage focused on the improved efficiency gained from the use of multiple robots, but did not formally addressed the potential for greater robustness. We present a novel multi-robot on-line coverage algorithm, based on approximate cell decomposition. We analytically show that the algorithm is complete and robust, in that as long as a single robot is able to move, the coverage would be completed. We analyze the assumptions underlying the algorithm requirements and present a number of techniques for executing it in real robots. We show empirical coverage-time results of running the algorithm in two different environments and several group sizes

ICRA Conference 2005 Conference Paper

Redundancy, Efficiency and Robustness in Multi-Robot Coverage

• Noam Hazon
• Gal A. Kaminka

Area coverage is an important task for mobile robots, with many real-world applications. Motivated by potential efficiency and robustness improvements, there is growing interest in the use of multiple robots in coverage. Previous investigations of multi-robot coverage focuses on completeness and eliminating redundancy, but does not formally address robustness, nor examine the impact of the initial positions of robots on the coverage time. Indeed, a common assumption is that non-redundancy leads to improved coverage time. We address robustness and efficiency in a family of multi-robot coverage algorithms, based on spanning-tree coverage of approximate cell decomposition. We analytically show that the algorithms are robust, in that as long as a single robot is able to move, the coverage will be completed. We also show that non-redundant (non-back tracking) versions of the algorithms have a worst-case coverage time virtually identical to that of a single robot—thus no performance gain is guaranteed in non-redundant coverage. Moreover, this worst-case is in fact common in real-world applications. Surprisingly, however, redundant coverage algorithms lead to guaranteed performance which halves the coverage time even in the worst case.