Search

A defender wants to detect as quickly as possible whether some attacker is secretly conducting a project that could harm the defender. Security services, for example, need to expose a terrorist plot in time to prevent it. The attacker, in turn, schedules his activities so as to remain undiscovered as long as possible. One pressing question for the defender is: which of the project’s activities to focus intelligence efforts on? We model the situation as a zero-sum game, establish that a late-start schedule defines a dominant attacker strategy, and describe a dynamic program that yields a Nash equilibrium for the zero-sum game. Through an innovative use of cooperative game theory, we measure the harm reduction thanks to each activity’s intelligence effort, obtain insight into what makes intelligence effort more effective, and show how to identify opportunities for further harm reduction. We use a detailed example of a nuclear weapons development project to demonstrate how a careful trade-off between time and ease of detection can reduce the harm significantly. ispartof: FEB Research Report KBI_1812 status: Published online

This paper introduces a new class of interactive cooperative purchasing situations and provides an explicit alternative characterization of the nucleolus of cooperative games, which offers an alternative to Kohlberg (1971). In our cooperative purchasing situation, the unit price of a commodity depends on the largest order quantity within a cooperating group of players. Due to a decreasing unit price function, players can obtain cost savings by purchasing cooperatively. However, to establish fruitful cooperation a decision has to be made about an adequate allocation of the corresponding cost savings. We analyze Maximum Cooperative Purchasing (MCP)-situation from the perspective of allocation by defining corresponding cooperative MCP-games. It turns out that in an MCP-game all coalitional values can be determined from the values of two-player coalitions. Moreover, it is shown that a decreasing unit price function is a sufficient condition for a non-empty core: the Direct Price solution is both a core element and a marginal vector. It is seen that the nucleolus of an MCP-game can be derived in polynomial time from the Direct Price solution, using a socalled nucleolus determinant. To show this result, the explicit alternative characterization of the nucleolus is used. Using the decomposition of an MCP-game into unanimity games we find an explicit expression for the Shapley value. Interestingly, the Shapley value can be interpreted as a specific tax and subsidize system. Finally, the behavior of the three solution concepts is compared numerically.

To analyze the allocation problem of the maximal cost savings of the whole group of jobs, we define and analyze a so-called corresponding cooperative family sequencing game which explicitly takes into account the maximal cost savings for any coalition of jobs. Using nonstandard techniques we prove that each family sequencing game has a non-empty core by showing that a particular marginal vector belongs to the core. Finally, we specifically analyze the case in which the initial order is family ordered.

For the class of minimum coloring games (introduced by Deng et al. (1999)) we investigate the existence of population monotonic allocation schemes (introduced by Sprumont (1990)). We show that a minimum coloring game on a graph G has a population monotonic allocation scheme if and only if G is (P4, 2K2)-free (or, equivalently, if its complement graph G is quasi-threshold). Moreover, we provide a procedure that for these graphs always selects an integer population monotonic allocation scheme.

Covert organizations are constantly faced with a tradeoff between secrecy and operational efficiency. Lindelauf, Borm and Hamers (2008) developed a theoretical framework to deter- mine optimal homogeneous networks taking the above mentioned considerations explicitly into account. In this paper this framework is put to the test by applying it to the 2002 Jemaah Islamiyah Bali bombing. It is found that most aspects of this covert network can be explained by the theoretical framework. Some interactions however provide a higher risk to the network than others. The theoretical framework on covert networks is extended to accommodate for such heterogeneous interactions. Given a network structure the optimal location of one risky interaction is established. It is shown that the pair of individuals in the organization that should conduct the interaction that presents the highest risk to the organization, is the pair that is the least connected to the remainder of the network. Furthermore, optimal networks given a single risky interaction are approximated and compared. When choosing among a path, star and ring graph it is found that for low order graphs the path graph is best. When increasing the order of graphs under consideration a transition occurs such that the star graph becomes best. It is found that the higher the risk a single interaction presents to the covert network the later this transition from path to star graph occurs.

Game theoretic analysis of sequencing situations has been restricted to manufactur- ing systems which consist of machines that can process only one job at a time. However, in many manufacturing systems, operations are carried out by batch machines which can simultaneously process multiple jobs. This paper aims to extend the game theoretical approach to the cost allocation problems arising from sequencing situations on systems that consist of batch machines. We first consider sequencing situations with a single batch machine and analyze cooperative games arising from these situations. It is shown that these games are convex and an expression for the Shapley value of these games is provided. We also introduce an equal gain splitting rule for these sequencing situa- tions and provide an axiomatic characterization. Second, we analyze various aspects of flow-shop sequencing situations which consist of batch machines only. In particular, we provide two cases in which the cooperative game arising from the flow-shop sequencing situation is equal to the game arising from a sequencing situation that corresponds to one specific machine in the flow-shop.

