Что такое функции форм редуцированная расширенная классическая. Редуцированная форма кооперативной игры

Опред. Кооперат. игра с характеристической функцией u имеет (0,1)-редуцированную форму, если выполняются соотнош. : u(i) = 0 (i Î N), u(N) = 1. Теорема. Каждая существенная кооперат. игра стратег. эквивалентна одной и только одной игре в (0,1)-редуцированной форме. Сформулированная теорема показывает, что мы можем выбрать игру в (0,1)-редуцированной форме для представления любого класса эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме значение u(K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль, которую получают члены коалиции, образовав еѐ, а все дележи являются вероятностными векторами. В игре в (0,1)-редуцированной форме дележѐм является любой вектор x = (x1, ..., xn), для которого xi ³ 0 (i Î N) xi iÎN å = 1.

Свойства характеристической функции в 0,1-редуцированной коалиционной игре:

1. Всякая характеристическая функция является неотрицательной и неубывающей функцией.

2. Если K L, то v(K) + v(L/K) v(L)

3. Всякая характеристическая функция в игре из n игроков, I={1,2,…,n}, описывается 2n-1 числом параметров, а при приведении игры в 0,1-редуцированную форму накладывается n+1 дополнительных связей, и, следовательно, получается (2n - n - 2) свободных параметров.

16. Определение кооперативной игры (в форме характеристической функции). Основные свойства характеристической функции (супераддитивность, выпуклость). Игры существенные и несущественные.

Игра называется кооперативной, если до начала игры игроки образуют коалиции и принимают взаимообязывающие соглашения о своих стратегиях.

Предположим, что имеется множество игроков K – Некоторое подмножество , состоящее из игроков.

Число возможных коалиций игроков, договаривающихся о совместных действиях.

Определение 1. Функция V , ставящая в соответствии каждой коалиции K наибольший выигрыш, называется характеристической функцией игры.

Определение 2. Характеристическая функция V(K) называется простой, если она принимает два значения: 0 и 1.

Определение 3. Если характеристическая функция V простая, то коалиции K, для которых V(K) = 1 называются выигрывающими, а для которых V(K) = 0 – проигрывающими.

Свойства характеристической функции.

1) персональность (коалиция, не содержащая ни одного игрока, ничего не выигрывает).

2) супераддитивность

3) дополнительность

Обозначим через Xi выигрыш i-го игрока. И рассмотрим следующие два условия:

индивидуальная рациональность

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

Определение 4. Вектор выигрышей X = (X1, ¼, Xn), удовлетворяющий условиям 1 и 2, называется дележом в условиях характеристической функции V.

Определение 5. Множество {N, V}, удовлетворяющее условиям 1 и 2, называется классической кооперативной игрой.

Теорема 1. Для того чтобы X = (X1, ¼, Xn) был дележом в классической кооперативной игре, необходимо и достаточно, чтобы

Определение 6. Кооперативные игры называются существенными, если для любых коалиций K и L выполняется неравенство:

Если выполняется неравенство , то такая игра называется несущественной.

Рассмотрим следующие свойства:

для того, чтобы характеристическая функция V была аддитивной (кооперативная игра несущественной), необходимо и достаточно выполнения следующего равенства:

в несущественной игре имеется только один дележ:

в существенной игре более, чем одному игроку множество дележей бесконечно:

17. Определение и основные свойства дележа в кооперативной игре. Понятие доминирования дележей. Вектор называется дележом в игре , если выполняются условия

(коллективная рациональность);

xi≥v(i) для всех iÎN (индивидуальная рациональность).

В дальнейшем для краткости будем использовать следующее обозначение. Если x – дележ, а K – коалиция, то . В частности, x({i})=xi, x(N)=v(N).

Лемма. Множество дележей не пусто.

Доказательство. Определим вектор условиями x1=v(1),…,xn–1= v(n–1), . В силу свойства супераддитивности выполняется неравенство xn≥v(n), значит, этот вектор является дележом.

Лемма. В несущественной игре дележ единственный.

Доказательство. Если – дележ, то для всех iÎN выполняются неравенства xi≥v(i). Суммируя их, получим

(последнее равенство выполняется в силу несущественности игры). Значит, на самом деле все сложенные неравенства на самом деле являются равенствами, то есть единственный дележ – вектор (v(1),…,v(n)).

Дележ x доминирует дележ y по коалиции K, если выполняются условия

xi>yi для всех iÎN.

