Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 22

Имеем  t₁-1³t₂-1 Û t₁³t₂ ,   t₁-1³3-t₁-t₂ Û t₂³4-2t₁    и   t₂-1³3-t₁-t₂  Û t₁³4-2t₂ .

min l̃(t) = min {¹/₃,¹/₃,¹/₃} = 0,

N-ядро: argmin l̃(t) = (⁴/₃, ⁴/₃, ¹/₃).

Можно решать задачу проще, т.к. точка пересечения n плоскостей в Âⁿ есть точка минимума их верхней огибающей. У нас осталось 3 плоскости. Их пересечение t= (⁴/₃,⁴/₃,¹/₃).ÎE(u). N-ядро совпало с вектором Шепли:

j₁(u) = j₂(u) = (1-0)/(1*C₃¹)+(3-1)/(2*C₃²) +(2-0)/(2*C₃²) +(3-2)/(3*C₃³)= ⁴/₃,

j₃(u) =       0/(1*C₃¹)+(2-1)/(2*C₃²) +(2-1)/(2*C₃²) +(3-3)/(3*C₃³)= ¹/₃

Th. В игре с постоянной суммой для 3-х игроков N-ядро всегда совпадает с вектором Шепли?

Пример К2. На выборах 4 партии набрали 48, 32, 16 и 4 % голосов соответственно.

Как им разделить министерские портфели? Дележ: t₁+t₂+t₃+t₄=1, t_i≥0

max _S l(S,t)= max{t₁, t₂+t₃, t₂+t₄, t₃+t₄}→ min_t

Исключим t₁ и, используя симметрию по t₂,t₃,t₄ и выпуклость целевой функции, положим t₂=t₃=t₄=t.

max{1-3t, 2t}→ min Þ 1-3t = 2t Þ t = ¹/₅.

N-ядро = ( ²/₅, ¹/₅, ¹/₅, ¹/₅) не совпадает с вектором Шепли = ( ¹/₂, ¹/₆, ¹/₆, ¹/₆).

Сведение к ЛП: min υ при ограничениях дележа и t₁ ≤ υ, t₂+t₃ ≤ υ, t₂+t₄ ≤ υ, t₃+t₄ ≤ υ.

3. СЕТЕВЫЕ МОДЕЛИ.

Граф G– это пара (V, E), где V- конечное множество помеченных вершин, а E Ì V ´ V - множество ребер. Если ребра ( v₁, v₂) и ( v₂, v₁) различают, то граф называют ориентированным (или орграфом), а его ребра ‑ дугами. Граф полный, если все пары вершины соединены ребрами (число ребер ); граф планарный, если его можно нарисовать на плоскости без пересечения ребер (число ребер планарного графа по теореме Эйлера не превосходит 3∙(n-1)).

3.1. СПОСОБЫ ЗАДАНИЯ ГРАФОВ.

Графический: вершины изображаются точками, а ребра – линиями между ними.

Матричный: n = | V |, m = | E |.

Матрица смежности – лучший способ задания графов, близких к полным. Если граф планарен, то в каждой строке матрицы стоит в среднем ≈6 единиц. Выгоднее указать список всех ребер или список подсписков смежных вершин = {(номер вершины, {номера смежных вершин})},затрачивая log ₂ n бит на номер.

Ex: n = 1000. Матрица смежности занимает 1000 ´ 1000 = 1000000 бит, список ребер ‑ 3 ´ 1000 ´ 20 = 60000 бит (10 бит на номер, 20 на ребро).

Т.к. граф определяется своей матрицей смежности, то существует 2^n ´ n различных графов (= матриц смежности = наборов из n² нулей и единиц)!!!

Граф называется графом без петель, если в нем нет ребер вида ( v_i, v_i), т.е. на диагонали матрицы стоят нули. Число таких графов равно 2^n (n-1). Число неориентированных графов без петель равно ^n (n-1) (матрица симметрична).