Amnon Meisels

JAAMAS Journal 2025 Journal Article

Solving multi-agent games on networks

• Yair Vaknin
• Amnon Meisels

Abstract Multi-agent games on networks (GoNs) have nodes that represent agents and edges that represent interactions among agents. A special class of GoNs is composed of 2-players games on each of their edges. General GoNs have games that are played by all agents in each neighborhood. Solutions to games on networks are stable states (i. e. , pure Nash equilibria), and in general one is interested in efficient solutions (of high global social welfare). This study addresses the multi-agent aspect of games on networks—a system of multiple agents that compose a game and seek a solution by performing a multi-agent (distributed) algorithm. The agents playing the game are assumed to be strategic and an iterative distributed algorithm is proposed, that lets the agents interact (i. e. , negotiate) in neighborhoods in a process that guarantees the convergence of any multi-agent game on network to a globally stable state. The proposed algorithm—the TECon algorithm—iterates, one neighborhood at a time, performing a repeated social choice action. A truth-enforcing mechanism is integrated into the algorithm, collecting the valuations of agents in each neighborhood and computing incentives while eliminating strategic behavior. The proposed method is proven to converge to globally stable states that are at least as efficient as the initial state, for any game on network. A specific version of the algorithm is given for the class of Public Goods Games, where the main properties of the algorithm are guaranteed even when the strategic agents playing the game consider their possible future valuations when interacting. An extensive experimental evaluation on randomly generated games on networks demonstrates that the TECon algorithm converges very rapidly. On general forms of public goods games, the proposed algorithm outperforms former solving methods, where former methods are applicable.

AIJ Journal 2018 Journal Article

Incentive-based search for efficient equilibria of the public goods game

• Vadim Levit
• Zohar Komarovsky
• Tal Grinshpoun
• Amnon Meisels

The “best-shot” public goods game is a network game, defined on a social network. The simple version of the public goods game (PGG) has a fixed utility for a player who has at least a single neighbor buying the good. Players in the general version of PGG have additional utility when multiple neighbors purchase the good. The general version of the public goods game is shown to be a potential game, establishing the convergence to a stable state (i. e. , a pure Nash equilibrium – PNE) by best-response dynamics. One can think of best-response dynamics as a distributed algorithm that runs in a fixed order of players/agents and is guaranteed to converge to a PNE. A new distributed algorithm is proposed for finding PNEs with improved efficiency by the use of transfer of payoffs among players. For the simple version of PGG, it is shown that the proposed algorithm can stabilize an outcome that maximizes social welfare. For the general version of the game, the proposed procedure transforms any initial outcome into a stable solution at least as efficient as the initial outcome by using transfers. An extensive experimental evaluation on randomly generated PGGs demonstrates that whereas pure best-response dynamics converges on stable states that have lower efficiency than the initial outcome, the proposed procedure finds PNEs of higher efficiency.

AIJ Journal 2017 Journal Article

Forward bounding on pseudo-trees for DCOPs and ADCOPs

• Omer Litov
• Amnon Meisels

Complete search algorithms for solving Distributed constraint optimization problems (DCOPs) can be divided into two groups: algorithms that use a pseudo tree and algorithms that do not use one. The best performing algorithms that do not use a pseudo tree use some form of forward bounding. In order to try and gain from both worlds, a new algorithm, which incorporates a hybrid approach of the two groups is presented. The proposed algorithm – Pseudo-Tree Forward-bounding (PT-FB) – is shown to perform very well. PT-FB is next extended to be able to solve Asymmetric DCOPs (ADCOPs). Here again, its performance is better than its competitors. An extensive experimental evaluation of the performance of each of the proposed algorithms is presented.

AAMAS Conference 2016 Conference Paper

Distributed Search for Pure Nash Equilibria in Graphical Games (Extended Abstract)

• Omer Litov
• Amnon Meisels

