The online scheduling with lookahead is a very important scheduling model, which has the character that at any time, it can foresee the information of some jobs that will coming in the near feature. The information can be the number of jobs that can foresee, or the jobs that will come in some time intervals. The $LK_\beta$ is one of the models, in which the length of the time interval that can foresee is fixed with value $\beta, \beta\geq0$. This paper considers the online scheduling on a single parallel-batch machine with linear lookahead. The main character of the linear lookahead model is that at any time $t$, one can foresee the jobs that will come in the time interval $(t, \lambda t+\beta]$ with $\lambda\geq1, \beta\geq0$. The length of the interval $(t, \lambda t+\beta]$ is changed as the time $t$ going on, having the tend of steady growth. When $\lambda=1$, it is in fact the $LK_\beta$ lookahead model. In this paper, the objective is to minimize the makespan. When the capacity of the batch is unbounded and the jobs arrive with no-decreasing processing times, for different values of $\lambda, \beta$, it gives optimal algorithm and best possible online algorithm, respectively.
A mixed graph is obtained by orienting some edges of a simple graph. The negative inertia index of a mixed graph is defined as the number of negative eigenvalues of its adjacency matrix. This paper mainly studies the negative inertia index of mixed graphs via the second kind Hermitian adjacency matrix. All mixed graphs with negative inertia index 1 are characterized.
Piecewise linear functions arise in many application domains, including transportation, telecommunications and production planning. In this paper, we concentrate on unsplittable multicommodity network flow problem with piecewise linear objective function. By introducing additional 0-1 variables, it can be modeled as a mixed integer linear programming formulation. We use the piecewise linear unsplittble flow arc set polyhedron of the considered problem as a substructure and derive two classes of valid inequalities. In addition, we describe the necessary and sufficient condition for these derived inequalities to be facet-defining. Finally, we demonstrate the effectiveness of using the derived inequalities as cutting planes to solve piecewise linear unsplittable multicommodity network flow problems by numerical results.
Population game theory is a new direction of game theory, developed in recent thirty years, which originated from "Mass-Action" interpretation on mixed strategies and equilibria in 1950 by J. Nash in his PhD dissertation. It established rational decision making theory for individuals in population and society consisting of large number of individuals, and has been applied extensively and intensively in sociology, biology, economics, management science and information science, etc. In this paper, we give a review on recent advances of population game theory and investigate new developing directions.
The aircraft takeoff/landing scheduling problem is an important problem for current airport operations. One difficulty in scheduling is that improving scheduling efficiency requires air traffic controller to issue more instructions, leading to a sharp increase in air traffic control workload. Overloading work may cause personnel fatigue, decision-making errors, and safety hazards. In view of this situation, a multi-objective mixed integer programming model for single runway takeoff/landing scheduling was constructed, which not only considers improving runway efficiency but also avoids excessively increasing air traffic control workload. The rank 2 matrix approximation based ant colony (RMA-AC) algorithm was designed. In comparison with the classical M-TPLP algorithm and CPLEX optimizer, numerical result validates that all the three methods have better performance than the first come first sever (FCFS) algorithm which is widely used in current aviation system. Specifically, the new algorithm RMA-AC is better than CPLEX for the runway efficiency improvement, and better than M-TPLP for the aircraft position shift control. It balances the runway efficiency and the air traffic controller workload. All these have positive effect on the airport efficiency improvement, delay reduction and safety scheduling.
The cooperative game with coalition structure generally involves two levels of cooperation: in which the players first form a small coalition, and then participate in the cooperation of the big coalition as a whole. In the One Belt, One Road Initiative, small sized alliance groups often have a weak voice in participating in cooperation projects, so they are easily at the disadvantages of profit distribution and their cooperative enthusiasm are affected. Therefore, it is necessary to further study the cooperative game with coalition structure and its solution. Based on this, a new solution method (i.e., weighted Owen value) is proposed in this paper, which can consider the impact of small coalition size on the cooperation. Then, based on the cooperative game with coalition structure and weighted Owen value, we describe the multi-level and complex cooperation relationship in the One Belt, One Road Initiative. The possible range of profit distribution are gotten for the player in the cross-border cooperation projects. Thus, the proposed weighted Owen value can be used to get a possible profit distribution range for each participant in cross border cooperation projects, which may provide a theoretical decision basis for the cross border largescale projects.
With differential games and classical pursuit-evasion problems as the main focus, this article aims to trace the historical development of group pursuit-evasion differential games. By addressing large-scale group pursuit-evasion issues from the point of mean-field games, the prospects of applying reinforcement learning techniques are elucidated. It proposes exploring solutions to inverse pursuit-evasion differential games, suitable for scenarios such as underwater autonomous vessels, terrestrial robots, and swarms of unmanned aerial vehicles. Diverging from other review papers, it devotes significant attention to the distinctive academic schools of thought in Russia and the former Soviet Union, highlighting their influence in the evolution of this field.
This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.
Considering a resources allocation scenario, in which the decision makers always tend to choose an allocation plan that does not render them regret. To this end, this paper proposes to employ regret aversion to help to allocate resources. Firstly, the data envelopment analysis approach is applied to measure the allocation performance. Then, the utility functions of beneficial resources and cost resources are distinguished. Thereafter, the regret value and rejoice value functions for resources allocation are built. With the help of Max-min rejoice value and Min-max regret value, the optimal resources allocation plan is determined. A numerical example is employed to show the applicability of the proposed approach. It shows that the method based on the regret aversion can help the decision maker to find an efficient resources allocation scheme and fairly distribute resources among decision making units.
This paper considers an $M/G/1$ queueing model with single vacation and modified $(p, N)$-policy. The modified $(p, N)$-policy means that when the vacation ends and the server returns to the system, if there are less than $N$ customers but at least one customer in the system, the server begins service with probability $p (0 \le p \le 1)$ or stays idle with probability $(1-p)$ until there are $N$ customers in the system and starts its service at once. By the renewal process theory, total probability decomposition technique and Laplace transform tool, we study the transient queue length distribution of the system, and obtain the expressions of the Laplace transform of the transient queue length distribution with respect to time $t$. Then, employing L'Hospital's rule and some algebraic manipulations, the recursive formulas of the steady-state queue length distribution are derived. Meanwhile, the explicit expressions for probability generating function of the steady-state queue length distribution and the expected queue size are presented. Finally, employing the renewal reward theorem, the explicit expression of the long-run expected cost per unit time is also presented. Numerical examples are provided to discuss the optimal control policy $N^*$ for economizing the system cost as well as the optimal two-dimensional control policy $(N^*, T^*)$ when the vacation time is a fixed length $T (T \ge 0)$.
The goal of thispaper is to establish a general framework for “Consensus Game” thatcharacterizes the behavior of blockchain ecosystems, and to addressbehaviors of the “Mining Pool Gap Game”, that is, we first give thecharacterizing and interpreting the behavior of “ConsensusEquilibria”, and establishing and explaining the stability of theblockchain platform itself with the positive answer based on theexistence of consensus equilibrium through the new concept called“consensus game” in the presence of mining gap (game) behavior, here, the blockchain ecosystem where “Gap Game” is located refersto a mining platform based on the consensus principle of “Proof ofWork” (PoW) with longest chain rules (LCR) proposed by Nakamoto in2008. Specifically, this paper first establishes the existence ofgeneral consensus equilibrium and the corresponding stabilityresults for continuous operation of the blockchain ecosystem undergeneral incentive mechanism conditions, based on the consensus gameframework in the blockchain ecosystem. Then, combined with the threemain factors involved in “mining Bitcoin” work, including workcosts, reward mechanisms, and mining capabilities, from theperspective of mining miner (group) profits, it interprets andanalyzes the potential impact of different embedding scenarios onthe “gap game behavior” of mining miners (groups). The theoreticalresults and case analysis of this article indicate that by combiningappropriate incentive compatibility mechanisms for different miningscenarios, the concept of consensus game (equilibrium) can obtain orform a consistent explanation and interpretation of mining behaviorin different scenarios without simulation results of scenario data.In addition, we have reason to expect and believe that consensusgames, combined with factors related to mining (group) profits, canhelp us build appropriate incentive compatibility mechanisms. Bycharacterizing behaviors such as “interval behavior”, “branchingchains”, and “mining pool attacks”, we can support the healthydevelopment of the digital economy and promote the development ofbasic theories of consensus economics.
This studies the existence and stability of α-core of games with discontinuous vector payoffs. By proposing the conditions of minimum values of games with vector payoffs and coalitional C-security, this gives two kinds of sufficient conditions to guarantee the existence of α-core of games with discontinuous vector payoffs. Furthermore, by using the lemma for generalized Hadmard well-posedness, the well-posedness of α-core is proven for a kind of game with discontinuous vector payoffs.
The refinement and formalization of equilibrium concepts mark the establishment of game theory as a distinct discipline. The development of game theory has been centered around the fundamental properties of various equilibrium concepts. It is generally accepted that the nonexistence of equilibrium is seen as a negative outcome, impeding the advancement of equilibrium research. This holds true for economic research as well. This paper illustrates, through two examples from the literature on non-cooperative games and perfectly competitive markets, that sometimes valuable interpretations can be provided for the nonexistence of equilibrium. The first example examines the evolution of fashion phenomena through a network game based on matching pennies, where the nonexistence of equilibrium is used to interpret the emergence of fashion cycles. The second example discusses the matching problem between companies and workers in a perfectly competitive labor market, where the nonexistence of equilibrium is used to explain the phenomenon of early contracting. Additionally, we briefly introduce Shapley's insightful interpretation regarding the empty core in transferable utility cooperative games.
Multi-convex programming(MCP) is an important model in solving many engineering optimization problems in areas like machine learning and signal and information processing. In this paper, some new concepts of partial optimum, partial KKT condition, partial KKT ponit, partial Slater constraint qualification, partial exactness and partial stableness for the penalty function of multi-convex programming are defined. Under the partial Slater constraint qualification, a partial optimum of MCP is proved to be equivalent to partial KKT condition of MCP. The partial exactness of MCP is proved to be equivalent to partial KKT condition of MCP. The partial exactness of MCP is proved to be equivalent to partial stableness of MCP. These results are important for studying the exact penalty function of multi convex programming.
The compensation solution is one of the important component efficient allocation rules for cycle-free graph game. Béal et al.(2018) proposed and characterized its efficient extension. In this paper, we propose an alternative axiomatic characterization of the efficient compensation solution. We first show that the efficient compensation solution can be characterized by efficiency, relative fairness and fair distribution of surplus. Secondly, we compare this value with other allocation rules through an application example.
The research of subnetwork reliability is valuable for designation and development of high performance computer system, and provides theoretical basis for system maintenance. In this paper, we derive an upper bound and a lower bound of the subnetwork reliability in Cayley graphs generated by complete graphs under the probability fault model. The effectiveness of theoretical results are analyzed.
In this paper, the reliability and optimization model of repairable $k/(M+N):G$ retrial system with standby switching failure, Bernoulli vacation and working breakdown is established. It is assumed that when the working component fails, it is replaced by a warm standby component that has not yet failed. The replacement operation will lead to the failure of the warm standby component with a certain probability. In retrial space, the failed components follow the principle of random retrial. By using Runge-Kutta method and Cramer's rule, the transient and steady-state probabilities of the system are solved respectively, and the transient and steady-state reliability indexes and some other steady-state performance indexes of the system are obtained. Based on the defined cost elements and the steady-state performance indexes of the system, a minimization model of the total cost function per unit time is constructed, and the genetic particle swarm optimization (GA_PSO) hybrid algorithm is used to solve the optimization design model. The effects of different system parameters on the total cost function per unit time and steady-state performance index are evaluated by numerical experiments. The experimental results verify the reliability of the established model.
How to allocate profit reasonablely is an important issue in cooperative game research. The distribution rule based on Shapley value, proposed by Shapley, the winner of the Nobel Prize in Economics, is the commonly used one in cooperative games. The cooperative game theory on graphs greatly enriches the research methods of game theory, and Shapley value on graphs has been widely applied in node influence, community detection and link prediction of social networks. Shapley distance on graphs is suggested based on Shapley value and it can be used to measure the cost of one vertex to access another one. Analogous to Wiener index and Kirchhoff index in graph theory, a new graph parameter, namely Shapley index, is proposed. In this paper, we establish the analytical expressions of Shapley distance and Shapley index of three kinds of conglutinate graphs, such as friendship graphs, book graphs and generalized rose graphs. These empirical examples provide methodological guidance for the computation of Shapley index of other complex topological structures.
With the increasing integration of global economy and closer international relations, win-win cooperation has become a core trend in today. As a powerful tool for studying cooperative issues, cooperative game mainly explores how to allocate the benefits generated by cooperation among players. The Shapley value, as one of the most important solutions in cooperative games, has significant research significance and value. This paper mainly introduce some research on the axiomatization of the Shapley value from the point of additivity, balanced contribution, marginality, fairness, reduced consistency, associated consistency and some special player properties. We finally give a brief summary from the perspective of future research.
With the advancement of Internet technology and social network, a multitude of real-world issues can be modeled as combinatorial optimization problems on networks, attracting widespread attention. In the optimization process, agents often engage in strategic behavior driven by personal interests to maximize their utilities. This "selfish" behavior can, on one hand, affect other participants, while on the other hand, the strategies of all agents directly determine the achievement of societal objectives. Therefore, cooperation and competition coexist among participants, giving rise to combinatorial optimization games. This paper aims to delve into three challenging combinatorial optimization games on networks: public goods games, vertex cover games, and routing games. These three categories of games not only hold significant positions in the fields of combinatorial optimization and theoretical computer science, but also have extensive applications across multiple interdisciplinary areas including management science and engineering, economics, and more. To this end, we will provide a systematic introduction to these three types of combinatorial optimization games and thoroughly review their recent research progress and breakthroughs.
