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.

The management of operations in a large hospital is performed jointly by several groups of people. These include the doctors, the coordinators of the pre-operation units, the managers of the different wards, and the administrative managers of the operating theatres and of the teams of operating rooms. The present study models this problem as a distributed assignment problem within the field of distributed constraints optimization problems (DCOPs) and proposes an innovative representation of constraints and a distributed search algorithm for solving it. Due to the size of the problem, the common approach is to use an incomplete search algorithm. The research reported in the present thesis focuses on the problem of assigning operation requests within a single medical ward in a large public hospital.There is a natural strong hierarchy among the groups that manage the monthly schedule of operations in a ward. The proposed algorithm takes advantage of the hierarchy, in representing the multiple preferences of the different agents. One class of agents performs an initial assignment of operation requests to rooms and days. The assignment incorporates multiple constraints and preferences of patients, of doctors, and of features of specific operations. Another class of agents, that represents the heads of medical wards or senior surgeons, needs to approve the schedule by checking it against a variety of additional medical considerations. This class can request specific changes in order to improve the partial assignment to conform better to its preferences. The distributed nature of the problem is intrinsic and stems from the fact that the medical preferences can only be stated with respect to daily or weekly assignments of operations to operating rooms and to times (computed by the pre-operation unit), due to the huge number of possible such assignments.The interaction among the classes of agents forms an interactive (or procedural) representation of constraints and preferences over assignments. This is a new form of constraints representation. The proposed algorithm enables a distributed multi-objective hill climbing, by using the strict hierarchy among the agents during the exchange of improvements and approvals of assignments.In order to evaluate the resulting assignments of the distributed hill climbing search, real hospital data is used. Tables of operation requests and their resulting assignments over 3 months in the general surgery ward.

Distributed resource allocation problems (DRAPs) are composed of multiple agents and of resources that need to be allocated among them, and can be easily represented as asymmetric distributed constraints optimization problems (ADCOPs). Standard methods for solving ADCOPs use distributed multi-agent search to find solutions of high global social welfare. The present paper focuses on a family of resource allocation problems - allocating operating rooms to medical wards in a large hospital - that also benefit from allocations with increased fairness. The proposed multi agent algorithm has agents that represent ward managers that use a partially cooperative ADCOP algorithm. The proposed DRAP algorithm uses a new approach to partial cooperation - agents can offer or propose (non-strategic) side payments in exchange for resources. The use of side payments enables the agents to perform transactions that increase the global social welfare while retaining their own utility throughout the search. The proposed method is experimentally compared to an existing model of partial cooperation in a recent study of these problems. It is found to improve all measured objectives - both the utilitarian social welfare and well known fairness measures.

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 grid-integrated 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.

A wireless mesh network is a self organized set of nodes that are connected by wireless links. Communicating parties that are not in wireless range of each other relay packets via intermediate nodes. A common approach to wireless mesh routing is reactive routing, where a fixed path between the communicating endpoints is established on-demand when a new session is initiated. This paper proposes a distributed algorithm which guarantees service even when some wireless mesh nodes deliberately change, discard, or misroute data packets to disrupt service. When a misbehaving route is encountered, the proposed algorithm starts a process in which a virtual cost penalty is iteratively added to suspicious nodes and a new shortest route is derived until the disrupted path is replaced with one that avoids the misbehaving nodes. The algorithm enables proactive calculation of several alternative routes. The proactively calculated routes can be used to perform multipath routing that drastically enhances the robustness of the algorithm versus adversaries that dynamically change their behavior. Our algorithm can co-exist with common reactive wireless routing protocols. Furthermore, although every intermediate nodes may be malicious, the proposed algorithm does not impose costly authentication of messages from the participating intermediate nodes. This means that existing deployed infrastructures of wireless mesh nodes can be software-modified to work with the algorithm. We show that the proposed algorithm quickly converges to efficient alternative routes and present a bounded complexity for its time, communication, and computation overhead. Copyright © 2013 John Wiley & Sons, Ltd.

Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. 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). In ADCOPs different agents may have different valuations for constraints that they are involved in. The new framework bridges the gap between multi-agent problems which tend to have asymmetric structure and the standard symmetric DCOP model. The benefits of the proposed model over previous attempts to generalize the DCOP model are discussed and evaluated. Innovative algorithms that apply to the special properties of the proposed ADCOP model are presented in detail. These include complete algorithms that have a substantial advantage in terms of runtime and network load over existing algorithms (for standard DCOPs) which use alternative representations. Moreover, standard incomplete algorithms (i.e., local search algorithms) are inapplicable to the existing DCOP representations of asymmetric constraints and when they are applied to the new ADCOP framework they often fail to converge to a local optimum and yield poor results. The local search algorithms proposed in the present paper converge to high quality solutions. The experimental evidence that is presented reveals that the proposed local search algorithms for ADCOPs achieve high quality solutions while preserving a high level of privacy.

