Обговорюється новий метод дослідження ієрархічних ігор. обчислюється максимальний гарантований результат гравця верхнього рівня в ієрархічної грі двох осіб. Аналізується стійкість цього завдання по відношенню до змін функції виграшу другого гравця.

Анотація наукової статті з математики, автор наукової роботи - Горєлов Михайло Олександрович


Maximal guaranteed result in hierarchical games

A new method of investigation of hierarchical two-player games is discussed. This method consists of solving games with complex information exchanges using, for the most part, identical transformation of predicate calculus formulas. We introduce the notion of maximal guaranteed result in a game, give two definitions and discuss the relationship between them. The new method is illustrated on a classical example for which a maximal guaranteed result of a high level player in hierarchical game of two players is calculated. Some particular cases are discussed. Stability of this problem according to variation of the payoff function of the second player is analyzed. We also demonstrate how the definition, and, accordingly, the method are modfied for a benevolent or a bounded-rational second player. Also, we show that the new definiton is convenient for the investigation of stability of maximal guaranteed result calculation procedure with respect to the parameters of the game.


Область наук:

  • Математика

  • Рік видавництва: 2017


    Журнал: Управління великими системами: збірник праць


    Наукова стаття на тему 'Максимальний гарантований результат в ієрархічних іграх'

    Текст наукової роботи на тему «Максимальний гарантований результат в ієрархічних іграх»

    ?УДК 519.865 + 519.95 ББК 22.165

    МАКСИМАЛЬНИЙ гарантований РЕЗУЛЬТАТ В ІЄРАРХІЧНИХ ІГРАХ

    Горєлов М. А.1

    (Обчислювальний центр ім. О.О. Дородніцина Фіц ІУ РАН, Москва)

    Обговорюється новий метод дослідження ієрархічних ігор. Обчислюється максимальний гарантований результат гравця верхнього рівня в ієрархічній грі двох осіб. Аналізується стійкість цього завдання по відношенню до змін функції виграшу другого гравця.

    Ключові слова: інформаційна теорія ієрархічних систем, ієрархічні ігри, максимальний гарантований результат.

    1. Введення

    В даній статті обговорюється новий метод дослідження ієрархічних ігор. Він уже показав свою ефективність при дослідженні декількох важких завдань [6-13]. Але саме тому, що досліджувалися складні моделі, прості основні ідеї методу «обростали» складними технічними деталями. Нижче робиться спроба продемонструвати метод на простого завдання, але більш докладно. Метод заснований на альтернативному способі визначення максимального гарантованого результату.

    Традиційне визначення максимального гарантованого результату було, мабуть, вперше дано Ю.Б. Гермейе-ром [3] і потім багато разів використовувалося в теорії ієрархи-

    1 Михайло Олександрович Горєлов, кандидат фізико-математичних наук (Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.).

    чеських ігор [4-5], теорії активних систем [1-2], теорії контрактів [15-16].

    Для обчислення максимального гарантованого результату в іграх зі складними інформаційними обмінами Ю.Б. Гермейера був запропонований метод, заснований на вгадуванні структури оптимальних рішень. Цей метод виявився дуже плідним, але чомусь погано сприймається представниками інших наукових шкіл.

    Нове визначення дозволяє вирішувати аналогічні завдання, використовуючи, головним чином, тотожні перетворення формул обчислення предикатів. Можливо, для когось такий підхід буде більш зрозумілим. І, як показує досвід, в деяких завданнях, де вгадати структуру рішення важко, цей метод виявляється працездатним.

    Стаття побудована наступним чином. У розділі 2 наводяться два визначення максимального гарантованого результату і обговорюється зв'язок між ними. У розділі 3 новий метод демонструється на прикладі класичної задачі обчислення максимального гарантованого результату в грі Г2. Наступний розділ присвячений неформального обговорення деяких особливостей методу і отриманих результатів. У п'ятому розділі показано, як модифікується нове визначення і, відповідно, метод для ігор з доброзичливим або обмежено раціональним другим гравцем. Останній розділ присвячений демонстрації того, що нове визначення зручно і для дослідження стійкості завдання обчислення максимального гарантованого результату по відношенню до змін параметрів гри.

    2. Визначення

    Розглянемо конфлікт, в якому беруть участь два гравці. Перший з них вибирає свої управління (стратегії) з безлічі і, другий - з безлічі V. Інтереси першого гравця описуються прагненням до максимізації функції g, що відображає декартовій твір і х V в безліч дійсних чисел Я. Другий гравець прагне максімізі-

    ровать значення функції h: U х V ^ R. Таким чином задається гра Г = (U, V, g, h).

    Результат, отриманий в даній ситуації кожним з учасників конфлікту, залежить не тільки від його вибору, але і від вибору його партнера. Цей вибір, взагалі кажучи, може бути невідомий оскільки він розглядався гравцеві в момент прийняття рішень. Тому, щоб отримати замкнуту модель конфлікту, потрібно задати відношення гравців до такого роду невизначеності. Традиційно це робиться завданням принципу оптимальності. У даній статті в цій іпостасі буде використовуватися принцип максимального гарантованого результату. Класичне визначення, що йде від Ю.Б. Гермейера, виглядає наступним чином.

    Визначення 1. Безліч раціональних відповідей другого гравця на стратегію u е U першого визначається рівністю

    (1) BR (u) = (v eV: h (u, v) = max h (u, w)),

    weV)

    якщо максимум в цій формулі досягається, і формулою

    (2) BR (u) = \ v eV: h (u, v) > sup h (u, w) - до)

    l weV)

    в іншому випадку (тут до- заздалегідь заданий позитивне число). Максимальний гарантований результат першого гравця в грі Г дорівнює

    RK (T) = sup inf g (u, v) .

    ueU veBRK (u)

    Змістовний сенс цих конструкцій такий. Передбачається, що гравець номер 1 першим вибирає свою стратегію u е U і цей вибір стає відомим його партнеру. В цьому випадку результат другого гравця вже залежить тільки від його власного вибору. А оскільки його мета полягає в максимізації функції h, природно припустити, що він вибере стратегію з безлічі, визначеного формулою (1). Проблема виникає в тому випадку, коли це безліч виявляється порожнім через те, що максимум не досягається. У цьому випадку потрібна «латочка». Досить природно використовувати в такому

    Як формулу (2). Знаючи функцію виграшу партнера, перший гравець може прорахувати таку логіку його дій. Тому гравець 1 може розраховувати на отримання виграшу, не меншої ШГ g (і, V) в разі вибору стратегії і. А при

    уеБЯк (і)

    оптимальних діях він може отримати виграш, як завгодно близьке до ЛДГ).

    Дамо альтернативне визначення максимального гарантованого результату. Тепер почнемо з мотивації.

    Припустимо, перший гравець вибрав свою стратегію і е і і цей вибір став відомий його партнеру. В такому випадку другий гравець може розділити всі безліч своїх стратегій на дві частини: вигідні стратегії і невигідні. Цілком природно припустити, що цей поділ проводиться за допомогою деякого порогового значення Л його функції виграшу: стратегії, для яких виграш більше або дорівнює цьому граничного значення, є вигідними, а всі інші - невигідними. При такій логіці поведінки партнера перший гравець може розраховувати на гарантоване отримання виграшу у, якщо для будь-якої вигідною стратегії V другого гравця виконується нерівність g (u, V) > у. В даному випадку не передбачається можливості відмови другого гравця від гри, тому безліч його вигідних стратегій при будь-якої стратегії і має бути непустою.

    Таким чином, приходимо до наступного визначення.

    Визначення 2. Число у називається гарантованим результатом першого гравця в грі Г, якщо існують такі стратегія і е і і число Л, що виконуються умови

    1 °. Існує стратегія ^ е V, для якої Н (і, w) > Л. 2 °. Для будь-якої стратегії V е V або g (u, V) > у, або І (і, V) < Л.

    Точна верхня межа ^ (Г) гарантованих результатів називається максимальним гарантованим результатом першого гравця в грі Г.

    Природно виникає питання про співвідношення цих двох визначень. Почнемо з наступного простого результату.

    Лемма 1. Для будь-якої гри Г і будь-якого числа до> 0 справедливо нерівність R (r) > RJT).

    Доведення. Досить довести, що будь-яке число y< R * (r) є гарантованим результатом в сенсі визначення 2. Якщо остання нерівність виконано, то існує стратегія u е U, для якої inf g (u, v) >y .

    veBRк (u)

    Фіксуємо одну з таких стратегій.

    Якщо ця стратегія така, що максимум max h (u, w) до-

    weV

    Стигала, то покладемо Л = max h (u, w). При такому виборі мно-

    weV

    дружність тих стратегій v, для яких h (u, w) > Л, буде непустою. Отже, пункт 1 ° визначення 2 виконаний. Далі, якщо v е BRKu), то g (u, v) > inf g (u, v) >y. А в іншому

    veBRK (u)

    випадку h (u, w) < Л, тобто виконується і другий пункт визначення 2.

    Якщо для стратегії u максимум max h (u, w) не досягається,

    weV

    то покладемо Л = sup h (u, w) -К. Тоді для будь-якого w е BR ^ u)

    weV

    нерівність h (u, w) > Л буде справедливим, тому пункт 1 ° визначення 2 виконаний. І знову, якщо v е BRKu), то g (u, v) > inf g (u, v) >y, а якщо v i BRJ ^ u), то h (u, w) < Л, зна-

    veBR (u)

    чит, виконаний і пункт 2 °. Лема доведена.

    Рівність R (r) = RK (r), взагалі кажучи, невірно, як показує наступний приклад.

    Приклад 1. Нехай U = [0, 1], V = (0, 1), g (u, v) = h (u, v) = u - v. Для будь-якої стратегії u максимум max h (u, w) не досягає-

    weV

    ся, тому BRJu) = (0, до]. Отже, inf g (u, v) = u -до і

    veBRK (u)

    RJF) = 1 - до.

    З іншого боку, при будь-якому y< 1, u = 1 і Л = y безліч {v е V: h (u, v) > Л} не порожньо, а при співпадаючих інтересах гравців і Л = y умова 2 ° визначення 2 виконується автомати-

    тично. Значить, будь-у< 1 є гарантованим результатом і Л (Г) = 1.

    У наведеному прикладі результати R (0 і ^ ДГ) мало відрізняються при невеликих значеннях к. Цей факт має загальну природу, як показує наступне твердження.

    Лемма 2. Для будь-якої гри Г справедливо рівність R (Г) = lim ДДГ) .

    Доведення. З леми 1 негайно слід нерівність R (Г) > lim Rr (Г). Щоб довести зворотне нерівність, зауважимо, що безліч BR ^ u) не може розширитися при зменшенні к. Тому величина R ^ O зі зменшенням до може тільки зрости. Отже, досить довести, що для будь-якого гарантованого (в сенсі визначення 2) результату у знайдеться таке значення до, що R ^ O > у.

    Отже, нехай у - гарантований результат, а u е U, w е V і Л - стратегії і число, існування яких передбачено визначенням 2.

    Якщо стратегія u така, що максимум max h (u, v) достига-

    veV

    ється, то для будь-якої стратегії v е BR ^ u) маємо h (u, v) = max h (u, v) > h (u, w) > Л,

    veV

    отже, g (u, v) > у. Значить, Inf g (u, v) > у, і тим більше

    veBRJu)

    RJT) > у (незалежно від к).

    Якщо ж max h (u, v) не досягається, то sup h (u, v) > h (u, w) .

    veV veV

    Покладемо к = sup h (u, v) - h (u, w). Тоді для будь-якої стратегії

    veV

    v е BR (u) виконуються умови

    h (u, v) = sup h (u, v) - до > h (u, w) > Л .

    veV

    Тому Inf g (u, v) >у і, отже, R ^ O > у.

    veBRк (u)

    Приклад 1 вказує основну причину, по якій R (0 > R ^ O. Це в свою чергу дозволяє виділити важливий

    клас «хорошіх1» ігор, для яких вірно рівність Д (Г) = ДДГ).

    Визначення 3. Гру Г назвемо хорошою, якщо для будь-якої стратегії ті U знайдеться така стратегія u е U, що inf g (u, v) > inf g (і, v)

    ve BRK (u) veBRK (m)

    і максимум maxh (u, v) досягається.

    veV

    Хорошими є, наприклад, ігри, у яких безлічі V наділені топологиями і компактні, і при будь-якій фіксованій стратегії u функція (p (v) = h (u, v) неперервна. Але насправді клас хороших ігор набагато ширше. Про це мова піде в наступному параграфі. Поки ж констатуємо наступний простий факт.

    Лема 3. Для будь-якої хорошої гри Г і будь-якого до> 0 справедливо рівність Л (Г) = RJT).

    Доведення. Фіксуємо довільну S> 0. Нехай у-довільне число, менше R ^ T), а стратегія і така, що inf g (і, v) >у. Фіксуємо стратегію u, існування

    veBRg (і)

    якою передбачено визначенням 3. Тоді inf g (u, v) >у.

    veBRs (u)

    Але стратегія u обрана так, що BR? (U) = BRJu) - Отже, inf g (u, v) > у, а тоді RJT) > у. Так як у довільно, підлозі-

    veBRK (u)

    чим нерівність RJT) > R ^ T). Значить, Rr (Г) > lim R ^ (Г). з

    цієї нерівності і леми 2 випливає, що R (0 < R ^ F). А в силу леми 1 R (0 > R ^ O, що і доводить потрібне твердження.

    Зауваження 1. Практично тими ж міркуваннями можна довести зворотне нерівність RK (Г) < lim Rs (Г) (це нерівність можна отримати і як безпосередній наслідок

    1 Можливо, більш доречними були б терміни «регулярна» або «узгоджена», але ці і схожі терміни вже перевантажені іншими значеннями.

    лем 1 і 2). Таким чином, для хороших ігор результат R ^ r) від до насправді не залежить.

    3. Гра Г2

    Тепер можна продемонструвати нове визначення в дії. Розглянемо модифікацію гри Г, в якій перший гравець до вибору свого управління отримує достовірну інформацію про управління, обраному партнером. Таким чином, він може вибрати сові управління u в залежності від обраного другим гравцем управління v, і стратегіями першого гравця стають функції u *: V ^ U. Безліч всіх таких функцій позначимо через U *.

    Отримаємо нову гру Г * = (U *, V, g *, h *), в якій функції виграшу g * і h * визначаються умовами g * (u *, v) = g (u * (v), v) і h * (u *, v) = h (u * (v), v) відповідно. Перш за все зазначимо, що два визначення максимального гарантованого результату в цій грі при стандартних припущеннях збігаються. Це випливає з наступного твердження.

    Лемма 4. Якщо безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U х V, то гра Г * є хорошою.

    Доведення. Почнемо з пояснення основної ідеї докази. Якщо стратегія зі * така, що верхня межа suph (с, v) = suph (c (v), v) досягається, то все очевидно. це

    veV veV

    може бути не так, якщо функція зі *: V ^ U розривна, і відповідно, розривної в якійсь точці v0 буде функція (fv) = h (f * (v), v). Її графік буде виглядати, наприклад, як на рис. 1. Безліч BRK (c) на цьому малюнку показано жирною лінією. Якщо ми поміняємо значення функції з * так, щоб цей графік став виглядати як на рис. 2, то нас цікавить верхня межа буде досягатися в одній точці v0, і, відповідно, з однієї цієї точки складатиметься безліч раціональних відповідей другого гравця на отриману стратегію. Точка v0 не належить безлічі BRK (c *), але належить

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

    Мал. 1.

    Мал. 2.

    Якщо стратегія про * така, що верхня межа sup h (о, v)

    veV

    досягається, то можна покласти u * = о * і твердження буде доведено.

    В іншому випадку розглянемо довільну послідовність vi, v2, ..., для якої limh (о, vk) = suph (о, v) .

    veV

    Безліч V компактно, отже, з цієї послідовності можна виділити сходящуюся підпослідовність. Тому, не обмежуючи спільності, можна вважати, що сама ця послідовність сходиться до точки v0. Оскільки верхня межа sup h (о, v) не досягається, можна вважати, що

    veV

    vk Ф v0 при k = 1, 2, ... Послідовність o * (v1), o * (v2), ... належить компактному безлічі U, значить, перейшовши ще раз до підпослідовності, можна домогтися того, що і послідовність o * (v1), o * (v2), ... буде сходитися до деякої точці u0. Визначимо функцію u * умовою

    u * (v) = •

    р (v) в іншому випадку.

    u0, якщо v = v0,

    В силу безперервності функції h

    h * (u *, v0) = h (u * (v0), v0) = h (M0, v0) = lim h (u * (vt), vt) =

    = Limh (a (vk), vt) = suph (a (v), v) .

    k ^ lX) veV

    А при v Ф v0 маємо

    h (u ", v) = h (u" (v), v) = h (a, (v), v) < sup h (a, (v), v)

    veV

    (Оскільки верхня грань suph (a, v) не досягається).

    veV

    Тому верхня межа sup h (u ,, v) досягається в єдиній

    veV

    точці v0 і, отже, BR ^ u *) = {v0}.

    Тоді в силу безперервності функції g inf g * (u *, v) = g (u * v), v0) = lim g (u * (vt), vk) =

    veBRK (u *) до ^ ад

    = Lim g (® * (vk), vk) .

    до ^ ад

    Але оскільки верхня грань sup h (a, v) не досягається і

    veV

    lim h (a, vk) = sup h (a, v), для досить великих значень до

    до ^ ад veV

    маємо vk e BR ^ (® *). Отже, для цих значень до виконуються нерівності g (a (vk), vk) > inf g * (a, v) а, значить,

    veBRk (a *)

    вірно нерівність limg (a (vk), vk) > inf g * (a, v). Отже,

    veBRk (a *)

    inf g (u, v) > inf g (a, v).

    ve BRK (u *) veBRc (o *)

    Лема доведена.

    Тепер можна продемонструвати ефективність нового визначення.

    За визначенням число у є гарантованим результатом першого гравця в грі Г *, якщо 3u, e U3 ^, [3w e V: h (u ,, w) >X \ &

    &[Vve V g (u ,, v)>у vh (u ,, v) <X \.

    У цьому умови фігурує функціональний простір U *. Найближча мета полягає в тому, щоб переформулювати це умова в термінах вихідної гри Г.

    Умова (3) рівносильне умові

    Зі е і З Л [Зи е V: к (і ,, м>) > Л & g, (і ,, м>) > у \&

    &[Уу е V g, (і ,, V) >у V до (і ,, V) < Л \.

    Справді, достатність умови (4) для виконання умови (3) очевидна. Необхідність випливає з того, що для управління w, існування якого передбачена першою частиною умови (3), в силу другої частини того ж умови повинно виконуватися нерівність h * (u *, w) > у.

    В умови (4) поміняємо порядок кванторів існування ЗЛЗі е і \ Зм> ЕV: к (і ,, м>) > Л & g, (і ,, м>) >у \ &

    &[Vv е V g, (і ,, V) >у V до (і ,, V) <Л \ і перепишемо його у вигляді

    ЗЛ [З®, єї Зи ЕV: к (а ,, м>) >Л& g, (а ,, м>) >у \&

    &[ЗШ, єї Vv е V ^ (ш ,, V) >у V до (ш ,, V) <Л \

    (Тут важливо «розділити» один квантор існування на два).

    Умова (5) рівносильне умові (4). Справді, необхідність умови (5) для виконання умови (4) очевидна. Для доказу достатності доведеться використовувати функціональну структуру безлічі і. Якщо функції а * і ш * задовольняють умові

    [За е Ізи ЕV: к (а, м>) > Л & ^ (А, м>) >у \&

    & [З ш, е і V V е Vg (ш ,, V) >уv до (ш ,, V) < Л \, то функція

    задовольняє умові

    Зі е і [Зи ЕV: к (і, и) > Л & g (і, и) > у \ &

    &[Vv ЕV g (і, V) > у V до (і, V) < Л \.

    Тепер можна приступати до спрощення формули (5). Умова

    За єї Зие V: к (а, и) > Л& g (а, м /) >у

    а, (V), якщо g (а (V), V) > у, ш, (V) в іншому випадку,

    або

    За е іЗwеV: к (а * (м), м>) > Л &g (а (м), м>) > у, очевидно, еквівалентна умові

    За еіЗм е V: видання (а, м) > Л &g (а, м) > у. А умова

    Зет, еіуу ЕV ^ (ш ", V) > у V К (ш ", V) <Л або, що те ж саме,

    Зет е і Vv е V g (ет (V), V) >уv до (ш "(V), V) < Л, рівносильно условію1

    Vv еVЗетеU g (ш, V) >уv видання (ш, V) <Л.

    Таким чином, умова (5) може бути замінено умовою

    ЗЛ [За е вим е V: к (а, м) > Л & g (а, м) >у] &

    &[Vv еVЗетеU g (ет, V) >уv до (ш, V) <Л],

    або більш простим умовою

    ЗЛ [За е вим е V: Н (а, м) >Л] &

    &[Vv еVЗетеU g (w, V) >уv до (ш, V) <Л].

    Отже, справедливо наступне твердження.

    Теорема 1. Число у є гарантованим результатом в грі Г * тоді і тільки тоді, коли виконана умова (6).

    Основна мета досягнута. Можна переписати отриманий результат в більш звичних термінах, замінивши квантори спільності та існування операторами максимуму і мінімуму.

    Теорема 2. Нехай безлічі і і V наділені топологиями і компактні, а функції g і І безперервні на і х V. Позначимо

    1 Це центральний момент доведення теореми 1. Саме тут ми позбавляємося від функціонального простору і *. Даний прийом з'явився в теорії ігор, мабуть, першим (ще до робіт фон Неймана). Але до сих пір він ефективно працює.

    Л (у) = {v eV: maxg (u, v) < y),

    (, UeU)

    Д (у) = {(u, v) e U x V: g (u, v) > y) .

    Число y є максимальним гарантованим результатом в грі Г * тоді і тільки тоді, коли або max h (u, v) > sup inf h (u, v),

    (U, v)<од (y) veЛ (y) ueU

    або

    max h (u, v) = sup inf h (u, v)

    О, v) од (y) уел (y) ueU

    і верхня межа в правій частині цієї рівності не досягається.

    Доведення. Доведемо достатність. Можна взяти Л = max h (u, v) і в якості со і w - одну з точок максимуму

    (U, v) од (y)

    в останній формулі. Тоді перша частина умови (6) буде виконана. Крім того, для v е Л (у) будемо мати inf h (u, v) < Л,

    ueU

    значить, знайдеться u, для якого h (u, v) < Л. А для v <i Л (у) виконано нерівність max g (u, v) > y, отже, знайдеться

    ueU

    таке u, що g (u, v) > y. Таким чином, виконана і друга частина умови (6).

    Для доказу необхідності зауважимо, що умова Vv ​​eV3m eU g (rn, v) >yv h (m, v) <Л

    виконати тим легше, чим більше Л. Єдиною перешкодою для збільшення Л є умова

    Зс eU3w eV: h (c, w) >Л. Тому, не обмежуючи спільності, можна вважати, що Л = max h (u, v), а тоді висновок теореми негайно

    (U, v) EД (y)

    випливає з умови (6).

    Втім, з теореми 1 неважко отримати і класичну формулу для максимального гарантованого результату в грі Г2. Будемо вважати, що безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U x V.

    Нехай у - гарантований результат. Фіксуємо X так, щоб виконувалася умова

    [За е U3w е V: h (a, w) > X & g (a, w) >у] &

    &[Vv eVB ^ eU g (rn, v) >уv h (rn, v) <X].

    Як вже зазначалося, можна вважати, що точки а і w обрані так, що h (a, w) = max h (u, v). А в такому разі, не обме-

    (U, v) од (у)

    вая спільності, можна вважати, що X = h (®, w). Але в такому випадку X < L, де

    L = max min h (u, v).

    veV ueU

    Справді, для будь-якого v е V знайдеться u е U, для якого h (u, v) < X (для v е Л (у) це випливає з другої частини умови (7), а для інших v з угоди про вибір X). Але це і є потрібне твердження.

    Якщо X = L, то для будь-якого v з безлічі

    E = jv е V: min h (u, v) = max min h (u, w)>

    ue U weV ue U)

    і будь-якого u е U виконано нерівність h (u, v) > X, а тому в силу умови (7) для будь-якого v е E має існувати u е U, для якого g (u, v) > у, тобто у не перевищує величини M = min max g (u, v) .

    veE ueU

    Назад, якщо у< M, то у - гарантований результат, оскільки для v е E знайдеться u е U, для якого g (u, v) > M > у, а для v <t E існує таке u е U, що h (u, v) < L = X.

    Якщо ж X > L, то автоматично виконується умова Vv ​​е V 3u е U: h (u, v) < X. Тому єдиним обмеженням на величину у буде умова

    За е U3w е V: h (a, w) > X & g (a, w) > у. Отже, будь-яке число у, менше ніж sup max g (a, w)

    X>L (а ^) ЄВ (X)

    де

    D (X) = {(a, w) е U x V: h (a, w) > X}.

    Але якщо позначити

    D = {(с, w) e U x V: h (o, w) > L},

    то

    sup max g (c, w) = sup g (c, w) = K .

    Л>Ь (c, w) eD (Л) (cw) ED

    Таким чином, справедливо наступне твердження. Теорема 3 (Ю.Б. Гермейера). Якщо безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U x V, то Д (Г *) = max {K, M}.

    4. Неформальне обговорення отриманих результатів

    Наведемо ще кілька аргументів на користь нового визначення максимального гарантованого результату.

    Зазвичай дослідження ієрархічної гри проводиться в інтересах гравця, який володіє правом першого ходу. Таким чином, функція виграшу другого гравця h відображає уявлення оперує боку про цілі партнера. Максимальний гарантований результат в сенсі визначення 2 не змінюється при будь-якому монотонному перетворення функції h, тобто ця функція задає лише порядок на безлічі U x V, що описує переваги другого гравця. Якщо користуватися визначенням 1, то величина до вводить вже деяку кількісну міру на «шкалою цінностей» другого гравця, тобто в даному випадку необхідно припускати набагато кращу інформованість оперує сторони про супротивника.

    Спробуємо виписати визначення гарантованого результату в сенсі визначення 1 «в Квантор». Число уявляю-ся гарантованим результатом тоді і тільки тоді, коли виконується умова

    3u e U: {[3v e V: Vw e Vh (u, v) > h (u, w)] ^ ^ [Vv e Vg (u, v) < y ^ 3w e V: h (u, w) > h (u, v)] & & [Vv e V: 3w e V h (u, v) < h (u, w)] ^ ^ [Vv e Vg (u, v) < y ^ 3w e V: h (u, w) > h (u, v) + к]}.

    Ця формула набагато складніше формули (3). Якщо вимірювати складність формули кількістю використаних кванторів, то складність збільшується більш ніж удвічі. Значною мірою з цим і пов'язана велика ефективність визначення 2 при дослідженні складних задач.

    Нарешті, чисто естетично «латочка» у визначенні безлічі BR ^ u) виглядає не дуже привабливо, а краса при побудові теорії - не остання річ.

    З леми 3, зокрема, випливає, що якщо безліч V звичайно, то два визначення максимального гарантованого результату збігаються. Припущення про нескінченність безлічі V - це, звичайно ж, ідеалізація. Але в багатьох випадках заміна великого кінцевого безлічі континуумом буває дуже зручна. У зв'язку з цим варто зазначити наступне. Якщо два визначення дають різні результати, то вибір одного з них має вирішуватися в кожному випадку на основі аналізу модельованої системи. Але потрібно розуміти, що питання про перевагу одного з визначень, це питання про те, яке з визначень краще узгоджується з ідеалізацією нескінченності.

    До цього додамо ще, що відмінність двох визначень свідчить про те, що вийшла задача не стійка по відношенню до апроксимації кінцевими сітками. А тому постановка завдання потребує суттєвого уточнення. Звернемося до аналізу отриманих результатів. Якщо у є гарантованим результатом в грі Г *, то аналіз формули (6) дозволяє побудувати стратегію, яка гарантує отримання такого результату. Для простоти1 припустимо, що безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U х V.

    Визначимо стратегії і * і і, умовами g (u * (v), v) = max g (w, v), h (u * (v), v) = min h (w, v)

    weU weU

    (Для будь-якого v e V). Тоді безпосередньо перевіряється, що шуканої є стратегія

    1 У даному випадку це дійсно не принципово.

    про I і * + (V), якщо g (і. + (V), V) > у,

    і * (V) = <

    [І, (V) в іншому випадку.

    Стратегію Иi можна природним чином інтерпретувати як стратегію покарання другого гравця. Її поява в структурі оптимальної стратегії природним чином пояснюється наявністю квантора спільності в поєднанні з нерівністю «<»У формулі (6). А вони, в свою чергу, присутні вже в визначенні 2, тобто поява «покарання» в даному випадку негайно випливає з постановки задачі.

    Відзначимо, що така структура оптимальної стратегії була спочатку вгадати Ю.Б. Гермейера. Справедливості заради відзначимо, що його стратегія була навіть більш «кровожерливої», ніж побудована тільки що.

    Нарешті, відзначимо, що класична теорема 3 і теорема 1 припускають два різних підходи до чисельного пошуку максимального гарантованого результату в грі Г *. Теорема 3 передбачає обчислення щодо простого максимина Ь, рішення оптимізаційної задачі, і, найголовніше, обчислення минимакса М зі складно визначаються безліччю Е. Якщо ж виходити з теореми 1, то потрібно знайти корінь функції, для обчислення одного значення якої необхідно вирішити задачу оптимізації та потім обчислити максимин на безлічі і х V. Який із підходів простіше, напевно, залежить від конкретного завдання. Але наявність двох підходів саме по собі приємно.

    Сказане в попередньому абзаці навіть в ще більшій мірі відноситься до обчислення максимального гарантованого результату в грі Г, які не наділеною додаткової структурою інформаційного розширення.

    5. Інші визначення

    Часто розглядають гри з доброзичливим другим гравцем, тобто вважають, що, приймаючи своє рішення, другий гравець прагне максимізувати власний виграш, а якщо варіантів отримати максимальний виграш кілька, то буде обраний той, який більш вигідний першого гравця.

    Класичне визначення максимального гарантованого результату в цьому випадку дає величину

    (8) R '(Г) = sup sup g (u, v) ,

    ueU veBR (u)

    де безліч BR (u) задається умовою

    (9) BR (u) = {veV: h (u, v) = maxh (u, w)) .

    (. WeV)

    У багатьох випадках припущення про доброзичливість спрощує розглянуту задачу, але є і підводні камені.

    По-перше, припущення про доброзичливість - це додаткова гіпотеза, яку на практиці перевірити досить складно. Тому її широке застосування за межами чисто академічних досліджень викликає питання. Детальніше обговорювати цю проблему навряд чи варто.

    По-друге, знову виникає питання: а що робити, якщо максимум у формулі (9) не досягається? І в даному випадку, як не дивно, проблема виявляється більш гострою, ніж у розглянутому вище. Справа в наступному. З міркувань двох попередніх параграфів видно, що при відсутності гіпотези про доброзичливості в більшості цікавих ігор серед оптимальних стратегій першого гравця неодмінно знайдеться така, що максимум у формулі (1) досягається. Тому «латочка», що дається формулою (2), робить постановку задачі логічно коректною, але нічого не змінює по суті. У припущенні доброзичливості другого гравця це не так. Якщо ми доповнимо визначення аналогічним чином, то в такій моделі першого гравця буде вигідно вибирати стратегію, так, щоб максимум у формулі (9) не досягає. У цьому випадку максимальний гарантований результат буде істотно залежати від «порогу чутливості» другого гравця, що призведе до ускладнення розв'язуваної задачі і т.д.

    Альтернативний варіант визначення знімає другу із зазначених проблем. Виглядає він так.

    Визначення 4. Число y називається гарантованим результатом першого гравця в грі Г з доброзичливим другим гравцем, якщо існують такі стратегія і e U і число Л, що виконуються умови

    1 °. Існує стратегія w е V, для якої h (u, w) > X і g (u, v) > у.

    2 °. Для будь-якої стратегії v е V або g (u, v) > у яких h (u, v) < X.

    Точна верхня межа Л (Г) гарантованих результатів називається максимальним гарантованим результатом першого гравця в грі Г з доброзичливим другим гравцем.

    Якщо гра така, що при будь-якої стратегії u максимум у формулі (9) досягається, то формула (8) дає вираз для максимального гарантованого результату в сенсі визначення 4.

    Визначення 4 відрізняється від визначення 2 лише заміною знака «<»Знаком«<»В пункті 2 °. Тому і працювати з новим визначення можна практично так само. Наприклад, аналоги теорем 1-3 виглядають наступним чином.

    Теорема 4. Число у є гарантованим результатом в грі Г * тоді і тільки тоді, коли виконана умова

    3X [3® е U3w е V: h (a, w) > X & g (a, w) >у] &

    &[Vv eV3meU g (ш, v) > у v h (m, v) < X].

    Теорема 5. Нехай безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U х V. Позначимо

    Л (у) = Iv е V: maxg (u, v) < у},

    (, Іеі)

    Д (у) = | (u, v) і U х V: g (u, v) > у} .

    Число у є максимальним гарантованим результатом в грі Г * тоді і тільки тоді, коли max h (u, v) > sup inf h (u, v) .

    (U, у) од (у) уел (у) u? U

    Теорема 6. Якщо безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U х V, то максимальний гарантований результат першого гравця в грі Г з доброзичливим другим гравцем дорівнює

    max g (u, v),

    (U, v) eD '

    де

    D '= {(©, w) е U х V: h (a>,w) > L},

    L = max min h (u, v).

    veV ueU

    Доказ теореми 4 практично дослівно повторює доказ теореми 1. Докази теорем 5 і 6 слідують схемами доведення теорем 2 і 3 відповідно, з деякими спрощеннями.

    Ще один варіант моделі виникає, коли припускають другого гравця обмежено раціональним, тобто вважають, що він може піти на невеликі втрати свого виграшу, не рахуючи їх принциповими. Мабуть, у багатьох випадках таке припущення навіть краще описує реальність, ніж припущення абсолютної раціональності, зроблене в параграфі 2. Класичний варіант визначення в цьому випадку виглядає наступним чином.

    Визначення 5. Максимальний гарантований результат першого гравця в грі з обмежено раціональним гравцем нижнього рівня дорівнює

    RK (Г) = sup inf g (u, v),

    ueU veBR * (u)

    де безліч раціональних відповідей другого гравця визначається рівністю

    BR (u) = <v e V: h (u, v) > suph (u, w) -до

    } |

    а до- заданий позитивне число.

    Альтернативне визначення може бути сформульовано таким чином.

    Визначення 6. Число у називається гарантованим результатом першого гравця в грі в грі з обмежено раціональним гравцем нижнього рівня Г, якщо існують такі стратегія і е і і число Л, що виконуються умови

    1 °. Існує стратегія ^ е V, для якої Н (і, w) > Л; 2 °. Для будь-якої стратегії V е V або g (u, V) > у яких І (і, V) < Л - до.

    Точна верхня межа Лк (Г) гарантованих результатів називається максимальним гарантованим результатом

    першого гравця в грі в грі з обмежено раціональним гравцем нижнього рівня.

    В даному випадку ці два визначають одне й те саме число ЯК (Г) для довільної гри Г. Доказ в цілому повторює докази лем 1 і 3.

    Аналогами теорем 1-2 є наступні твердження. Теорема 7. Число у є гарантованим результатом в грі з обмежено раціональним гравцем нижнього рівня Г * тоді і тільки тоді, коли виконана умова 3X [3a е U3w е V: h (a, w) > X] &

    &[Vv еV3шеU g (m, v) >уv h (m, v) <X-k].

    Теорема 8. Нехай безлічі U і V наділені топологиями і компактні, а функції g і h безперервні на U х V. Позначимо

    Л (у) = I v ЕV: max g (u, v) < у},

    (, UеU)

    Д (у) = | (u, v) еUxV: g (u, v) > у} .

    Число у є максимальним гарантованим результатом в грі з обмежено раціональним гравцем нижнього рівня Г * тоді і тільки тоді, коли або max h (u, v) > sup inf h (u, v) + до,

    (U, v) од (у) vеЛ (у) ^

    або

    max h (u, v) = sup inf h (u, v) + до

    (U, v) од (у) vеЛ (у) ^

    і верхня межа в правій частині цієї рівності не досягається.

    Аналог теореми 3 теж може бути сформульований [14], правда, виглядає він значно складніше. Тому в даному випадку більше підстав вважати за краще теорему 8 теоремі з [14].

    6. Стійкість і регуляризація

    При дослідженні будь-якої моделі постає питання про стійкість рішення задачі по відношенню до змін параметрів моделі. В даному параграфі буде показано, як нове

    визначення максимального гарантованого результату працює при аналізі стійкості по відношенню до змін функції виграшу другого гравця. Такий вибір постановки обумовлений, по-перше, тим, що таке завдання нетривіальна, але і не призводить до занадто складних формул. По-друге, зазвичай дослідження ієрархічних ігор зазвичай проводиться в інтересах гравця, який володіє правом першого ходу. А в такому випадку інтереси партнера - це елемент моделі, відомий досліднику операції найгірше.

    У загальному випадку задача обчислення максимального гарантованого результату нестійка, що показує наступний приклад.

    Приклад 2. Розглянемо гру Г = (U, V, g, к), в якій U = V = [0, 1], g (u, v) = v, до (і, v) = u.

    У цій грі другому гравцеві байдуже, яку стратегію вибрати. Тому в найгіршому для першого гравця разі він вибере v = 0, отже, Л (Г) = 0.

    Розглянемо «обурену» гру Г = (U, V, g, КS), де ке (і, v) = і + sv. якщо s > 0, то при будь-якої стратегії v другому гравцеві вигідно вибирати v = 1, значить, Л (Г) = 1.

    Таким чином, при як завгодно малому позитивному s різниця між Л (Г) і ^ (rs) залишається великий.

    Насправді, даний простий приклад демонструє типову причину появи нестійкості в розглянутій задачі.

    Для постановки задачі в загальному випадку потрібна міра близькості ігор з різними критеріями другого гравця. Будемо використовувати в якості такого заходу величину

    р (Г, Г ') = sup | h (u, v) - f (u, v) ,

    (U, v) eU xV

    де Г = (U, V, g, к), Г = (U, V, g, f).

    Припустимо, досліднику операції не відома «точна» модель Г, а відомо лише, що побудована їм модель Г 'мало відрізняється від Г. Тоді виникає необхідність в отриманні оцінки величини Л (Г) в термінах параметрів моделі Г'.

    Розглянуті вище конструкції підказують нижню оцінку.

    Лемма 5. Якщо ДГ, Г ') < е, то R2s (Y ') < R (T).

    Доведення. Нехай у - довільне число, менше R2e (P). Фіксуємо стратегію u і число Л, існування яких передбачено визначенням 6. Тоді

    [3w е V: fu, w) > Л] & [Vv е V g (u, v) > у v f u, v) < Л 2е].

    В силу умови ДГ, Г ') < е справедливі нерівності h (u, w) > fu, w) - е і h (u, v) < fu, v) + е. Тому виконується умова

    [3w е V: h (u, w) > Л '] & [Vv е Vg (u, v) > у v h (u, v) < Л '], де Л' = Л - е.

    Безпосередньо в силу визначення 2 це означає, що у - гарантований результат в грі Г і, отже, R (0 > у В силу довільності у звідси виходить потрібна оцінка. Лема доведена.

    Отримана оцінка є неулучшаемой. Щоб уникнути зайвих технічних деталей, доведемо це при деякому додатковому припущенні. А саме, будемо вважати, що гра Г 'така, що безліч

    {(Х, y) | 3 (u, v) і U х V: x = g (u, v), y = fu, v)} компактно.

    Зауважимо, що якщо в грі Г 'безлічі U і V наділені топологиями і компактні, а функції g і f неперервні на U x V, то і сама гра Г', і будь-яке її квазіінформаціонное розширення задовольняють сформульованим умові.

    Нехай число у є гарантованим результатом для будь-якої гри Г, що задовольняє умові р (Г, Г ') < е. Покажемо, що тоді у< R2ff (P).

    Отже, фіксуємо число у, що задовольняє сформульованим умові. Нехай Л (у) = {(u, v) і U xV: g (u, v) >у} і

    Л0 = max f (u, v)

    (U, v) їв (у)

    (Максимум досягається в силу зробленого припущення про гру Г '). Розглянемо гру Г = (U, V, g, h), в якій

    [Minif (u, v) -s, Л -s], якщо f (u, v)>Л -s, h (u, v) = 1

    [Max {f (u, v) + s, Л -s) в іншому випадку.

    Очевидно, тоді ДГ, Г ') < s. Тому у є гарантованим результатом в грі Г.

    Отже, знайдуться стратегія u і число Л, для яких виконується умова

    (10) [3w е V: h (u, w) > Л] & [Vv е V g (u, v) > у v h (u, v) < Л]. У цій формулі має бути Л < Л - s. Справді, якщо Л > Л0 - s, то h (u, w) > Л > Л0 - s, а тоді f (u, w) > Л0 і, в силу вибору числа Л0, маємо g (u, w) < у. Отже, умова g (u, w) > у v h (u, w) < Л невірно, що суперечить умові (10).

    Але тоді не обмежуючи спільності можна вважати, що Л = Л0 - s. Дійсно, при такому виборі Л перша частина умови (10) виконується в точці максимуму функції fin, v) на множині А (Г), а друга частина умови (10) виконується при цьому значенні Л, якщо вона виконується при якомусь значенні Л< Л ° - s.

    Але при такому виборі Л з умови (10) і способу побудови функції h слід, що

    [3w е V: f (u, w) > Л0] & [Vv е V g (u, v) > yv fu, v) < Л0 - 2s]. Отже, y< RZ? (R '), що й треба було довести.

    Ці результати отримані в найзагальнішому вигляді. Якщо гра наділена якоїсь додаткової структурою, то і результат може бути деталізований. Наприклад, якщо ми розглядаємо задачу обчислення максимального гарантованого результату в інформаційному розширенні Г * гри Г, то лема 5 в поєднанні з теоремою 7 або 8 дають «конечномерного» регулярізірующего-ющую оцінку для R (^). При традиційному підході відповідне завдання доводилося вирішувати окремо.

    Верхня регулярізірующего оцінка, мабуть, являє менший практичний інтерес. Але і вона може бути отримана аналогічно нижньою оцінкою.

    Нехай число R ** (T) - точна верхня грань чисел у, для яких існують такі стратегія u е U і число Л, що виконуються умови

    1 °. Існує стратегія w е V, для якої w) > Л;

    2 °. Для будь-якої стратегії V е V або g (u, v) > у яких h (u, v) < Л + к.

    справедлива

    Лемма 6. Якщо ДГ, Г ') < е, то Я * 2е (Г ') > ^ (Г).

    Доказ цієї леми мало відрізняється від докази леми 5.

    Змістовну інтерпретацію величини прийду-

    мати не вдається, але працювати з нею можна так само, як з величиною Rк (Г). Наприклад, для обчислення величини R * к (Г *) можна довести аналоги теорем 7 і 8, причому докази аналогів повторюють докази цих теорем практично дослівно.

    Оцінка леми 6 теж неулучшаема. Доказ цього факту в цілому слід доказу неулучшаемості нижньої оцінки, але в даному випадку зручно використовувати наступну конструкцію:

    Ця конструкція робить доказ навіть простіше. Але тут є один нюанс. Розглянуті гри можуть задовольняти деяким топологічним умов. Наприклад, безлічі U і V можуть бути наділені такими топологиями, що U та V компактні, а функції g і h безперервні на U х V. Або гра є інформаційним розширенням іншої гри, яка володіє таким топологічним властивістю. Конструкція формули (11), очевидно, порушує цю властивість. Тому якщо таке топологічний властивість випливає з природи модельованого конфлікту, доведеться повозитися з «згладжуванням» формули (11). Втім, ці деталі виходять за рамки даної статті.

    7. Висновок

    В даний час немає точного визначення терміна «теорія ієрархічних ігор». Але значна частина результатів, що традиційно відносяться до цієї галузі науки, має сліду-

    / (І, V) + е, якщо g (і, V) > у, / (і, V) - е в іншому випадку.

    ющий вид. Є гра Г і її інформаційне розширення Г #. Тим чи іншим способом задається поняття оптимального рішення гри Г #, а потім воно описується в термінах більш простої гри Г. Виникло розуміння того, що відповідну частину теорії можна розглядати як прикладної розділ числення предикатів. Щодо рішень типу рівноваги Неша це стало ясно досить давно [5]. Тепер стало зрозуміло, що те ж саме відноситься і до обчислення максимального гарантованого результату.

    Можливо, такий спосіб побудови теорії є кращим, ніж традиційний. І вже у всякому разі наявність двох способів буде корисно.

    література

    1. Бурков В.М. Основи математичної теорії активних систем. - М .: Наука, 1977. -255 с.

    2. Бурко В Н., НОВІКОВ Д А. Теорія активних систем: стан і перспективи. - М .: Синтег, 1999. - 128 с.

    3. Гермейера Ю.Б. Про іграх двох осіб з фіксованою послідовністю ходів // ДАН. - 1971. - Т. 198, №5. -З. 1001-1004.

    4. Гермейера Ю.Б. Ігри з непротилежними інтересами. - М .: Наука, 1976. - 327 с.

    5. ГОРЕЛИК В.А., ГОРЄЛОВ М.А., КОНОНЕНКО А.Ф. Аналіз конфліктних ситуацій в системах управління. - М .: Радио и связь, 1991. -288 с.

    6. ГОРЄЛОВ М.А. Максимальний гарантований результат при обмеженому обсязі переданої інформації // Автоматика і телемеханіка. - 2011. - №3. - С. 124-144.

    7. ГОРЄЛОВ М.А. Гра з помилками при передачі інформації // Автоматика і телемеханіка. - 2012. - №12. -З. 137-152.

    8. ГОРЄЛОВ М.А. Ігри з обміном недостовірною інформацією // Управління великими системами. - 2013. -Вип. 41. - С. 5-27.

    9. ГОРЄЛОВ М.А. Ігри з дорогими інформаційними обмінами // Управління великими системами. - 2014. -Вип. 49. - С. 37-56.

    10. ГОРЄЛОВ М.А. Ігри з випадковими помилками при передачі інформації // Автоматика і телемеханіка. - 2015. -№12. - С. 135-153.

    11. ГОРЄЛОВ М.А. Ієрархічні ігри з невизначеними факторами // Управління великими системами. - 2016. -Вип. 59. - С. 6-22.

    12. ГОРЄЛОВ М.А. Ієрархічна гра з навмисне спотворює інформацією // Автоматика і телемеханіка. - 2016. -№4. - С. 99-113.

    13. ГОРЄЛОВ М.А. Ієрархічні ігри з випадковими факторами // Управління великими системами. - 2016. -Вип. 63. - С. 87-105.

    14. ГОРЄЛОВ М.А. Про одну гіпотезу в підставах теорії ієрархічних ігор // Управління великими системами. -2010. - Вип. 28. - С. 5-23.

    15. BOLTON P., DEWATRIPONT M. Contract Theory. - Mass .: MIT Press, 2005. - 740 p.

    16. LAFFONT J.-J., MARTIMORT D. The Theory of Incentives: The Principal-Agent Model. - Princeton: Princeton University Press, 2002. - 440 pp.

    MAXIMAL GUARANTEED RESULT IN HIERARCHICAL GAMES

    Mikhail Gorelov, Computer Center of RAS, Moscow, Cand.Sc., (Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.).

    Abstract: A new method of investigation of hierarchical two-player games is discussed. This method consists of solving games with complex information exchanges using, for the most part, identical transformation of predicate calculus formulas. We introduce the notion of maximal guaranteed result in a game, give two definitions and discuss the relationship between them. The new method is illustrated on a classical example for which a maximal guaranteed result of a high level player in hierarchical game of two players is calculated. Some particular cases are discussed. Stability of this problem according to variation of the payoff function of the second player is analyzed. We also demonstrate how the definition, and, accordingly, the method are modfied for a benevolent or a bounded-rational second player. Also, we show that the new definiton is convenient for the investigation of stability of maximal guaranteed result calculation procedure with respect to the parameters of the game.

    Keywords: informational theory of hierarchical systems, hierarchical games, maximal guaranteed result.

    Стаття представлена ​​до публікації членом редакційної колегії А.Г. Чхартішвілі.

    Надійшла до редакції 13.11.2016.

    опублікована 31.05.2017.


    Ключові слова: ІНФОРМАЦІЙНА ТЕОРІЯ ІЄРАРХІЧНИХ СИСТЕМ /ІЄРАРХІЧНІ ІГРИ /МАКСИМАЛЬНИЙ гарантований РЕЗУЛЬТАТ /INFORMATIONAL THEORY OF HIERARCHICAL SYSTEMS /HIERARCHICAL GAMES /MAXIMAL GUARANTEED RESULT

    Завантажити оригінал статті:

    Завантажити