all days

View: session overviewtalk overview

10:00-12:00 Session 11: Plenary talk and tutorials
Svensson-Traub algorithm and approximation of asymmetric routing problems within fixed ratios
Markov Decision Process and Convex Optimization
Hyperheuristics for Automated Synthesis and Control of Evolutionary Optimization Algorithms
12:00-12:20Coffee Break
12:20-13:20 Session 12A: Integer Programming and Combinatorial Optimization
Bi-Objective Optimization Problems with Fuzzy Input Parameters in Scheduling and Vehicle Routing

ABSTRACT. We consider combinatorial optimization problems with fuzzy input data in the objective functions. A general approach, formulating a crisp model with two criteria: objective function and its membership function, is investigated. For the case of triangular fuzzy numbers and summed objective functions we construct a series of instances with the given number of the elements in the Pareto set. Specific properties of the set of feasible solutions are identified. We also investigate the Pareto set reduction in the context of the axiomatic approach. The degree of the reduction is evaluated for the crisp and fuzzy cases of the information about the DM’s preferences. The results are applied to scheduling problems with setup times and vehicle routing problems with alternatives in visiting points. The research is supported by the Russian Foundation for Basic Research (Projects 20-07-00298 and 20-07-00458).


ABSTRACT. In graph clustering problems, one has to partition the set of vertices of a graph into disjoint subsets (called clusters) so as to minimize the number of edges between clusters and the number of missing edges within clusters. We consider a version of the problem in which cluster sizes are bounded from above by a positive integer s. This problem is NP-hard for any fixed s>2. We propose a polynomial-time approximation algorithm for this version of the problem. Its performance guarantee is better than earlier known bounds.

Manifold Regularization and a Probabilistic Approach in the Problem of Weakly Supervised Regression

ABSTRACT. In the real world, the problem of weakly supervised learning often arises: this happens in cases where only part of the data is well labeled, and the other part is not labeled at all, or the labeling contains noise or errors. In this article, we consider optimization approaches to solving the problem of weakly supervised regression using manifold regularization in combination with a cluster ensemble, which is needed to obtain a co-association matrix. To reduce the training time and increase the quality of the resulting co-association matrix, a probabilistic approach is applied using fuzzy clustering. We also evaluated the improvement in the quality and stability of the solution from the use of each of the proposed techniques, and also compared the final algorithm with classical machine learning algorithms that are used in supervised learning problems. The work was carried out with the financial support of the Russian Science Foundation, project 22-21-00261.

A method of joint optimization of convolutional neural networks with decision trees in the task of interpretable image recognition

ABSTRACT. Convolutional neural networks have achieved high recognition quality, but suffer from lack of interpretability. On the other hand, decision trees are quite interpretable for humans, but have not high recognition accuracy rate, especially in image recognition tasks. The joint usage of the two methods would make it possible to compensate for the disadvantages of both, but this is difficult due to the impossibility of joint learning. This work proposes a new method of interpretable image recognition. The model consists of three components: a fully convolutional network, a pattern layer, and a ”soft” decision tree. First, the fully convolutional network extracts the feature maps from the input image. Next, a sample layer containing vector representations of specific samples (parts of the image), presence of which partially or completely determines the category of the object, calculates the proximity of parts of the image to the samples. Finally, optimal “soft” decision tree is used as a classifier, utilizing the pattern layer output as input features. The algorithm and the corresponding software were developed. Testing on two public datasets (Animal-10 and RSNA Intracranial Hemorrhage Detection) showed a competitive recognition quality for the proposed method as compared to classical convolutional networks, while providing an interpretable prediction. The work was partly supported by RFBR grant 19-29-01175.

12:20-13:35 Session 12B: Game Theory
Two Level Cooperation in Dynamic Network Games with Partner Sets

ABSTRACT. In the presented paper we consider dynamic network games with partner sets in which players cooperate to get the best outcomes. Using the game structure the two-level cooperative scheme is introduced. On the first level, the partner sets are considered as players, and the cooperative behavior is used in the game with partner sets, it is assumed that partners intend to maximize their joint payoff and then distribute it using a given optimality principle as usual in cooperative game theory. On the second level, the gain obtained by each player (partner set) is distributed among members of this partner set. The distribution of this gain is also made based on solution concepts from classical cooperative game theory. Since the game is dynamic the problem of time-consistency (dynamic stability) of the proposed two-level solution arises. To simplify the calculations and made the results applicable to real-life situations the new characteristic function is introduced based on the possibility of cutting connections by players outside the coalition. Also, this newly defined characteristic function allows constructing time-consistent (dynamically stable) solutions. The results are illustrated on an example

The core of cooperative differential games on networks.

ABSTRACT. A class of differential games on networks is considered. The construction of cooperative optimality principles using a special type of characteristic function that takes into account the network structure of the game is investigated. It is assumed that interaction on the network is possible between neighboring players and between players connected by paths whose length does not exceed the specified value. It is shown that in such games the characteristic function is convex even if there are cycles in the network. The core is used as cooperative optimality principles. A necessary and sufficient condition for the imputation to belong to the core is obtained.

