Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions

NRU Higher School of Economics , 2008. No. 3.

Subochev A.

Twelve sets, proposed as social choice solution concepts, are compared: the core, five versions of the uncovered set, two versions of the minimal weakly stable sets, the uncaptured set, the untrapped set, the minimal undominated set (strong top cycle) and the minimal dominant set (weak top cycle). The main results presented are the following. A criterion to determine whether an alternative belongs to a minimal weakly stable set is found. It establishes the logical connection between minimal weakly stable sets and covering relation. In tournaments and in general case it is determined for all twelve sets, whether each two of them are related by inclusion or not. In tournaments the concept of stability is employed to generalize the notions of weakly stable and uncovered sets. New concepts of k-stable alternatives and k-stable sets are introduced and their properties and mutual relations are explored. A concept of the minimal dominant set is generalized. It helps to establish that in general case all dominant sets are ordered by strict inclusion. In tournaments the hierarchies of the classes of k-stable alternatives and k-stable sets combined with the system of dominant sets constitute tournament’s structure (“microstructure” and “macrostructure” respectively). This internal structure may be treated as a system of reference, which is based on difference in degrees of stability. An algorithm for calculating the minimal dominant sets and the classes of k-stable alternatives is also given.

Keywords: турнир, оптимальные системы, теория графов, solution concept, majority relation, tournament, matrix-vector representation, condorcet winner, top cycle, uncovered set, weakly stable set, externally stable set, uncaptured set, untrapped set, k-stable alternative, k-stable set, концепция решения, мажоритарное отношение, матрично-векторное представление, победитель Кондорсе, максимальный цикл, непокрытое множество, слабоустойчивое множество, внешнеустойчивое множество, незахваченное множество, незапертое множество, k-устойчивая альтернатива, k-устойчивое множество, моделирование процессов управления, теория полезности и принятия решений, теории организации и принятия экономических решений, принятие политических решений, математическая теория управляющих систем, формирование решений в интеллектуальной среде, модели рассуждений

Publication based on the results of: Модели принятия коллективных решений (2009)