Устройство поддержки принятия решений на основе кооперативных игр

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных устройствах вычислительной техники для определения наилучшей стратегии управления в условиях неопределенности. Технический результат заключается в увеличении быстродействия устройства, позволяющего на основе характеристической функции кооперативной игры находить ее решение в виде вектора Шепли быстрее, чем в эквивалентных программных реализациях. Требуемый технический результат достигается тем, что устройство, включающее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, дополнительно содержит два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала. 1 ил.

 

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

Известно устройство для моделирования процесса принятия решений (Патент РФ №2262131, опубл. 10.10.05 г.), содержащее две группы регистров, входы которых являются входами параметров устройства, блок умножения импульсов, четыре блока умножения, компаратор, генератор тактовых импульсов, блок суммирования, два блока вычитания, блок умножения на «0», счетчик, блок деления, интегратор и регистр.

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

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

Требуемый технический результат достигается тем, что устройство, содержащее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, дополнительно содержит два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала, причем входы группы регистров, первого и второго регистра, являются входами устройства, а выход третьего регистра является выходом устройства, при этом выходы первого регистра соединены с первым входом блока формирования очередной коалиции, а также с первым входом блока установления значения 1 в заданную позицию двоичного представления числа, выходы второго регистра соединены со вторым входом блока формирования очередной коалиции, входом блока уменьшения на «1» и входом первого блока вычисления факториала, выходы генератора тактовых импульсов соединены с входом блока умножения импульсов, счетным входом счетчика, вторым входом интегратора и вторым входом третьего регистра, выходы блока умножения импульсов соединены со вторыми входами первого и второго регистров, третьим входом блока формирования очередной коалиции, четвертым входом группы регистров, а также со вторым входом блока интегратора, выход переполнения счетчика соединен с входом останова генератора тактовых импульсов, выход значения счетчика соединен со вторым входом первого блока вычитания, а также с входом третьего блока вычисления факториала, выход блока уменьшения на «1» соединен с первым входом первого блока вычитания, выход первого блока вычисления факториала соединен со вторым входом блока деления, выходы блока формирования очередной коалиции соединены со вторым входом блока установки значения 1 в заданную позицию двоичного представления числа, а также с третьим адресным входом группы регистров, выход первого блока вычитания соединен с входом второго блока вычисления факториала, выход блока установки значения 1 в заданную позицию двоичного представления числа соединен со вторым адресным входом группы регистров, выход второго блока вычисления факториала соединен с первым входом первого блока умножения, выход третьего блока вычисления факториала соединен со вторым входом первого блока умножения, выход которого соединен с первым входом блока деления, первый и второй выходы группы регистров соединены соответственно с первым и вторым входом второго блока вычитания, выход которого соединен с первым входом первого интегратора, выход блока деления соединен со вторым входом второго блока умножения, выход блока интегратора подключен к первому входу второго блока умножения, выход которого соединен с первым входом интегратора, выход интегратора соединен с первым входом третьего регистра.

На чертеже представлена структурная схема устройства поддержки принятия решений на основе кооперативных игр.

Устройство поддержки принятия решений на основе кооперативных игр включает три регистра 1, 2 и 3, группу регистров 4, генератор тактовых импульсов 5, счетчик 6, блок умножения импульсов 7, два блока умножения 8 и 9, два блока вычитания 10 и 11, блок деления 12, блок интегратора 13, блок формирования очередной коалиции 14, блок установки значения 1 в заданную позицию двоичного представления числа 15, интегратор 16, блок уменьшения на «1» 17, три блока вычисления факториала 18, 19, 20.

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

Предполагается, что задана кооперативная игра (N, ν), где N={0,1, …, n-1} - множество игроков (конфликтующих лиц, принимающих решение), ν:2^N→R - характеристическая функция игры, определяющая для каждой коалиции K ее выигрыш ν(K). Имеются ограничения, накладываемые на характеристическую функцию:

1. Персональность. Пустая коалиция имеет нулевой выигрыш:

ν(⌀)=0.

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

$$\forall K,S\subseteq NK\cap S=\varnothing \Rightarrow \nu \left(K\cup S\right)>\nu \left(K\right)+\nu \left(S\right)$$ .

Выигрыш, получаемый игроком i∈N в результате совместно принимаемых решений, определяется соответствующей компонентной вектора Шепли φ[ν] по формуле:

$${\left(\phi [\nu ]\right)}_i={\displaystyle \sum _{k=\mathrm{0,}n-1}\frac{k!\left(n-1-k\right)!}{n!}}{\displaystyle \sum _{\begin{array}{l}K\subseteq N\backslash \left\{i\right\}\\ \left|K\right|=k\end{array}}\left(\nu \left(K\cup \left\{i\right\}\right)-\nu \left(K\right)\right)\left(1\right)}.$$

Вектор Шепли и является результатом работы устройства поддержки принятия решений на основе кооперативных игр.

Отметим ряд особенностей реализации данного алгоритма в виде устройства:

1. Характеристическая функция ν представляется в виде вектора вещественных значений, размера 2ⁿ по числу возможных коалиций.

2. Для представления произвольной коалиции K⊆N используется целое беззнаковое число достаточной длины, интерпретируемое в двоичной форме в виде вектора нулей и единиц размера n, причем i-я компонента равна единице тогда и только тогда, когда игрок i входит в коалицию - 1∈K.

3. Компоненты вектора характеристической функции v индексируются с помощью двоичных представлений всех возможных коалиций K⊆N, соответственно принимают в десятичном представлении все значения от 0 до 2ⁿ-1.

4. Под знаком внутренней суммы в формуле (1) перебор всех коалиций К⊆N\{i} таких, что |K|=k, осуществляется с помощью обычного комбинаторного принципа генерации всех сочетаний без повторений из n-1 элемента по k.