Graphical games introduce a compact representation, where agents’ outcomes depend only on their neighbors. A distributed search algorithm for pure Nash equilibria of graphical games is presented. The algorithm uses the analogy of graphical games with asymmetric distributed constraints optimization problems (ADCOPs). The proposed algorithm includes three components - an admissible pruning heuristic; a back-checking mechanism; and a pseudo tree representation of the game. An experimental evaluation of the components of the proposed search algorithm is presented for randomly generated networks of multiple agents. The major speedup over a naive search algorithm is shown to arise from the use of a pseudo tree representation. A simple assessment method of the privacy loss due to back-checking is presented and is shown to result in a tradeoff between the performance of the complete algorithm and its privacy loss.

AAMAS Conference 2016 Conference Paper

Efficient Boolean Games Equilibria: A Scalable Approach (Extended Abstract)

• Zohar Komarovsky
• Vadim Levit
• Tal Grinshpoun
• Amnon Meisels

The present study focuses on a family of Boolean games whose agents’ interactions are defined by a social network. The task of finding social-welfare-maximizing outcomes for such games is NP-hard. Moreover, such optimal outcomes are not necessarily stable. Therefore, our aim is to devise a procedure that finds stable outcomes with an as high as possible social welfare. To this end, we construct a quadratictime procedure, by which any initial outcome of a game in this family can be transformed into a stable solution by the use of side payments. The resulting stable outcome is ensured to be at least as efficient as the initial outcome. Considering the fact that this procedure applies for any initial state, one may use good search heuristics to find an outcome of high social welfare, and then apply the procedure to it. This naturally leads to a scalable process that finds desirable efficient and stable solutions.

JAAMAS Journal 2015 Journal Article

Distributed envy minimization for resource allocation

• Arnon Netzer
• Amnon Meisels
• Roie Zivan

Abstract Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, Distributed Envy Minimization Problems (DEMP) are formulated as Distributed Constraint Reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents.

IJCAI Conference 2015 Conference Paper

Tradeoffs between Incentive Mechanisms in Boolean Games

• Vadim Levit
• Zohar Komarovsky
• Tal Grinshpoun
• Amnon Meisels

Two incentive mechanisms for Boolean games were proposed recently – taxation schemes and side payments. Both mechanisms have been shown to be able to secure a pure Nash equilibrium (PNE) for Boolean games. A complete characterization of outcomes that can be transformed to PNEs is given for each of the two incentive mechanisms. Side payments are proved to be a weaker mechanism in the sense that the outcomes that they can transform to PNEs are a subset of those transformable by taxation. A family of social-networkbased Boolean games, which demonstrates the differences between the two mechanisms for securing a PNE, is presented. A distributed search algorithm for finding the side payments needed for securing a PNE is proposed. An empirical evaluation demonstrates the properties of the two mechanisms on the family of social-network-based Boolean games.

AAAI Conference 2014 Conference Paper

Congestion Games for V2G-Enabled EV Charging

• Benny Lutati
• Vadim Levit
• Tal Grinshpoun
• Amnon Meisels

A model of the problem of charging and discharging electrical vehicles as a congestion game is presented. A generalization of congestion games – feedback congestion games (FCG) – is introduced. The charging of gridintegrated vehicles, which can also discharge energy back to the grid, is a natural FCG application. FCGs are proven to be exact potential games and therefore converge to a pure-strategy Nash equilibrium by an iterated better-response process. A compact representation and an algorithm that enable efficient best-response search are presented. A detailed empirical evaluation assesses the performance of the iterated best-response process. The evaluation considers the quality of the resulting solutions and the rate of convergence to a stable state. The effect of allowing to also discharge batteries using FCG is compared to scenarios that only include charging and is found to dramatically improve the predictability of the achieved solutions as well as the balancing of load.

AIJ Journal 2012 Journal Article

Concurrent forward bounding for distributed constraint optimization problems

• Arnon Netzer
• Alon Grubshtein
• Amnon Meisels

