ПОИСК ИНДИВИДУАЛЬНО-ОПТИМАЛЬНЫХ РАВНОВЕСИЙ В УСЛОВИЯХ ЧАСТИЧНОЙ ИНФОРМИРОВАННОСТИ ИГРОКОВ
ПОИСК ИНДИВИДУАЛЬНО-ОПТИМАЛЬНЫХ РАВНОВЕСИЙ В УСЛОВИЯХ ЧАСТИЧНОЙ ИНФОРМИРОВАННОСТИ ИГРОКОВ
Автор: Сергей Мащенко
Аннотация: Рассматривается понятие индивидуально- оптимального равновесия в некооперативных играх. Описаны методы параметризации множества этих равновесий. Предлагается процедура поиска индивидуально-оптимальных равновесий в условиях частичной информированности игроков.
Ключевые слова: не кооперативные игры, равновесие по Нешу, оптимальность по Парето,
индивидуально-оптимальное равновесие.
ACM Classification Keywords: H4.2 Decision support
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Наиболее привлекательными концепциями оптимальности в условиях полной информированности игроков являются принципы оптимальности по Парето и по Нешу [1].
Концепция оптимальности по Парето основана на идее кооперативного поведения игроков, когда они коллективно выбирают свои стратегии и совместно учитывают функции выигрыша. Поэтому не существует ситуаций, которые будут для всех игроков одновременно лучше любой Парето-оптимальной. В случае, когда игроки выбирают основой для соглашения между собой концепцию Парето- оптимальности, у некоторых из них может возникнуть соблазн при выборе конкретной Парето- оптимальной ситуации изменить свою стратегию на другую, которая будет лучше для них. В этом случае такая ситуация будет нестабильной и их договоренность может быть разрушенной.
Концепция равновесий по Нешу основывается на идее некооперативного поведения игроков, когда они индивидуально выбирают свои стратегии и каждый учитывает лишь свою функцию выигрыша. Ситуация игры называется равновесием Неша, если от нее невыгодно отклоняться любому одному игроку (все другие игроки свои стратегии не изменяют), поскольку значение его функции выигрыша не улучшится (будет для него оптимальным). Если игроки заключают соглашение о своем будущем поведении и его основой является равновесие Неша, то оно будет стабильным. “Ценой” привлекательности равновесий Неша являются серьезные проблемы, которые связаны с их существованием, сложностью нахождения, проблемой выбора единственного равновесия [1].
( Читать дальше )
Автор: Сергей Мащенко
Аннотация: Рассматривается понятие индивидуально- оптимального равновесия в некооперативных играх. Описаны методы параметризации множества этих равновесий. Предлагается процедура поиска индивидуально-оптимальных равновесий в условиях частичной информированности игроков.
Ключевые слова: не кооперативные игры, равновесие по Нешу, оптимальность по Парето,
индивидуально-оптимальное равновесие.
ACM Classification Keywords: H4.2 Decision support
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Наиболее привлекательными концепциями оптимальности в условиях полной информированности игроков являются принципы оптимальности по Парето и по Нешу [1].
Концепция оптимальности по Парето основана на идее кооперативного поведения игроков, когда они коллективно выбирают свои стратегии и совместно учитывают функции выигрыша. Поэтому не существует ситуаций, которые будут для всех игроков одновременно лучше любой Парето-оптимальной. В случае, когда игроки выбирают основой для соглашения между собой концепцию Парето- оптимальности, у некоторых из них может возникнуть соблазн при выборе конкретной Парето- оптимальной ситуации изменить свою стратегию на другую, которая будет лучше для них. В этом случае такая ситуация будет нестабильной и их договоренность может быть разрушенной.
Концепция равновесий по Нешу основывается на идее некооперативного поведения игроков, когда они индивидуально выбирают свои стратегии и каждый учитывает лишь свою функцию выигрыша. Ситуация игры называется равновесием Неша, если от нее невыгодно отклоняться любому одному игроку (все другие игроки свои стратегии не изменяют), поскольку значение его функции выигрыша не улучшится (будет для него оптимальным). Если игроки заключают соглашение о своем будущем поведении и его основой является равновесие Неша, то оно будет стабильным. “Ценой” привлекательности равновесий Неша являются серьезные проблемы, которые связаны с их существованием, сложностью нахождения, проблемой выбора единственного равновесия [1].
( Читать дальше )
- +2
- 4 ноября 2009, 15:55
- комментировать
ОБ ОСОБЕННОСТЯХ ПРИНЯТИЯ РЕШЕНИЙ ПРИ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ НА ОСНОВЕ МЕТОДА БАЗИСНЫХ МАТРИЦ часть 2
ОБ ОСОБЕННОСТЯХ ПРИНЯТИЯ РЕШЕНИЙ ПРИ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ НА ОСНОВЕ МЕТОДА БАЗИСНЫХ МАТРИЦ
Таблица 1. Порядок точности обращения матрицы (log10 ?1)
Алгоритм без выбора ведущего элемента
Double -15.30 -12.48 -10.31 -9.15 -5.47
double+1 -18.95 -17.62 -15.87 -13.96 -8.12 -9.63 -6.44
double+2 -16.84 -15.80 -15.79 -14.08 -5.86 -9.30 -5.95
Dd -46.26 -43.88 -41.67 -39.77 -39.57 -37.05
dd+1 -51.36 -48.99 -48.01 -44.47 -43.88 -41.87 -39.02
dd+2 -51.22 -49.99 -47.43 -45.22 -43.99 -41.83 -39.68 -38.17
Qd -108.82 -110.08 -108.03 -102.56 -102.79
qd+1 -116.80 -112.97 -113.53 -110.23 -109.95 -108.10 -105.26
qd+2 -117.52 -116.17 -113.75 -111.40 -108.72 -105.66 -106.13 -103.19
Алгоритм с выбором ведущего элемента
Double -17.70 -16.82 -14.54 -13.07 -9.87 -8.95 -7.10
double+1 -19.02 -17.63 -15.83 -13.92 -8.27 -9.57 -6.33 -5.31
double+2 -16.83 -15.77 -15.76 -14.06 -5.89 -9.37 -5.93 -3.22
dd -49.96 -47.71 -46.16 -43.81 -43.16 -40.95 -38.16 -35.42
dd+1 -51.31 -48.97 -47.99 -44.48 -43.85 -41.86 -39.33 -38.69
dd+2 -51.21 -49.90 -47.41 -45.21 -44.03 -41.83 -39.70 -38.16
qd -115.70 -113.03 -111.33 -109.47 -106.46 -104.84 -103.51 -100.48
qd+1 -117.04 -114.58 -113.83 -110.06 -109.04 -106.80 -105.47 -102.29
qd+2 -112.25 -114.94 -113.79 -111.73 -108.24 -105.84 -104.93 -103.90
( Читать дальше )
Таблица 1. Порядок точности обращения матрицы (log10 ?1)
Алгоритм без выбора ведущего элемента
Double -15.30 -12.48 -10.31 -9.15 -5.47
double+1 -18.95 -17.62 -15.87 -13.96 -8.12 -9.63 -6.44
double+2 -16.84 -15.80 -15.79 -14.08 -5.86 -9.30 -5.95
Dd -46.26 -43.88 -41.67 -39.77 -39.57 -37.05
dd+1 -51.36 -48.99 -48.01 -44.47 -43.88 -41.87 -39.02
dd+2 -51.22 -49.99 -47.43 -45.22 -43.99 -41.83 -39.68 -38.17
Qd -108.82 -110.08 -108.03 -102.56 -102.79
qd+1 -116.80 -112.97 -113.53 -110.23 -109.95 -108.10 -105.26
qd+2 -117.52 -116.17 -113.75 -111.40 -108.72 -105.66 -106.13 -103.19
Алгоритм с выбором ведущего элемента
Double -17.70 -16.82 -14.54 -13.07 -9.87 -8.95 -7.10
double+1 -19.02 -17.63 -15.83 -13.92 -8.27 -9.57 -6.33 -5.31
double+2 -16.83 -15.77 -15.76 -14.06 -5.89 -9.37 -5.93 -3.22
dd -49.96 -47.71 -46.16 -43.81 -43.16 -40.95 -38.16 -35.42
dd+1 -51.31 -48.97 -47.99 -44.48 -43.85 -41.86 -39.33 -38.69
dd+2 -51.21 -49.90 -47.41 -45.21 -44.03 -41.83 -39.70 -38.16
qd -115.70 -113.03 -111.33 -109.47 -106.46 -104.84 -103.51 -100.48
qd+1 -117.04 -114.58 -113.83 -110.06 -109.04 -106.80 -105.47 -102.29
qd+2 -112.25 -114.94 -113.79 -111.73 -108.24 -105.84 -104.93 -103.90
( Читать дальше )
- +2
- 4 ноября 2009, 15:30
- комментировать
ОБ ОСОБЕННОСТЯХ ПРИНЯТИЯ РЕШЕНИЙ ПРИ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ НА ОСНОВЕ МЕТОДА БАЗИСНЫХ МАТРИЦ часть 1
ОБ ОСОБЕННОСТЯХ ПРИНЯТИЯ РЕШЕНИЙ ПРИ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ НА ОСНОВЕ МЕТОДА БАЗИСНЫХ МАТРИЦ
Автор: Алексей Волошин, Всеволод Богаенко, Владимир Кудин
Аннотация. Использование разных типов данных при проведении вычислений (чисел с плавающей запятой одинарной, двойной, повышенной точности) существенно влияет на основные критерии оценки эффективности: быстродействие, точность и объемы вычислений. В работе исследовано влияние использования разных вариантов организации вычислений на эффективность алгоритмов метода базисных матриц. Предложен вариант построения системы поддержки принятия решения для организации вычислений на линейных моделях для достижения заданных значений параметров по основным критериям: точности и быстродействию.
Ключевые слова: линейная модель, типы данных, базисная матрица.
ACM Classification Keywords: H.4.2 Information Systems Applications: Types of Systems: Decision Support
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Известно, что большинство исследуемых физических процессов на определенном этапе моделирования описываются в классе линейных моделей, в частности, в виде системы плохо обусловленных линейных алгебраических уравнений(СЛАУ) с квадратной матрицей ограничений. Малые неточности представления подобных математических моделей могут существенно влиять на количественные и качественные характеристики получаемого решения при использовании конкретного метода (алгоритма) [Воеводин, 1979]. Такие неточности зачастую обусловлены ограниченностью длины мантиссы при представлении чисел с плавающей запятой. Важно отметить, что, несмотря на наличие ЭВМ, у которых операции округления реализованы самым лучшим образом, тем не менее, избежать ошибок округления и улучшить их известные теоретические оценки не удается [Воеводин, 1979]. Выбором конкретных типов данных с плавающей запятой, достигается различная эффективность по точности получаемого решения, быстродействию и объемам вычислений. Дополнительной возможностью для повышения эффективности вычислений является правильная организация использования регистровой, кэш-памяти, оперативной и внешней памяти [Деммель, 2001]. Известно, что скорость обменов между этими типами памяти зачастую намного выше скорости проведения вычислений и при плохой организации вычислений может “свести на нет” эффект от использования “быстрой” памяти. Все это обуславливает включение в контур принятия решения лица, принимающего решение (ЛПР), с целью правильной организации вычислительного процесса: указания механизма (процедуры) устранения неопределенностей при выборе приоритетов по критериям к решению и типам данных. Достигается это, например, использованием категории функций принадлежности [Орловский, 1981]. Такой подход усложняет исследования, но, в тоже время, открывает новые возможности для построения алгоритмов.
( Читать дальше )
Автор: Алексей Волошин, Всеволод Богаенко, Владимир Кудин
Аннотация. Использование разных типов данных при проведении вычислений (чисел с плавающей запятой одинарной, двойной, повышенной точности) существенно влияет на основные критерии оценки эффективности: быстродействие, точность и объемы вычислений. В работе исследовано влияние использования разных вариантов организации вычислений на эффективность алгоритмов метода базисных матриц. Предложен вариант построения системы поддержки принятия решения для организации вычислений на линейных моделях для достижения заданных значений параметров по основным критериям: точности и быстродействию.
Ключевые слова: линейная модель, типы данных, базисная матрица.
ACM Classification Keywords: H.4.2 Information Systems Applications: Types of Systems: Decision Support
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.
Введение
Известно, что большинство исследуемых физических процессов на определенном этапе моделирования описываются в классе линейных моделей, в частности, в виде системы плохо обусловленных линейных алгебраических уравнений(СЛАУ) с квадратной матрицей ограничений. Малые неточности представления подобных математических моделей могут существенно влиять на количественные и качественные характеристики получаемого решения при использовании конкретного метода (алгоритма) [Воеводин, 1979]. Такие неточности зачастую обусловлены ограниченностью длины мантиссы при представлении чисел с плавающей запятой. Важно отметить, что, несмотря на наличие ЭВМ, у которых операции округления реализованы самым лучшим образом, тем не менее, избежать ошибок округления и улучшить их известные теоретические оценки не удается [Воеводин, 1979]. Выбором конкретных типов данных с плавающей запятой, достигается различная эффективность по точности получаемого решения, быстродействию и объемам вычислений. Дополнительной возможностью для повышения эффективности вычислений является правильная организация использования регистровой, кэш-памяти, оперативной и внешней памяти [Деммель, 2001]. Известно, что скорость обменов между этими типами памяти зачастую намного выше скорости проведения вычислений и при плохой организации вычислений может “свести на нет” эффект от использования “быстрой” памяти. Все это обуславливает включение в контур принятия решения лица, принимающего решение (ЛПР), с целью правильной организации вычислительного процесса: указания механизма (процедуры) устранения неопределенностей при выборе приоритетов по критериям к решению и типам данных. Достигается это, например, использованием категории функций принадлежности [Орловский, 1981]. Такой подход усложняет исследования, но, в тоже время, открывает новые возможности для построения алгоритмов.
( Читать дальше )
- +2
- 4 ноября 2009, 15:19
- комментировать