Если x доминирует дележ y по коалиции K, то будем писать .Лемма. Отношение доминирования по коалиции K обладает свойствами строгого порядкаДля любого дележа x не верно, что x y (антисимметричность);

Для любых дележей x,y,z из условий x y и y z следует отношение x z (транзитивность).

Доказательство. Лемма немедленно следует из того, что указанными свойствами обладает отношение «больше».

Лемма. Отношение x y не выполняется ни для каких дележей x и y.

Доказательство. Если x y, то xi>yi для любого iÎN. Суммируя эти равенства, получим
(равенства выполняются в силу определения дележа). Получено противоречие.

Лемма. Отношение x y не выполняется ни для какого игрока i и ни для каких дележей x и y.

Мне уже порядком надоело вставлять "расшифровку" редуцированные разговорные формы в параллельные тексты. Проще привести сам список.

Заодно даю и список общепринятых сокращений (для тех, кто уже подзабыл о их).

Слова, входящие в число наиболее часто встречающихся (по моим подсчетам) даны жирным шрифтом. Я имею в виду: yeah, gonna, gotta, wanna, alright, out(t)a. И, наоборот, - редко встречающиеся слова даны курсивом.

Редуцированные разговорные формы встречаемые в художественных произведениях.

ain’t = am not/ is not /are not/ have not/ has not - может означать одно из перечисленных отрицаний (в зависимости от смысла речи)

ain’tcha ["eIn"tʃə] = ain’t you

alright [ɔ:l"rait] = all right: a - удовлетворительный ; adv - удовлетворительно, приемлемо ; как междометие- ладно!, согласен!, идет!

betcha ["betʃə] you bet! = you betcha! = просто betcha! - конечно! не сомневайтесь! можете быть уверены! (я согласен, я хочу и т. п.);

2) betcha = bet you – спорим !

"bout [" baut] = about – о, относительно, насчет (здесь чаще как объект разговора, забот и т.п.); чаще всего в выражении How " bout …? Как насчет того, (чтобы)…?

bro " - сокращенная форма от brother типа pal , friend или buddy . Чаще братанами зовут друг друга американские негры

cantcha = can ’ tcha = can’t you

‘cause = because – потому что, так как

c’mon = come on – 1) давай!, живее!, пошли!; 2) брось!, перестань!, кончай!

coulda = could have – здесь could в сочетании с формой Perfect переводится как мог бы, могли бы и т.п.