A distributed search algorithm for solving Distributed Constraints Optimization Problems (DCOPs) is presented. The new algorithm scans the search space by using multiple search processes (SPs) that run on all agents concurrently. SPs search in non-intersecting parts of the global search space and perform Branch & Bound search. Each search process (SP) uses the mechanism of forward bounding (FB) to prune efficiently its part of the global search space. The Concurrent Forward-Bounding (ConcFB) algorithm enables all SPs to share their upper bound across all parts of the global search space. The number of concurrent SPs is controlled dynamically by the ConcFB algorithm, by performing dynamic splitting. Within each SP a dynamic variable ordering is employed in order to help control the balance of computational load among all agents and across different SPs. The ConcFB algorithm is evaluated experimentally and compared to all state of the art DCOP algorithms. The number of Non-Concurrent Logical Operations, Non-Concurrent Steps, the total number of messages sent and CPU time are used as performance metrics. The evaluation procedure considers different DCOP problem types with a varying number of agents and different constraint graphs. As problems become larger and denser, ConcFB is shown to outperform all other evaluated algorithms by 2–3 orders of magnitude in all performance measures. Further evaluations comparing different variants of ConcFB provide important insights into the working of the algorithm and reveals the contribution of its different components.

ECAI Conference 2012 Conference Paper

Partial Cooperation in Multi-agent Local Search

• Alon Grubshtein
• Roie Zivan
• Amnon Meisels

Multi-agent systems usually address one of two forms of interaction. One has completely competitive agents that act selfishly, each maximizing its own gain from the interaction. Auctions and voting scenarios usually assume such agents and follow game theoretic results. The other form of interaction has multiple agents that cooperatively search for some global goal, such as an optimal time slot allocation for all landing aircrafts in an airport.

AAMAS Conference 2012 Conference Paper

Partial Cooperation in Multi-agent Search

• Roie Zivan
• Alon Grubshtein
• Michal Friedman
• Amnon Meisels

Multi-agent systems usually address one of two pure scenarios, completely competitive agents that act selfishly, each agent maximizing its own gain from the interaction or multiple agents that operate cooperatively in order to achieve a common goal. The present paper proposes a paradigm for multiple agents to solve a distributed problem, acting partly cooperatively and keeping a limited form of their self-interest. The proposed framework has multiple agents solving an asymmetric distributed constraints optimization problem (ADCOP), where agents have different personal gains from any mutual assignment. Three modes of cooperation are proposed – Non-cooperative, Guaranteed personal gain, and λ-cooperation (where agents’ willingness to suffer relative loss is parametrized by λ). The modes of cooperation are described, as well as their realization in search algorithms.

AAMAS Conference 2010 Conference Paper

Asynchronous Partitioning Framework

• Vitaliy Freidovich
• Amnon Meisels

A new general framework for agent cooperation and coordinationin solving distributed constraint satisfaction problems (DCSPs) ispresented. The Asynchronous Partitioning Framework (APF) firstpartitions agents into groups of agents, based on some heuristic, prior to any search being conducted. During the partitioning phaseone of the agents in each group is assigned the role of a groupleader. Next, two distinct types of search processes among theagents are performed concurrently. The first type of search isconducted within each group, in parallel and asynchronously toall searches in other groups. The second type of search, the globalsearch, is conducted between the groups, and treats each group asif it is a single agent represented by its group leader. The structureof the groups remains static throughout the search processes. Twodistinct algorithms implementing APF are presented, and theadvantages of APF are evaluated experimentally.

AAMAS Conference 2010 Conference Paper

Local search for Distributed Asymmetric Optimization

• Alon Grubshtein
• Roie Zivan
• Tal Grinshpoun
• Amnon Meisels

Distributed Constraints Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. DCOP algorithms search for the optimal solution, optimizing the total gain (or cost) that iscomposed of all gains of all agents. Local search (LS) DCOP algorithms search locally for an approximate such solution. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model. The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). The new framework is described and its differences from former attempts are discussed. New local search algorithms for ADCOPs are introduced and their advantages over existing algorithms and over formerrepresentations are discussed in detail. The new proposed algorithms for the ADCOP framework are evaluated experimentally and their performance compared to existing algorithms. Two measures of performance are used: quality of solutions and loss of privacy. The results show that the new algorithms significantly outperform existing DCOP algorithms with respect to both measures.