The reported study was funded by RFBR and DFG, project number 21-51-12007

Tax authorities and taxpayers: when does the mutual collection of information cease to be effective?

ABSTRACT. Lots of works have been devoted to the modeling of tax control. In the classical game-theoretic formulation, the object of study is the interaction between the tax authority and taxpayers. However, along with such a formulation of the problem, some works allow us to study auxiliary problems related to tax collection and tax control. Two of these issues are worth mentioning. The first is the dissemination of information about future tax audits among the taxable population. The second is the collection and analysis of information on the propensity of taxpayers to evasion. Both processes allow the tax authorities to adjust their strategy and optimize audits in terms of collections to the budget. However, previously built models and simulations of these processes showed that they allow increasing net tax profit (total fees without costs) only up to a certain point. After it, the collection, analysis, and dissemination of information become ineffective, and profits cease to grow or, in some cases, decrease. The current research is devoted to the study of the question about the optimal moment of the indicated processes in the meaning of increasing the tax profit. The formulated problem is accompanied by the construction of models of both processes, their simulation, and comparative analysis of the results.

Stackelberg solution in a Friedkin–Johnsen opinion dynamics game

ABSTRACT. In this talk, we propose a 2-person dynamic game with leadership based on a Friedkin–Johnsen opinion dynamics model. We suppose that two centers of influence, called players, sequentially alter the opinions of the agents in a social network targeting specific opinions. To analyze the behavior of the players, we use the Stackelberg solution concept. Next, we demonstrate how the key parameters of the game affect this solution. This study is a continuation of our previous research on the subject.

Stable networks in society partitioned into ordered and nonordered groups

ABSTRACT. In our previous research, we consider a society partitioned into ordered groups and examine the stable networks that players form. In particular, we focus on the various forms of cost functions which are considered in two ways: (i) a link’s cost depends only on the distance between the types of groups players belong to, (ii) cost is affected not only by distance but also by the composition of a player’s neighborhood (the more members of a group the player has in her neighborhood, the less the average cost of a link is within this group). In this paper, in comparison with the previous model, we discuss how ordered groups influence the formed structures. Therefore, we assume that the cost function only differentiates whether a link is formed with someone from the same group or a different group. We compare the results about stable networks obtained with the new assumption with the previous ones.

15:00-16:00 Session 13A: Integer Programming and Combinatorial Optimization
Problem on (r|X)-medianoid with uncertainty

ABSTRACT. The problem of the (r|X)-medianoid is considered, i.e. Follower's problem in the (r|p)-centroid problem, in the formulation with uncertain data. A mathematical model in the form of a mixed-integer programming problem has been developed. Experiments were carried out using the Gurobi Optimizer package. The dependence of the behavior of the package on the use of a quadratic or linearized formulation of the problem was studied. The efficiency of using linearization in solving with Gurobi is shown.

Approximate algorithms for some maximin clustering problems

ABSTRACT. In this paper we consider three problems of searching for disjoint subsets among a finite set of points in an Euclidean space. In all three problems, it is required to maximize the size of the minimal cluster so that each intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are given as input. In the second problem, the centers are unknown, but belong to the initial set. In the last problem, the center of each cluster is defined as the arithmetic mean of all its elements. It is known that all three problems are NP-hard even in the one-dimensional case. The main result of the work is constant-factor approximation algorithms for all three problems. For the first two problems, 1/2-approximate algorithms for an arbitrary space dimension are constructed. Also we propose a 1/2-approximate algorithm for the one-dimensional case of the third problem.

On a class of combinatorial optimization problems with incomplete data

ABSTRACT. We propose a novel methodology and solution approach for a class of combinatorial nertwork optimization problems under distributional uncertainty. Specifically, we assume that the uncertain parameters (e.g., arc costs in the context of the shortest problem or uncertain demands in the context of the capacitated vehicle routing problem) are only observable through a finite set of random observations. However, in contrast to most related studies, the random observations are also subject to uncertainty, e.g., due to measurment errors or a problem-specific form of historical data. We employ a distributionally robust optimization approach, where the uncertainty of problem parameters is described by an ambiguity set (or a family) of probability distributions that are deemed possible under the existing information. We demonstrate that under some additional assumptions the resulting three-level optimization problem admits a linear mixed integer programming problem. Finally, we conduct numerical experiments to demonstrate the advantages and practical relevance of the proposed approach.

Multistage inventory model with probabilistic and quantile criteria

ABSTRACT. We consider a multistage inventory model. At each stage, a company determines order quantities of several products. The demand is described by a discrete random process. Additional ordering and holding the rest of the products are taken into account. The company can use a storage. The capacity of the storage is bounded. We consider two objective functions in this model. The first objective function is the probability that the losses are less or equal to a desirable level. The second one is the quantile of losses. To solve the considered problem we reduce them to mixed integer linear programming problems. This reduction is based on introducing auxiliary variables. We suggest conditions ensuring the equivalence of the original problems and the reduced ones. Also, we consider the problems when the distribution of the random process is unknown. For this case, we prove the convergence of the sample approximation method. Numerical results are discussed.