(a) coupla ["kʌpl] = (a) couple of – пара

didja ["deja] = did you

dontcha = don’tcha = don’t you

dunno = don " t know – не знаю, не известно, не понятно ; в подавляющем больш. Случаев как I dunno. = I don"t know. Я не знаю .

d’ya = do you

Well what d"ya know ?

Ладно, что тебе известно/ ты знаешь?

’em = them – их, им; (встреч. суперчасто, обычно так и говорят в разг. речи)

fella ["felə] = просторечное от fellow - человек, парень, дружище, старина

g’by = good by – до свидания, прощай;

Фразовые глаголы с основой get в таком начертании обычно не встречаются, но произносятся по-американски именно так:

gerraway ["gɛrəwei] = get away – ускользнуть; уходить, уезжать; прочь! и др.

gerrin ["gəriŋ] = get in - входить; садиться в транспорт и др.

gerrit ["gerit] = get it – понимать; разузнать; победить; иметь и др.

gerron = get on - садиться на/в; приступать к / продолжать дело и др.

gerrup ["gærəp] = get up - подниматься; вставать (просыпаться); усиливаться; дорожать и др.

getcha или get"cha ["getʃə] = get you. По аналогии с gotcha (см. ниже), но относится к настоящему или будущему (в отличии от gotcha – к прошедшему). Встречается очень редко.

gimme ["gimi] = give me - дай(те)/ передай(те)/ отдай(те) и т. п. мне

g ’ night = good night - спокойной ночи;

gonna ["g(ə)nə] = going to . Употр. в обороте to be going to : (am / is / are + going + инфинитив с to ) собираться, намереваться сделать что-либо ; 1) Употребляется для выражения намерения совершить действие в будущем; 2) Для выражения большой вероятности или неизбежности совершения действий в будущем (прогнозируемое будущее). Чаще отдельно не переводится, а действие, выраженное последующим инфинитивом, просто переводится будущим временем.

gotcha ["gɔtʃə] = got you. В зависимости от контекста: 1) Я понял (тебя) . (уловил твою мысль) ;

2) Ага! Попался! (в буквальном или переносн. смысле, когда кто-либо хитрит);

3) доставить/ поместить кого-л. куда-либо, (встреч. редко)

gotta ["gɔtə] = (have) got to - должен, должна(…ны), нужно и т.п. (выражает долженствование, have часто совсем выпадает без потери смысла)

hadda ["hadə] = had to – выражает долженствование относительно прошлого

hafta = have to – выражает долженствование относительно настоящего и будущего

(a) helluva ["heləvə] = (a) hell of – как прилагательное: чертовский, ужасный, жуткий, адский, невыносимый, классный и т.п. (как в отрицат., так и в положит. смысле: восхищение и др.)

hellya = hell are you в вопросах типа What the hell are you…? Что , черт возьми , ты …?

"im = him - его

kinda = kind of: 1) если речь идет о каком-л. действии, процессе, ситуации и т.п., то: что-то/ нечто вроде, типа как, нечто похожее, как будто, словно и т.п.;

2) если речь идет о существительном, то переводится: сорта, класса, типа, вида и т.п.

lemme ["lemi] = let me позволь(те) мне, разреши(те) мне и т.п.

letcha = let you позволить/ дать/ разрешить тебе/ вам

let"s = let us. Сочетание сокр. глагольной конструкции let " s в значении "давайте " с инфинитивом имеет оттенок приглашения или совета.

lotsa ["lʌtsə] = lots of - полно, много, множество

(a) lotta = (a) lot of - полно , много , множество

’member ["membə] = remember - помнить

musta = must have - в сочетании с перфектным инфинитивом переводится как должно быть, вероятно, наверно и т.п.

’n’ = and – и или than - чем

naw = no – нет, не-а

nope = no – нет, не-а

O. K./ OK/ Ok/ ok = okay [əu"kei] - Ладно.; Хорошо.; Согласен.; Правильно.; Да.; Порядок.; Нормально.; Идет.; Есть!; Слушаюсь! и др.

oughta [ɔ:tə] = ought to – следует, следовало бы, надо бы ; (выражает долженствование; порицание; предположение)

outta /outa ["autə] = out of – из , от , с

" scuse = excuse – извинять . Обычно в варианте "Scuse me. Извините/ Простите меня.

seeya = see you увидимся!, пока!, всего! (при прощании)

shoulda ["judə] = should have, будущее в прошлом в форме Perfect, переводится как следовало бы, нужно бы и т.п.

shurrup = shut up – замолчи , заткнись . В таком написании встречается очень редко, но произносится по-американски так.

sonuvabitch/ sonovabitch/ sonofabitch/ sonofa-bitch/ sum-bitch и др. = son of a bitch – сукин сын, подонок, стервец и т.п.

sorta ["sɔ:tə] - sort of - вроде, как бы, типа как (дословно – вида, рода, типа, разновидности и т.п. чего-л.)

so’s = so as - также как (и), тоже

speaka = speak to – говорить с кем-л.

" spect = expect полагать, ожидать, надеяться ; или suspect предполагать, подозревать

" spose = suppose – полагать, допускать

talka = talk to – разговаривать/ беседовать с кем-л.

tellya = tell you – говорю / скажу тебе / вам

tha’s [ðiz] = that is - это есть …

usta = used to - иметь обыкновение: обычно, бывало, раньше обычно/ часто и т.п.

wanna [брит. "wɔnə, амер. "wʌnə] = want to – хотеть, желать что-либо сделать (want + инфинитив глагола); пример абсолютно логичного разговорного сокращения, иначе можно просто язык "сломать".

whaddaya = what do you … – что ты / вы …?

whatcha = what do/ did/ are you - что ты …? ; В вопросах типа What do you want? Что ты хочешь? , What are you doing? Что ты делаешь? Вспомогательный глагол are вообще редуцируется в подавляющем числе случаев в разговорной речи. Он не выбрасывается совсем, но на слух нам его почти не уловить.

whatta = в зависимости от смысла может означать: 1) what do/ are – в вопросах:

2) (реже) what a – в восклицаниях в значении какой, что за, что , например:

whattaya / whatta ya = what do you … – что ты / вы …?

willya = will you (обычно в просьбах и вопросах)

woulda ["wudə] = would have, будущее в прошлом в форме Perfect, переводится как бы

wuddaya = what do you … – что ты / вы …?

ya = you / your ты, вы/твой, ваш

ye = you – ты, вы (встречается очень редко)

yea = yes – да (встречается очень редко)

yeah = yes – да (так даже пишется очень часто, а говорится почти всегда; слово yes с "проглоченным" [s])

yep = yes – да (встречается гораздо реже, сродни "nope" – не-а)

yup = yes – да, ага (встречается очень редко)

Часто причастия настоящего времени (IV форма или – ing форма) пишутся с апострофом на конце вместо g, например: doin" = doing, livin" = living, tryin" = trying и т.д.

Общепринятые сокращения.

aren’t = are not

can’t = cannot

couldn’t ["kudnt] = could not

didn’t ["didn(ə)t] = did not

doesn’t ["dʌz(ə)nt] = does not

don’t = do not

hadn’t ["hædnt] = had not

haven’t = have not

hasn’t ["hæz(ə)nt] = has not

he’d = he had/ should / would

he’ll = he will

he’s = he is / has

here"s = here is / has

I’d = I had / should / would

I’ll = I shall / will

I’m = I am

I’ve = I have

isn’t = is not

it’ll ["it(ə)l] = it will

it’s = it is / has

let’s = let us

mayn’t = may not

mightn’t ["mait(ə)nt] = might not

mustn’t ["mʌs(ə)nt] = must not

shan’t [ʃa:nt] = shall not

she’d [ʃid] = she had / should / would

she’ll [ʃi:l] = she will

she’s [ʃiz] = she is / has

shouldn’t ["ʃudnt] = should not

that’ll [ðætl] = that will

that’s [ðæts] = that is

there’s [ðəz] = there is / has

they’d [ðeid] = they had / should / would

they’ll [ðeil] = they will

they’re ["ðeiə] = they are

they’ve ["ðeiv] = they have

wasn’t = was not

we’d = we had / should / would

we’ll = we shall / will

we’re = we are

weren’t = were not

we’ve = we have

what’s = what is

won’t = will not

wouldn’t ["wud(ə)nt] = would not

you’d = you had / should / would

you’ll = you will

you’re = you are

Кооперативная игра (IV,V) игра если в0-1, редуцированной форме, если V(i)=0 ; i=1,2,…,n; V(N)=1

Выигрыш отдельного игрока, если он играет один -0, а если коалицией то 1.

Каждая существенная игра эквивалентна одной и только одой игре в0-1 редуцированной форме.

Доказательство.

Дана игра (IV,V) будем искать игру эквивалентную данной (IV/V ”) ~(IV,V), которая к тому же является в игре 0-1 редуцированной форме. Составим уравнение:

V´(i)= KV(i) + C i =0 i=1,2,…,n условие эквивалентности

V´(N)=KV(N)+ =1 (n+1)

Всего записано n+1 уравнение

Сложим первые n уравнения

Полученное равенство вычтем из уравнения n+1. Получим:

Кооперативная игра существенная, то >0 (непонятное слово) обе части можно поделить на эту скобку

Зная K найдем неизвестные C i = - KV(i)=>

Найдем характеристическую функцию

Для следующей игры найти эквивалентную, которая представлена в 0-1 редуцированной форме. Найти: V’ V(S)-стадия задания характеристическая форма V’(S)- новая, требуется построить S-коалиция

Исходные данные:

V(1)=100 V(1,2)=300 V(1,2,3)= 550

V(2)=150 V(1,3)=350

V(3)=300 V(2,3)=420

V’ (1) = V’ (2) = V’ (3) =0 V’(1,2,3)=1

28. Доминирование дележей.

29. С-ядро кооперативной игры .

Естественно положить в основу анализа кооперативной игры принцип оптимального распределения максимального выигрыша u(S ) между сторонами .

Реализация этого принципа приводит к рассмотрению С-ядра − множество недоминируемых «вполне устойчивых» дележей кооперативной игры.

Вектор x = (x1 , ..., xn ), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции u.

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi выигрыш i- го игрока, то, во-первых, должно удовлетворяться условиеиндивидуальной рациональности

xi ³ u(i ), для i ÎN (1)

т. е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности

U(N ) (2)

т. е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N ), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем u(N ), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

Система {N , u}, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой .

Делёж x доминирует y , если существует такая коалиция S , для которой делёж x доминирует y . Это доминирование обозначается так: x > y.

Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y . Соотношение доминирования возможно не для всякой коалиции. Так невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

Любой дележ из С-ядра устойчив, в том смысле, что ни одна из коалиций не имеет ни желания, ни возможности изменить исход игры.

Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции S выполнялось неравенство .

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