Table of Content

15 June 2024, Volume 28 Issue 2

Previous Issue    Next Issue

Survey on several combinatorial optimization games on networks

Yukun CHENG, Xin HAN, Xiuyang CHEN, Zhao ZHANG

2024, 28(2):  1-29.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.001

Asbtract ( 318 )   HTML ( 13)   PDF (1125KB) ( 271 )  

Figures and Tables | References | Related Articles | Metrics

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.

A study of manufacturer's selection of internet channel construction strategy under consumer behavior-based pricing

Tao WANG

2024, 28(2):  30-46.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.002

Asbtract ( 261 )   HTML ( 2)   PDF (1128KB) ( 74 )  

Figures and Tables | References | Related Articles | Metrics

By considering the fact of the increasingly prominent phenomenon of consumer Behavior-Based Pricing (BBP) in the internet sales environment, we establish an internet channel decision model that is constituted by an e-commerce platform and a manufacturer. The decision problems about the manufacturer building its own internet direct channel mode and entering the e-commerce platform mode are analyzed respectively. Equilibrium decisions in the two modes are compared. Results show that if the manufacturer establishes its own internet direct channel, the e-commerce platform will offer lower price for new customers than for existing customers, while the manufacturer will treat new and existing customers differently based on the cost of building own channel and consumers' shopping cost. Under the manufacturer enters the e-commerce platform mode, the manufacturer will offer lower price for new customers, and the e-commerce platform's strategy for new and existing customers is influenced by commission rate. Moreover, when the commission rate is small and the licensing fee is moderate, or when the commission rate is moderate and the licensing fee is small can make the e-commerce platform will be willing to attract the manufacturer to move in and at the same time the manufacturer will choose to enter the e-commerce platform. Finally, we find that in order to enable the two participants to implement BBP when the manufacturer builds its own internet direct channel, it is necessary to ensure that the sales cost per unit product is small enough when it builds its own channel. In order to enable the two participants to implement BBP when the manufacturer enters the e-commerce platform, it is necessary to ensure that the commission rate and licensing fee charged by the e-commerce platform are low. The numerical analysis results show that it can generate more producer surplus than building its own internet direct channel if the manufacturer enters into the e-commerce platform, while the opposite is true for consumer surplus. Furthermore, if consumers' shopping cost and commission rate are large, the manufacturer enters into the e-commerce platform will generate more social welfare than in the case of establishing its own internet channel.

A class of differential privacy stochastic gradient descent algorithm with adaptive gradient clipping

Jiaqi ZHANG, Jueyou LI

2024, 28(2):  47-57.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.003

Asbtract ( 404 )   HTML ( 10)   PDF (842KB) ( 190 )  

Figures and Tables | References | Related Articles | Metrics

Gradient clipping is an effective method to prevent gradient explosion, but the selection of the gradient clipping parameter usually has a great influence on the performance of training models.To address this issue, this paper proposes an improved differentially private stochastic gradient descent algorithm by adaptively adjusting the gradient clipping parameter. First, an adaptive gradient clipping method is proposed by using the quantile and exponential averaging strategy to dynamically and adaptively adjust the gradient clipping parameter. Second, the convergence and privacy of the proposed algorithm for the case of non-convex objective function are analyzed. Finally, numerical simulations are performed on MNIST, Fasion-MNIST and IMDB datasets. The results show that the proposed algorithm can significantly improve the model accuracy compared to traditional stochastic gradient descent methods.

An allocation scheme of multilevel cooperative games based on a weighted Owen value under the Belt and Road Initiative

Xiaohui YU, Wu LI, Hanzhang LI

2024, 28(2):  58-70.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.004

Asbtract ( 449 )   HTML ( 5)   PDF (805KB) ( 124 )  

Figures and Tables | References | Related Articles | Metrics

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.

Single-machine online scheduling to minimize maximum weighted completion time with limited weights

Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG

2024, 28(2):  71-80.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.005

Asbtract ( 217 )   HTML ( 5)   PDF (2542KB) ( 65 )  

Figures and Tables | References | Related Articles | Metrics

