The influence of memory in a threshold model for distributed task assignment

A nature inspired decentralised multi-agent algorithm is proposed to solve a problem of distributed task selection in which cities produce and store batches of different mail types. Agents must collect and process the mail batches, without a priori knowledge of the available mail at the cities or inter-agent communication. In order to process a different mail type than the previous one, agents must undergo a change-over during which it remains inactive. We propose a threshold based algorithm in order to maximise the overall efficiency (the average amount of mail collected). We show that memory, i.e. the possibility for agents to develop preferences for certain cities, not only leads to emergent cooperation between agents, but also to a significant increase in efficiency (above the theoretical upper limit for any memoryless algorithm), and we systematically investigate the influence of the various model parameters. Finally, we demonstrate the flexibility of the algorithm to changes in circumstances, and its excellent scalability.

An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method. © 2012 Operational Research Society Ltd. All rights reserved.

Molecular identification of 26 syntaxin genes and their assignment to the different trafficking pathways in Paramecium

SNARE proteins have been classified as vesicular (v)- and target (t)-SNAREs and play a central role in the various membrane interactions in eukaryotic cells. Based on the Paramecium genome project, we have identified a multigene family of at least 26 members encoding the t-SNARE syntaxin (PtSyx) that can be grouped into 15 subfamilies. Paramecium syntaxins match the classical build-up of syntaxins, being 'tail-anchored' membrane proteins with an N-terminal cytoplasmic domain and a membrane-bound single C-terminal hydrophobic domain. The membrane anchor is preceded by a conserved SNARE domain of approximately 60 amino acids that is supposed to participate in SNARE complex assembly. In a phylogenetic analysis, most of the Paramecium syntaxin genes were found to cluster in groups together with those from other organisms in a pathway-specific manner, allowing an assignment to different compartments in a homology-dependent way. However, some of them seem to have no counterparts in metazoans. In another approach, we fused one representative member of each of the syntaxin isoforms to green fluorescent protein and assessed the in vivo localization, which was further supported by immunolocalization of some syntaxins. This allowed us to assign syntaxins to all important trafficking pathways in Paramecium.

Genetic Algorithm Approach for Solving the Task Assignment Problem

This research was partially supported by the Serbian Ministry of Science and Ecology under project 144007. The authors are grateful to Ivana Ljubić for help in testing and to Vladimir Filipović for useful suggestions and comments.

Solving the Task Assignment Problem with a Variable Neighborhood Search

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

Establishing Correspondences between Attribute Spaces and Complex Concept Spaces Using Meta-PGN Classifier

In this paper, we present one approach for extending the learning set of a classification algorithm with additional metadata. It is used as a base for giving appropriate names to found regularities. The analysis of correspondence between connections established in the attribute space and existing links between concepts can be used as a test for creation of an adequate model of the observed world. Meta-PGN classifier is suggested as a possible tool for establishing these connections. Applying this approach in the field of content-based image retrieval of art paintings provides a tool for extracting specific feature combinations, which represent different sides of artists' styles, periods and movements.

A Distance-Based Method for Attribute Reduction in Incomplete Decision Systems

There are limitations in recent research undertaken on attribute reduction in incomplete decision systems. In this paper, we propose a distance-based method for attribute reduction in an incomplete decision system. In addition, we prove theoretically that our method is more effective than some other methods.

Generalized Discernibility Function Based Attribute Reduction in Incomplete Decision Systems

A rough set approach for attribute reduction is an important research subject in data mining and machine learning. However, most attribute reduction methods are performed on a complete decision system table. In this paper, we propose methods for attribute reduction in static incomplete decision systems and dynamic incomplete decision systems with dynamically-increasing and decreasing conditional attributes. Our methods use generalized discernibility matrix and function in tolerance-based rough sets.

Analyzing evacuation decisions using multi-attribute utility theory (MAUT)

Emergency managers are faced with critical evacuation decisions. These decisions must balance conflicting objectives as well as high levels of uncertainty. Multi-Attribute Utility Theory (MAUT) provides a framework through which objective trade-offs can be analyzed to make optimal evacuation decisions. This paper is the result of data gathered during the European Commission Project, Evacuation Responsiveness by Government Organizations (ERGO) and outlines a preliminary decision model for the evacuation decision. The illustrative model identifies levels of risk at which point evacuation actions should be taken by emergency managers in a storm surge scenario with forecasts at 12 and 9 hour intervals. The results illustrate how differences in forecast precision affect the optimal evacuation decision. Additional uses for this decision model are also discussed along with improvements to the model through future ERGO data-gathering.

On axiomatizations of the Shapley value for assignment games

We consider the problem of axiomatizing the Shapley value on the class of assignment games. We first show that several axiomatizations of the Shapley value on the class of all TU-games do not characterize this solution on the class of assignment games by providing alternative solutions that satisfy these axioms. However, when considering an assignment game as a communication graph game where the game is simply the assignment game and the graph is a corresponding bipartite graph buyers are connected with sellers only, we show that Myerson's component efficiency and fairness axioms do characterize the Shapley value on the class of assignment games. Moreover, these two axioms have a natural interpretation for assignment games. Component efficiency yields submarket efficiency stating that the sum of the payoffs of all players in a submarket equals the worth of that submarket, where a submarket is a set of buyers and sellers such that all buyers in this set have zero valuation for the goods offered by the sellers outside the set, and all buyers outside the set have zero valuations for the goods offered by sellers inside the set. Fairness of the graph game solution boils down to valuation fairness stating that only changing the valuation of one particular buyer for the good offered by a particular seller changes the payoffs of this buyer and seller by the same amount.