При запуске от внешнего источника, не показанного на чертеже, генератора тактовых импульсов 5, на входы устройства, выполненные в виде регистра 1, регистра 2 и группы регистров 4, по первому импульсу подаются соответственно значения номера вычисляемой компоненты вектора Шепли i, число игроков n и вектор значений характеристической функции ν. В начальном состоянии счетчик 6 имеет значение 0.

Импульсы генератора тактовых импульсов 5 передаются в блок умножения импульсов 7 и умножаются на значение мощности множества $$\left|\{K\right|K\subseteq N\backslash \left\{i\right\}\&\left|K\right|=k\left\}\right|=C_{n-1}^k$$ с учетом получаемого значения k от счетчика 6, и передаются с целью синхронизации к регистру 1, регистру 2, блоку формирования очередной коалиции 14 и блоку интегратора 13. Импульсы генератора тактовых импульсов 5 также передаются на входы счетчика 6, интегратора 16 и регистра 3.

Для каждого значения k счетчика 6 на входы блока формирования очередной коалиции 14 поступают значения i и n соответственно от регистра 1 и регистра 2. После чего данный блок формирования очередной коалиции 14 в виде двоичного беззнакового целого числа формирует очередную коалицию К⊆N\{i} такую, что |K|=k, и передает ее в блок установки значения 1 в заданную позицию двоичного представления числа 15 и в блок группы регистров 4.

Блок установки значения 1 в заданную позицию двоичного представления числа 15 также от регистра 1 на вход принимает значение i. Он устанавливает значение 1 в позицию i двоичного представления очередной коалиции K, тем самым вычисляя объединение K∪{i}.

Полученные коалиции K и K∪{i} передаются в качестве номеров (адресов) компонент вектора характеристической функции ν на входы группы регистров 4, в результате на входы блока вычитания 11 поступают соответственно значения ν(K∪{i}) и ν(K).

Полученная разность передается на вход блока интегратора 13, который за $${С}_{n-1}^k$$ шагов суммирования в результате перебора всех коалиций К для заданного k вычисляет величину:

$${\displaystyle \sum _{\begin{array}{l}K\subseteq N\backslash \left\{i\right\}\\ \left|K\right|=k\end{array}}\left(\nu \left(K\cup \left\{i\right\}\right)-\nu \left(K\right)\right)}$$ .

При каждом такте генератора тактовых импульсов 5 на вход блока уменьшения на «1» 17 передается от регистра 2 величина n, полученное значение n-1 поступает вместе с величиной k счетчика 6 на входы блока вычитания 10. Вычисленное значение n-1-k передается на вход блока вычисления факториала 19. Вместе со значением (n-1-k)! от блока 19 на вход блока умножения 8 передается величина k!, полученная с выхода блока вычисления факториала 20, который от счетчика 6 на вход принимает значение k.

Также при каждом такте генератора тактовых импульсов 5 на вход блока вычисления факториала 18 передается от регистра 2 значение n. Полученное значение n! и выходная величина блока умножения 8 передаются на входы блока деления 12, который вычисляет значение $$\frac{k!\left(n-1-k\right)!}{n!}.$$

На входы блока умножения 9 поступают значение блока интегратора 13, накопленное за $$C_{n-1}^k$$ шагов суммирования, результат работы блока деления 12. Полученное произведение передается в интегратор 16, который за n шагов вычисляет результирующую величину (φ[ν])_i и помещает ее в выходной регистр 3.

Работа устройства останавливается, когда величина k счетчика 6 примет все значения от 0 до n-1, после чего сигнал переполнения счетчика 6 подается на вход останова генератора тактовых импульсов 5.

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

Устройство поддержки принятия решений на основе кооперативных игр, включающее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, отличающееся тем, что оно содержит дополнительно два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала, причем входы группы регистров, первого и второго регистра, являются входами устройства, а выход третьего регистра является выходом устройства, при этом выходы первого регистра соединены с первым входом блока формирования очередной коалиции, а также с первым входом блока установления значения 1 в заданную позицию двоичного представления числа, выходы второго регистра соединены со вторым входом блока формирования очередной коалиции, входом блока уменьшения на «1» и входом первого блока вычисления факториала, выходы генератора тактовых импульсов соединены с входом блока умножения импульсов, счетным входом счетчика, вторым входом интегратора и вторым входом третьего регистра, выходы блока умножения импульсов соединены со вторыми входами первого и второго регистров, третьим входом блока формирования очередной коалиции, четвертым входом группы регистров, а также со вторым входом блока интегратора, выход переполнения счетчика соединен с входом останова генератора тактовых импульсов, выход значения счетчика соединен со вторым входом первого блока вычитания, а также с входом третьего блока вычисления факториала, выход блока уменьшения на «1» соединен с первым входом первого блока вычитания, выход первого блока вычисления факториала соединен со вторым входом блока деления, выходы блока формирования очередной коалиции соединены со вторым входом блока установки значения 1 в заданную позицию двоичного представления числа, а также с третьим адресным входом группы регистров, выход первого блока вычитания соединен с входом второго блока вычисления факториала, выход блока установки значения 1 в заданную позицию двоичного представления числа соединен со вторым адресным входом группы регистров, выход второго блока вычисления факториала соединен с первым входом первого блока умножения, выход третьего блока вычисления факториала соединен со вторым входом первого блока умножения, выход которого соединен с первым входом блока деления, первый и второй выходы группы регистров соединены соответственно с первым и вторым входом второго блока вычитания, выход которого соединен с первым входом первого интегратора, выход блока деления соединен со вторым входом второго блока умножения, выход блока интегратора подключен к первому входу второго блока умножения, выход которого соединен с первым входом интегратора, выход интегратора соединен с первым входом третьего регистра.