In order to be able to devise successful strategies for destabilizing terrorist organizations it is vital to recognize and understand their structural properties. This paper deals with the opti- mal communication structure of terrorist organizations when considering the tradeoff between secrecy and operational efficiency. We use elements from game theory and graph theory to determine the `optimal' communication structure a covert network should adopt. Every covert organization faces the constant dilemma of staying secret and ensuring the necessary coordina- tion between its members. For several different secrecy and information scenarios this dilemma is modeled as a game theoretic bargaining problem over the set of connected graphs of given order. Assuming uniform exposure probability of individuals in the network we show that the Nash bargaining solution corresponds to either a network with a central individual (the star graph) or an all-to-all network (the complete graph) depending on the link detection probabil- ity, which is the probability that communication between individuals will be detected. If the probability that an individual is exposed as member of the network depends on the information hierarchy determined by the structure of the graph, the Nash bargaining solution corresponds to cellular-like networks.

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera and Zarzuelo (2006) introduce highway problems and the corresponding cooperative cost games called high- way games to address the problem of fair allocation of the construction costs in case the underlying graph is a chain. In this note, we study the concavity and the balancedness of highway games on more general graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. The main result of our study is that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we provide sufficient conditions on highway problems defined on cyclic graphs such that the corresponding highway games are balanced.

A path scheme for a game is composed of a path, i.e., a sequence of coalitions that is formed during the coalition formation process and a scheme, i.e., a payoff vector for each coalition in the path. A path scheme is called population monotonic if a player’s payoff does not decrease as the path coalition grows. In this study, we focus on Shapley path schemes of simple games in which for every path coalition the Shapley value of the associated subgame provides the allocation at hand. Obviously, each Shapley path scheme of a game is population monotonic if and only if the Shapley allocation scheme of the game is population monotonic in the sense of Sprumont (Games Econ Behav 2:378–394, 1990). We prove that a simple game allows for population monotonic Shapley path schemes if and only if the game is balanced. Moreover, the Shapley path scheme of a specific path is population monotonic if and only if the first winning coalition that is formed along the path contains every minimal winning coalition. We also show that each Shapley path scheme of a simple game is population monotonic if and only if the set of veto players of the game is a winning coalition. Extensions of these results to other efficient probabilistic values are discussed.

In a proportionate flow shop problem several jobs have to be processed through a fixed sequence of machines and the processing time of each job is equal on all machines.By identifying jobs with agents, whose costs linearly depend on the completion time of their jobs, and assuming an initial processing order on the jobs, we face an additional problem: how to allocate the cost savings obtained by ordering the jobs optimally?In this paper, PFS games are defined as cooperative games associated to proportionate flow shop problems.It is seen that PFS games have a nonempty core.Moreover, it is shown that PFS games are convex if the jobs are initially ordered in decreasing urgency.For this case an explicit expression for the Shapley value and a specific type of equal gain splitting rule which leads to core elements of the PFS game are proposed.

In this paper we generalise marginal vectors and permutational convexity.We show that if a game is generalised permutationally convex, then the corresponding generalised marginal vector is a core element.Furthermore we refine the concept of permutational convexity and show that this refinement yields a sufficient condition for the corresponding marginal vector to be a core element.Finally, we prove that permutational convexity is equivalent to a restricted set of inequalities and that if a game is permutationally convex with respect to an order, then it is permutationally convex with respect to a related order as well.

An assignment situation can be considered as a two-sided market consisting of two disjoint sets of objects.A non-negative reward matrix describes the profit if an object of one group is assigned to an object of the other group. Assuming that each object is owned by a different agent, Shapley and Shubik (1972) introduced a class of assignment games arising from these assignment situations.This paper introduces assignment situations with multiple ownership. In these situations each object can be owned by several agents and each agent can participate in the ownership of more than one object.In this paper we study simple assignment games and relaxations that arise from assignment situations with multiple ownership.First, necessary and sufficient conditions are provided for balanced assignment situations with multiple ownership.An assignment situation with multiple ownership is balanced if for any choice of the reward matrix the corresponding simple assignment game is balanced.Second, balancedness results are obtained for relaxations of simple assignment games.

Two classes of one machine sequencing situations are considered in which each job corresponds to exactly one player but a player may have more than one job to be processed, so called RP(repeated player) sequencing situations.In max-RP sequencing situations it is assumed that each player's cost function is linear with respect to the maximum completion time of his jobs, whereas in min-RP sequencing situations the cost functions are linear with respect to the minimum completion times.For both classes, following explicit procedures to go from the initial processing order to an optimal order for the coalition of all players, equal gain splitting rules are defined.It is shown that these rules lead to core elements of the associated RP sequencing games.Moreover, it is seen that min-RP sequencing games are convex.

This paper considers one machine job scheduling situations or sequencing problems, where clients can have more than a single job to be processed in order to get a final output.Moreover, a job can be of interest for different players. This means that one of the main assumptions in classic sequencing problems is dropped: the one to one correspondence between clients and jobs.It is shown that the corresponding cooperative games are balanced for specific types of cost criteria.

This paper is a reaction on Ginsburgh and Zang (2003).It reconsiders the problem where a group of museums offer a pass such that the owner can visit these museums an unlimited number of times during a fixed period of time.The problem addressed is how to share the total joint income of this pass system among the museums.Ginsburgh and Zang propose to use the Shapley value of an associated cooperative game.Arguments are provided to model this problem within the framework of bankruptcy problems.

This paper introduces fixed tree games with repeated players (FRP games) which are a generalization of standard fixed tree games.This generalization consists in allowing players to be located in more than one vertex.As a consequence, these players can choose among several ways of connection with the root.In this paper we show that FRP games are balanced.Moreover, we prove that the core of an FRP game coincides with the core of a related concave fixed tree game.We show how to find the nucleolus and we characterize the orders which provide marginal vectors in the core of an FRP game.

In this paper we construct sets of marginal vectors of a TU game with the property that if the marginal vectors from these sets are core elements, then the game is convex.This approach leads to new upperbounds on the number of marginal vectors needed to characterize convexity.An other result is that the relative number of marginals needed to characterize convexity converges to zero.

This paper considers a special class of sequencing situations with two parallel machines in which each agent has precisely two jobs to be processed, one on each machine.The costs of an agent depend linearly on the final completion time of his jobs.We describe a procedure that provides an optimal processing order of the jobs.Furthermore, we study cooperative games arising from these sequencing situations.Our main result is balancedness of these games.

This paper considers sequencing situations with due date criteria. Three different types of criteria are considered: the weighted penalty criterion, the weighted tardiness criterion and the completion time criterion. The main focus is on convexity of the associated cooperative games.

Contains fulltext : 223712.pdf (Publisher’s version ) (Open Access) 13 p.

In a resource allocation problem there is a common-pool resource, which has to be divided among agents. Each agent is characterized by a claim on this pool and an individual concave reward function on assigned resources. An assignment of resources is optimal if the total joint reward is maximized. We provide a necessary and sufficient condition for optimality of an assignment. Analyzing the associated allocation problem of the maximal total joint reward, we consider corresponding resource allocation games. It is shown that these games have a non-empty core and thus allow for stable allocations. Moreover, an explicit expression for the nucleolus of these games is provided.

In this paper we study the relation between convexity of TU games and marginal vectors.We show that if specfic marginal vectors are core elements, then the game is convex.We characterize sets of marginal vectors satisfying this property, and we derive the formula for the minimum number of marginal vectors in such sets.

This note provides a methodological contribution to the allocation of joint revenues obtained from passepartouts. In a passepartout system a group of service providers offers a passepartout that allows its owners the use of specified services for an unlimited number of times during a fixed period of time. The corresponding allocation problem is then how to share the total joint revenues of the passepartout system adequately among the service providers. Arguments are provided to model a passepartout problem within the framework of bankruptcy and context-specific properties are considered in order to select an appropriate allocation rule.

This article investigates the structural position of covert (terrorist or criminal) networks. Using the secrecy versus information tradeoff characterization of covert networks it is shown that their network structures are generally not small-worlds, in contradistinction to many overt social networks. This finding is backed by empirical evidence concerning Jemaah Islamiyah's Bali bombing and a heroin distribution network in New York. The importance of this finding lies in the strength such a topology provides. Disruption and attack by counterterrorist agencies often focuses on the isolation and capture of highly connected individuals. The remarkable result is that these covert networks are well suited against such targeted attacks as shown by the resilience properties of secrecy versus information balanced networks. This provides an explanation of the survival of global terrorist networks and food for thought on counterterrorism strategy policy.

Subject classifications: Terrorism; Counterinsurgency; Intelligence; Defense; Covert networks; Affiliation networks.

This paper focuses on sharing the costs and revenues of maintaining a public network communication structure.Revenues are assumed to be bilateral and communication links are publicly available but costly.It is assumed that agents are located at the vertices of an undirected graph in which the edges represent all possible communication links.We take the approach from cooperative game theory and focus on the corresponding network game in coalitional form which relates any coalition of agents to its highest possible net benefit, i.e., the net benefitt corresponding to an optimal operative network.Although finding an optimal network in general is a difficult problem, it is shown that corresponding network games are (totally) balanced.In the proof of this result a specific relaxation, duality and techniques of linear production games with committee control play a role.Sufficient conditions for convexity of network games are derived.Possible extensions of the model and its results are discussed.

In this paper we introduce multiple longest traveling salesman (MLTS) games. An MLTS game arises from a network in which a salesman has to visit each node (player) precisely once, except its home location, in an order that maximizes the total reward.First it is shown that the value of a coalition of an MLTS game is determined by taking the maximum of suitable combinations of one and two person coalitions.Secondly it is shown that MLTS games with ¯ve or less players have a nonempty core.However, a six player MLTS game may have an empty core.For the special instance where the reward between a pair of nodes is equal to 0 or 1, we provide relations between the structure of the core and the underlying network.