The setting we consider is nonpreemptive single machine online scheduling, with the objective to minimize the maximum weighted completion time of jobs. The weight of the job is not only limited strictly within the processing time compass of this job, but also agreeable with processing time of this job, i.e., $ ap_j\leq w_j\leq bp_j(a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$ and if $ w_i>w_j$, then $ p_i\geq p_j$. Especially, if $ w_i=w_j$, then $ p_i=p_j$. Significantly, there are irrelevant jobs arriving online over time and the knowledge of each job $ J_j$, such as its processing length $ p_j$ and weight $ w_j$, is not revealed for the scheduler until it is released at time $ r_j$. By means of adversary method, it is explicitly derived that the lower bound of the considered problem is $ 1+\frac{b}{b+a}$. Then we provide a best possible online algorithm with the competitive ratio of $ 1+\frac{b}{b+a}$. Moreover, the competitive ratio of this algorithm is $ \frac{\sqrt5+1}{2}$, when $ a=\frac{\sqrt{5}-1}{2}b$.

An inertial projection algorithm for nonmonotone continuous variational inequalities

Minglu YE, Ming HUANG

2024, 28(2):  81-92.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.006

Asbtract ( 214 )   HTML ( 4)   PDF (746KB) ( 87 )  

Figures and Tables | References | Related Articles | Metrics

An infeasible projection algorithm (IPA) for solving nonmonotone variational inequality problems was proposed by Ye (2022). Without needing any monotonicity condition of the underlying mapping, the global convergence of the sequence generated by IPA is established whenever the underlying mapping is continuous and the solution set of the dual variational inequality is nonempty. In this paper, we present an inertial IPA for solving nonmonotone variational inequalities. The global convergence of this new algorithm is proved under the same assumptions in IPA. Numerical experiments show that the inertial technique can accelerate IPA.

Production capacity sharing bargaining based on Lagrangian relaxation

Qiiong WU, Changjun WANG

2024, 28(2):  93-102.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.007

Asbtract ( 308 )   HTML ( 2)   PDF (908KB) ( 104 )  

Figures and Tables | References | Related Articles | Metrics

The production capacity sharing problem was studied in this paper. Considering that the game is composed of a capacity provider and customers, in which the capacity provider and customers are self-interest, with different demands and different market relations. Nash bargaining theory was adopted to explore the sharing strategy of the production capacity. To be specific, the classic scheduling model and the asymmetric Nash bargaining model were combined to develop a production capacity sharing model, which was essentially a nonlinear integer program. To address the computational issue, a solving method based on Lagrangian relaxation was designed, and then, the bargaining results of production capacity sharing were given. Simulation analysis shows that the proposed algorithm performs well in most cases. It is found that when the capacity provider has a min-sum objective function, the capacity provider pays attention to the performance indicators of all customers, and the conflict between the capacity provider and customers are particularly significant. With the increase of bargaining power of the capacity provider, the capacity provider index is optimized, but the customer performance index becomes worse. However, when the bargaining power of the capacity provider is very strong, it will lead to the fluctuation of the overall efficiency of the system. Therefore, the game parties need to maintain a reasonable bargaining power.

Robust optimal reinsurance based on multiple insurance businesses and competition

Peng YANG

2024, 28(2):  103-116.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.008

Asbtract ( 207 )   HTML ( 3)   PDF (837KB) ( 55 )  

Figures and Tables | References | Related Articles | Metrics

Based on the mean-variance criterion, this paper studies the robust optimal reinsurance problem under the competition between an insurance company and a reinsurance company. The insurance company operates $ n $ kinds of dependent insurance businesses, and it buys reinsurance for each insurance business to reduce the claim risk. Through relative performance, this paper quantifies the competition between the insurance company and the reinsurance company. The insurance company's goal is to choose an optimal reinsurance strategy to minimize the risk when the mean of terminal wealth is given in the worst market situation. By using the theory of stochastic control and stochastic dynamic programming, this paper establishes the Hamilton-Jacob-Bellman-Isaacs (HJBI) equation. Furthermore, by solving HJBI equation and using Lagrange duality theory, this paper obtains the explicit solution for the robust optimal reinsurance strategy. Finally, the influence of model parameters on the robust optimal reinsurance strategy and efficient frontier is explained by numerical experiments. The research results can guide insurance companies to adopt optimal reinsurance strategies to minimize the risks that they face when operating a variety of insurance businesses.

The smoothing method of the oriented distance function and its application

Xinyi LI, Ying GAO, Chunjie ZHAO

2024, 28(2):  117-130.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.009

Asbtract ( 230 )   HTML ( 21)   PDF (936KB) ( 80 )  

Figures and Tables | References | Related Articles | Metrics

This paper considers the smooth representation of the oriented distance function and its application. On the basis of two existing smoothing methods, the smoothing representation of this special non-smooth function is given. As a special case, a more specific smoothing function of this function is given in two dimensional space. Finally, by using the smoothing function of the oriented distance function and its application in the scaling method of multi-objective optimization problem, we study the non-smooth multi-objective optimization problem and the corresponding smooth single-objective optimization problem, and give the relationship between the solution sets of the two problems.

An accelerated proximal stochastic gradient method with variance reduction based on Polyak step size

Fusheng WANG, Luyu SHI

2024, 28(2):  131-142.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.010

Asbtract ( 222 )   HTML ( 7)   PDF (24485KB) ( 85 )  

Figures and Tables | References | Related Articles | Metrics

To solve stochastic composite optimization problems in machine learning, we propose a new accelerated proximal variance reduction gradient algorithm called Acc-Prox-SVRG-Polyak, which combines the Acc-Prox-SVRG algorithm with the Polyak step size method. Compared to the existing algorithms, the new algorithm can make full use of the advantages of acceleration technology and Polyak step size to improve its accuracy, the convergence of the algorithm is demonstrated under the usual assumptions, and the complexity is analyzed. Finally, numerical experiments on standard data sets verify the effectiveness of the new algorithm.

The reciprocal degree distance of trees with given independence number

Baohua XING, Minhao SUN, Guidong YU

2024, 28(2):  143-150.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.011

Asbtract ( 177 )   HTML ( 0)   PDF (1242KB) ( 37 )  

Figures and Tables | References | Related Articles | Metrics

Let $G$ be a simple undirected connected graph, $T_{n, \alpha}$ be the set of trees with independence number $\alpha$ and order $n$. In this paper, we discuss the maximum reciprocal degree distance of trees in $T_{n, \alpha}$ and characterize the unique corresponding extremal graph.

The expansion problem of maximum capacity spanning arborescence in networks

Zilan YANG, Juanping ZHU, Yu YANG

2024, 28(2):  151-158.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.012

Asbtract ( 198 )   HTML ( 0)   PDF (802KB) ( 90 )  

Figures and Tables | References | Related Articles | Metrics

For the expansion problem of the maximum capacity spanning arborescence in networks (EMCSA), NP-hardness is proved by constructing an instance of EMCSA from 0-1 knapsack problem, and a heuristic algorithm is designed. Finally, one special version of EMCSA, the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks (NEMCSA), is considered. For NEMCSA, a strongly polynomial algorithm, in $O(mn) $ time, is provided by substituting the arc with the minimum weight difference.