close

Вход

Забыли?

вход по аккаунту

?

Гомоморфизмы и конгруэнтности игр с отношениями предпочтения.

код для вставкиСкачать
УДК 519.83
Т.Ф. Савина
ГОМОМОРФИЗМЫ И КОНГРУЭНТНОСТИ ИГР
С ОТНОШЕНИЯМИ ПРЕДПОЧТЕНИЯ
Игра двух игроков с отношениями предпочтения определяется как система объектов
G = hX, Y, A, ?1 , ?2 , F i,
где X множество стратегий игрока 1, Y множество стратегий игрока 2, A множество исходов, ?i отношение предпочтения игрока i, i = 1, 2, заданное на A, F отображение множества ситуаций
X Ч Y в множество исходов A.
Пусть теперь, кроме игры G, задана еще одна игра с отношениями
предпочтения тех же игроков ? = hU, V, B, ?1 , ?2 , ?i.
Определение 1. Тройка отображений (? , ? , ?), где ? : X ? U,
1
2
1
?2 : Y ? V, ? : A ? B, называется гомоморфизмом игры G в игру ?,
если для i = 1, 2 выполняются следующие условия:
?i
?i
a1 . a2 ? ?(a1 ) . ?(a2 ),
(i = 1, 2),
(H1)
? ? F = ? ? (?1 ?2 ).
(H2)
Определение 2. Тройка отображений (? , ? , ?), где ? : X ? U,
1
2
1
?2 : Y ? V, ? : A ? B, называется строгим гомоморфизмом игры G в
игру ?, если выполняются следующие условия (здесь ??i есть строгая
часть, а ?si симметричная часть отношения ?i ):
??i
?i?
a1 < a2 ? ?(a1 ) < ?(a2 ),
?s
(i = 1, 2),
?s
a1 ?i a2 ? ?(a1 ) ?i ?(a2 ) (i = 1, 2)
(H1a)
(H1b)
и условие (H2).
Ясно, что строгий гомоморфизм является гомоморфизмом, но обратное неверно.
Если ?1 отображение X на U , ?2 отображение Y на V (т.е.
эти отображения являются сюръекциями), то гомоморфизм (?1 , ?2 , ?)
называется сюръективным или гомоморфизмом игры G на игру ?. Если
же отображения ?1 , ?2 и ? являются биекциями и выполняется условие
?i
?i
a1 . a2 ? ?(a1 ) . ?(a2 ),
63
i = 1, 2,
(1)
то гомоморфизм (?1 , ?2 , ?) называется изоморфизмом игры G на игру ?.
Две игры с отношениями предпочтения называются изоморфными, если существует изоморфизм одной из них на другую. Если отображения
?1 , ?2 и ? инъективны и в условии (1) вместо ? выполнена импликация ?, то будем говорить, что первая игра изоморфно вкладывается во
вторую.
Пусть G = hX, Y, A, ?1 , ?2 , F i игра с отношениями
предпочтения. Пусть на множествах стратегий игроков и множестве
исходов заданы отношения эквивалентности ?1 ? X 2 , ?2 ? Y 2 , ?3 ? A2
и для тройки эквивалентностей ? = (?1 , ?2 , ?3 ) выполняется следующее
условие согласованности:
Теорема 1.
0 ?1
x ?x
?2
y0 ? y
)
?3
? F (x0 , y 0 ) ? F (x, y).
(2)
Тогда определена фактор-игра
G/ ? = hX/ ?1 , Y / ?2 , A/ ?3 , ?1 / ?3 , ?2 / ?3 , F? i
с отношениями предпочтения, и тройка канонических отображений
? = (??1 , ??2 , ??3 ) является сюръективным гомоморфизмом G на G/ ?.
Доказательство.
Определим
функцию
реализации
F?
игры
G/ ?
условием:
df
F? ([x]?1 , [y]?2 ) = [F (x, y)]?3 .
Покажем, что определение отображения F? корректно, т.е. не зависит
от выбора представителей из классов эквивалентностей. Действительно,
возьмем других представителей этих классов x0 ? [x]?1 , y 0 ? [y]?2 . Тогда
?1
?2
?3
x0 ? x, y 0 ? y , отсюда по условию согласованности F (x0 , y 0 ) ? F (x, y),
т.е. [F (x0 , y 0 )]?3 = [F (x, y)]?3 . Таким образом, корректность определения
отображения F? сводится к выполнению условия согласованности.
Определение функции реализации F? может быть записано в виде
F? (??1 (x), ??2 (y)) = ??3 (F (x, y)). Таким образом, здесь выполнено условие (H2) гомоморфизма, причем ? = ??3 , ? = F? , ?1 = ??1 , ?2 =
= ??2 . Условие (H1) гомоморфизма выполняется по определению факторотношения.
Теорема доказана.
Пусть G, ? две игры с отношениями предпочтения
и тройка отображений ? = (?1 , ?2 , ?3 ) гомоморфизм G на ?.
Тогда справедливы следующие утверждения:
1) тройка отношений эквивалентности ?? = (??1 , ??2 , ??3 ), каждое
из которых представляет собой ядро соответствующего отображения,
Теорема 2.
64
удовлетворяет условию согласованности (2), следовательно, можно построить фактор-игру G/ ?? ;
2) существует тройка отображений ? = (?1 , ?2 , ?3 ) из игры G/ ??
в ?, которая является изоморфным вложением G/ ?? в ?.
Доказательство.
1. По определению выполняются равносильности:
??1
x0 ? x ? ?1 (x0 ) = ?1 (x);
??2
y 0 ? y ? ?2 (y 0 ) = ?2 (y);
??3
a0 ? a ? ?3 (a0 ) = ?3 (a).
Каждое из отношений (??1 , ??2 , ??3 ) является отношением эквивалентности. Проверим условие согласованности, которое сводится
здесь к выполнению равенства ??3 (F (x0 , y 0 )) = ??3 (F (x, y)). Так как
(?1 , ?2 , ?3 ) гомоморфизм, то доказываемое равенство принимает
вид ?(?1 (x0 ), ?2 (y 0 )) = ?(?1 (x), ?2 (y)), а так как ?1 (x0 ) = ?1 (x),
?2 (y 0 ) = ?2 (y), то доказываемое равенство очевидно. По теореме 1 можно
построить фактор-игру G/ ?? , причем тройка канонических отображений
будет сюръективным гомоморфизмом G на G/ ?? .
2. Строим изоморфное вложение игры G/ ?? в игру ? по правилу: ?1 ([x]??1 ) = ?1 (x), ?2 ([y]??2 ) = ?2 (y), ?3 ([a]??3 ) = ?3 (a). Убедимся, что
определения отображений ?1 , ?2 , ?3 корректны, т.е. каждое из указанных
отображений не зависит от выбора представителя из соответствующего
класса эквивалентности. Пусть x0 и x находятся в одном и том же классе,
??1
тогда x0 ? x, откуда ?1 (x0 ) = ?1 (x). Аналогично убеждаемся в корректности определений ?2 , ?3 .
Докажем инъективность отображений ?1 , ?2 , ?3 (например, для ?1 ).
Инъективность следует из цепочки равносильностей
??1
?1 ([x0 ]??1 ) = ?1 ([x]??1 ) ? ?1 (x0 ) = ?1 (x) ? x0 ? x ? [x0 ]??1 = [x]??1 .
Проверим, что тройка отображений (?1 , ?2 , ?3 ) является гомоморфизмом из игры G/ ?? в ?.
Убедимся, что выполняется условие (H1). Пусть [a1 ]??3 , [a2 ]??3 ?
??3
??3
? ?i / ??3 . Тогда ?a01 ? a1 , a02 ? a2 (т.е. ?3 (a01 ) = ?3 (a1 ), ?3 (a02 ) = ?3 (a2 ))
(a01 , a02 ) ? ?i ; так как ? гомоморфизм, то (?3 (a01 ), ?3 (a02 )) ? ?i . Используя написанные выше равенства, получаем (?3 (a
1 ), ?3 (a2 )) ? ?i . Согласно
определению ?3 получаем ?3 ([a1 ]??3 ), ?3 ([a2 ]??3 ) ? ?i .
65
Условие (H2) принимает вид
?3 (F? ([x]??1 , [y]??2 )) = ?(?1 ([x]??1 ), ?2 ([y]??2 )).
Запишем цепочку равенств:
?3 (F? ([x]??1 , [y]??2 )) = ?3 ([F (x, y)]??3 ) = ?3 (F (x, y));
так как ? гомоморфизм, то
?3 (F (x, y)) = ?(?1 (x), ?2 (y)) = ?(?1 ([x]??1 ), ?2 ([y]??2 )).
Обратная импликация в (1) может не выполняться. Таким образом,
тройка отображений (?1 , ?2 , ?3 ) является изоморфным вложением факторигры G/ ?? в игру ?.
Теорема доказана.
УДК 517.518.85
С.П. Сидоров
ОШИБКА ОПТИМАЛЬНОЙ ИНТЕРПОЛЯЦИИ
ПОЛОЖИТЕЛЬНЫМИ АЛГОРИТМАМИ
Пусть W есть замкнутое уравновешенное выпуклое подмножество линейного пространства X . Рассмотрим проблему оптимального восстановления линейного функционала L на основе множества значений линейных
функционалов l1 , . . . , ln . Для f ? W положим
If := (l1 f, . . . , ln f ).
Оператор I : W ? Rn называется информационным.
Задачи оптимального восстановления функционалов возникают во
многих приложениях теории приближения функций и привлекают повышенное внимание. Подробное изложение предмета можно найти в статье
[1] и книге [2].
Пусть V некоторый конус в Rn . Пусть ?(V ) означает класс всех
линейных алгоритмов A : Rn ? R, использующих информацию I , таких,
что A(v) > 0 для всех v ? V .
Величина
e(L, W, I, V ) := inf
sup |Lf ? A(If )|
A??(V ) f ?W
66
Документ
Категория
Без категории
Просмотров
4
Размер файла
299 Кб
Теги
конгруэнтности, игр, гомоморфизмов, отношения, предпочтений
1/--страниц
Пожаловаться на содержимое документа