Processing games with shared interest

This paper introduces processing problems with shared interest as an extension of processing situations with restricted capacities (Meertens, M., et al., Processing games with restricted capacities, 2004). Next to an individual capacity to handle jobs, each player now may have interest in the completion of more than one job, and the degrees of interest may vary among players. By cooperating the players can bundle their capacities and follow an optimal processing scheme to minimize total joint costs. The resulting cost allocation problem is analyzed by considering an associated cooperative cost game. An explicit core allocation of this game is provided.     

Sequencing games with repeated players

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. We thank two referees for their valuable suggestions for improvement. Financial support for P. Calleja has been given by the Ministerio de Educación y Ciencia and FEDER under grant SEJ2005-02443/ECON, and by the Generalitat de Catalunya through a BE grant from AGAUR and grant 2005SGR00984.     

带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

On coalition formation: a game-theoretical approach

This paper deals with the question of coalition formation inn-person cooperative games. Two abstract game models of coalition formation are proposed. We then study the core and the dynamic solution of these abstract games. These models assume that there is a rule governing the allocation of payoffs to each player in each coalition structure called a payoff solution concept. The predictions of these models are characterized for the special case of games with side payments using various payoff solution concepts such as the individually rational payoffs, the core, the Shapley value and the bargaining set M₁ ⁽ⁱ⁾. Some modifications of these models are also discussed.     

Two-step coalition values for multichoice games

We introduce and compare several coalition values for multichoice games. Albizuri defined coalition structures and an extension of the Owen coalition value for multichoice games using the average marginal contribution of a player over a set of orderings of the player’s representatives. Following an approach used for cooperative games, we introduce a set of nested or two-step coalition values on multichoice games which measure the value of each coalition and then divide this among the players in the coalition using either a Shapley or Banzhaf value at each step. We show that when a Shapley value is used in both steps, the resulting coalition value coincides with that of Albizuri. We axiomatize the three new coalition values and show that each set of axioms, including that of Albizuri, is independent. Further we show how the multilinear extension can be used to compute the coalition values. We conclude with a brief discussion about the applicability of the different values.     

Share functions for cooperative games with levels structure of cooperation

In a standard TU-game it is assumed that every subset of the player set N can form a coalition and earn its worth. One of the first models where restrictions in cooperation are considered is the one of games with coalition structure of Aumann and Drèze (1974). They assumed that the player set is partitioned into unions and that players can only cooperate within their own union. Owen (1977) introduced a value for games with coalition structure under the assumption that also the unions can cooperate among them. Winter (1989) extended this value to games with levels structure of cooperation, which consists of a game and a finite sequence of partitions defined on the player set, each of them being coarser than the previous one.     

Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

A general procedure to compute mixed modified semivalues for cooperative games with structure of coalition blocks

Semivalues are solution concepts for cooperative games that assign to each player a weighted sum of his/her marginal contributions to the coalitions, where the weights only depend on the coalition size. The Shapley value and the Banzhaf value are semivalues. Mixed modified semivalues are solutions for cooperative games when we consider a priori coalition blocks in the player set. For all these solutions, a computational procedure is offered in this paper.     

A sufficiency condition for coalitive pareto-optimal solutions

In ak-player, nonzero-sum differential game, there exists the possibility that a group of players will form a coalition and work together. If allk players form the coalition, the criterion usually chosen is Pareto optimality whereas, if the coalition consists of only one player, a minmax or Nash equilibrium solution is sought.In this paper, games with coalitions of more than one but less thank players are considered. Coalitive Pareto optimality is chosen as the criterion. Sufficient conditions are presented for coalitive Pareto-optimal solutions, and the results are illustrated with an example.     

On a New Class of Parallel Sequencing Situations and Related Games

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 for some particular classes. Furthermore, we study cooperative games arising from these sequencing situations. Our main result will be on the balancedness of these games.     

A coalition formation value for games in partition function form

The coalition formation problem in an economy with externalities can be adequately modeled by using games in partition function form (PFF games), proposed by Thrall and Lucas. If we suppose that forming the grand coalition generates the largest total surplus, a central question is how to allocate the worth of the grand coalition to each player, i.e., how to find an adequate solution concept, taking into account the whole process of coalition formation. We propose in this paper the original concepts of scenario-value, process-value and coalition formation value, which represent the average contribution of players in a scenario (a particular sequence of coalitions within a given coalition formation process), in a process (a sequence of partitions of the society), and in the whole (all processes being taken into account), respectively. We give also two axiomatizations of our coalition formation value.     

