Performance evaluation of some special classes of weighted majority rules

The main concern of this paper is the performance evaluation of four classes of decision rules: the expert rule, the balanced expert rules, the simple majority rule, and the restricted simple majority rules. Employing the uncertain dichotomous choice model we first establish the necessary and sufficient conditions for the optimality of these four types of decision rules.For small groups consisting of less than six members the optimality conditions cover all the potentially optimal decision rules. Consequently, we are able to pursue a complete analysis of the small group cases. The analysis of the special (small group) cases as well as that of the general (n-member group) cases is based on the assumption that individual decisional skills are uniformly distributed. In evaluating the quality of a decision rule we resort to four alternative criteria: the expected optimality likelihood of the rule, the expected probability of yielding a correct collective decision given complete information on decisional skills, the expected probability of yielding a correct collective judgement given complete inability of skills verification, and, finally, the sensitivity of the rule to skills verifiability.     

Necessary and sufficient conditions forl-stability of games in constitutional form

This paper is devoted to the notion of game in constitutional form. For this game, we define three notions of cores: theo-core, thei-core and thej-core. For each core, we give a necessary and sufficient condition for a game to be stable. We finally prove that these theorems generalize Nakamura's theorems for stability of a simple game and Keiding's theorems for stability of an effectivity function.     

Efficient and strategy-proof social choice when preferences are single-dipped

We study the problem of locating a single public good along a segment when agents have single-dipped preferences. We ask whether there are unanimous and strategy-proof rules for this model. The answer is positive and we characterize all such rules. We generalize our model to allow the set of alternatives to be unbounded. If the set of alternatives does not have a maximal and a minimal element, there is no meaningful notion of efficiency. However, we show that the range of every strategy-proof rule has a maximal and a minimal element. We then characterize all strategy-proof rules.     

The Stability of Self-Organized Rule-Following Work Teams

Self-organized rule-following systems are increasingly relevant objects of study in organization theory due to such systems&2018; capacity to maintain control while enabling decentralization of authority. This paper proposes a network model for such systems and examines the stability of the networks&2018; repetitive behavior. The networks examined are Ashby nets, a fundamental class of binary systems: connected aggregates of nodes that individually compute an interaction rule, a binary function of their three inputs. The nodes, which we interpret as workers in a work team, have two network inputs and one self-input. All workers in a given team follow the same interaction rule.We operationalize the notion of stability of the team&2018;s work routine and determine stability under small perturbations for all possible rules these teams can follow. To study the organizational concomitants of stability, we characterize the rules by their memory, fluency, homogeneity, and autonomy. We relate these measures to work routine stability, and find that stability in ten member teams is enhanced by rules that have low memory, high homogeneity, and low autonomy.     

Comparing influence theories in voting games under locally generated measures of dissatisfaction

The Isbell desirability relation (I), the Shapley?CShubik index (SS) and the Banzhaf?CColeman index (BC) are power theories that grasp the notion of individual influence in a yes?Cno voting rule. Also, a yes?Cno voting rule is often used as a tool for aggregating individual preferences over any given finite set of alternatives into a collective preference. In this second context, Diffo Lambo and Moulen (DM) have introduced a power relation which ranks the voters with respect to how ably they influence the collective preference. However, DM relies on the metric d that measures closeness between preference relations. Our concern in this work is: do I, SS, BC and DM agree when the same yes?Cno voting rule is the basis for collective decision making? We provide a concrete and intuitive class of metrics called locally generated (LG). We give a characterization of the LG metrics d for which I, SS, BC and DM agree on ranking the voters.     

Forms of representation for simple games: Sizes,conversions and equivalences

Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

MEPAR-miner: Multi-expression programming for classification rule mining

