Оценка сложности проверки гипотезы о временном диктаторе с положительно-однородной функцией полезности

Результаты численных экспериментов, представленные в [7–10], показывают, что на практике торговые статистики даже для большого числа товаров могут оказаться нераци-онализируемыми в классе положительно-однородных функций. Чтобы иметь возможность говорить о степени нерационализируемости торговой статистики, в работах [6, 11–19] были предложены различные количественные показатели, характеризующие степень нарушения условий рационализируемости.

Рационализируемость торговой статистики может нарушаться из-за ошибок в исходных данных. В этом случае для построения индексов Конюса–Дивизиа следует использовать обобщённый непараметрический метод (см. [16]).

Другой причиной нарушения условий может служить неоднородность общества. Если общество состоит из нескольких социальных классов, то их совокупное поведение может не описываться моделью одного репрезентативного потребителя. В этом случае следует строить не один, а несколько индексов, соответствующих отдельным социальным классам. Поскольку априорно количество социальных классов неизвестно, а индексы строятся для агрегированного описания изменений в экономике, возникает задача о поиске минимального числа социальных классов, торговые статистики которых рационализируемы в классе положительно-однородных функций. Связь минимального числа социальных классов с классом дифференциальной формы обратных функций спроса была исследована в [20].

В работе [21] была исследована бюджетная статистика ¹ домашних хозяйств Великобритании. Совокупная торговая статистика оказалась нерационализируемой в классе положительно-однородных функций полезности. Однако удалось выделить два социальных класса, торговые статистики которых рационализируемы в классе положительнооднородных функций полезности.

Бюджетная статистика доступна не всегда, поэтому актуальной является задача о построении минимального количества социальных классов с рационализируемыми торговыми статистиками по торговой статистике всего общества. Разработкой непараметрических критериев согласованности торговой статистики с моделью нескольких репрезентативных потребителей занимались в работах [22–24]. В отличие от модели с одним репрезентативным потребителем, предложенные в этих работах алгоритмы имеют экспоненциальную сложность. В работе [25] доказывается NP-полнота задачи проверки согласованности торговой статистики с моделью двух репрезентативных потребителей.

Частным случаем модели с двумя репрезентативными потребителями является модель временного диктатора (см. [22]), согласно которой в каждый момент времени только один из социальных классов принимает решение о совокупном потреблении. В неопубликованной работе Р. Деба ² доказывается NP-полнота задачи о проверке согласованности торговой статистики с моделью временного диктатора для двух и более диктаторов.

Все вышеупомянутые работы по разработке критериев согласованности торговой статистики с моделью нескольких репрезентативных потребителей не накладывают требования положительной однородности функций полезности. Результаты численных экспериментов, представленные в работе [26], показывают, что торговые статистики наугад выбранных товарных групп с высокой вероятностью рационализируемы не положительно-однородными функциями полезности. С другой стороны, вероятность рационализируемости торговой статистики наугад выбранной товарной группы в классе положительно-однородных функций оказывается низкой. Эти результаты показывают, что выявление содержательных и интересных для анализа товарных групп невозможно без требования положительной однородности функций полезности.

В данной работе рассматривается модель временного диктатора с положительнооднородными функциями полезности. Доказывается NP-полнота задачи проверки согласованности торговой статистики с такой моделью для двух и более диктаторов.

• 2.    Основные определения и теоремы

Обозначим через R ™ множество т-мерных векторов с неотрицательными элементами, а множество ттг-мерных векторов с положительными элементами через R ^ ₊ . Скалярное произведение двух векторов X и Y будем обозначать через ( X, Y } .

Определение 1. Торговой статистикой товарной группы из т товаров называется конечный набор {( Р * , X * ) } *=i векторов цен Р * G R ™ ₊ и объёмов потребления X * G R ™ \{ 0 }.

Определение 2. Говорят, что функция F рационализирует торговую статистику { (Р * , X * ) } *=i , если для любого t G { 1,..., Т }

F ( X ) 6 F ( X * ) V X G R ^ \ { 0 } : ( Р * , X ) 6 ( Р * , X * ) .

Обозначим множество всех непрерывных, ненасыщаемых ³ , монотонных, вогнутых, положительно-однородных функций через Ф ^ .

Определение 3. Торговая статистика {( Р * , X * ) } ^т =1 рационализируема в классе функций из Ф ^ , если существует функция F G Ф ^ , рационализирующая эту торговую статистику.

Определение 4. Торговая статистика {( Р * ,X * ) } *=1 согласуется с моделью временного диктатора с К диктаторами с положительно-однородными функциями полезности, если существуют функции F i , F 2 ,..., F k из множества Ф ^ , такие что для каждого t G { 1, ... ,Т } существует k G { 1,..., К }, такое что