Stable sets in one-seller assignment games

We consider von Neumann -- Morgenstern stable sets in assignment games with one seller and many buyers. We prove that a set of imputations is a stable set if and only if it is the graph of a certain type of continuous and monotone function. This characterization enables us to interpret the standards of behavior encompassed by the various stable sets as possible outcomes of well-known auction procedures when groups of buyers may form bidder rings. We also show that the union of all stable sets can be described as the union of convex polytopes all of whose vertices are marginal contribution payoff vectors. Consequently, each stable set is contained in the Weber set. The Shapley value, however, typically falls outside the union of all stable sets.

Lexicographic allocations and extreme core payoffs: the case of assignment games

We consider various lexicographic allocation procedures for coalitional games with transferable utility where the payoffs are computed in an externally given order of the players. The common feature of the methods is that if the allocation is in the core, it is an extreme point of the core. We first investigate the general relationship between these allocations and obtain two hierarchies on the class of balanced games. Secondly, we focus on assignment games and sharpen some of these general relationship. Our main result is the coincidence of the sets of lemarals (vectors of lexicographic maxima over the set of dual coalitionally rational payoff vectors), lemacols (vectors of lexicographic maxima over the core) and extreme core points. As byproducts, we show that, similarly to the core and the coalitionally rational payoff set, also the dual coalitionally rational payoff set of an assignment game is determined by the individual and mixed-pair coalitions, and present an efficient and elementary way to compute these basic dual coalitional values. This provides a way to compute the Alexia value (the average of all lemacols) with no need to obtain the whole coalitional function of the dual assignment game.

Assignment Games with Externalities

We examine assignment games, wherematched pairs of firms and workers create some monetary value to distribute among themselves and the agents aim to maximize their payoff. In the majority of this literature, externalities - in the sense that a pair’s value depends on the pairing of the others - have been neglected. However, inmost applications a firm’s success depends on, say, the success of its rivals and suppliers. Thus, it is natural to ask how the classical results on assignment games are affected by the introduction of externalities? The answer is – dramatically. We find that (i) a problem may have no stable outcome, (ii) stable outcomes can be inefficient (not maximize total value), (iii) efficient outcomes can be unstable, and (iv) the set of stable outcomes may not form a lattice. We show that stable outcomes always exist if agents are "pessimistic." This is a knife-edge result: there are problems in which the slightest optimism by a single pair erases all stable outcomes.

The effects of attribute quality information and sources of information on consumers' perceptions and behavior: A model of Pre-purchase Information Utilization in Service Physical Environments

The search-experience-credence framework from economics of information, the human-environment relations models from environmental psychology, and the consumer evaluation process from services marketing provide a conceptual basis for testing the model of "Pre-purchase Information Utilization in Service Physical Environments." The model addresses the effects of informational signs, as a dimension of the service physical environment, on consumers' perceptions (perceived veracity and perceived performance risk), emotions (pleasure) and behavior (willingness to buy). The informational signs provide attribute quality information (search and experience) through non-personal sources of information (simulated word-of-mouth and non-personal advocate sources).^ This dissertation examines: (1) the hypothesized relationships addressed in the model of "Pre-purchase Information Utilization in Service Physical Environments" among informational signs, perceived veracity, perceived performance risk, pleasure, and willingness to buy, and (2) the effects of attribute quality information and sources of information on consumers' perceived veracity and perceived performance risk.^ This research is the first in-depth study about the role and effects of information in service physical environments. Using a 2 x 2 between subjects experimental research procedure, undergraduate students were exposed to the informational signs in a simulated service physical environment. The service physical environments were simulated through color photographic slides.^ The results of the study suggest that: (1) the relationship between informational signs and willingness to buy is mediated by perceived veracity, perceived performance risk and pleasure, (2) experience attribute information shows higher perceived veracity and lower perceived performance risk when compared to search attribute information, and (3) information provided through simulated word-of-mouth shows higher perceived veracity and lower perceived performance risk when compared to information provided through non-personal advocate sources. ^

A case study of the assignment of withdrawal codes for reporting dropout in two disciplinary alternative schools

Dropout rates are major issues facing any nation's continued economic and social progress. The seriousness of this issue in the United States is evidenced by the recent legislation of the 2001 No Child Left Behind Act. The purpose of this study was to use the richness of qualitative methodology to analyze inaccuracies in the assignment of withdrawal codes by school administrators in two different disciplinary alternative schools. The primary codes examined were Code 05, any students over the age of 16 who leaves school voluntarily with no intention of returning; Code 15, any PK–12 student who is withdrawn from school due to nonattendance; Code 22, whereabouts unknown; Code 23, no other code can be used to identify the student's reason for leaving school, and Code 26, entering an adult program. ^ The cross-case method was used for this study. The participants were comprised of 19 school personnel and 25 students from two disciplinary alternative schools, designated X and Y, in the Miami-Dade County Public School system, Miami, FL. Data collection procedures included semi-structured interview, observations, field notes, and district documents. With a matrix, these data were analyzed to compare patterns and themes that emerged within both schools. ^ Results indicated that withdrawal codes were assigned inaccurately for two distinct reasons. At School Y, withdrawal codes were inaccurately assigned intentionally to keep the students from returning to a regular school without notification. At School X, withdrawal codes were inaccurately assigned due to lack of ability to properly track students and ascertain the real circumstances for their departure from school. The end result in both cases was that the school systems were not accurately identifying the whereabouts of students. It was recommended that further investigation be conducted to compare the accuracy of reporting dropouts among traditional/regular high schools and disciplinary alternative schools. ^