15:00-16:00 Session 13B: Game Theory
Modeling and analysis of generating companies' strategic behavior in the forward and spot electricity market

ABSTRACT. In this paper, we investigate the behavior of generating companies in the electricity market, where there is the possibility of forward contracts creating. Companies behave strategically, making decisions first about the volumes of forward contracts, and then about their bids for the spot market, which are formed as linear functions of supply. Competition in two markets is Cournot competition. Consumers and generating capacities are located in the nodes of the electric power system, which are interconnected by a network having limited power transmission. We formulate this two-stage game as an Equilibrium Constrained Equilibrium Problem (EPEC). Here, the optimization problem for each company in the forward market is a quadratic programming problem with the equilibrium constraints of the spot market problem, supplemented by network constraints. The work is a continuation of [1], where we discuss the forward market model without network restrictions. In this edition of the model, we have similar [1] results: firstly, generating companies with relatively high marginal costs enter the forward market at first, and secondly, the presence of the forward market increases competition, which is manifested in lower prices. We confirm this result by an example of modeling an electric power system similar to the real one.

1.Aizenberg N. Model LSFE with conjectural variations for electricity forward market. Communications in Computer and Information Science. 2021. Vol. 21. No. 1514. Pp. 1-15

International Trade under Monopolistic Competition with Investments in R&D: Non-monotonicity of Social Welfare w.r.t. Transport Costs

ABSTRACT. We study a homogeneous international trade model under the monopolistic competition of producers. The utility of consumers is additively separable. We assume that the transport costs are of iceberg type, while the production costs are non-linear: the marginal costs decrease when investments in R&D increase. We examine the local comparative statics of market equilibrium with respect to transport costs. For the case of linear production costs, the known (and counter-intuitive!) result is that social welfare increases near autarky. Early, we generalize this result for the model with investments in R&D and symmetric countries. In the present paper, we try to generalize this result to the case of non-symmetric countries.

Differential Game of Renewable Resources with Sliding Modes and Hybrid Limit Cycles

ABSTRACT. We explore the effects of multiple regimes in a standard renewable resource optimal harvesting model. We consider cooperative and non-cooperative solutions to the game with $n$ fisheries. We argue that thresholds of the state variable may yield tipping points, and we show that these thresholds may result in optimal policies where harvesting takes place on the boundary; in this case, the sliding mode may emerge. We consider two different settings with varying fish resource growth rate and varying harvesting efficiency rate. In the first case we observe the sliding mode as the optimal equilibrium outcome under certain conditions. In the second we prove the necessary conditions for the crossing hybrid limit cycle trajectory to be the optimal outcome of the game. We shortly discuss environmental and policy implications of these novel types of dynamics.

Retailing in Monopolistic Competition Model under Free Entry Condition with Taxation

ABSTRACT. The Dixit-Stiglitz model of monopolistic competition is modified by the introduction of retailing. We assume that the utility function of consumers is quadratic, while the demand function is linear. The paper considers various Stackelberg equilibrium situations with taxation. We consider in detail a case of retailer leadership, and describe the combinations of model parameters that are most preferable for the retailer, or the consumer, or society as a whole. As a result, we obtain that, from the point of view of social welfare, the optimal taxation can be both positive and negative, while, from the point of view of consumer surplus, the optimal taxation takes only positive values.

16:00-16:20Coffee Break
16:20-18:35 Session 14A: Integer Programming and Combinatorial Optimization (Online Session)
Integer Linear Programming in Solving the Problem on Pour at the Mixing Department of the Steel Making Production

ABSTRACT. One of the most important stage of the steel making production is the preparation of the cast iron at the mixing department. The main problems at this stage are timely delivery of the cast iron to the convertor shop floor, as well as satisfaction of chemical requirements with respect to production orders. To satisfy chemical requirements one need to provide an optimal logistic process at mixing department. Indeed, for timely delivery of the cast iron to the convertor shop floor, there needs either prepare a cast iron with high quality by mixing with corresponding proportions, or provide preliminary processing of the cast iron using a special machine, which also needs an additional time resourses. Thus there occures an optimisation problem with complex objective of unloading railway carriages for ongoing delivery of cast iron from the furnace shop floor to the mixing department, as well as provide a mixing process with respect to constraints on both the weight of ladles and requirements on chemical quality corresponding to production orders. To solve a problem above there proposed an integer linear programming model, which corresponds in full to thechnological specific of mixing department processes at the steel making production. The powerful and effectiveness of the proposed model is proof by full-scale computational experiments on real-world data from mixing department of the convertor shop floor № 2 of the Novolipetsk Metallurgical Enterprise.