Classification and rule induction are two important tasks to extract knowledge from data. In rule induction, the representation of knowledge is defined as IF-THEN rules which are easily understandable and applicable by problem-domain experts. In this paper, a new chromosome representation and solution technique based on Multi-Expression Programming (MEP) which is named as MEPAR-miner (Multi-Expression Programming for Association Rule Mining) for rule induction is proposed. Multi-Expression Programming (MEP) is a relatively new technique in evolutionary programming that is first introduced in 2002 by Oltean and Dumitrescu. MEP uses linear chromosome structure. In MEP, multiple logical expressions which have different sizes are used to represent different logical rules. MEP expressions can be encoded and implemented in a flexible and efficient manner. MEP is generally applied to prediction problems; in this paper a new algorithm is presented which enables MEP to discover classification rules. The performance of the developed algorithm is tested on nine publicly available binary and n-ary classification data sets. Extensive experiments are performed to demonstrate that MEPAR-miner can discover effective classification rules that are as good as (or better than) the ones obtained by the traditional rule induction methods. It is also shown that effective gene encoding structure directly improves the predictive accuracy of logical IF-THEN rules.     

A distributed social choice protocol for combinatorial domains

In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.     

The influence of domain interpretations on computational models

Computational models are usually defined over specific domains. For example, Turing machines are defined over strings, and the recursive functions over the natural numbers. Nevertheless, one often uses one computational model to compute functions over another domain, in which case, one is obliged to employ a representation, mapping elements of one domain into the other. For instance, Turing machines (or modern computers) are understood as computing numerical functions, by interpreting strings as numbers, via a binary or decimal representation, say.We ask: Is the choice of the domain interpretation important? Clearly, complexity is influenced, but does the representation also affect computability? Can it be that the same model computes strictly more functions via one representation than another? We show that the answer is “yes”, and further analyze the influence of domain interpretation on the extensionality of computational models (that is, on the set of functions computed by the model).We introduce the notion of interpretation-completeness for computational models that are basically unaffected by the choice of domain interpretation, and prove that Turing machines and the recursive functions are interpretation-complete, while two-counter machines are incomplete. We continue by examining issues based on model extensionality that are influenced by the domain interpretation. We suggest a notion for comparing computational power of models operating over arbitrary domains, as well as an interpretation of the Church-Turing Thesis over arbitrary domains.     

Essential collections for equilibrium concepts

The aim of this study is to identify and characterize the parts of an extensive form game that are ??relevant?? to determining whether the outcome of a certain strategy profile is an equilibrium outcome. We formally define what we mean by ??relevant?? and refer to the associated collection of information sets as essential. We apply this idea to a number of classic equilibrium concepts and discuss some implications of our approach.     

On the risk-equivalence of two methods of randomization in statistics

For statistical decision problems, there are two well-known methods of randomization: on the one hand, randomization by means of mixtures of nonrandomized decision functions (randomized decision rules) in the game “statistician against nature,” on the other hand, randomization by means of randomized decision functions. In this paper, we consider the problem of risk-equivalence of these two procedures, i.e., imposing fairly general conditions on a nonsequential decision problem, it is shown that to each randomized decision rule, there is a randomized decision function with uniformly the same risk, and vice versa. The crucial argument is based on rewriting risk-equivalence in terms of Choquet's integral representation theorem. It is shown, in addition, that for certain special cases that do not fulfill the assumptions of the Main Theorem, risk-equivalence holds at least partially.     

Cycle games and cycle cut games

Two players play a game on a connected graphG. Each player in his turn occupies an edge ofG. The player who occupies a set of edges that contains a cycle, before the other does it, wins. This game may end in a draw. We call this game the normal cycle game. We define furthermore three similar games, which are called the misère cycle game, the normal cycle cut game and the misère cycle cut game. We characterize the above four games.     

Automatic knowledge extraction from survey data: learning <Emphasis Type="Italic">M</Emphasis>-of-<Emphasis Type="Italic">N</Emphasis> constructs using a hybrid approach

Data collected from a survey typically consist of attributes that are mostly if not completely binary-valued or binary-encoded. We present a method for handling such data where the underlying data analysis can be cast as a classification problem. We propose a hybrid method that combines neural network and decision tree methods. The network is trained to remove irrelevant data attributes and the decision tree is applied to extract comprehensible classification rules from the trained network. The conditions of the rules are in the form of a conjunction of M-of-N constructs. An M-of-N construct is a rule condition that is satisfied if (at least, exactly, at most) M of the N binary attributes in the construct are present. The effectiveness of the method is illustrated on data collected for a study of global car market segmentation. The results show that besides achieving high predictive accuracy, the method also allows meaningful interpretation of the relationships among the data variables.     