IJCAI Conference 2007 Conference Paper

• Roie Zivan
• Amnon Meisels

Max-CSPs are Constraint Optimization Problems that are commonly solved using a Branch and Bound algorithm. The B\B algorithm was enhanced by consistency maintenance procedures. All these algorithms traverse the search space in a chronological order and gain their efficiency from the quality of the consistency maintenance procedure. The present study introduces Conflict-directed Backjumping (CBJ) for Branch and Bound algorithms. The proposed algorithm maintains Conflict Sets which include only assignments whose replacement can lead to a better solution. The algorithm backtracks according to these sets. CBJ can be added to all classes of the Branch and Bound algorithm, in particular to versions of Branch and Bound that use advanced maintenance procedures of local consistency levels, NC*, AC* and FDAC. The experimental evaluation of B&B CBJ on random Max-CSPs shows that the performance of all algorithms is improved both in the number of assignments and in the time for completion.

ECAI Conference 2006 Conference Paper

Asynchronous Forward-Bounding for Distributed Constraints Optimization

• Amir Gershman
• Amnon Meisels
• Roie Zivan

A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and propagate their assignments asynchronously. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. Forward bounding propagates the bounds on the cost of solutions by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven. Experimental evaluation of AFB on random Max-DisCSPs reveals a phase transition as the tightness of the problem increases. This effect is analogous to the phase transition of Max-CSP when local consistency maintenance is applied [3]. AFB outperforms Synchronous Branch & Bound (SBB) as well as the asynchronous state-of-the-art ADOPT algorithm, for the harder problem instances. Both asynchronous algorithms outperform SBB by a large factor.

AIJ Journal 2006 Journal Article

Concurrent search for distributed CSPs

• Roie Zivan
• Amnon Meisels

A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a search space can be found unsolvable by a different search process. This enhances the efficiency of the ConcDB algorithm. Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is shown to be faster than former algorithms for solving DisCSPs. Experimental evaluation of ConcDB, on randomly generated DisCSPs demonstrates that the network load of ConcDB is similar to the network load of synchronous backtracking and is much lower than that of asynchronous backtracking. The advantage of Concurrent Search is more pronounced in the presence of imperfect communication, when messages are randomly delayed.

AAMAS Conference 2006 Conference Paper

Distributed Navigation in an Unknown Physical Environment

• Arnon Gilboa
• Ariel Felner
• Amnon Meisels

AAAI Conference 1997 Conference Paper

Bayes Networks for Estimating the Number of Solutions to a CSP

• Amnon Meisels

The problem of counting the number of solutions to a constraint satisfaction problem (CSP) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree-structured CSPs. For other CSPs, it is a less optimistic approximation than those suggested in prior work, and experiments show that it is more accurate on the average. We present empirical evidence that our approximation is a useful search heuristic for finding a single solution to a CSP.

EAAI Journal 1990 Journal Article

On resource allocation by an expert system

• Ehud Gudes
• Tsvi Kuflik
• Amnon Meisels

A general paradigm for solving resource allocation, timetabling and scheduling problems is presented. The paradigm is based on an expert-system approach which looks for a feasible solution that satisfies the problem's real-life constraints. The new paradigm includes generic concepts for resources, activities, constraints and allocations, as well as a general control strategy for the family of resource allocation problems. The control strategy includes three parts that deal with allocation, with constraints checking and with changes to allocations, termed local changes. The proposed paradigm has been tested on three real-world problems: crews assignment to air force missions, class scheduling for a university department, and timetabling of final examinations for the faculty of natural sciences. All cases were solved well in a few minutes' running time of Prolog-based systems that implemented the proposed paradigm on a VAX 780. These case studies are described in the paper in some detail, and an overall evaluation of the methodology is given.