Recommender systems provide consumers with ratings of items. These ratings are based on a set of ratings that were obtained from a wide scope of users. Predicting the ratings can be formulated as a regression problem. Ensemble regression methods are effective tools that improve the results of simple regression algorithms by iteratively applying the simple algorithm to a diverse set of inputs. The present paper describes a simple and effective ensemble regressor for the prediction of missing ratings in recommender systems. The ensemble method is an adaptation of the AdaBoost regression algorithm for recommendation tasks. In all iterations, interpolation weights for all nearest neighbors are simultaneously derived by minimizing the root mean squared error. From iteration to iteration instances that are hard to predict are reinforced by manipulating their weights in the goal function that needs to be minimized. The experimental evaluation demonstrates that the ensemble methodology significantly improves the predictive performance of single neighborhood-based collaborative filtering.

Information sharing is a key objective in the age of Internet and virtual communities. Reputation information is an important part of a user’s identity and is both a sensitive and desired data for communities to share. At the same time, a reputation that a user has gained at some point in time can leverage her state in new communities. Communities use various trust and reputation models to compute the internal reputation of their members and each model may represent and quantify reputation in different manners. This paper introduces the Cross-Community Reputation (CCR) model that enables to bridge the gap between communities. The CCR model identifies the fundamental terms required for a meaningful sharing of reputation information among communities and proposes means to make them feasible. The model describes the actions taken in response to a request for CCR in three major stages – evaluation of reconditions, conversion of reputation values, and the matching of reputation attributes. The CCR model inherently supports policies specified by both communities and users.

A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and compute bounds on partial assignments asynchronously. The asynchronous bounds computation is based on the propagation of partial assignments. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. The algorithm is described in detail and its correctness proven. Experimental evaluation shows that AFB outperforms synchronous branch and bound by many orders of magnitude, and produces a phase transition as the tightness of the problem increases. This is an analogous effect to the phase transition that has been observed when local consistency maintenance is applied to MaxCSPs. The AFB algorithm is further enhanced by the addition of a backjumping mechanism, resulting in the AFB-BJ algorithm. Distributed backjumping is based on accumulated information on bounds of all values and on processing concurrently a queue of candidate goals for the next move back. The AFB-BJ algorithm is compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is shown to be a very efficient algorithm for DisCOPs.

Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The original proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. The present paper demonstrates that this expected growth of subproblems does not occur in some situations, leading to a termination problem of the algorithm. The problematic parts in the APO algorithm that interfere with its completeness are identified and necessary modifications to the algorithm that fix these problematic parts are given. The resulting version of the algorithm, Complete Asynchronous Partial Overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given. A detailed performance evaluation of CompAPO comparing it to other DisCSP algorithms is presented, along with an extensive experimental evaluation of the algorithm’s unique behavior. Additionally, an optimization version of the algorithm, CompOptAPO, is presented, discussed, and evaluated.