Genetic algorithm for the variable-sized vector bin-packing problem with limited number of bins

ABSTRACT. In this paper, we consider a generalization of the well-known bin packing problem, in which several types of bins are given and the number of bins of each type is limited. Unlike the classic bin packing problem, this variant is not well represented in the literature, although it has a considerable practical value. For solving this problem, a genetic algorithm is proposed. It is based on a new representation scheme that uses first fit decreasing algorithm for decoding genotipes to solutions. The computational evaluation on the test instances have shown a competitive performance Variable sized bin packing \and Limited number of bins \and Genetic algorithm.of the proposed approach comparing to the heuristic algorithm previously known from the literature and Gurobi solver.

Uncertainty of clustering algorithms in random variables networks

ABSTRACT. Cluster analysis is a powerful tool in network science and it is well developed in many directions. However, the uncertainty analysis of clustering algorithms is still not sufficiently investigated in the literature. Probabilistic approach to robust clustering based on the theory of labeled random point processes was proposed in (Dalton at al, 2018). In the present paper we propose to study uncertainty of clustering algorithms within the framework of the random variable network model (Kalyagin at al, 2020). This model can be considered as generalization of various network models: gene expression network, brain network, climate observation network, and stock market network. Random variables network model is a complete weighted graph, where the nodes are associated with components of a random vector X, and weights of edges are given by pair wise correlations between these components. Our research question is the following: given a sample of observations of the random vector X, and a clustering algorithm, evaluate uncertainty of identification of clusters by this algorithm in associated random variable network model. We use the concept of reference or true network and the concept of sample network (Kalyagin at al, 2020). Associated cluster structures will be called reference and sample cluster structures. Uncertainty of identification of the cluster structure will be measured by expected value of loss related with error of identification. To measure this loss we compare reference and sample cluster structures with the use of popular RAND index (this index measure a difference of two partitions of the set of nodes of graph). We study uncertainty of different clustering algorithms including single linkage hierarchical algorithm, spectral clustering algorithm, and others. Finally, we discuss an impact of uncertainty of clustering on portfolio optimization in stock market network (Tola at al., 2008). References: 1. Dalton LA, Benalcázar ME, Dougherty ER (2018) Optimal clustering under uncertainty. PLoS ONE 13(10): e0204627 2. Kalyagin V. A., Koldanov A. P., Koldanov P.A., Pardalos P.M. (2020) Statistical analysis of graph structures in random variable networks, Springer Brief in Optimization, Springer. 3. Tola, V., Lillo, F., Gallegati, M., & Mantegna, R. N. (2008). Cluster analysis for portfolio optimization. Journal of Economic Dynamics and Control, 32(1), 235-258.

Metaheuristic Approach to Spectral Reconstruction of Graphs

ABSTRACT. Characterization of a graph by its spectrum is a very attractive research problem that has numerous applications. It is shown that the graph is not necessarily uniquely determined by its spectrum in the most general case, i.e., there could be several non-isomorphic graphs corresponding to the same spectrum. All such graphs are called cospectral. However, in most of the cases, it is important to find at least one graph whose spectrum is equal to a given constant vector. This process is called Spectral Reconstruction of Graph (SRG) and it is known as one of the most difficult optimization problems. We address the SRG problem by the metaheuristic methods, more precisely, by Basic Variable Neighborhood Search (BVNS) and improvement-based Bee Colony Optimization (BCOi) methods. The resulting heuristics are called SRG-BVNS and SRG-BCOi, respectively. Both methods are implemented in such a way to take into account the graph properties defined by its spectrum. We compare the performance of the proposed methods with each other and with the results obtained by other approaches from the relevant literature on the reconstruction of some well-known graphs.

Variable Neighborhood Search for Multi-label Feature Selection

ABSTRACT. With the growing dimensionality of the data in many real-world applications, feature selection is becoming an increasingly important preprocessing step in multi-label classification. Finding a smaller subset of the most relevant features can significantly reduce resource consumption of model training, and in some cases, it can even result in a model with higher accuracy. Traditionally, feature selection has been done by employing some statistical measure to determine the most influential features, but in recent years, more and more metaheuristics have been proposed to tackle this problem more effectively. In this paper, we propose using the Basic Variable Neighborhood Search (BVNS) algorithm to search for the optimal subset of features, combined with a local search method based on mutual information. The algorithm can be considered a hybrid between the wrapper and filter methods, as it uses statistical knowledge about features to reduce the number of examined solutions during the local search. We compared our approach against Ant Colony Optimization (ACO) and Memetic Algorithm (MA), using the K-nearest neighbors classifier to evaluate solutions. The experiments conducted using three different metrics on a total of four benchmark datasets suggest that our approach outperforms ACO and MA.

Performance Evaluation of Genetic Algorithm Based on Idempotent Algebra Methods for RCPSP