F k ( X ) 6 F _k ( X * ) V X * G R ^ \ { 0 } : ( Р *, X } 6 ( Р * X *Y

Определение 5. Торговая статистика {( Р * ,X * ) } *=i удовлетворяет однородной сильной аксиоме выявленного предпочтения, если для любого k >  1 , для любых индексов t i ,t 2 ,... ,t _k из { 1, ... ,Т } выполнено

( Р * 1 , X * 2 )( Р * 2 , X * 3 ) ... ( Р * ^к ,X * 1 } > ( Р * 1 , X * 1 )( Р * 2 , X * 2 ) ... ( Р * ^к ,X * ^к ) .

Проверить, удовлетворяет ли торговая статистика однородной сильной аксиоме, можно за полиномиальное время с помощью алгоритма Варшалла–Флойда [4, 5].

Теорема 1 (Африата–Вериана, [11, 16]). Следующие свойства торговой статистики эквивалентны:

• 1)    торговая статистика {( Р * ,X * ) } *=i рационализируема в классе функций из Ф ^ ;

• 2)    торговая статистика {( Р * ,X * ) } *=i удовлетворяет однородной сильной аксиоме;

• 3)    существует решение (A i , ..., Х т ) >  0 системы линейных неравенств

Х _Т ( Р^т,X * ) > Х * ( Р * X *1 t,T = 1,...,Т;                    (1)

• 4)    функция вида

• 3.    Доказательство основного результата

F(X) = тіп{Х*(Р*, X) | t G {1,..., Т}}, где Ai > 0,... ,Хт > 0 удовлетворяют (1), рационализирует торговую статистику {(Р *,X *)}Т=1.

Из теоремы Африата-Вериана следует, что торговая статистика {( Р ¹ ,X ^t )} ^T ₌i согласуется с моделью временного диктатора с К диктаторами с положительно-однородными функциями полезности тогда и только тогда, когда множество { 1,... ,Т } можно разбить на К непересекающихся подмножеств T i ,..., Т к , таких что торговые статистики

{(Р t,X t)}tGTi,..., {(Р \X удовлетворяют однородной сильной аксиоме выявленного предпочтения.

Сформулируем основной результат статьи.

Предложение 1. Задача проверки согласованности торговой статистики {( Р ^t ,X ^t ) } t=i с моделью временного диктатора с К диктаторами с положительнооднородными функциями полезности при К >  2 является NP-полной.

Доказательство предложения 1 приводится в следующем разделе.

Рассмотрим три задачи.

Задача DAP(K) . Заданы ориентированный граф G = (V, Е ) размера Т и натуральное число К >  2. Требуется определить, существует ли разбиение множества V на s 6 К непересекающихся множеств V 1 ,..., V _s , такое что для любого j ( j = 1, s) подграф G j = ( V j ,E j ), порождённый вершинами из Vj , не содержит циклов.

Задача WAP(K) . Заданы взвешенный граф G = (V, Е ) размера Т с матрицей весов W Е R ^{T хТ} , причём w _tt = 0 для всех t ( t = 1 ,Т ), и натуральное число К >  2. Требуется определить, существует ли разбиение множества V на s 6 К непересекающихся множеств V 1 ,..., V _s , такое что для любого j ( j = 1, s) подграф G j = ( V j , E j ), порождённый вершинами из V j , не содержит циклов отрицательной длины.

Задача HARP(K) . Заданы торговая статистика {( Р ^t ,X ^t )} ^T ₌i и натуральное число К >  2. Требуется определить, существует ли разбиение множества { 1,...,Т } на s 6 К непересекающихся множеств T i ,..., T _s , такое что для любого j ( j = 1, s) торговая статистика {( Р ^t ,X ^t ) } _tG7 ^ удовлетворяет однородной сильной аксиоме выявленного предпочтения.

Задача DAP(К) называется задачей ациклического разбиения ориентированного графа.

Очевидно, что задача HARP(К) принадлежит классу NP, поскольку её можно решить, перебирая всевозможные разбиения и проверяя правильность каждого, а проверить правильность одного разбиения можно за полиномиальное время с помощью алгоритма Варшалла–Флойда.

Доказательство основного результата строится следующем образом. Мы сводим задачу DAP(К) к задаче WAP(К), тем самым доказывая NP-полноту задачи WAP(К), а затем сводим задачу WAP(К) к задаче HARP(К).

NP-полнота задачи DAP(К) для К >  2 утверждается в [27] (стр. 193), однако доказательство не приводится. Доказательство NP-полноты задачи DAP(2) можно найти, например, в [28]. Нам не удалось найти доказательства NP-полноты задачи DAP(K) для К >  3, поэтому мы приводим это доказательство в данной статье.

Предложение 2. Задача DAP( К ) для К >  3 является NP-полной.

Доказательство. Рассмотрим задачу раскраски графа к К цветов.

COL(K) . Заданы граф G ( V,E ), натуральное число К >  3. Требуется определить, существует ли правильная вершинная раскраска графа G в К цветов.

NP-полнота задачи COL(К) для К >  3 доказана в [29].

Задача DAP(К) принадлежит классу NP, поскольку она может быть решена перебором всевозможных разбиений множества V на К непересекающихся подмножеств, а проверка ацикличности графов, порождённых заданным разбиением множества вершин, может быть выполнена за полиномиальное время.

Сведём задачу COL(К) к задаче DAP(К) для К >  3.

Пусть есть граф G ( V, Е ), натуральное число К >  3. Построим ориентированный граф G следующим образом. Рассмотрим множество вершин

V c = { c i , . . . , С К } .

Эти вершины соответствуют цветам раскраски графа. Зададим множество рёбер, соединяющих вершины из V _c друг с другом следующим образом:

^Е с = ^{{( c} i ^,c j ^)} | г,] = 1 ^,К,г = ^{j }} .