The MediaScout system is envisioned to function as personalized media (audio, video, print) service within mobile phones, online media portals, sling boxes, etc. The MediaScout recommender engine uses a novel stereotype-based recommendation engine. Upon the registration of new users the system must decide how to classify the new users to existing stereotypes. In this paper we present a method to achieve this classification through an anytime, interactive questionnaire, created automatically upon the generation of new stereotypes. A comparative study performed on the IMDB database illustrates the advantages of the new system

. Counter constraints are a naturalrepresentation of constraints on the finite capacity of resources in resource-allocation type problems. They are a generic family of non-binary constraints that limit the number of variables that may be assigned particular values. Counter constraints can be represented by binary constraints, at a cost. We analyse the cost, show how a counter can be represented as a linear number of binary constraints, and demonstrate empirically that even with the optimal reduction,an explicit representation of counters is preferable to their representation as a set of binary constraints. For counter constraints, value ordering is essential. An heuristic for value ordering on constraint satisfaction problems (CSP), based on the estimated likelihoodof a solution, is presented. The proposed value ordering heuristic is useful for counter constraints, as well as for binary CSPs, where it can be used to approximate the number of solutions consistent with a particular value assignment to a variable. The proposed value ordering heuristic integrates counter constraints with binary constraint networks in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope, yet we demonstrated empirically that the proposed value ordering heuristic is significantly superior to heuristics used in previous work.

The binary version of the school timetabling (STT) problem is a real‐world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real‐world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real‐world high school. To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.

Employee Timetabling Problems (ETP) are all around us. One possible approach for solving ETPs is to use constraint processing techniques. Another approach is to model human knowledge which is commonly used for solving such problems into knowledge-based systems for timetabling. It is difficult to represent the complex constraints of timetabling explicitly in constraint networks. On the other hand, knowledge-based representations of constraints are implicit and cannot support most of the heuristics of constraint-based processing that have been developed over the last decade. The present article presents on approach to representing and processing employee timetabling problems by a combination of explicit representations of some constraints and rule-based processing with heuristics for generic ETP constraints. This mixed-mode approach has been implemented in the form of a software package for defining and solving real-word ETPs. A general description of the design and organization of this software tool is given. Results for solving a typical real-world employee timetabling problem are presented and a comparison with the use of standard CSP (Constraint Satisfaction Problems) techniques is made. © 1997 John Wiley & Sons, Inc.

A general language for specifying resource allocation and time-tabling problems is presented. The language is based on an expert system paradigm that was developed previously by the authors and that enables the solution of resource allocation problems by using experts' knowledge and heuristics. The language enables the specification of a problem in terms of resources, activities, allocation rules, and constraints, and thus provides a convenient knowledge acquisition tool. The language syntax is powerful and allows the specification of rules and constraints that are very difficult to formulate with traditional approaches, and it also supports the specification of various control and backtracking strategies. We constructed a generalized inference engine that runs compiled resource allocation problem specification language (RAPS) programs and provides all necessary control structures. This engine acts as an expert system shell and is called expert system for resource allocation (ESRA). The performance of RAPS combined with ESRA is demonstrated by analyzing its solution of a typical resource allocation problem.>

A rule-based system for image segmentation and understanding is proposed. Called ROF (rule-based object finder), it is the low-level state of an image understanding system for aerial photographs. The general design of ROF uses a novel paradigm for segmentation. Candidate pixels for regions (or borders of regions) are chosen by the raw data module (RDM) on the basis of the geometric shape of their neighborhoods. The RDM has full access to the digital picture and its pixels. Compatible sets of candidate pixels for segment formation are found by search and decision-making techniques by the aggregation module. The segmentation module, the only one that is visible to the user, attempts to construct abstract entities which can serve as global regions or parts of objects in the picture. A specialized module deals with the quantitative side of object features such as size, shade and contrast. This quantification module interfaces to all other modules of ROF.>