Достаточные условия неманипулируемости прямых механизмов планирования

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Достаточные условия неманипулируемости прямых
механизмов планирования
Петраков С. Н.
(Институт проблем управления РАН- Москва) *
1. Введение
т
В теории активных систем (ТАС) рассматривается задача назначения планов в активной системе (АС), состоящей из управляющего органа-центра и п активных элементов (АЭ). Планы, назначаемые АЭ, зависят от предпочтений элементов, определяемых неизвестными центру параметрами. Возникающую неопределенность центр устраняет тем, что запрашивает информацию о предпочтениях элементов, по которой в соответствии с некоторой процедурой планирования назначаются планы [1 j
В общем случае сообщения АЭ могут иметь достаточно сложный вид Мы будем считать, что элементы сообщают непосредственно параметры своих функций
*
предпочтения или их оценки. При этом элементы называют сообщения из некоторого заранее оговоренного множества возможных сообщений Совокупность множества возможных сообщений и процедуры планирования называется механизмом планирования. Механизмы, в которых элементы сообщают непосредственно параметры своих функций, предпочтения называются прямыми механизмами В прямых механизмах иногда возникают условия, когда элементам выгодно сообщать недостоверную информацию. Механизмы, в которых элементам выгодно сообщение достоверной информации, называются неманипулируемыми, и естественным желанием ценгра является создание неманипулируемых механизмов.
Возникает необходимость поиска достаточных условий неманипулируемости прямых механизмов. Такие условия для механизмов голосования были получены Moulin [2J, Border и Jordan (3) В механизмах голосования полезноегь АЭ определяется однопиковыми функциями, а АЭ выбирают единственную скалярную альтернативу, что в принятой постановке значит, что всем АЭ назначаются одинаковые планы В
работе [2] допустимые функции полезности принадлежат классу одноплатных функций 6 работе [3] были получены достаточные условия неманипулируемости механизмов голосования, коїда выбираемая альтернатива является вектором, а функции полезности АЭ однопиковые
Неманипулируемость прямых механизмов в задаче назначения планов исслс довалась в И], где условия неманипулируемости формулировались в виде требований на монотонность процедуры планирования Как оказалось, довольно широкий класс
неманипулируемых прямых механизмов определяет на /?& quot- структуру & quot-множеств диктаторства", исследованию свойств которой и посвящена настоящая работа
2. Неманипулируемость прямых механизмов
Обозначим /~~ п} -множество всех АЭ, х^Их-план /-го А Э Будем считать, ЧТО функции полезности элементов & lt-р,{хіу Г і) являются однопиковыми [ 1 ] с точкой пика г,& amp-Н Набор точек пика всех элементов образует вектор точек пиков
Пусть элементы посылают в центр сообщения. ?,€$ План /-го элемента
Обозначим вектор планов через х, хя) е. Механизм будет определяться множеством 6'- и процедурой g: S -& gt- Я& quot-
Вектор сообщений. V* называется равновесием Нэша, если У/е/, fsieS, выполнено
и равновесием в доминантных стратегиях, если Vs^єSl V 5., б выполнено
п
определяется процедурой планирования gl{s), где
& lt-Р, (#,).) а & lt-Р. (#, (*,. •"'.), г,),
Ъ (Я, (*,'- & gt- К)& gt- гг) * & lt-Рг (8, (& gt- 5., 1 О
В прямом механизме каждый АЭ сообщает только свою точку пика г (еЛ поэтому Л, Я1 и механизм будег отображением $ Я& quot- * И*. Прямой механизм
называется неманипулируемым, если для любых идеальных точек АЭ сообщение достоверной информации является равновесием Нэша
Рассмотрим прямой механизм g R" -* R*. Пусть для некоторого сообщения
ге/f" выбирается вектор планов x^g{r) Так как полезность каждого АЭ определяется однопиковой функцией полезности, то каждый АЭ может находиться в одном и только одном из трех возможных состояний: (а) либо g,®& gt-rt и тогда АЭ будет полу чать план, строго больший желаемого, (б) либо gir)-rt и АЭ будет назначаться оптимальный для него план, (в) либо g,{r)& lt-rt и план будет недостаточным Введем индекс состояния /-го АЭ р", принимающий значения из набора {а, с, т}=р, где, а соответствует состоянию (а), с-состоянию (б), а /я-{в). (Символы индекса являются первыми буквами слов manque-нехватка, contentement-удовлетворенность, abondance-избыток) Вектор индексов состояния всех АЭ обозначим через ре рп.
Введем функции М: pn~y2It С: рп-& gt-2?, А: рп->-2!, значениями которых для каждого вектора состояний ре рп будет подмножество АЭ из /, таких что индексы состояния этих элементов равны, соответственно, т, с и а: М (р)=(/е/: pj=m}, С (р)={/е/: р,~с},
9
Л (р)={/е/: рга}, рер'-.
%
Определение 2.1. Разбиением В пространства Rn назовем совокупность множеств D^c/T, таких, что
?& gt-р-{геД"-: g{r)& lt-rit при /еМ (р), g{r)=r (, при /еС (р), g{r)& gt-rh при /еЛ (р)}, ре р Сокращенно неравенства g{r)& lt-ru при /еА/(р) будем записывать gM{p)®& lt-rM (ph, а неравенства g? r)& gt-rh при /еЛ (р) как gA^®& gt-rA (p).
Далее будем предполагать, что в каждом из множеств Dp разбиения В планы, назначаемые всем АЭ, зависят только от сообщений удовлетворенных элементов С (р), то есть выполнено предположение
А. 2.1. Vpe рп Зх^год): R^C (p)^-& gt-Rn и VreDp выполнено g® — х?(гС (р)).
Определение 2.2. Определим совокупность В0 множеств
?$={геЛ& quot-: Гщру& gt-Хщр)(гС (р)), Гс{р) = Proj гЛ{р)& lt-хрА{р)(гс (/3))}, ре рп.
Свойства множеств из ВР иллюстрируются следующей леммой.
Лемма 2.1. Пусть re, тогда: a) V/eA/(p) {(rifr4) е D°p} о {/- & gt- xf (rc{p))}, (1)
9
б) У/еЛ (/& gt-) {(л, Г,) е /& gt-«(<->- I'-- & lt-х?(гГЛр))) (2)
Доказательство. Пусть г1 & gt- х? (лг (& gt--) Тогда по определению
4
/& gt-"- = {г е/Г: ГС (Й) е. Ркусч& gt-() ир,
ГМур & gt- ХМ[рАГС (р& gt-)>-
ГЛ (р) & lt- хл& lt-р)(гсш)) —
(3)
(4)
(5)
Так как геО^то- ГодеРго^^р. Обозначим г-(г, г,). Так как /еМ (р), то ГС (Р) = ^(р) • и (3). (5) выполнены Из г, = г, следует, что
Гшрмч & gt- хм (р& gt-чф (?о»)>- а так как П & gt- х& gt- & lt-Гс (?))>- то Гщр^Хщр^пр)) Поэтому справедливо (4) и доопределению 1) р получаем (1).
Обратно, предположение, что при некотором /- & lt- х/(гС (4)) верно (/-,/ ,) е /)^,
входит в противоречие с определением О0р.
Аналогично доказывается, что имеет место второе утверждение леммы Под записью будем подразумевать, что V/? е рп, Ор — Ор.
Теорема 2.1. Если для прямого механизма -& gt-/?", удовлетворяющего, А 2. 1, выполнено /?=В°, то он неманипулируем.
Доказательство: Рассмотрим произвольный ге/Г и докажем, что V/ е/, V/- р,(& amp-(г), г.)& gt-р, (#,(/-, г,), /-).
Допустим, что существуют элемент /е/ И Г. € Я? такие, что
& lt-р№Аг ъ)& lt-<-р№№>- г. ,)>- г,) —
(6)
Гак как В — разбиение, то существует единственный вектор р^рп, такой, что геВр. Возможны три случая: / может принадлежать либо А/(р), либо С (р либо А (р). Рассмотрим последовательно три этих случая.
1) Пусть / еС& lt-«, тогда V?, еЯ1, г{) = & lt-р,{гп г () * & lt-р^,{г, г,), г,), так как г,
единственный максимум (х, г,) по х,.
2) Если 1 €М (р), то из определения Ор и А. 2 1, П & gt- g,® ~ х?(гС (р)). Так как = /)р, то по лемме 2 1 для любого ^ & gt- ж/*(гС (/7)), Г = (г, г ,) е /), ~ и
Если г] & lt-, х- (гС (р)), то *Ор — Ор и существует единственный вектор
р €- р» такой, что г е О- Если верно (6), то из того, что & lt-р,{хи г,) строго возрастает по х, при Х: <-г, следует, что при сообщении г) /~ый АЭ должен получать
Поэтому (гС{?}) & gt- х?(гС (р))у х?(гГ (Э)) & gt- г, и i & amp-А (р)
•"
В силу того, что X? (гС{?)) & gt- х* (гС{р)), существует г (еЯ1 такой, что
Х? & lt-%&-)) & gt- t & gt- х, р (ГС (Р& gt-) ¦ Обозначим г = (r{? г () = (г, г 4) Из xf {rC (P)) & gt- rt и леммы 2 1
ВИДНО
, что г € D2. Аналогично г е D°a и г е /)" П /Й, Но гак как то
О" п о- - 0. Получили противоречие и (6) не выполнено.
*) Случай, когда / е А (р), рассматривается аналогично случаю 2)
3. Заключение
Таким образом, получено достаточное условие неманипулируемости прямых
9
механизмов в терминах геометрических свойств множеств параметров функций предпочтения, которое является удобным инструментом исследования свойств механизмов планирования: манипулируемости, эффективности и др.
Литература-
/// Бурков В. Н., Новиков Д. А. Введение в теорию активных систем. М.: ИЛУ РАН,
1996.
Condorcet
Preferences //Social Choice and Welfare. 1984. P. 127−147.
[3] Border K. S., Jordan J. S. Straightforward Elections, Unanimity and Phantom Voters // Review of Economic Studies. 1983. P. 153−170.
[4] Новиков Д. А. Оптимальность правильных механизмов управления активными системами. I //Автоматика и телемеханика. 1997. № 2. С. 154−161,

ПоказатьСвернуть
Заполнить форму текущей работой