ABSTRACT. This paper considers the problem of scheduling an investment project with constrained resources and the criterion of maximizing the net present value. All resources in the model are represented in monetary form. The project budget, as well as income from the reinvestment of profits are the source of cost coverage. We propose a modification of the previously developed genetic algorithm based on the methods of idempotent algebra to solve the problem. The paper shows that the RCSP problem can be formulated in terms of zero-one linear programming; therefore, to find its exact solution, the IBM ILOG CPLEX software package is used. Since this problem is NP-hard, as the number of model variables increases, the capabilities of the CPLEX package are limited. Under these conditions, it is advisable to use a genetic algorithm. Computational experiments were carried out to prove the effectiveness of the genetic algorithm. The results of the work of the modified genetic algorithm are analyzed depending on the initial data of the model, as well as, in comparison with the CPLEX package. Such parameters of the algorithm as the number of activities, the characteristics of cash flows, the size of the population, and the number of generations are taken into account. The algorithm has demonstrated high performance in finding exact solutions to the problem.

Approach to Text Data Clustering Based on Molecular Chemical Reactions

ABSTRACT. Text data clustering is one of the problems of information retrieval. The purpose of cluster analysis of text data is to detect groups of semantically similar documents among a collection of given text data without predefined categories (characteristics) of grouping. In the literature, there are many scientific approaches to text data clustering, for example, the k-means local search algo-rithm is widely used. The paper proposes an algorithm for clustering text data using the k-means algorithm combined with molecular chemical reactions. By molecular structure we mean a possible solution to text data clustering, by op-timizing the molecular chemical reactions we mean optimizing the results of text data clustering (search for a global optimal solution). The solution obtained with k-means is used as an initial molecular structure solution to optimize chemical reactions in combination with k-means by generating new solutions: single-molecule collision, single-molecule decomposition, intermolecular collision, and intermolecular synthesis. The computational experiment showed the comparative efficiency of the proposed algorithm, taking into account numerical metrics: accuracy, precision, recall, and F-measure.

A faster algorithm for counting of the integer points in $\Delta$-modular polyhedra

ABSTRACT. Let $\PC$ be a polyhedron, defined by a system $A x \leq b$, where $A \in \ZZ^{m \times n}$, $\rank(A) = n$, and $b \in \ZZ^{m}$. In the Integer Feasibility Problem, we need to decide whether $\PC \cap \ZZ^n = \emptyset$ or to find some $x \in \PC \cap \ZZ^n$ in the opposite case. Currently, its state of the art algorithm, due to \cite{DadushDis,DadushFDim} (see also \cite{Convic,ConvicComp,DConvic} for more general formulations), has the complexity bound $O(n)^n \cdot \poly(\phi)$, where $\phi = \size(A,b)$. It is a long-standing open problem to break the $O(n)^n$ dimension-dependence in the complexity of ILP algorithms.

We show that if the matrix $A$ has a small $l_1$ or $l_\infty$ norm, or $A$ is sparse and has bounded elements, then the integer feasibility problem can be solved faster. More precisely, we give the following complexity bounds \begin{gather*} \min\{\|A\|_{\infty}, \|A\|_1\}^{5 n} \cdot 2^n \cdot \poly(\phi),\\ \bigl( \|A\|_{\max} \bigr)^{5 n} \cdot \min\{\colSparse(A),\rowSparse(A)\}^{3 n} \cdot 2^n \cdot \poly(\phi). \end{gather*} Here $\|A\|_{\max}$ denotes the maximal absolute value of elements of $A$, $\colSparse(A)$ and $\rowSparse(A)$ denote the maximal number of nonzero elements in columns and rows of $A$, respectively. We present similar results for the integer linear counting and optimization problems.

Additionally, we apply the last result for multipacking and multicover problems on graphs and hypergraphs, where we need to choose a minimal/maximal multiset of vertices to cover/pack the edges by a prescribed number of times. For example, we show that the stable multiset and vertex multicover problems on simple graphs admit FPT-algorithms with the complexity bound $2^{O(|\VC|)} \cdot \poly(\phi)$, where $\VC$ is the vertex set of a given graph.

Application of the second-order optimization methods to the stochastic programming problems with quantile function

ABSTRACT. We consider the application of the second-order optimization algorithms for stochastic optimization problems with the quantile function as the objective function. To apply these methods, we consider approximations of the probability and quantile functions and their derivatives. The idea of the approximation lies in the replacement of the Heaviside function with the sigmoid function. Previously we showed that approximated probability and quantile functions along with their derivatives converge to the exact ones. Furthermore, it has been shown that the usage of the first-order and second-order optimization methods for problems with the probability function as a criterion leads to a good approximation of the optimal control vector and the optimal value of the target function. In this research, the direct formulas for the second-order derivatives of the approximated quantile function with respect to the elements of the control vector are provided. Also, we consider some numerical examples of problems with quantile function as a criterion. The proof of convergence of the second-order derivatives is not considered in this research. Possible applications of such approximations include the development of the new numerical algorithms for solving stochastic optimization problems, and new algorithms to determine the surface level of the quantile function.