A shapley value for games with restricted coalitions

A restriction is a monotonic projection assigning to each coalition of a finite player setN a subcoalition. On the class of transferable utility games with player setN, a Shapley value is associated with each restriction by replacing, in the familiar probabilistic formula, each coalition by the subcoalition assigned to it. Alternatively, such a Shapley value can be characterized by restricted dividends. This method generalizes several other approaches known in literature. The main result is an axiomatic characterization with the property that the restriction is determined endogenously by the axioms.     

Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems

This paper is about games where the agents face constraints in the combined strategy space (unlike in standard games where the action sets are defined separately for each player) and about computational methods for solutions to such games. The motivation examples for such games include electricity generation problems with transmission capacity constraints, environmental management to control pollution and internet switching to comply to buffers of bounded capacity. In each such problem a regulator may aim at compliance to standards or quotas through taxes or charges. The relevant solution concept for these games has been known under several names like generalised Nash equilibrium, coupled constraint equilibrium and more. Existing numerical methods converging to such an equilibrium will be explained. Application examples of use of NIRA, which is a suite of Matlab routines that implement one of the methods, will be provided.      

具有学习效应的排序对策

建立了具有学习效应的排序对策模型,在这类排序对策中,工件的实际加工时间不再是常数,而是关于工件位置的递减幂函数。当所有工件的正常加工时间相等时,松弛可行顺序的条件,相应的排序对策是均衡的,但不一定是凸对策。     

On the NP-completeness of finding an optimal strategy in games with common payoffs

Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game. Received January 2001/Final version May 1, 2001     

Coordinating multi-location production and customer delivery

We study two parallel machine scheduling problems with equal processing time jobs and delivery times and costs. The jobs are processed on machines which are located at different sites, and delivered to a customer by a single vehicle. The first objective considered is minimizing the sum of total weighted completion time and total vehicle delivery costs. The second objective considered is minimizing the sum of total tardiness and total vehicle delivery costs. We develop several interesting properties of an optimal scheduling and delivery policy, and show that both problems can be solved by reduction to the Shortest-Path problem in a corresponding network. The overall computational effort of both algorithms is O(n ^m2+m+1) (where n and m are the number of jobs and the number of machines, respectively) by the application of the Directed Acyclic Graph (DAG) method. We also discuss several special cases for which the overall computational effort can be significantly reduced.     

The collective value: a new solution for games with coalition structures

In this study, we provide a new solution for cooperative games with coalition structures. The collective value of a player is defined as the sum of the equal division of the pure surplus obtained by his coalition from the coalitional bargaining and of his Shapley value for the internal coalition. The weighted Shapley value applied to a game played by coalitions with coalition-size weights is assigned to each coalition, reflecting the size asymmetries among coalitions. We show that the collective value matches exogenous interpretations of coalition structures and provide an axiomatic foundation of this value. A noncooperative mechanism that implements the collective value is also presented.     

Coalition formation in simple games with dominant players

A player, in a proper and monotonic simple game, is dominant if he holds a “strict majority” within a winning coalition. A (non-dictatorial) simple game is dominated if it contains exactly one dominant player. We investigate several possibilities of coalition formation in dominated simple games, under the assumption that the dominant player is given a mandate to form a coalition. The relationship between the various hypotheses on coalition formation in dominated games is investigated in the first seven sections. In the last section we classify real-life data on European parliaments and town councils in Israel.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

Tree,web and average web values for cycle-free directed graph games

On the class of cycle-free directed graph games with transferable utility solution concepts, called web values, are introduced axiomatically, each one with respect to a chosen coalition of players that is assumed to be an anti-chain in the directed graph and is considered as a management team. We provide their explicit formula representation and simple recursive algorithms to calculate them. Additionally the efficiency and stability of web values are studied. Web values may be considered as natural extensions of the tree and sink values as has been defined correspondingly for rooted and sink forest graph games. In case the management team consists of all sources (sinks) in the graph a kind of tree (sink) value is obtained. In general, at a web value each player receives the worth of this player together with his subordinates minus the total worths of these subordinates. It implies that every coalition of players consisting of a player with all his subordinates receives precisely its worth. We also define the average web value as the average of web values over all management teams in the graph. As application the water distribution problem of a river with multiple sources, a delta and possibly islands is considered.