Group activity selection problem with approval preferences

We consider a setting where one has to organize one or several group activities for a set of agents. Each agent will participate in at most one activity, and her preferences over activities depend on the number of participants in the activity. The goal is to assign agents to activities based on their preferences in a way that is socially optimal and/or stable. We put forward a general model for this setting, which is a natural generalization of anonymous hedonic games. We then focus on a special case of our model where agents’ preferences are binary, i.e., each agent classifies all pairs of the form ‘(activity, group size)’ into ones that are acceptable and ones that are not. We formulate several solution concepts for this scenario, and study them from the computational point of view, providing hardness results for the general case as well as efficient algorithms for settings where agents’ preferences satisfy certain natural constraints.     

Reactive model for autonomous vehicles formation following a mobile reference

The emergence of collective motion in nature is ubiquitous and can be observed from colonies of bacteria to flocks of birds. The scientific community is interested in understanding how the local interactions drive the crowd toward global behaviors. This paper presents an agent-based reactive model for groups of vehicles that aims to make the formation to follow a moving reference, represented as a virtual agent. The model is called reactive because the agents do not keep previous information but only respond to the current system state. Moreover, they only communicate with their close neighbors, limited by their sensory radius, except with the virtual agent that can be seen by everyone at the whole time. The aim of the model is to group the agents around the virtual agent while it moves to desirable directions. We solve the inverse problem of parameter estimation in order to drive the model toward specific objectives. This task is performed with the Generalized Extremal Optimization (GEO) algorithm, and the results are tested with path planning scenarios.     

A PGM framework for recursive modeling of players in simple sequential Bayesian games

We consider the situation where two agents try to solve each their own task in a common environment. In particular, we study simple sequential Bayesian games with unlimited time horizon where two players share a visible scene, but where the tasks (termed assignments) of the players are private information. We present an influence diagram framework for representing simple type of games, where each player holds private information. The framework is used to model the analysis depth and time horizon of the opponent and to determine an optimal policy under various assumptions on analysis depth of the opponent. Not surprisingly, the framework turns out to have severe complexity problems even in simple scenarios due to the size of the relevant past. We propose two approaches for approximation. One approach is to use Limited Memory Influence Diagrams (LIMIDs) in which we convert the influence diagram into a set of Bayesian networks and perform single policy update. The other approach is information enhancement, where it is assumed that the opponent in a few moves will know your assignment. Empirical results are presented using a simple board game.     

Stable and Pareto optimal group activity selection from ordinal preferences

In several situations agents need to be assigned to activities on basis of their preferences, and each agent can take part in at most one activity. Often, the preferences of the agents do not depend only on the activity itself but also on the number of participants in the respective activity. In the setting we consider, the agents hence have preferences over pairs “(activity, group size)” including the possibility “do nothing”; in this work, these preferences are assumed to be strict orders. The task will be to find stable assignments of agents to activities, for different concepts of stability such as Nash or core stability, and Pareto optimal assignments respectively. In this respect, particular focus is laid on two natural special cases of agents’ preferences inherent in the considered model, namely increasing and decreasing preferences, where agents want to share an activity with as many (as few, respectively) agents as possible.     

The influence of random interactions and decision heuristics on norm evolution in social networks

In this paper we explore the effect that random social interactions have on the emergence and evolution of social norms in a simulated population of agents. In our model agents observe the behaviour of others and update their norms based on these observations. An agent’s norm is influenced by both their own fixed social network plus a second random network that is composed of a subset of the remaining population. Random interactions are based on a weighted selection algorithm that uses an individual’s path distance on the network to determine their chance of meeting a stranger. This means that friends-of-friends are more likely to randomly interact with one another than agents with a higher degree of separation. We then contrast the cases where agents make highest utility based rational decisions about which norm to adopt versus using a Markov Decision process that associates a weight with the best choice. Finally we examine the effect that these random interactions have on the evolution of a more complex social norm as it propagates throughout the population. We discover that increasing the frequency and weighting of random interactions results in higher levels of norm convergence and in a quicker time when agents have the choice between two competing alternatives. This can be attributed to more information passing through the population thereby allowing for quicker convergence. When the norm is allowed to evolve we observe both global consensus formation and group splintering depending on the cognitive agent model used.     

On finite groups isospectral to simple symplectic and orthogonal groups

The spectrum of a finite group is the set of its element orders. Two groups are said to be isospectral if their spectra coincide. We deal with the class of finite groups isospectral to simple and orthogonal groups over a field of an arbitrary positive characteristic p. It is known that a group of this class has a unique nonabelian composition factor. We prove that this factor cannot be isomorphic to an alternating or sporadic group. We also consider the case where this factor is isomorphic to a group of Lie type over a field of the same characteristic p.     

On nonabelian simple groups having the same prime graph as an alternating group