16:20-19:05 Session 14B: Game Theory
Tensor train global optimization of source problems for diffusive-logistic mathematical model in online social networks

ABSTRACT. Various information in social networks can lead to a significant social effect (that is, social unrest, dramatic economic changes, etc.). Control and management of such information are complex tasks; therefore, it is necessary for timely identification of the source of information diffusion. In this work we investigate the information diffusion in online social networks represented by the simplified Kolmogorov-Fokker-Planck equation which is characterized by its coefficients and the initial condition [1]. These parameters describe the main features of information diffusion in a social network. The aim of the work is to clarify the source of information propagation for formulation the control problem of such diffusion [2]. The problem of determining the initial condition is reduced to the problem of minimization of the misfit function (inverse problem). The tensor train (TT) global optimization method was used for solving the minimization problem. TT effectively solves multi-parameter optimization problems [3], has parallel implementation and asymptotic convergence theorems [4]. The robustness of the TT optimization method for various artificial social networks: Digg, Twitter, Facebook was investigated. This work is supported by the Russian Science Foundation (project no. 18-71-10044-П) and the Council for Grants of the President of the Russian Federation (project no. МК-4994.2021.1.1).

References: [1] Wang F., Wang H., Xu K., Wu J., Jia X. Characterizing Information Diffusion in Online Social Networks with Linear Diffusive Model // Proceedings of ICDCS. 2013;307–316. [2] Krivorotko O., Zvonareva T., Zyatkov N. Numerical solution of the inverse problem for diffusion-logistic model arising in online social networks // Commun. Comput. Info. Sci. 2021;1476:444–459. [3] Zheltkova V.V., Zheltkov D.A., Grossman Z., Bocharov G.A., Tyrtyshnikov E.E. Tensor based approach to the numerical treatment of the parameter estimation problems in mathematical immunology // J. Inverse Ill-Posed Probl. 2018;26:5–66. [4] Oseledets I.V. Tensor-train decomposition // SIAM J. Sci. Comput. 2011;33(5):2295–2317.

How should we score athletes and candidates: geometric scoring rules

ABSTRACT. Scoring rules are widely used to rank athletes in sports and candidates in elections. Each position in each individual ranking is worth a certain number of points; the total sum of points determines the aggregate ranking. The question is how to choose a scoring rule for a specific application. First, we derive a one-parameter family with geometric scores which satisfies two principles of independence: once an extremely strong or weak candidate is removed, the aggregate ranking ought to remain intact. This family includes Borda count, generalised plurality (medal count), and generalised antiplurality (threshold rule) as edge cases, and we find which additional axioms characterise these rules. Second, we introduce a one-parameter family with optimal scores: the athletes should be ranked according to their expected overall quality. Finally, using historical data from biathlon, golf, and running we demonstrate how the geometric and optimal scores can simplify the selection of suitable scoring rules, show that these scores closely resemble the actual scores used by the organisers, and provide an explanation for empirical phenomena observed in golf tournaments. We see that geometric scores approximate the optimal scores well in events where the distribution of athletes’ performances is roughly uniform

Comparison of Reinforcement Learning based Control Algorithms for Autonomous Driving Problem

ABSTRACT. Autonomous driving systems consist of tasks at several levels of perception, which have now achieved high accuracy thanks to the deep learning architecture. In addition to perception, autonomous driving systems consist of many tasks in which classical methods of supervised learning are no longer applicable. We solve the problem of driving a car to move along a given trajectory using reinforcement learning algorithms. In control theory, this problem is called the optimal control of moving along the reference trajectory. Airsim environment is used to simulate a moving car for a fixed period of time without obstacles.

The purpose of our research is to determine the best reinforcement learning algorithm for a formulated problem among DDPG, PPO, SAC, DQN and others. It is also planned to train PID and MPC regulators using genetic algorithms to conduct the comparison with the classical numerical control techniques.

Multicriteria Dynamic Games with Asymmetric Horizons

ABSTRACT. We consider a dynamic, discrete-time, game model where many players use a common resource and have different criteria to optimize. Moreover, the players’ planning horizons are assumed to be different. Multicriteria Nash and cooperative equilibria are defined via modified bargaining schemas. To stabilize the multicriteria cooperative solution a time-consistent payoff distribution procedure is constructed. To illustrate the presented approaches, a dynamic bi-criteria bioresource management problem with many players and asymmetric planning horizons is investigated.

Optimal arrivals to preemptive queue system

ABSTRACT. This paper considers a single-server queueing system with strategic users in which customers (players) enter the system with preemptive access. As soon as the customer request enters the system, the server immediately starts the service. But when the next request arrives in the system, the previous one leaves the system even he has not finished his service yet. We study the following non-cooperative game for this service system. Each player decides when to arrive at the queueing system within a certain period of time. The objective of the player is to maximize the probability of receiving service. We show that there exists a unique symmetric Nash equilibrium in this game. Finally, some numerical experiments are carried out to compare the equilibria under different values of the model parameters.

