Design of integrated rating mechanisms based on separating decomposition

This paper proposes an approach to reducing significantly the computational complexity of optimization problems in the design of integrated rating mechanisms (IRMs). The background concepts are introduced. The representability of a given discrete function as some IRM is proved. The decomposition procedure for a particular training example on some partition of input parameters is considered, and the following results are established under some restrictive conditions. First, an IRM matrix for a particular example of an input data set can be designed by maximizing a certain polynomial. Second, a set of given examples can be implemented by some IRM matrix. Third, an IRM can be implemented on a training data set in a certain complete binary tree based on the decomposition method. Fourth, some discrete function is implemented through a given complete binary tree if the discrete functions represented by convolution matrices are implemented in each node of this tree. All these results are rigorously formulated and proved. An illustrative example of the decomposition procedure based on a complete binary tree on three leaves is given. We propose a method for finding IRMs that implement a given training set in the space of all possible complete binary trees based on the branch table. In addition, we describe the decomposition procedure according to the branch table for each partition of input parameters. Finally, the advantages of the proposed method are outlined.