Stabilizing Identical Parallel Machine Scheduling Cooperative Game Via Pricing

The main research object of cooperative games is a coalition composed of multi-ple players.An important hypothesis is that players can form coalition to obtain higher utility.From the perspective of economics,unlike non-cooperative games that empha-size individual rationality,cooperative games emphasize collective rationality,allowing players in the game to cooperate with each other and form coalitions to improve their own interests.One of the main research purposes of cooperative games is to design cer-tain rules to allocate costs among players in a fair and reasonable manner.An important concept is the core,which represents the collection of the cost allocation vectors.If the core exists,the corresponding cooperative game is balanced and the grand coalition is stable.In practice,a stable grand coalition is often ideal because it represents the best social efficiency.But in an unbalanced cooperative game with an empty core,the grand coalition is unsustainable.In order to be able to bring the best social welfare,the external third party may take measures to stabilize the grand coalition.The tool of subsidy,in order to cooperate among all the players,the third party will provide a certain amount of external subsidies so that the formation of a grand coalition is the best choice for all the players.The tool of subsidy is another way to stabilize the grand coalition,that is,if a coalition wants to leave the grand coalition,it must pay the cost of deviation.Unlike the subsidy tool that comes at the price of a third party’s social opportunity cost,the punishment tool can cause dissatisfaction among players in the game.This paper studies a new tool for the third party to maintain the stability of the grand coalition in the parallel machine scheduling cooperative game.We propose a new scheme:use the setup cost of the machine as the price in the parallel identical ma-chine scheduling game,the third party can change the price and use the increment of the price as a subsidy to stabilize the grand coalition.Our core idea is to explore an appro-priate price so that the increment in price can be exactly used as a subsidy to stabilize the grand coalition.At this time,without sacrificing the social opportunity cost of the third party,the players in the game can stabilize themselves.Let’s start with an inspired example to more intuitively explain how the price and subsidy affect the parallel ma-chine scheduling cooperative game and stabilize the grand coalition.Based on these,we built a model that allows decision makers to quantify the trade-off between price and subsidy.By establishing the price subsidy function,we demonstrated the trade-off re-lationship between price and subsidy,and analyzed some properties of the model.Due to the inherently exponential coalition stability constraints in the cooperative game,it is more difficult to solve the problem.The direct use of conventional algorithms has a higher computational complexity.For this reason,we further explored some theorems to provide the theoretical basis for the effectiveness of algorithms we proposed.Mean-while,the simulation results show that the proposed algorithms are also very efficient.The model and algorithms in this paper are applicable for parallel identical machine scheduling cooperative games with unweighted and weighted jobs,and it shows how decision makers choose the appropriate price to stabilize the grand coalition without paying additional costs.