Optimal Pricing in Two-Sided Markets on the Plain with Different Agent Types

ABSTRACT. This paper investigates the price equilibrium in a two-sided platform market with external network effects between the agents of different groups. The focus is on the problem of optimal pricing on the two-sided market which takes into account the platform position and the search for the optimal allocation of the platforms.

The models implies two different groups of agents, which are distributed uniformly in the plane of a circle. Agents in both groups choose between two platforms based on the utility they can derive from visiting the each platform. The utility function is constructed via Hotelling’s specification and thus consists of the utility from network effect of interaction any one of the groups with another group and costs of accessing the platform including transport costs. The payoff of each platform depends on the number of agents in both groups on the platform, the price of accessing the platform and costs of serving users. The study indicates the optimal price strategies in the two-sided market of identical and different platforms. Furthermore, the problem of platform's allocation on the plane is derived and numerical results for different parameter values are presented.

Network centralities based on non-additive measures

ABSTRACT. Network models are widely employed in many areas of science and technology. Mathematical analysis of their properties includes various methods to characterize, rank and compare network nodes. Non-additive measures allow to express the importance of a set of network nodes. In this work, we investigate variants of network centralities based on non-additive measures, calculated using the Choquet integral. We construct centrality measures where the importance of a set of nodes depends on their distance from a target node, explain their meaning and the connection with existing algorithms.

What a Captain Needs to Know: on Selfish Voting when Dividing a Good in an Ordered Group

ABSTRACT. The well-known ``Pirate game'' is a mathematical model of decision-making by rational agents ordered by their superiority. An offer of the senior player must be approved by the prescribed fraction $Q$ of the ``crew''. In this paper, we generalize this problem for any $Q$ and crews of arbitrary size. We describe the payoff patterns and a recursive algorithm for their generation, thus demonstrating that the the problem always has a solution. We show that the payoff pattern is stable within a range of $Q$, and changes at some threshold values, all rational numbers. We also address the loyalty problem: an agent who is offered exactly what he would expect from the next offer, may vote against, for, or for provided that the offer is nonzero. We show that even for large $Q$ there usually is some freedom in choosing agents to offer something, and we discuss how this freedom can be used to reduce the payoff through negotiation. Also, we consider the looped queue, when the senior agent is not expelled but becomes the junior.

Agreements of Continuous-Time Games

ABSTRACT. We propose a method for formulating and solving for subgame perfect equilibria of continuous-time games. The main idea is to study self-enforcing agreements corresponding to a strategic interaction directly, without setting up a whole extensive-form game. Our method allows for non-Markov and asymmetric players’ behavior, and it does not impose restrictions on players’ strategies. The method applies to a broad class of games, including stochastic games, in which arbitrarily many players can have both observable and hidden actions. In many cases, this approach produces tractable and explicit solutions

Extended backward induction

ABSTRACT. We propose a novel generalization of backward induction reasoning for general finite games with imperfect information. In contrast to existing attempts, the extended backward induction algorithm employs equilibrium, rather than rationalisability, reasoning; its output is the set of all extended subgame-perfect equilibria (Kreps & Wilson, 1982). This lesser known equilibrium concept is a refinement of subgame-perfect equilibrium yet is itself refined by sequential equilibrium. In addition, we link the concept of extended subgame-perfect equilibrium, via the extended BI algorithm, to the equilibrium's epistemic foundation—the common belief in future* rationality, introduced in (Topolyan, 2020).

On the two-stage construction of a rational strategy of an economic entity

ABSTRACT. The object of the study is a dynamic management model of an economic entity. A subject's development strategy is called rational if his wellfare exceeds a given level during each interval of the period under consideration. In [1], based on the Solow equation [2], a new model for finding rational strategies was proposed. A comparative analysis of the strategies obtained using this model with the strategies developed by the classical Ramsey-Kass-Koopmans model [3] unexpectedly revealed the superiority of new strategies for the medium term. The criteria for comparison are integral indicator of welfare and integral indicator of expended effort. In this paper, it is proposed to substantiate this statement with the help of a new algorithm of actions of the social planner. At the first stage, he determines the maximum level of wellfare for the economic entity, at the second stage, a rational strategy for the development of the entity is built, the level of wellfare in which is not less than a given percentage of the maximum. The work was supported in part by the Russian Foundation for Basic Research, project 20-010-00151. [1] Antsyz S.M.: On Refinement of the Simplest Growth Model // 17th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS), Moscow, Novosibirsk (Russia), Almaty (Kazakhstan). IEEE Xplore, 2021. – P. 9-12. [2] Solow R.M.: A Contribution to the Theory of Economic Growth // The Quarterly Journal of Economics, vol. 70, is. 1, pp. 65-94, February 1956. [3] Romer D.H.: Advanced macroeconomics, 4th ed. p. cm., University of California. Berkeley: McGraw-Hill, 2012.