Fuzzy relations for the analysis of traders’ preferences in an information market game

In this paper we focus on preference and decision data gathered during a computer-supported information market game in which 35 students participated during seven consecutive trading sessions. The participants’ individual preferences on the market shares are collected to calculate a collective preference ranking using the Borda social choice method. Comparing this preference ranking to the shares’ actual market ranking resulting from the participants’ trading, we find a statistically significant difference between both rankings. As the preferences established by market behavior cannot be adequately explained through a social choice rule, we propose an alternative explanation based on the herd behavior phenomenon where traders imitate the most successful trader in the market. Using a decision analysis technique based on fuzzy relations, we study the participants’ rankings of the best share in the market during 7 weeks and compare the most successful trader to the other traders. The results from our analysis show that a substantial number of traders is indeed following the market leader.     

Group strategy-proof social choice functions with binary ranges and arbitrary domains: characterization results

We define different concepts of group strategy-proofness for social choice functions. We discuss the connections between the defined concepts under different assumptions on their domains of definition. We characterize the social choice functions that satisfy each one of them and whose ranges consist of two alternatives, in terms of two types of basic properties. Finally, we obtain the functional form of all rules satisfying our strongest version of group strategy-proofness.     

Generalized domination in closure systems

In the context of extracting maximal item sets and association rules from a binary data base, the graph-theoretic notion of domination was recently used to characterize the neighborhood of a concept in the corresponding lattice.In this paper, we show that the notion of domination can in fact be extended to any closure operator on a finite universe and be efficiently encoded into propositional Horn functions. This generalization enables us to endow notions and algorithms related to Formal Concept Analysis with Horn minimization and minimal covers of functional dependencies in Relational Databases.     

Rough sets theory for multicriteria decision analysis

The original rough set approach proved to be very useful in dealing with inconsistency problems following from information granulation. It operates on a data table composed of a set U of objects (actions) described by a set Q of attributes. Its basic notions are: indiscernibility relation on U, lower and upper approximation of either a subset or a partition of U, dependence and reduction of attributes from Q, and decision rules derived from lower approximations and boundaries of subsets identified with decision classes. The original rough set idea is failing, however, when preference-orders of attribute domains (criteria) are to be taken into account. Precisely, it cannot handle inconsistencies following from violation of the dominance principle. This inconsistency is characteristic for preferential information used in multicriteria decision analysis (MCDA) problems, like sorting, choice or ranking. In order to deal with this kind of inconsistency a number of methodological changes to the original rough sets theory is necessary. The main change is the substitution of the indiscernibility relation by a dominance relation, which permits approximation of ordered sets in multicriteria sorting. To approximate preference relations in multicriteria choice and ranking problems, another change is necessary: substitution of the data table by a pairwise comparison table, where each row corresponds to a pair of objects described by binary relations on particular criteria. In all those MCDA problems, the new rough set approach ends with a set of decision rules playing the role of a comprehensive preference model. It is more general than the classical functional or relational model and it is more understandable for the users because of its natural syntax. In order to workout a recommendation in one of the MCDA problems, we propose exploitation procedures of the set of decision rules. Finally, some other recently obtained results are given: rough approximations by means of similarity relations, rough set handling of missing data, comparison of the rough set model with Sugeno and Choquet integrals, and results on equivalence of a decision rule preference model and a conjoint measurement model which is neither additive nor transitive.     

When is tit-for-tat unbeatable?

We characterize the class of symmetric two-player games in which tit-for-tat cannot be beaten even by very sophisticated opponents in a repeated game. It turns out to be the class of exact potential games. More generally, there is a class of simple imitation rules that includes tit-for-tat but also imitate-the-best and imitate-if-better. Every decision rule in this class is essentially unbeatable in exact potential games. Our results apply to many interesting games including all symmetric 2 $\times $ 2 games, and standard examples of Cournot duopoly, price competition, public goods games, common pool resource games, and minimum effort coordination games.