Логические методы построения и анализа моделей выбора | ПДМ. 2009. № 1(3).

Логические методы построения и анализа моделей выбора

Логические методы используют представление функций выбора и моделей выбора в виде формул некоторого логического языка и сводят задачи построения и исследования моделей выбора к формальным преобразованиям и анализу этих представлений. Они позволяют решать широкий круг конструктивных задач, связанных с построением, анализом, упрощением и оценкой сложности формальных моделей выбора, дают возможность применить к задачам выбора методологию Шеннона-Яблонского-Лупанова изучения управляющих систем. В данной статье систематизируются результаты автора по исследованию моделей выбора логическими методами, полученные в разное время и опубликованные в разных изданиях. Приводятся относящиеся к этой области результаты других авторов.

Logical methods for design and analysis of choice models .pdf В связи с широким применением вычислительной техники в процедурах принятия и реализации решений повышается роль формальных методов исследования моделей выбора вариантов. При построении и исследовании моделей выбора возникает ряд задач конструктивного характера. Основной является задача синтеза - построения модели из заданного класса, реализующей требуемый выбор. При синтезе существенная роль отводится сложности моделей и обычно решается задача построения моделей малой (лучше минимальной) сложности. Иногда ставят задачу минимизации - нахождения по заданной модели эквивалентной ей модели наименьшей сложности. Если выбор не представим моделями рассматриваемого класса, возникает задача его аппроксимации в этом классе (наилучшей в условленном смысле). Важную роль играет задача анализа моделей - выяснения, обладает ли модель или реализуемый ей выбор требуемыми свойствами. Кроме этого рассматриваются задачи агрегирования нескольких моделей выбора в одну и декомпозиции модели на более простые.В теории и приложениях имеют дело с двумя основными типами моделей выбора. В моделях первого типа варианты считаются некоторыми целостными объектами, не имеющими структурного описания, и предпочтительность одного варианта другому выявляется на основе их непосредственного сравнения. Выбор в рамках таких моделей будем называть свободным в соответствии с термином «свободный», принятым в математике и означающим отсутствие дополнительных соотношений. В моделях второго типа вариантам сопоставляются оценки по заданной совокупности критериев, и1 Работа выполнена при финансовой поддержке ОНИТ РАН по программе «Фундаментальные основы информационных технологий и систем».Логические методы построения и анализа моделей выбора39варианты сравниваются на основе этих оценок. Выбор такого типа называют многокритериальным. В качестве моделей многокритериального выбора часто используются порядковые модели, в которых важны не сами величины оценок по критериям, а их соотношения (больше, меньше, равно).Логические методы используют представление функций и моделей выбора в виде формул некоторого логического языка и сводят задачи, связанные с построением и анализом моделей, к формальным преобразованиям и исследованию этих представлений. Вид применяемого логического языка зависит от типа моделей. В задачах свободного выбора с конечным числом вариантов в качестве логического языка используется язык булевой алгебры. В случае, когда число вариантов потенциально бесконечно, логические описания требуют привлечения кванторов и применяется некоторый вариант языка первого порядка. В частности, это относится к многокритериальному (в том числе порядковому) выбору, где множество вариантов (наборов значений критериев), вообще говоря, бесконечно. Поскольку результат сравнения оценок может иметь три исхода (больше, меньше, равно), исследование свойств порядковых отношений основывается на языке (3,2)-значной логики.Логические методы оказались весьма эффективными в силу ряда причин. Описание многих модели выбора использует теоретико-множественные операции над множествами вариантов, различные логические связки и кванторы. Поскольку имеется естественное соответствие между теоретико-множественными и логическими операциями, а связки и кванторы присутствуют в логическом языке, такие описания легко переводятся в формулы языка. Часто более сложные модели выбора строятся из простых с помощью некоторых операций (агрегирование отношений, параллельное и последовательное соединение моделей и др.). Этим операциям соответствуют определенные преобразования логических формул, что дает возможность находить логические представления достаточно сложных иерархических моделей выбора. Богатая система формальных преобразований позволяет переходить от одних записей в логическом языке к другим, существенно упрощать представления. Имеется возможность привлечения результатов, методов и технических приемов, развитых в математической логике и теории моделей. Логические методы позволяют применять к задачам выбора методологию исследования управляющих систем, заложенную в работах К. Э. Шеннона и получившую существенное развитие в научной школе СВ. Яблонского и О. Б. Лупанова. Все это делает логические методы удобным и универсальным инструментом для решения широкого круга конструктивных задач в области выбора. Впервые логическое описание функций (но не моделей) выбора использовалось в [1]. Логические методы исследования моделей выбора ведут начало от [2]. Различные варианты логических методов для задач выбора применялись в [3-6].Важную роль при решении конструктивных задач в области выбора играют слож-ностные аспекты, и им уделяется значительное внимание в проводимых исследованиях. Рассматриваются два типа характеристик сложности:•·сложность моделей выбора, измеряемаяемая каким-либо существенным параметром, связанным с описанием или структурой моделей;•·сложность (трудность) задач, относящихся к построению либо анализу моделей выбора, характеризуемая размером какого-либо вычислительного ресурса (времени, памяти), затрачиваемого на их решение.•·В области оценок сложности моделей выбора большое внимание уделено асимптотическим результатам. Они дают возможность получить качественное представление•·40•·Л. А. Шоломов•·о поведении сложности, выяснить влияние на нее тех или иных параметров задачи выбора, зависимость от класса используемых моделей, взаимоотношение различных характеристик сложности. При исследовании трудности задач основная роль отведена их анализу на полиномиальность, NP-полноту и алгоритмическую неразрешимость. Согласно существующей точке зрения считается, что задачи с полиномиальной оценкой трудоемкости эффективно решаемы, NP-полные задачи труднорешаемы, алгоритмически неразрешимые задачи в принципе не решаемы.•·Часть I. МОДЕЛИ СВОБОДНОГО ВЫБОРА•·1. Логическое представление свободного выбора•·1.1. Функции выбора•·Пусть задано множество А вариантов (конечное или бесконечное). Подмножества X С А называются предъявлениями (более точно - множествами, предъявленными для выбора). Функция выбора (ФВ) С на множестве вариантов А представляет собой отображение 2 -> 2 , сопоставляющее каждому X С А множество вариантов С(Х) С X, выбранных в предъявлении X.•·Более общим понятием является функция неполного выбора (ФНВ) [2, 7], которая задается множеством А С 2А допустимых предъявлений и функциями С1 ,С° : А -► 2А такими, что С\Х) С X, С°{Х) С X, С\Х) П С°(Х) = 0 для любого X Е А. Варианты из множества С1(Х) называются принятыми (в предъявлении X), из множества С°(Х) - отвергнутыми. Такую ФНВ будем обозначать [А, С1, С0). Поскольку всякую ФВ С можно рассматривать как ФНВ при А = 2А, С1{Х) = С{Х) и С°(Х) = Х\С(Х), все дальнейшие понятия будут формулироваться применительно к ФНВ.•·Доопределением ФНВ [А, С1, С0) будем называть любую ФВ С (всюду определенную), для которой С1(Х) С С(Х) С X \ С°(Х), X Е А. Всякой модели (механизму, правилу, процедуре) выбора М соответствует некоторая ФВ См, которая сопоставляет каждому предъявлению X С А множество вариантов См(Х), выбранных из X моделью М. Скажем, что модель М реализует ФНВ (Л, С1, С0), если См является доопределением этой функции.•·1.2. Логическое представление функций выбора•·Пока не оговорено противное, будем рассматривать модели свободного выбора с конечным множеством вариантов А] пусть его мощность равна п. Не различая варианты и их номера, будем полагать А = А^п> = {1,... ,п}. С каждым вариантом г свяжем булеву переменную Хг, и предъявление X будем задавать набором X = (х\,... , хп), где Xi = 1 и Xi = 0 соответственно при г G X и г ф X. ФНВ (А, С1, С0) будем описывать п частичными булевыми функциями С^г'(Х), 1 ^ г ^ п [2, 7], где•·{•·1, еслиХ G AM E С\Х), О, если(Хе ААгЕС°(Х))Уг^Х, * в остальных случаях.•·Здесь * обозначает неопределенное значение. Совокупность п функций С^(Х) будем называть логическим представлением функции неполного выбора. Включение С1(Х) С X эквивалентно тому, что каждая функция С® (X) выразима в виде С«(Х) = XiC^(X^), где X» = (хъ ... , Xi_1}xi+1, ...,xn), С®(Х®) - частичная булева функция, полученная из С^г'(Х) подстановкой Xi = 1. В случае ФВ представляющие булевы функции всюду определены.•·Логические методы построения и анализа моделей выбора41•·Модель выбора М реализует ФНВ (Л, С1, С0) тогда и только тогда, когда при каждом i булева функция СЦ(Х) доопределяет частичную функцию С«(Х).•·1.3. Логическое представление выбора по отношению•·Обычно модели выбора строятся с использованием бинарных отношений г С А2 (на множестве вариантов А), в которых соотношение хгу интерпретируется как «вариант х предпочтительнее у». Для i G А обозначим r(i) = {j \ irj}, r~l(i) = {j \ jri}. В теории и приложениях используются различные правила выбора по бинарным отношениям (см., например, [8, 9]). Приведем три из них:•·выбор максимальных вариантов СГ>\(Х) = {х G X | (\/у G X)yfx}]•выбор лучших вариантов СГ>2(Х) = {х G X | (\/у G Х)хгу}]•·выбор отбраковкой худших вариантов СГ^(Х) = X \ {х G X | (\/у G X)xfy A (3z G X)zrx).В первом и третьем правилах отношение предполагается иррефлексивным (хгх), во втором - рефлексивным (хгх). Указанные правила имеют следующие логические представления [7]:Cf}(X)=xt Д xj} С^(Х)=хг Д Щ, С%(Х) = х%[\] хгУ \J %).j€r_1(i)j&(i)l(zr(i)j€r_1(i)Двойственным отношением к г называется отношение г* = г-1 (операции и _1 перестановочны и их порядок не существен). Правила выбора максимальных и лучших вариантов сводятся друг к другу путем перехода к двойственному отношению: СГ;1 = Сг*;2, СГ;2 = C*r*,i- Основным правилом выбора по отношению обычно считают первое, и, если не оговорено противное, будем под выбором по отношению понимать СГ;1 и использовать для него обозначение Сг. Класс всех моделей выбора по отношению (использующих первое правило) обозначим через Ш.1.4. Суперпозиция логических представленийДанный раздел написан по материалам [2, 10, 11], систематическое изложение имеется в [7].Введем некоторые операции над функциями и моделями выбора. Операция суперпозиции С\ о С*2 функций выбора С\ и С*2 задается равенством [С\ о Сг)(Х) = = С2(С\(Х)). Логическое представление суперпозиции выражается через логические представления исходных ФВ в виде(d о C2f\X) = C^iC^iX),..., С{Г](Х)).Эта операция возникает при последовательном соединении моделей выбора М\ и М2, когда выход модели М\ подается на вход М2. Полученная модель реализует ФВCmiM2 = СМх ° См2-Операция суперпозиции ФВ ассоциативна: (С\ о С2) о Сз = С\ о (С2 о Сз), поэтому можно рассматривать многоместную операцию С\ о С2 о ■ ■ ■ о Си, которая не зависит от расстановки скобок. Последовательное соединение к моделей выбора по отношению дает модель последовательного выбора глубины к. Для нее СГ1Г2,„Гк = СГ1оСГ2о- ■ -оСГк, или в другой записиСг1г2...гк(Х) - СГк(... СГ2(СГ1(Х))...).42Л. А. ШоломовС использованием приведенных выше формул можно найти логическое представление этой модели. В частности, для моделей глубины 2 оно преобразуется к видуСГ1Г2 (X) = XiДXj (хт V \J xij.j(zr^ (г), mEr^ (i)lEr^ (m)Классы моделей последовательного выбора произвольной глубины и глубины к обозначим соответственно через Sq и Sqfc.1.5. Композиция логических представленийОперация композиции функций выбора Ci,...,Ck при способе композиции F = F(YU ...,Yk) реализует ФВ С{Х) = F(C\(X),.. .,Ck(X)). В качестве F обычно используется монотонная теоретико-множественная операция (операция голосования). В этом случае логическое представление композиции имеет видC^(X) = /(Cf(X),...,cf(X)),где / = f(y 1,..., у к) - монотонная булева функция, естественным образом сопоставленная операции F. Операция композиции возникает при параллельном соединении моделей М\,... , Мк, когда их выходы подаются на вход блока, реализующего fc-местный оператор F. Если в качестве М\,... , Мк использовать модели выбора по отношениям Г\,... ,Гк, получим модель параллельного выбора ширины к. Ей соответствует логическое описаниеc^ru...,r^) = f(c^x),...,ci^x)).Класс моделей параллельного выбора обозначим через Рг.С помощью введенных операций над моделями выбора можно определить более сложные модели - последовательно-параллельного выбора [12], обобщенного математического программирования [13] и др. - и найти их логическое описание.Помимо суперпозиции и композиции используются и другие операции над моделями выбора. В их числе операция ветвления, когда в зависимости от наличия некоторого свойства применяется та или иная модель выбора, операция ограниченной обратной связи, при которой выбор производится в несколько туров, каждый из которых зависит от результатов предыдущего тура. Для реализации этих операций используются более сильные логические средства - логика первого порядка [14] (см. п. 6.2). Весьма распространенным способом выбора на основе нескольких отношений является выбор по некоторому отношению, образованному их агрегированием. Исследование этой модели производится в рамках языка (3,2)-значной логики, развитого для порядковых отношений (см. п. 8.2).2. Сложность задач, связанных с анализом и синтезом моделей2.1. Формулировка задачПусть задан некоторый класс М моделей выбора. Будем говорить, что ФНВ (Л, С1, С0) представима в классе М, если она реализуется некоторой моделью этого класса. Задача синтеза в классе М состоит в том, чтобы по заданной ФНВ установить, представима ли она в этом классе, и, если представима, - построить реализующую ее модель М Е М.ФВ С* (ФВ С*) называется мажорантой [минорантой) заданной ФНВ [Л, С1, С0), если для любого X Е А выполнено С\Х) С С*(Х) (С°(Х) С Х\С*{Х)). ФВ С+Логические методы построения и анализа моделей выбора43(ФВ С~) называется верхней [нижней] аппроксимацией заданной ФНВ (А, С1, С°) в классе моделей М, если С+ - мажоранта (С~ - миноранта) этой ФНВ, представи-мая в классе М, и для всякой ее мажоранты С* (миноранты С*), пред ставимой в М, при всех X выполнено включение С*(Х) ~Э С+(Х) (С*(Х) С С~(Х)). Легко видеть, что верхняя (нижняя) аппроксимация, если она существует, - единственна. Задача об аппроксимации (верхней или нижней) в классе М состоит в том, чтобы по ФНВ узнать, имеет ли она соответствующую аппроксимацию в этом классе, и, если имеет,-найти ее.Пусть с моделью М связана некоторая характеристика сложности 1(М). Задача оптимального синтеза в классе моделей М ставится как задача построения по ФНВ реализующей ее модели М Е М с минимальным значением 1(М). Модели М\ и Мг будем называть эквивалентными, если Смх = См2- Задача минимизации в классе М состоит в том, чтобы по модели МеМ построить эквивалентную модель М' Е М, имеющую наименьшую сложность.Приведем результаты по исследованию перечисленных задач на NP-трудность и полиномиальность применительно к классам моделей Rl, Sq и Рг, введенным выше.2.2.Результаты для класса R1Под сложностью /(г) отношения г будем понимать число входящих в него пар. Пусть задана ФНВ (А, С1, С0). С каждым i, 1 ^ г ^ п, свяжем множество£г = (J X.Если оно пусто, полагаем Ej = {i}. Образуем отношение г, задав г-1 (г) = = А \ Ej, 1 ^ г ^ п. Кроме того, построим парно-выявленное отношение г, где irj ^^ {i,j} eAAje C°({i,j}).Теорема 1 [7, 10].1.ФНВ (А, С1, С0} представима в классе R1 тогда и только тогда, когда(VX Е А)(Х С Ej =^ г ^ С°(Х)), и при выполнении этого условия в качестве еереализации может быть взято отношение г.2..Всякая ФНВ имеет в классе R1 верхнюю аппроксимацию, которая реализуется отношением г.3.Нижняя аппроксимация в классе R1 для ФНВ существует тогда и только тогда, когда (VX E A)(Cf(X) П С°(Х) = 0), и при выполнении этого условия нижняя аппроксимация реализуется отношением г.4..Задача оптимального синтеза в классе R1 является NP-трудной.Для всюду определенных ФВ п. 3 теоремы доказан в [15]. Теорема показывает, что задачи синтеза и аппроксимации в классе R1 полиномиальны, а оптимального синтеза-NP-трудна. Задача минимизации в классе R1 не возникает, поскольку разным отношениям соответствуют разные ФВ. Отметим, что если рассматривать выбор лучшихвариантов (правило 2), то все перечисленные задачи (включая задачу оптимальногосинтеза) оказываются полиномиальными [7].2.3.Результаты для класса SqМодель М последовательного выбора задается набором отношений (ri,...,rfc). С такой моделью М будем связывать две сложностные характеристики: 1(М) - суммарное число пар в отношениях модели М и к(М) - число отношений в М. Эти характеристики будем называть соответственно сложностью и глубиной модели. Для44Л. А. Шоломовуменьшения сложности модели можно использовать операцию приведения, при выполнении которой для каждых i,j Е А связывающие их пары (i,j) и (j, г) удаляются из всех отношений, кроме того, где они встретились впервые. Приведенная модель эквивалентна исходной [10].При решении конструктивных задач для моделей последовательного выбора возникают трудности принципиального характера, поскольку в большинстве своем эти задачи оказываются NP-трудными.Теорема 2 [7, 10, 16].1..При любом к ^ 2 задача синтеза моделей в классе Sqfc NP-трудна.2..При любом к ^ 2 задачи нахождения верхней и нижней аппроксимаций в классе Sqfc NP-трудны.3..При любом к задача минимизации сложности в классе Sqfc полиномиальна: минимальной по сложности является приведенная модель.4..При любом к ^ 3 задача минимизации глубины в классе Sqfc NP-трудна. При к = 2 она полиномиальна.NP-трудность задач синтеза и аппроксимации в классе Sqfc объясняется тем, что задача о реализуемости ФНВ в этом классе является NP-трудной (данный факт доказан в [7] для к = 2, но может быть распространен на произвольные к). В связи с выявленной трудностью этих задач рассматривались некоторые их ослабленные постановки, для которых удалось найти эффективные способы решения. В [7] описан метод последовательной аппроксимации, который с полиномиальной трудоемкостью при определенных статистических предположениях относительно множества допустимых предъявлений Л строит при каждом к для почти всех (при п -> оо) функций, представимых в Sqfc, модели, одновременно лучшие по сложности и глубине. В [16] изучен некоторый ослабленный вариант задачи минимизации глубины (задача сжатия), и в случае, когда модель использует лишь ацикличные отношения (определение см. в п. 4.2), предложен полиномиальный алгоритм ее решения. Отметим, что в прикладных задачах обычно применяются ацикличные отношения, ибо лишь они гарантируют непустоту выбора.2.4. Результаты для класса РгПусть модель М параллельного выбора использует отношения г\,..., г к и оператор F. С такой моделью М будем связывать две сложностные характеристики: 1(М) - суммарное число пар в отношениях модели М и к(М) - число отношений в М. Эти характеристики будем называть соответственно сложностью и шириной модели.В большинстве своем конструктивные задачи, относящиеся к модели Рг, оказываются эффективно решаемыми. В определенной степени это объясняется тем, что имеется простой алгоритм проверки представимости ФНВ в классе Рг, основанный на том, что необходимым и достаточным условием представимости в классе Рг является антимонотонность частичных булевых функций С^г'(Х^г'), 1 ^ г ^ п (антимонотонные функции - отрицания монотонных) [7, 11].Теорема 3 [7, 11].1..Задача синтеза моделей в классе Рг полиномиальна.2..Верхняя и нижняя аппроксимации в классе Рг существуют для всех ФНВ, и задача их построения полиномиальна.3..Задача минимизации сложности в классе Рг полиномиальна.4.Задача минимального синтеза в классе Рг NP-трудна.1.Логические методы построения и анализа моделей выбора45Нахождение верхней (нижней) аппроксимации в классе Рг сводится к построению минимальных (максимальных) всюду определенных антимонотонных функций, не меньших (не больших) С®{Х®). В случае верхней аппроксимации такие функции имеют видС®{Х®) =\/Д Xj,l^i^n.Z\ Z={i}vZ£AAi£C1(Z) jeA\ZДля нижней аппроксимации функции строятся двойственным образом. Если ФНВ представима в классе Рг (т.е. функции С«(Х«) антимонотонны), то в качестве ее реализации может быть взята модель, реализующая верхнюю аппроксимацию.Что касается задачи минимизации ширины модели (которая в теореме не упомянута), то скорее всего она NP-трудна, ибо к ней полиномиально сводится задача о минимальном дизъюнктивном базисе системы множеств, не сравнимых по включению [7]. Задача о минимальном дизъюнктивном базисе NP-трудна [17] и, по-видимому, то же справедливо при условии несравнимости множеств системы.3. Сложность моделей выбора3.1. Характеристики сложностиПусть М - некоторый класс моделей выбора и (£^ - класс ФВ на гг-элементном множестве вариантов А^п', пред ставимых моделями из М. Пусть с каждой моделью М G М связана некоторая характеристика сложности 1(М). Сложностью функции выбора С G £j^ (в классе моделей М) называется величина/М(С) = min{/(M) \МеМ, См = С}.Сложность класса моделей М характеризуется функцией/MW=max{/M(C)|CG^)}.Возникает задача исследования поведения функции 1м.{р) и разработки методов синтеза, гарантирующих оценки, близкие к /м(^)- Ставятся и другие задачи оценочного характера. Одна из них связана с изучением взаимного влияния различных характеристик сложности. Пусть помимо 1(М) задана некоторая характеристика сложности к(М) моделей М G М. Введем величинуГШ(С) = min{/(M) | М G М, См = С, к(М) = км(С)}.Сравнение величин l^(C) с /м(С) показывает, к какому увеличению сложности / приводит минимизация к. Аналогично может быть введена величина к^^{С*) и на ее основе изучено влияние / на к.Исследуем поведение сложностных характеристик для классов моделей Sq и Рг. Как и раньше, для моделей М из этих классов в качестве характеристик сложности будем рассматривать суммарное число 1(М) пар в отношениях модели М и число отношений к(М). Отметим, что в классе R1 нетривиальной характеристикой является лишь Zri(ti), ибо кц\(п) = 1. Из достаточно простых соображений следует, что 1т(п) = п(п- 1).3.2. Сложность моделей класса SqАсимптотически точные значения сложности и глубины моделей класса Sq даются следующим утверждением.46Л. А. ШоломовТеорема 4 [7, 10].lsq(n) ~ п2, kS(i(n) ~ п2/2.Следует отметить, что обе асимптотики могут быть достигнуты одновременно (в одной модели).Для выяснения взаимного влияния параметров реализации в классе Sq рассмотрим величины /gq(C) и kg (С). Если обозначить через 1^„(п) и к$ (п) их максимумы повсем С Е (£gq , то можно показать, что они совпадают с /sq(^) и ksq(n). Поэтому для изучения взаимного влияния 1(М) и к(М) в классе Sq будем использовать другие функции. Введем величиныAU(C0 = ^sq(C)Asq(C), AzSq(n) = тах{Лг8с1(С) | С е еЦ},характеризующие увеличение сложности при минимизации глубины. Аналогично введем характеристики As (С) и ASq(n) увеличения глубины при минимизации сложности.Теорема 5 [7, 10].\lS4(n) ~ n, n2/4 < A*» ^ п2/2.Доказательство теоремы показывает, что асимптотически максимальное увеличение сложности может произойти при уменьшении глубины всего на 1, а максимальное по порядку увеличение глубины - при небольшом уменьшении сложности.3.3. Сложность моделей класса РгАсимптотически точные значения сложности и ширины моделей класса Рг приводятся в следующем утверждении. Теорема 6 [7, 11]./рг(гг) ~ п2, kpr(n) ~ п.В отличие от класса Sq здесь не удалось совместить обе асимптотики в одной конструкции. Однако для произвольной функции С из (£рг построена модель М, параметры которой отличаются от /sq(^) и ^Sq(^) не более чем в 2 раза. Более точно, 1(М) ^ 2п(п - 1), к(М) ^ 2п + 1. Кроме того, в случае, когда в модели используются лишь частичные порядки и сложность отношения измеряется числом дуг в базисном графе, в [18] предложена конструкция, асимптотически наилучшая одновременно по сложности и ширине.Для выяснения взаимного влияния параметров реализации в классе Рг рассмотрим величины /рг(С) и кРг(С) и обозначим через 1Рг(п) и кРг(п) их максимумы по всем С G £рг. Получены следующие результаты.Теорема 7 [7, 11].ГРг(п)~п3, 0,94гг3/2

Ключевые слова

функция выбора , модель выбора , анализ , синтез , аппроксимация , оптимизация , оценка сложности , последовательный выбор , параллельный выбор , оператор группового выбора , декомпозиция , агрегирование , порядковое отношение , порядковая модель

Авторы

ФИООрганизацияДополнительноE-mail
Шоломов Лев Абрамович Институт системного анализа РАН, г. Москва профессор, доктор физико-математических наук sholomov@isa.ru
Всего: 1

Ссылки

Murakami Y. Logic and cocial choice. London: Routledge & Kegan Paul Ltd.; New York: Dover Publication Inc., 1968.
Шоломов Л. А. Логические методы в задачах согласованного выбора / Препринт ВНИИ системных исследований. М., 1978.
Березовский Б. А., Барышников Ю. М., Борзенко В. И., Кемпнер Л. М. Многокритериальная оптимизация: математические аспекты. М.: Наука, 1989.
Макаров И.М., Виноградская Т.М., Рубчинский A.M., Соколов В. Б. Теория выбора и принятия решений. М.: Наука, 1982.
Левченков В. С. Алгебраический подход в теории группового выбора. М.: Наука, 1990.
Aleskerov F. Т., Vladimirov А. V. Hierarchical voting // Information sciences. 1986. V. 39. P. 41-86.
Шоломов Л. А. Логические методы исследования дискретных моделей выбора. М.: Наука, 1989.
Айзерман М. А., Вольский В. И., Литваков Б. М. Элементы теории выбора. Псевдокритерии и псевдокритериальный выбор. М.: Нефтяник, 1994.
Вольский В. И., Лезина З. М. Голосование в малых группах: процедуры и методы сравнительного анализа. М.: Наука, 1991.
Шоломов Л. А. Применение логических методов в задачах последовательного выбора / Препринт. ВНИИ системных исследований. М., 1980.
Шоломов Л. А. Логические методы композиции функций выбора / Препринт ВНИИ системных исследований. М., 1981.
Шоломов Л. А. Оценка сложностных характеристик одного механизма выбора с участием нескольких лиц // Изв. АН СССР. Техническая кибернетика. 1985. №2. С.3-13.
Шоломов Л. А., Юдин Д. Б. Сложность многошаговых схем обобщенного математического программирования // Изв. АН СССР. Техническая кибернетика. 1988. № 1. С. 13-22.
Sholomov L. Context-independent choice: description and analysis by means of first-order logic // Logic, Game theory and Social choice. Proceedings of the Intern. Conference LGS'99. Tilburg University Press, 1999. P. 549-559.
Литваков Б. М. Аппроксимация функций выбора // Автоматика и телемеханика. 1984. №9. С. 138-146.
Шоломов Л. А. О сложности задач минимизации и сжатия моделей последовательного выбора // Дискретный анализ и исследование операций. Сер. 1. 1999. Т. 6. №3. С. 87-109.
Stockmeyer L. J. The set-basis problem is NP-complete // Report N RC-5431. New York: IBM Research Center, Yorctown Heights, 1975.
Шоломов Л. А. О сложности реализации функций выбора системой отношений частичного порядка // Проблемы кибернетики. Вып.41. М.: Наука, 1984. С. 111-116.
Шоломов Л. А. Функциональные возможности и сложность механизмов выбора, основанных на исключении худших вариантов // Изв. АН СССР. Техническая кибернетика. 1987. №1. С. 10-17.
Юдин Д. Б., Шоломов Л. А. Многошаговые схемы обобщенного математического программирования и функции выбора // Докл. АН СССР. 1985. Т. 282. №5. С. 1066-1069.
Arrow K.J. Difficulty in the concept of social welfare //J. Political Economy. 1950. V. 58. P. 326-346.
Arrow K. J. Social Choice and Individual Values, 2nd ed. New Haven-London: Yale University Press, 1963.
Айзерман М.А., Алескеров Ф. Т. Выбор вариантов: основы теории. М.: Наука, 1990.
Фишберн П. Теория полезности для принятия решений. М.: Наука, 1978.
Шоломов Л. А. Операторы над отношениями, сохраняющие транзитивность // Дискретная математика. 1998. Т. 10. Вып. 1. С. 28-45.
Шоломов Л.А. Исследование отношений в критериальных пространствах и синтез операторов группового выбора // Математические вопросы кибернетики. Вып. 5. М.: Физматлит. 1995. С. 109-143.
Шоломов Л. А. Агрегирование линейных порядков в задачах группового выбора // Автоматика и телемеханика. 1998. №2. С. 113-122.
Sholomov Lev A. Explicit form of neutral social decision rules for basic rationality conditions // Mathematical Social Sciences. 2000. V. 39. No. 1. P. 81-107.
Моркялюнас А. Групповой выбор при независимости и слабой симметрии альтернатив // Математические методы в социальных науках. Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1985. Вып. 18. С. 57-60.
Данилов В. И. Модели группового выбора // Изв. АН СССР. Техническая кибернетика. 1983. №1. С. 143-164.
Владимиров А. В. Исследование процедур построения коллективных решений: Автореф. дис. ... канд. техн. наук / Ин-т проблем управления. М., 1987.
Шоломов Л.А. О сложности реализации бинарных отношений путем теоретико-множественных операций над отношениями линейного порядка // Проблемы кибернетики. Вып. 41. М.: Наука, 1984. С. 101-109.
Шоломов Л. А. О представлении бинарного отношения набором критериев // Изв. АН СССР. Техническая кибернетика. 1984. №1. С. 6-14.
Hiraguchi T. On the dimension of partially ordered sets // Sci Rep. Kanazawa University. 1951. V. 1. No.2. P. 77-94.
Ope О. Теория графов. М.: Наука, 1980.
Trotter W.T. Embedding finite posets in cubes // Discrete Math. 1975. V. 12. No.2. P. 165-172.
Erdös P., Moser L. On the representation of directed graphs as unions orderings // Magyar tud. akad. Mat. kutató int. közl. 1964. V. 9. No. 1-2. P. 125-132.
Шоломов Л. А. Декомпозиция отношений в задачах выбора: вполне разделимые отношения и независимость от пути // Автоматика и телемеханика. 2001. №11. С. 154-164.
Шоломов Л. А. Анализ рациональности модели последовательного выбора // Автоматика и телемеханика. 2000. №5. С. 124-132.
Шоломов Л. А. Представление и исследование порядковых моделей выбора средствами логики первого порядка // Математические вопросы кибернетики. Вып. 7. М.: Наука, Физматлит, 1998. С. 169-202.
Мальцев А. И. Алгебраические системы. М.: Наука, 1970.
Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.
Шоломов Л. А. Сложность распознавания свойств порядковых отношений в п-мерных пространствах // Дискретный анализ и исследование операций. Сер. 1. 2002. Т. 9. №4. С.82-105.
Подиновский В. В. Многокритериальные задачи с однородными равноценными критериями // Журнал вычислительной математики и математической физики. 1975. Т. 15. №2. С. 130-141.
Подиновский В. В. Многокритериальные задачи с упорядоченными по важности критериями // Автоматика и телемеханика. 1976. №11. С. 118-127.
Шоломов Л. А. Синтез транзитивных порядковых отношений, согласованных с информацией о силе критериев // Сибирский журнал исследования операций. 1994. Т. 1. №4. С. 64-92.
Шоломов Л. А. Метод интерпретаций в задаче синтеза операторов группового выбора // Алгебра и теория моделей 6. Новосибирск: НГТУ, 2007. С. 96-110.
Шоломов Л. А. Логические методы исследования отношений в критериальных пространствах с порядковыми шкалами произвольного вида // Автоматика и телемеханика. 2004. №5. С. 120-130.
Шоломов Л. А. Распознавание свойств порядковых отношений в дискретных пространствах // Дискретный анализ и исследование операций. Сер. 1. 2004. Т. 11. №3. С. 88-110.
Шоломов Л. А. Теоретико-модельный подход к описанию порядковых отношений в конечнозначных пространствах // Синтаксис и семантика логических систем: Материалы Российской школы-семинара, посвященной Ю.Е. Шишмареву. Владивосток: Дальнаука, 2008. С. 28-29.
 Логические методы построения и анализа моделей выбора             | ПДМ. 2009. № 1(3).

Логические методы построения и анализа моделей выбора | ПДМ. 2009. № 1(3).

Полнотекстовая версия