LS sets as cohesive subsets of graphs and hypergraphs

For social scientists, a ‘clique’ has long been seen as a subset of a population whose members are more tightly linked to other members of the subset than they are to non-members. Similar ideas have arisen in clustering theory. Most approaches to the problem of defining such subsets have concentrated either on maximizing the number of intra-subset ties or minimizing the number of inter-subset ties. LS sets in graphs or hypergraphs provide a way of addressing simultaneously both intra-subset ties and inter-subset ties. A new characterization of LS sets is given and used to derive simple proofs of several important results on LS sets.     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

Compensatory transfers in two-player decision problems

This paper presents an axiomatic characterization of a family of solutions to two-player quasi-linear social choice problems. In these problems the players select a single action from a set available to them. They may also transfer money between themselves.The solutions form a one-parameter family, where the parameter is a non-negative number, t.The solutions can be interpreted as follows: Any efficient action can be selected. Based on this action, compute for each player a “best claim for compensation”. A claim for compensation is the difference between the value of an alternative action and the selected efficient action, minus a penalty proportional to the extent to which the alternative action is inefficient. The coefficient of proportionality of this penalty is t. The best claim for compensation for a player is the maximum of this computed claim over all possible alternative actions. The solution, at the parameter value t, is to implement the chosen efficient action and make a monetary transfer equal to the average of these two best claims. The characterization relies on three main axioms. The paper presents and justifies these axioms and compares them to related conditions used in other bargaining contexts. In Nash Bargaining Theory, the axioms analogous to these three are in conflict with each other. In contrast, in the quasi-linear social choice setting of this paper, all three conditions can be satisfied simultaneously.This work was supported by the Division of Research at the Harvard Business School. Thanks are due to the Cowles Foundation for Research in Economics at Yale University for its kind hospitality during the Spring of 2002. I have received helpful advice and comments from Youngsub Chun, Ehud Kalai, Herve Moulin, Al Roth, Ilya Segal, Adam Szeidl, Richard Zeckhauser, and other members of the Theory Seminars at Harvard, MIT, Princeton, Rice and Northwestern.     

Representations of simple games by social choice functions

We investigate possible constructions of choice procedures (social choice functions) for committees (simple games). The notion of a capacity of a committee is derived from our construction. We determine the capacity of strong, symmetric and weak simple games. We also provide an upper bound on the capacity of a simple game without veto players.     

Transitive permutation groups and equipotent voting rules

Let F a two-alternative voting rule and G_F the subgroup of permutations of the voters under which F is invariant. Group theoretic properties of G_F provide information about the voting rule F. In particular, sets of imprimitivity of G_F describe the ‘committee decomposition’ structure of F and permutation group transitivity of G_F (equipotency) is shown to be closely connected with equal distribution of power among the voters. If equipotency replaces anonymity in the hypotheses of May's theorem, voting rules other than simple majority are possible. By combining equipotency with two additional social choice conditions a new characterization of simple majority rule is obtained. Equipotency is proposed as an important alternative to the more restrictive anonymity as a fairness criterion in social choice.     

Cultural differences and collective action: A social network perspective

This study investigates how cultural differences on the individualism–collectivism (I–C) dimension of social networks influence the outcomes of collective action. Evidence shows that I–C values are indicators of how people construct their social networks and use strong/weak ties as a behavioral reference. Specifically, when compared with individualists, collectivists tend to hold larger strong‐tie networks and endow strong ties with greater interpersonal influence. Results obtained from agent‐based modeling indicate that individualistic cultures are more effective at propagating collective action when one of the two following conditions is met: (1) people have a strong motivation to participate and (2) the connectivity of the social system is low. In contrast, spread of collective action in collectivistic cultures is more effective when motivation is not strong and the connectivity of the social system is high. These findings call for a serious consideration of the role of culture in collective action. © 2014 Wiley Periodicals, Inc. Complexity 20: 68–77, 2015     

Asymptotic properties of rank tests under discrete distributions