18:35-19:50 Session 15: Optimization and Applications (Online Session)
Bilevel Models of Economic Policy Formation with Transaction Costs and Insurance of Contracts Breaking Risks

ABSTRACT. This article continues author research into cooperation between public and private investors in the resource region. In contrast to previous works, an attempt is made here to take into account the institutional features of the process of forming the investment climate. For this, transaction costs are introduced into the model and a mechanism for insuring the risks of breaking contracts is formed. In the Russian mineral resource complex, costs and risks of this kind can be very significant. This work aims to analyze the partnership mechanisms, taking into account these circumstances and using the game-theoretical Stakelberg model. Such mechanisms determine the economic policy of the state and play an important role in stimulating private investment. Model is formulated as a bilevel mathematical programming problem, effective solution algorithms based on metaheuristics and allowing solving large-dimensional problems will be developed. This opens up the possibility of practical study on the real data of the properties of Stackelberg equilibrium, which determines the design of the mechanism for the formation of economic policy, fully meeting the interests of society.


ABSTRACT. We propose a relaxation subgradient method (RSM) similar in its structure to quasi-Newtonian methods which includes parameter optimization of the metric matrices two-rank correction. The purpose of the transformation of the metric matrices is to map a wide bundle of sub-gradients of the current neighborhood of the minimum into a narrow bundle of directions that form an acute angle with all sub-gradients of the neighborhood of the current approximation of the minimum. Using such directions enables us to go beyond this neighborhood. The design of the metric matrix transformation algorithm includes the suppression of orthogonal and amplification of collinear components of the vector of the minimum length of the set of subgradients. The problem of constructing a metric matrix is ​​formulated as a problem of solving a system of inequalities. To solve it, a formalized model of subgradient sets is used and the concepts and algorithms of learning theory are involved, in particular, the iterative least squares method. A new learning algorithm has been developed, and an estimate of its convergence rate has been obtained depending on the parameters of the subgradient set. On this basis, a new RSM has been created and substantiated. A computational experiment on complex large-scale functions confirms the effectiveness of the proposed algorithm. The capability of the proposed method to solve non-smooth non-convex optimization problems makes it useful for the problems of mathematical model training with the use of technologies for suppressing non-informative variables, similar to the Tibshirani Lasso.

Competitive location strategies in the (r|p)-centroid problem on a plane with linear barriers

ABSTRACT. In 1982, Drezner [1] considered the problem of the competitive location of facilities on a plane, when the leader and follower place one facility each. He proposed polynomial-time algorithms for the follower and leader optimal facility location. In 2013, Davydov et al. [2] considered a generalization of this problem when the leader has a set of p−1 facilities and wants to open another facility in the best position, with the optimal response of the follower. We examine the influence of linear barriers on the optimal leader and follower strategies. The linear barrier is a straight line (or a sufficiently large segment) with a gouged point through which the goods are transported to the customer located in a different part of the plane relative to the barrier. We propose polynomial-time algorithms for formulations in which the number of already open facilities is fixed, and barriers divide the plane into polygons in such a way that two different paths cannot exist from one polygon to another.

1. Drezner Z.: Competitive location strategies for two facilities. Regional Science and Urban Economics.12, 485−493 (1982) 2. Davydov I.A., Kochetov Y.A., Carrizosa E.: A local search heuristic for the (r|p)-centroid problem in the plane. Computers & Operations Research. 52, 334−340 (2014).

On solving one spectral problem

ABSTRACT. When designing and optimizing modern semiconductor heterostructures, mathematical models are used that reflect the quantum mechanical nature of the behavior of charge carriers. At the nanoscale level, the applied mathematical model is a coupled system of Schrödinger and Poisson equations. As a result of solving these equations, data are obtained on the wave functions and the density distribution of charge carriers across the layered structure. The greatest computational costs when using such a model are associated with the solution of the Schrödinger equation. In this paper, we compare different methods for solving the spectral problem. A method based on the Prufer transformation of the Schrödinger equation, a variation method, and a method for solving the spectral problem for a symmetric sparse matrix of a band structure (a discrete analogue of the Schrödinger equation) are considered.

Development of a Greedy Algorithm for Robust Capacitated Facility Location and Design Problem with Elastic Demand

ABSTRACT. A new Robust Capacitated Facility Location and Design Problem with elastic demand (RCFLDP) is considered in this paper. In it, the company plans to open service centers in a competitive environment, capturing part of consumer demand. Consumers choose the service points of the company or competitors based on their preferences. The structure of demand elastically varies depending on what type of facility design of the company has opened. In contrast to a deterministic CFLDP, a situation is considered when the demand is not fixed and may change depending on various factors. The company plans to find a solution that would be profitable in case of uncertain demand. Such a solution is called robust, and methods for solving robust problems have been actively developing in recent years.

A new problem-specified greedy algorithm is proposed to solve the RCFLDP. The quality of its calculations is investigated on a series of test instances, a comparison with early developments is made, and the results are discussed.