Таким образом, граф (V C ,E _C ) является полным.

Каждая вершина c j Е V C соединяется со всеми вершинами из множества V. Обозначим множество соответствующих рёбер через E j :

^E j = ^{{( c} j ^{,и ) 1 V eV }} .

Каждому ребру в графе G соответствует пара рёбер в графе G:

^Е ‘ = ^и {_и<У}е Е ^{( n, у ) , ( и, п ^)} .

Граф G задаётся следующим образом:

V = V и V c ,

Е = Е U E c U Е ‘ U ( и К ₌₁Ез ) ,

G = (V ,2?).

Пусть функция f : V -4 { 1,..., К } задаёт правильную раскраску графа G. Тогда множества

Vj = {cji U {v EV 1 f(и) = ji задают разбиение множества вершин V, такое что графы

G j = (V ,Е), порождённые вершинами из Vj, не содержат циклов. Действительно, циклов, не содержащих cj, быть не может, поскольку f задаёт правильную вершинную раскраску. Циклов, содержащих cj, быть не может, поскольку в Е нет рёбер вида (и, cj) для и Е V.

Пусть непересекающиеся множества V i ,..., V _s , (s 6 К ) задают разбиение множества V, такое что графы

G j = (Vj ,Ез), порождённые вершинами из Vj, не содержат циклов.

Каждая из вершин множества V c должна быть хотя бы в одном из множеств V i ,... , V _s . Ни одно из множеств V i ,... ,V _S не может содержать двух вершин из множества V c , поскольку в противном случае эти две вершины образовывали бы цикл. Поэтому s = К и можно считать, что

V j n V c = { c j } .

Зададим функцию f : V 4 { 1,..., К } следующим образом:

^{f (v)} = ^{j : V eV} 3 .

Поскольку в V j нет циклов, среди вершин из V n V нет вершин, соединённых ребром из Е. Поэтому f задаёт правильную вершинную раскраску графа G.

Предложение доказано.

Предложение 3. Задача WAP( K ) для К >  2 является NP-полной.

Доказательство. Задача WAP(K) для К >  2 принадлежит классу NP, поскольку она может быть решена перебором всевозможных разбиений множества V на К непере-секающихся подмножеств, а проверка отсутствия циклов отрицательной длины в графах, порождённых заданным разбиением множества вершин, может быть выполнена за полиномиальное время с помощью алгоритма Варшалла–Флойда.

Сведём задачу DAP(K) к задаче WAP(K). Пусть есть ориентированный граф G = (V, E ) размера Т с матрицей инцидентности А Е { 0,1 } ^{Т хТ} . Для сведения задачи DAP(K) к задаче WAP(K) достаточно построить взвешенный граф Н = ( V,E ), такой что в этом графе есть цикл отрицательной длины, начинающийся и заканчивающийся в вершине v Е V тогда и только тогда, когда в графе G есть цикл, начинающийся и заканчивающийся в вершине v. При доказательстве достаточно ограничиться циклами без повторяющихся вершин.

Определим матрицу весов W = (w _tT ) ^Т _т=1 следующим образом:

^ tT =

Т + 1, 0 , ^{-1 ,}

если ( v _t ,v _T ) Е Е, если t = т , если ( v _t ,v _T ) Е Е.

Пусть в графе G есть цикл

^{( v} t 1 ^,v t 2 ,. . .^,v t _k ^,v t 1 ).

Это означает, что

^{( v} t i , ^v t 2 ) ^{Е E}, ^{( v} t 2 , ^v t 3 ) ^{Е E}, . . . , ^{( v} t k - 1 , ^v t k ) ^{Е E}, ^{( v} t _k , ^v t i ) ^{Е E.}

Следовательно,

^ t i t 2        1, ^ 4 ₂ І ₃        1, . . . , ^ t _k — i t _k        1, ^ t k t i        1,

и

^ t 1 t ₂ ⁺ ^ t ₂ t ₃ ⁺ ... ^{+ w} t _k-1 t _k ⁺ ^ t _k t 1 = ^— к <  0.

Таким образом,

^{( v} t i ^,v t 2 ,. . . ^,V t k ^,V t i )

является циклом отрицательной длины в графе Н .

Пусть в графе Н есть цикл

^{( v} t 1 ^,v t 2 ,. . . ^,V t k ^,V t 1 ) отрицательной длины, т.е.

^ t 1 1 2 ⁺ ^ t 2 t 3 ⁺ . . . ⁺ W t k — i t k ⁺ ^ t k t l <  0.                               ⁽²⁾

Если последовательность вершин

^{( v} t 1 ^,v t 2 ,. . . ^,V t k ^,V t 1 )

не образует цикла в графе G, то один из весов

W1t2 , ^t213 ,..., Wtk — itk , Wtk ti равен Т +1. Поскольку мы рассматриваем только циклы без повторяющихся вершин, к 6 Т. Поэтому сумма в (2) не может быть отрицательной. Полученное противоречие доказывает, что последовательность вершин

^{( u} t i ,V t 2 , . . .,V t _k ^,U t i )

образует цикл в графе G .

Предложение доказано.

Доказательство предложения 1. Сведём задачу WAP(K) к задаче HARP(K). Проверка однородной сильной аксиомы для торговой статистики {( Р ^t , X ^t )} ^T ₌i равносильна проверкам неравенств

* (SS) +'- (РРЖ)

+ ... + log

(

( p t k - 1 ,X t k

p > t k - i ,X ^{tk- 1}

) -- ( ір psd

> 0

для всех последовательностей различных индексов {t i , t ? ,... ,t k } из { 1,..., Т } .

Пусть есть взвешенный граф G = (V, Е ) размера Т с матрицей весов W Е R ^{T хТ} , причём w _tt = 0 для всех t (t = 1, Т), и натуральное число К >  2.

Для сведения задачи WAP(K) к задаче HARP(K) достаточно построить торговую статистику {( Р ^t ,X ^t ) } t=i так, что

,   ( ( р ^t ,X ^т ))

log (;<) = для всех t, т.

Построим такую торговую статистику для Т товаров. Положим pt = Т + 1 Vt, Р^ = е > 0 Vt, т : t = т.

Обозначим через Р Е R ^TхТ матрицу, строками которой являются векторы Р ^t . Будем искать X ^t , такие что

( Р ^t , X ^т ) = e ^{W tT}   V t, т,

X ^t Е R 7 \ 0 V t.                                   (4)

Система уравнений (3) распадается на Т независимых систем

Р X ^т

ew1T е™2т

\

у е^т у

При е = 0 определитель матрицы Р отличен от нуля. Поэтому для малых е >  0 этот определитель также отличен от нуля. Поэтому для таких е существует Р ¹ и X ^т определяются однозначно:

X ^т = Р ^{- 1}

е ^{Ш 1} е ^^т

\

\ е^т у

Для завершения доказательства необходимо убедиться в выполнении условий (4). При е = 0 X ^т >  0 для всех т . Поскольку элементы обратной матрицы непрерывно зависят от элементов исходной матрицы, существует е >  0, такое что векторы X ^t остаются положительными для всех т .

Предложение 1 доказано.

• 4.    Заключение

Мы доказали NP-полноту задачи о проверке согласованности торговой статистики с моделью временного диктатора с К диктаторами с положительно-однородными функциями полезности при К >  2. Эта модель является естественным обобщением модели с одним репрезентативным потребителем. На момент написания этой статьи в литературе не исследуется оценка сложности ещё более общей задачи о проверке согласованности торговой статистики с моделью с двумя и более репрезентативными потребителями с положительнооднородными функциями полезности.

Работа выполнена при финансовой поддержке гранта РФФИ 14-07-00075-А.