Summary This paper is devoted to problems of rank tests when samples are drawn from purely discrete distributions. There are considered two ways of treatment of ties, and the distribution of the respective test statistics is derived under the hypothesis of randomness and under the contiguous alternative. Furthermore, their asymptotic power and efficiency are established.     

The rational weakness of strong ties: Failure of group solidarity in a highly cohesive group of rational agents

Recent research (Flache, 1996; Flache and Macy, 1996) suggests a "weakness of strong ties." Cohesive social networks may undermine group solidarity, rather than sustain it. In the original analysis, simulations showed that adaptive actors learn cooperation in bilateral exchanges faster than cooperation in more complex group exchanges, favoring ties at the expense of the common good. This article uses game theory to demonstrate that cognitive simplicity is not a scope condition for the result. The game theoretical analysis identifies a new condition for the failure of group solidarity in a cohesive group. Task uncertainty may make rational cooperation increasingly inefficient in common good production. Accordingly, rational actors may increasingly sacrifice benefits from common good production in order to maintain social ties, as their dependence on peer approval rises.     

Pricing and logit-based mode choice models of a transit and highway system with elastic demand

The objective of this paper is to enhance the insights into transport pricing mechanism and the corresponding mode choice behavior in a simple bi-modal transportation system with elastic demand. This system comprises a mass transit parallel to a bottleneck-constrained highway between a residential area and a workplace. We derive and compare three pricing schemes: the arbitrarily fixed pricing, the first-best pricing for a social optimum of the system, and the second-best pricing in the case of incapability of road toll. It is shown that the first-best pricing requires to implement a road toll and a transit fare simultaneously, and the optimal transit fare for the second-best solution should be set to be a weighted sum of the marginal external costs between auto and transit commuters. A numerical example is presented to illustrate how the pricing policies affect the demand implementation, the mode choice behavior and the efficiency of the whole transportation system.     

Post-merger cultural integration from a social network perspective: a computational modeling approach

Although cultural integration, or sharing a common corporate culture, is crucial for the success of mergers, previous studies have been limited to firm-level analyses. From a social network perspective, this study explores how cultural integration emerges from the patterns of social interactions among individuals. Using an agent-based model, we investigate the impact of network structures within and between two merging firms on post-merger cultural integration and organizational dysfunctions—individual turnover, interpersonal conflict and organizational communication ineffectiveness—that arise from insufficient cultural integration. The simulation results demonstrate that the highest level of cultural integration is achieved when social ties are more centralized within each merging firm and the social ties between the merging firms are less concentrated on central individuals. Additionally, the results show that within-firm and between-firm network structures significantly affect individual turnover, interpersonal conflict and organizational communication ineffectiveness, and that these three outcome measurements do not vary in tandem.     

Proportion estimation in ranked set sampling in the presence of tie information

Ranked set sampling (RSS) is a statistical technique that uses auxiliary ranking information of unmeasured sample units in an attempt to select a more representative sample that provides better estimation of population parameters than simple random sampling. However, the use of RSS can be hampered by the fact that a complete ranking of units in each set must be specified when implementing RSS. Recently, to allow ties declared as needed, Frey (Environ Ecol Stat 19(3):309–326, 2012) proposed a modification of RSS, which is to simply break ties at random so that a standard ranked set sample is obtained, and meanwhile record the tie structure for use in estimation. Under this RSS variation, several mean estimators were developed and their performance was compared via simulation, with focus on continuous outcome variables. We extend the work of Frey (2012) to binary outcomes and investigate three nonparametric and three likelihood-based proportion estimators (with/without utilizing tie information), among which four are directly extended from existing estimators and the other two are novel. Under different tie-generating mechanisms, we compare the performance of these estimators and draw conclusions based on both simulation and a data example about breast cancer prevalence. Suggestions are made about the choice of the proportion estimator in general.     

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.     

On the information about individual utilities used in social choice