All instances of coincidence between the prime graphs of nonabelian simple groups G and S are found, where G is an alternating group of degree n ≥ 5 and S is a nonabelian finite simple group. The precise bound of the maximal number of pairwise nonisomorphic nonabelian simple groups with the same prime graph is given in the case that one of these groups is an alternating group.     

Evolution of Organizational Performance and Stability in a Stochastic Environment

In this study of optimal organizational performance, we explore how the extent of interactions, both within and among other organizations, affects group performance and stability in a stochastic environment. We have refined a modeling framework (Kauffman and Johnsen's NKC model) so that group size and connections among groups (externalities) can be finely tuned. The search for improved group configurations is modeled as a random walk on a space of possible configurations whereby agents in a group periodically have the opportunity to accept or reject random changes in their characteristics. By controlling which groups have external connections with which other groups, and the magnitude of such connections, we can manipulate the topology of the problem—the web of interactions within and between groups. We present numerical results showing that optimal group size relates to the magnitude of externalities and the accumulated number of random trials. Our main result suggests that for short periods with few trials, large organizations perform best, while for longer time horizons, the advantage accrues to small sized groups with a small number of externalities. However, over these long time horizons, as the extent of external connections increases, modest increases in group size enhances their performance. Under all circumstances, organizations that perform best in the long run fall into a regime of largely stable responses to perturbations, which however, borders on a region of instability.     

Collective increase of first impression bias

We propose a simple model of first impression bias (FIB), where agents tend to ignore features which contradict their initial view. We consider a population of agents which are all in contact with a media, communicating randomly chosen features of an object. In some cases, we observe on simulations that FIB is significantly more frequent when the agents interact with each other than when they are only in contact with the media. We design an analytical aggregated model of the global agent‐based model behavior, which helps to explain the higher number of FIB due to the interactions. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

The effects of mental model formation on group decision making: An agent‐based simulation

We investigated dynamics of group decision making on complex problems when agents can form mental models of others from discussion history. Results indicated that as the agents' memory capacity increases, the group reaches superficial consensus more easily. Surprisingly, however, the shared mental model of the problem develops only within a limited area of the problem space, because incorporating knowledge from others into one's own knowledge quickly creates local agreement on where relevant solutions are, leaving other potentially useful solutions beyond the scope of discussion. The mechanisms stifling group‐level exploration and their implications for decision making research are discussed. © 2010 Wiley Periodicals, Inc. Complexity 16: 49–57, 2011     

Interdependent binary choices under social influence: Phase diagram for homogeneous unbiased populations

Coupled Ising models are studied in a discrete choice theory framework, where they can be understood to represent interdependent choice making processes for homogeneous populations under social influence. Two different coupling schemes are considered: the nonlocal or group interdependence model is used to study two interrelated groups making the same binary choice and the local or individual interdependence model represents a single group, where agents make two binary choices that depend on each other. For both models, phase diagrams and their implications in socioeconomic contexts are described and compared in the absence of private deterministic utilities (zero opinion fields). © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Subgroup coverings of some sporadic groups

A set of proper subgroups is a covering for a group if their union is the whole group. Determining the size of a smallest covering is an open problem for many simple groups. For some of the sporadic groups, we find subgroup coverings of minimal cardinality. For others we specify the isomorphism types of subgroups in a smallest covering and use graphs to calculate bounds for its size.     

Extension groups between simple Mackey functors

In order to better understand the structure of indecomposable projective Mackey functors, we study extension groups of degree 1 between simple Mackey functors. We explicitly determine these groups between simple functors indexed by distinct normal subgroups. We next study the conditions under which it is possible to restrict ourselves to that case, and we give methods for calculating extension groups between simple Mackey functors which are not indexed by normal subgroups. We then focus on the case where the simple Mackey functors are indexed by the same subgroup. In this case, the corresponding extension group can be embedded in an extension group between modules over a group algebra, and we describe the image of this embedding. In particular, we determine all extension groups between simple Mackey functors for a p-group and for a group that has a normal p-Sylow subgroup. Finally, we compute higher extension groups between simple Mackey functors for a group that has a p-Sylow subgroup of order p.     

Simple groups, permutation groups, and probability

We derive a new bound for the minimal degree of an almost simple primitive permutation group, and settle a conjecture of Cameron and Kantor concerning the base size of such a group. Additional results concern random generation of simple groups, and the so-called genus conjecture of Guralnick and Thompson. Our proofs are based on probabilistic arguments, together with a new result concerning the size of the intersection of a maximal subgroup of a classical group with a conjugacy class of elements.

     

A hybrid model for opinion formation

This paper presents a hybrid model for opinion formation in a large group of agents exposed to the persuasive action of a small number of strong opinion leaders. The model is defined by coupling a finite difference equation for the dynamics of leaders opinion with a continuous integro-differential equation for the dynamics of the others. Such a definition stems from the idea that the leaders are few and tend to retain original opinions, so that their dynamics occur on a longer time scale with respect to the one of the other agents. A general well-posedness result is established for the initial value problem linked to the model. The asymptotic behavior in time of the related solution is characterized for some general parameter settings, which mimic distinct social scenarios, where different emerging behaviors can be observed. Analytical results are illustrated and extended through numerical simulations.     

Gregarious GDDs with Two Associate Classes

The existence of group divisible designs with two associate classes has been studied for over 50 years. Probably the most difficult cases to solve are those in which the number of groups is less than the size of the blocks. Recently, such an existence problem was solved in the case where the groups have the same size and the blocks have size 3. In this paper, we continue to focus on blocks of size 3, solving the existence problem when the required designs are gregarious (each block intersects each group). These designs are tight to construct in the sense that they satisfy equality in one of the bounds required for GDDs to exist.     

Dynamic job assignment: A column generation approach with an application to surgery allocation

We consider the assignment of jobs to heterogeneous agents in a dynamic system with a rolling time horizon. An example is a hospital operating theatre where the jobs are surgeries and the agents are the surgeons. The paper is presented in the context of surgery allocation and the system is characterized as follows: Patients are grouped into categories and they arrive continually following a stochastic process. Patients in each group have specific time limits within which they need treatment and if it cannot be accommodated then the patients are outsourced. The service level is the percentage of patients in each group treated within the time limit. Surgery durations are stochastic and depend on the surgeon conducting the surgeries. Each surgeon has limited time available and expected overtime is penalized by a non-decreasing convex function. We develop a column generation approach for the assignment of already arrived patients and tentative future patients to surgeons on specific days. It balances the conflicting objectives of including as many arrived patients as possible within their time limits, maximizing the service level of future patients, and minimizing the expected overtime of surgeons. A computational study is conducted with the model embedded in a rolling time horizon frame. The study indicates that the assignment of patients based on our model increases system performance in terms of service level and reduced overtime compared to a First-Come-First-Served (FCFS) policy when the arrival rates of patients are medium to high compared to the capacity of the system.     

Simple agents learn to find their way: An introduction on mapping polygons

This paper gives an introduction to the problem of mapping simple polygons with autonomous agents. We focus on minimalistic agents that move from vertex to vertex along straight lines inside a polygon, using their sensors to gather local data at each vertex. Our attention revolves around the question whether a given configuration of sensors and movement capabilities of the agents allows them to capture enough data in order to draw conclusions regarding the global layout of the polygon.In particular, we study the problem of reconstructing the visibility graph of a simple polygon by an agent moving either inside or on the boundary of the polygon. Our aim is to provide insight about the algorithmic challenges faced by an agent trying to map a polygon. We present an overview of techniques for solving this problem with agents that are equipped with simple sensorial capabilities. We illustrate these techniques on examples with sensors that measure angles between lines of sight or identify the previous location. We also give an overview over related problems in combinatorial geometry as well as graph exploration.     

Cluster fluctuation in two-dimensional lattices with local interactions

It is known that under the local interactions of agents, we find cluster formations of states of agents, but few works exist on the changes (fluctuations) of clusters. This paper deals with the analysis of fluctuations of clusters with respect to states of agents placed on two-dimensional lattices having local interactions. We use two models; first we use Model S that consists of agents producing goods, whose states denote the activity of agents, as well as the accompanying multiple states. An agent decides the states in the subsequent time period by monitoring the states of neighboring agents. Then, we introduce Model P to cope with cases that are more realistic. In Model P, we assume that there exists a group of agents comprising a pool of labor agents and several firm agents collaborating in production, where the labor agents are free to move neighborhoods seeking better incomes. We find cluster formation and equilibrium in both models after the passage of time, but these cluster formations deform and become other formations by changing certain states of agents into random states, or by changing parameters to be random. In simulation studies, we show the conditions for the fluctuations of clusters and possible real applications.     

Unconditionally secure key assignment schemes

In this paper we propose an information-theoretic approach to the access control problem in a scenario where a group of users is divided into a number of disjoint classes. The set of rules that specify the information flow between different user classes in the system defines an access control policy. An access control policy can be implemented by using a key assignment scheme, where a trusted central authority (CA) assigns an encryption key and some private information to each class.We consider key assignment schemes where the key assigned to each class is unconditionally secure with respect to an adversary controlling a coalition of classes of a limited size. Our schemes are characterized by a security parameter r, the size of the adversary coalition. We show lower bounds on the size of the private information that each class has to store and on the amount of randomness needed by the CA to set up any key assignment scheme. Finally, we propose some optimal constructions for unconditionally secure key assignment schemes.