Analysis of the sensitivity of efficient solutions of a vector problem of minimizing linear forms on a set of permutations

We consider a multicriteria formulation of the well-known combinatorial problem to minimise a linear form over an arbitrary set of permutations of the symmetric group. We give bounds (in the Chebyshev metric) for the coefficients of the linear forms preserving the corresponding efficiency of an arbitrary solution that is Pareto-, Slater-, or Smale-optimal. We present some conditions guaranteeing that a permutation possessing the efficiency property is locally stable. The class of quasi-stable problems is described.