This paper investigates the consequences of the requirement tha a social choice method should convey as much information as possible about the individuals' values. It is first shown that if interpersonal comparisons of utilities are excluded, then the only information about individual values that can be used in the context of social choice is ordinal information. It is then argued that Arrow's independence condition demands that only a part of the information about the individual preferences be used in the social choice. Finally, it is shown that the requirement of maximal information gives strong support to Smith's (1973) ‘separability’ condition. In combination with Smith's result this shows that the choice methods that convey the most information about individual preferences are the ‘generalized point systems’ (also called ‘scoring functions’ or ‘ranking systems’).     

On the choice of signs for householder's matrices

The numerical construction of Householder's matrices of the form I-2ww^H is known to be a problem with two distinct solutions; more precisely, the actual construction of such a matrix in a given context involves a choice of sign, and it is widely believed that only one alternative is correct, the other one leading to possible numerical unstabilities. This paper shows that the numerical stability of the process depends not on the chosen sign itself but only on the implementation of the actual computations; as well-conditioned approach for the non-classical case is presented and illustrated by a numerical example. Both signs are thus equally correct and there seems to be no reason at all why a specific sign should be prefered to the other.     

Modeling optimal social choice: matrix-vector representation of various solution concepts based on majority rule

Various Condorcet consistent social choice functions based on majority rule (tournament solutions) are considered in the general case, when ties are allowed: the core, the weak and strong top cycle sets, versions of the uncovered and minimal weakly stable sets, the uncaptured set, the untrapped set, classes of k-stable alternatives and k-stable sets. The main focus of the paper is to construct a unified matrix-vector representation of a tournament solution in order to get a convenient algorithm for its calculation. New versions of some solutions are also proposed.     

The stable marriage problem with master preference lists

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.     

Parametric linear programming and anti-cycling pivoting rules

The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.Supported in part by grant ECS-83-6224 from the Systems Theory and Operations Research Division of the National Science Foundation.Supported in part by Presidential Young Investigator grant 8451517-ECS of the National Science Foundation.     

Nothing else matters: Evolution of preference for social prestige

This paper seeks answers to two questions. First, if a greater social activity of an individual enhances oblique (i.e. to non-relatives) transmission of her cultural traits at the expense of vertical (i.e. to children) transmission as well as family size, which behavior is optimal from cultural evolution standpoint? I formalize a general model that characterizes evolutionarily stable social activity. The proposed model replicates the theory of Newson et al. (2007) that fertility decline is caused by increasing role of oblique cultural transmission. Second, if social activity is a rational choice rather than a culturally inherited trait, and if cultural transmission acts on preferences rather than behaviors, which preferences survive the process of cultural evolution? I arrive at a very simple yet powerful result: under mild assumptions on model structure, only preferences which emphasize exclusively the concern for social prestige, i.e. extent to which one’s cultural trait has been picked up by others, survive.     

Optimal bounds for the no-show paradox via SAT solving

One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by Moulin (1988) has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin’s result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.     

Feature-based elimination: Model and empirical comparison

Experimental and verbal protocol research suggest that consumers appear to use noncompensatory screening strategies to remove alternatives and simplify complex choice situations prior to making a choice. Existing multi-phased choice models assume that the consumer initially evaluates each alternative to determine whether it should pass the first-stage screen and enter the choice set. The feature-based elimination model proposed in this study allows the consumer to avoid processing information for each alternative when forming the choice set. The consumer is assumed to apply a sequence of noncompensatory screens, similar to the elimination-by-aspects strategy, to form the choice set. An empirical application of the model demonstrates that cross-sectional heterogeneity in screening strategies can also be accommodated. One finding from this application is that heterogeneity in screening strategies may be at least as prevalent as heterogeneity in preferences. A comprehensive empirical comparison of the proposed model with existing two-stage models for scanner panel data shows that the model performs at least as well as all existing models and substantially better than most. The empirical performance of the model, coupled with its theoretical appeal and consistency with actual accounts of decision making in complex situations, make the proposed model an appealing alternative to existing multi-phased choice models.