Введение к работе
Актуальность темы. В настоящее время, когда информация становится жизненно важным ресурсом, когда информационная деятельность определяется как приоритетная в процессе развития цивилизации и когда эта деятельность во всем своем широчайшем спектре в значительной степени опирается на современные достижения компьютерной техники, становится очевидной необходимость всестороннего фундаментального исследования основных понятий информатики, процессов представления, обработки, хранения и передачи информации. В этом отношении на первый план выдвигаются задачи строгой формализации понятий, нахождения эффективных алгоритмов обработки и анализа информации, принятия на их базе наиболее рациональных решений, генерации новых знаний. Безусловно, основой решения этих задач следует считать математические методы, те достижения, которые накопило человечество в важнейшей из научных областей - математике.
Интерес к задачам наилучшего выбора был высоким всегда, но особенно возрос в последние годы в связи с интенсивным развитием науки и техники. С одной стороны, людям все чаще и чаще триходится заниматься процессами, для осуществления которых требуется максимально эффективное использование имеющихся средств і ресурсов; с другой стороны, с развитием вычислительной техники зезко увеличились возможности изучения и воздействия человека на )бщественные и производственные процессы. Стал неизбежным научный юдход, базирующийся на математическом моделировании исследуемых іадач, что стимулировало возникновение и развитие новой науки-еории исследования операций.
При анализе задач исследования операций используется азнообразный математический аппарат, однако наиболее широкое-аспространение получили методы математического программирования, еории вероятностей и теории игр.
Теория игр изучает математические модели принятия ятимальных решений в условиях конфликта. В последнее время эцросн, связанные с реальными конфликтами, стали привлекать эистальное внимание экономистов, математиков, социологов и эедставителей других специальностей. Под конфликтом понимается зякое явление, в котором участвуют различные стороны, наделенные ібственннми интересами и обладающие определенными возможностями
действия. К конфликтам в этом понимании слова относятся многие явления экономического, социального, военного содержания. Несмотря на определенную ограниченность математических моделей ї трудность проверки адекватности реальности, их исследование все же помогает правильно оценить обстановку и выработай рекомендации по разрешению конфликта.
Теория игр, появившаяся как математическое описание экономических проблем, но получившая самостоятельное развитие внутри математики, представляется ныне полезным инструментом для. математизированного исследования конфликтов не толькс экономического содержания, а также процессов принятия решений і условиях, лишь модельно сходных с конфликтами. К числу первые относятся теоретике- игровые рассмотрения военных, дипломатических и правовых вопросов; к числу вторых- теория статистических решений, а также теоретико- игровые моделі: принятия решений в планировании, в прогнозировании, в технике, ь биологии и в медицине.
Практическое значение теории игр было обосновано еще е середине XX века в монографии Джона фон Неймана и Оскарг Моргенштерна и развито в работах их последователей. Большое внимание в этих работах уделено кооперативным играм п лиц.
Классически принято рассматривать кооперативную игру п лиц е форме характеристической функции. Пусть имеется множество игрокоЕ N=(1,2,...,п}. Игроки могут образовывать всевозможные коалиции S, выбирать совместно стратегии, составлять взаимообязывающие соглашения и даже выплачивать побочные платежи в виде компенсаций за участие в коалициях. При этом каждой коалиции S из множества всех коалиций ставится в соответсвие тот максимальный выигрыш v(S), который могут гарантировать себе в сумме все члены коалиции S независимо от действий остальных игроков.
Интересным является применение теории кооперативных игр к экономическим и внеэкономическим исследованиям, при выработке плановых и управленческих решений, в которых требуется найти лучшее решение для всех участников при столкновении интересов различных групп.
В реальных условиях принимающий решение субъект знает лишь множество вариантов тех обстоятельств, в которых ему приходится принимать решение, но не знает ни точно того варианта, который е действительности имеет место, 'ни даже вероятностного
распределения на множестве вариантов. Классическая кооперативная теория ориентируется на наименее благоприятное стечение обстоятельств для каждой коалиции S, хотя, совсем не обязательно, что у остальных игроков есть возможность помешать коалиции S получить больше выигрыша v(S). Это приводит к некоторой упрощенности и ограниченности математических моделей реальных конфликтов.
Для реальной оценки силы коалиции имеет смысл оценить значение выигрыша, превзойти который в сумме игрокам коалиции S могут гарантированно не позволить остальные игроки. Таким образом, разумно рассмотреть игру п лиц в форме интервальной характеристической функции, когда выигрыш любой коалиции принимает значение из отрезка, характеризующего в целом силу коалиции (аналогично нижней и верхней цене антагонистической игры в чистых стратегиях).
Интервальная сумма выигрыша имеет смысл при наличии чеопрвдоленных факторов, неполноте информации и т.д.
Неопределенные факторы моясно разбить на следующие подгруппы: і) неопределенные .факторы, появляющиеся за счет действующих іезависимо от оперирующей стороны лиц, имеющих в общем случае :вои цели; неопределенные фактори такого типа можно условно
[азвать стратегиями противника;
і) неопределенные факторы, появляющиеся из-за недостаточной
зученности каких-либо процессов или величин;
) неопределенные факторы, отражающие нечеткость знания цели
перации или критерия эффективности;
) технические информационные неопределенные факторы:
еопределенностй, возникающие в процессе сбора, переработки и
эредачи информации.
Применение интервального подхода, позволяющего учесть все
яды неопределенности и неполноты информации, к кооперативным
трам является новым направлением, актуальным как с точки зрения
эзвития теоретической информатики, так и с точки зрения создания
)лее адекватного математического аппарата для анализа прикладных
щач.
Целью работы является рассмотрение теории кооперативных игр лиц в случае, когда выигрыш любой коалиции задается не
днственным значением характеристической функции, а принимает которое значение из отрезка.
Объектом исследования является теория кооперативных игр п лиц.
Предмет исследования- кооперативные игры п лиц с интервальной характеристической функцией.
Проблема заключается в определении понятий решения для кооперативных игр с интервальной характеристической функцией.
Б основу исследования положена следующая гипотеза: для кооперативной игры п лиц с интервальной характеристической функцией, как и для классической кооперативной игры, можно определить следующие понятия: дележ, доминирование, решение игры; получить необходимые и достаточные условия их существования.
Для реализации поставленной mmi и проверки сформулированной выше гипотезы потребовалось решить следующие задачи:
- ввести понятие интервальной характеристической функции в
кооперативной игре п лиц;
- определить понятие допустимого дележа, как исходного в разумном
распределении выигрыша,
рассмотреть кооперативные игры п лиц с интервальной характеристической функцией в (О,^-редуцированной форме;
получить необходимые и достаточные условия существования множества дележей для таких игр с использованием fq-8J- покрытий;
рассмотреть различные понятия ядра в качестве решения для кооперативной игры п лиц с интервальной характеристической функцией.
Методологическую основу работы составляют современные методы теории игр, математического программирования, теории исследования операций, некоторые теоремы о линейных неравенствах.
Научная новизна. Отличие данной работы состоит в том, что в ней введен новый подход к кооперативным играм п лиц, а именно: предлагается учитывать не только наибольшее значение выигрыша, который могут гарантировать себе в сумме все члены коалиции независимо от действий остальных игроков, а еще и наименьшее значение выигрыша, которое могут гарантированно позволить коалиции остальные игроки. В этом случае выигрыш любой коалиции будет принадлежать отрезку. Этот подход приводит к тому, что дележ в такой игре, вообще говоря, может и не существовать. Поэтому возникает необходимость введения понятия допустимого дележа и доказательства необходимых и достаточных условий егс существования. Для этого кооперативные игры с интервальной
характеристической функцией; приводятся к (0,7 J-редуцированной форме и используются (q-Q)-покрытия для получения условий непустоты множества допустимих дележей, что приводит к специфическим задачам линейного программирования.
Далее решается вопрос, какой из дележей выбрать результатом игры. Здесь предложено несколько вариантов. Рассматривается понятие доминирования через введение степени доминирования а и определяется решение в виде С^-ядра. Опираясь на определение решения в виде ІУ-ядра, предложенного Д.Шмайдлером, вводится понятие нормированного эксцесса и решается задача минимизации нормированного эксцесса в лексикографическом порядке.
Рассматривается исходная игра как двухкритериальная. Разумный исход такой, игры естественно искать среда парето-олтимальных точек. Ядро определяется на основе функции эксцесса, которая в свою очередь определяется как расстояние до парето-оптимадьной точки, используются метод суммирования с весовыми коэффициентами и минимаксный метод с весовыми коэффициентами.
Практическая значимость работы. Предложенная интервальная форма кооперативной игры п лиц может быть применена к различным прикладным задачам: экономическим, экологическим, политическим. Разработка на ее базе экономико-математических моделей даст на чаш взгляд более адекватное реальности описание процессов тринятия решений и позволит получить эффективные решения в сфере мэнирования и управления в различных видах деятельности.
Основные положения, выносимые на защиту: - кооперативную игру можно и целесообразно задавать с помощью >трезка возможных значений характеристической функции; при этом юновной задачей остается установление возможных выигрышей [троков;
каждая кооперативная игра с интервальной характеристической іункцией, удовлетворяющая некоторому условию, стратегически квивалентна одной и только одной игре в (О, ^-редуцированной орме, а у последней существует дележ при выполнении пределенных условий;
для кооперативной игры с интервальной характеристической ункцией определяются разные вида решений, с использованием эклассических представлений D и №-ядер.
Апробация работы. Результаты исследования были представлены з III Международной конференции женщин- математиков (Воронеж, 29
мая- 2 июня 1995 года), на III Международной конференции "Компьютерные программы учебного назначения" (Донецк, 27-29 августа 1996 года), докладывались на научно- методическом семинаре кафедры информатики и дискретной математики МПГУ им. В.И.Ленина, на аспирантском объединении.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 95 источников. Всего ІЩ страниц.