We axiomatically define a cardinal social inefficiency function, which, given a set of alternatives and individuals' vNM preferences over the alternatives, assigns a unique number -- the social inefficiency -- to each alternative. These numbers -- and not only their order -- are uniquely defined by our axioms despite no exogenously given interpersonal comparison, outside option, or disagreement point. We interpret these numbers as per-capita losses in endogenously normalized utility. We apply our social inefficiency function to a setting in which interpersonal comparison is notoriously hard to justify -- object allocation without money -- leveraging techniques from computer science to prove an approximate-efficiency result for the Random Serial Dictatorship mechanism.
- ID статьи: 2412.11984
- Название: Quantifying Inefficiency
- Авторы: Yannai A. Gonczarowski (Гарвардский университет), Ella Segev (Еврейский университет Иерусалима)
- Классификация: econ.TH (Экономическая теория), cs.GT (Теория игр в информатике)
- Дата публикации: 6 ноября 2025 г. (arXiv v2)
- Ссылка на статью: https://arxiv.org/abs/2412.11984
В данной работе аксиоматически определяется кардинальная функция социальной неэффективности (cardinal social inefficiency function), которая на основе индивидуальных предпочтений фон Неймана-Моргенштерна (vNM) присваивает каждому альтернативному решению уникальное числовое значение — социальную неэффективность. Эти значения (а не только их порядковые отношения) однозначно определяются аксиомами без необходимости в экзогенных межличностных сравнениях полезности, внешних альтернативах или спорных точках. Авторы интерпретируют эти значения как среднедушевые потери эндогенно нормализованной полезности. Статья применяет данную функцию к сценариям, где межличностные сравнения крайне сложно обосновать — задачам распределения благ без денежного обмена, используя методы компьютерной науки для доказательства результатов приближённой эффективности механизма случайной последовательной диктатуры (Random Serial Dictatorship, RSD).
Центральная проблема теории социального выбора заключается в агрегировании индивидуальных предпочтений относительно альтернатив в социальное предпочтение. Традиционная порядковая агрегация (ordinal aggregation) позволяет сравнивать две альтернативы с точки зрения социальной эффективности, но не позволяет количественно оценить, насколько одна альтернатива эффективнее другой.
- Теоретическое значение: Arrow (1951) и Harsanyi (1955) заложили основы теории социального выбора, однако традиционная теория сосредоточена только на порядковых сравнениях и не позволяет проводить кардинальные сравнения
- Практическая ценность: Невозможность количественно оценить неэффективность затрудняет оценку политики, проектирование механизмов и сравнение между ситуациями
- Междисциплинарный спрос: В компьютерной науке «теоремы об ограничении неэффективности» (inefficiency-bounding theorems) требуют сравнимых кардинальных мер
- Неуникальность vNM-полезности: Функция полезности vNM индивида уникальна только при монотонных аффинных преобразованиях, что затрудняет межличностные сравнения
- Проблемы экзогенной нормализации:
- Функция социального благосостояния Нэша (Kaneko & Nakamura, 1979) требует экзогенного «наихудшего случая» в качестве точки отсчёта
- «Цена анархии» (Price of Anarchy) в компьютерной науке зависит от экзогенно нормализованных функций полезности
- Отсутствие межситуационной сравнимости: Существующие функции социального благосостояния обычно позволяют сравнивать только в рамках одной ситуации, но не позволяют проводить кардинальные сравнения между ситуациями
Данная работа направлена на построение кардинальной функции социальной неэффективности, обладающей тремя ключевыми свойствами:
- Порядковая агрегация (Ordinal Aggregation): агрегирование на основе порядковых предпочтений индивидов
- Внутриситуационная кардинальная сравнимость (Intra-context Cardinal Comparability): количественное сравнение различий в неэффективности между альтернативами в одной ситуации
- Межситуационная кардинальная сравнимость (Inter-context Cardinal Comparability): количественное сравнение неэффективности между различными ситуациями
- Аксиоматизация кардинальной функции социальной неэффективности: предложены семь аксиом, которые однозначно характеризуют (с точностью до глобальной мультипликативной константы) кардинальную функцию социальной неэффективности, основанную на порядковых предпочтениях vNM индивидов
- Метод эндогенной нормализации: инновационный подход к нормализации через диапазон полезности на границе Парето, без необходимости в экзогенных межличностных сравнениях или точках отсчёта
- Теоретическая характеризация: доказано, что характеризуемая функция социальной неэффективности имеет естественную интерпретацию: среднедушевые аддитивные потери благосостояния, где функция полезности каждого индивида эндогенно нормализуется в соответствии с величиной его распределительного конфликта на границе Парето
- Применение к распределению благ:
- Доказаны гарантии социальной неэффективности механизма RSD
- Доказано, что гарантии социальной неэффективности любого правдивого порядкового механизма не могут быть улучшены более чем на 28% по сравнению с RSD
- Предоставлен полиномиальный алгоритм для вычисления социальной неэффективности
- Связь между экономической теорией и компьютерной наукой: обеспечение экономико-теоретического обоснования для теорем приближения в компьютерной науке, применимых к ситуациям без экзогенной нормализации
Ситуация (Context): C=(X,(⪰i)i=1n), где:
- X: конечное множество альтернативных решений
- n: количество индивидов
- ⪰i: предпочтение индивида i на Δ(X) (пространство лотерей над X), удовлетворяющее аксиомам vNM
Функция социальной неэффективности (Social Inefficiency Function):
I:Ситуации×Альтернативы→R≥0∪{∞}
Присваивает каждой ситуации C и альтернативе x∈Δ(X) неотрицательное действительное число I(C,x) (возможно, бесконечность), представляющее социальную неэффективность x в ситуации C.
Статья предлагает семь аксиом для характеризации функции социальной неэффективности:
Если x Парето-доминирует y, то I(C,x)≤I(C,y); если x строго Парето-доминирует y, то либо I(C,x)<I(C,y), либо оба значения бесконечны (но существует более эффективное решение с конечной неэффективностью).
Перестановка порядка индивидов не изменяет социальную неэффективность:
I((X,(⪰π(i))i=1n),x)=I((X,(⪰i)i=1n),x)
для любой перестановки π.
Социальная неэффективность линейна относительно лотерей:
I(C,α⋅x+(1−α)⋅y)=α⋅I(C,x)+(1−α)⋅I(C,y)
Это гарантирует нейтральность социальной агрегации к риску.
Если две ситуации C и C′ имеют одинаковые идеальные точки (оптимальное решение для каждого индивида) и минимальные ожидаемые точки (наихудшее решение для каждого индивида на границе Парето), то относительная неэффективность сохраняется:
I(C′,x)−I(C′,y)=I(C,x)−I(C,y)
Это обобщение IIA Нэша (1953), использующее эндогенные точки отсчёта, определённые Ротом (1977).
В составной ситуации C⊕D относительная неэффективность двух альтернатив (x,y) и (x′,y), различающихся только в подситуации C, не зависит от предпочтений в подситуации D.
Самокомпозиция не изменяет относительную неэффективность:
I(⊕j=1kC,(x,…,x))−I(⊕j=1kC,(x′,…,x′))=I(C,x)−I(C,x′)
Это обеспечивает среднедушевой характер социальной неэффективности.
В каждой ситуации существует некоторое решение с нулевой социальной неэффективностью (т.е. наиболее эффективное решение).
Явная конструкция:
Для ситуации C=(X,(⪰i)i=1n) и альтернативы x∈Δ(X):
- Нормализованная полезность: Для каждого индивида i выбирается представление vNM полезности ui и вычисляются:
- uimax=maxx∈FCui(x) (максимальная полезность на границе Парето)
- uimin=minx∈FCui(x) (минимальная полезность на границе Парето)
- Функция социального благосостояния:
V(C,x)=n1∑i=1nuimax−uiminui(x)−uimin
При нулевом знаменателе (индивид безразличен на границе Парето) применяется соглашение: отрицательное число, делённое на ноль, даёт минус бесконечность; ноль, делённый на ноль, даёт ноль. - Социальная неэффективность:
I^(C,x)=maxx′∈XV(C,x′)−V(C,x)
Основная теорема (Theorem 1): Функция социальной неэффективности I удовлетворяет семи аксиомам тогда и только тогда, когда существует константа 0<c<∞ такая, что для всех ситуаций и решений:
I(C,x)=c⋅I^(C,x)
То есть семь аксиом однозначно характеризуют I^ (с точностью до глобальной мультипликативной константы).
- Изящество эндогенной нормализации:
- Нормализация через диапазон полезности на границе Парето делает каждого индивида единицей полезности равной его «величине распределительного конфликта»
- Такая нормализация полностью определяется предпочтениями, без внешней информации
- Математически эквивалентна нормализации диапазона полезности каждого индивида на границе Парето к [0,1]
- Обработка индивидов, безразличных на границе:
- Для индивидов, полностью безразличных на границе Парето (frontier-indifferent), нормализация включает деление на ноль
- Инновационно допускается бесконечная неэффективность, и Лемма 1 доказывает необходимость этого
- Бесконечная неэффективность присваивается только решениям, которые индивиды, безразличные на границе, считают хуже границы Парето
- Синергия аксиом:
- IIA и IIP совместно обеспечивают межситуационную сравнимость
- Стабильность по размеру популяции гарантирует среднедушевую интерпретацию
- Ожидаемая неэффективность в сочетании с монотонностью Парето обеспечивает аддитивную структуру
- Связь с компьютерной наукой:
- Предоставляет экономико-теоретическую альтернативу цене анархии
- Позволяет формулировать теоремы приближения без экзогенной нормализации
- Технически позволяет напрямую адаптировать методы доказательства из компьютерной науки
Определение задачи:
- n индивидов и n благ
- Каждый индивид имеет строгие предпочтения vNM относительно благ
- X=X(n): множество всех совершенных паросочетаний
- Порядковый механизм μ: отображение из профиля ранжирований Rn в Δ(X)
Изучаемые механизмы:
- RSD (Random Serial Dictatorship): индивиды в случайном порядке последовательно выбирают наиболее предпочитаемое неназначенное благо
- RSD известен своей неэффективностью ex-ante (Zhou, 1990; Bogomolnaia & Moulin, 2001)
Гарантия робастной социальной неэффективности (Robust Social Inefficiency Guarantee):
sup(X,⪰)∈MI^((X,⪰),μ(⪰))
То есть наихудшая социальная неэффективность выхода механизма при правдивом раскрытии информации во всех возможных задачах распределения благ.
Статья сравнивает RSD со всеми возможными правдивыми порядковыми механизмами с точки зрения гарантий социальной неэффективности.
- Адаптация доказательства Filos-Ratsikas et al. (2014):
- Исходная работа анализирует цену анархии (отношение)
- Данная работа адаптирует анализ к социальной неэффективности (разность)
- Ключевые технические различия:
- Исходная работа: экзогенная нормализация полезности к [0,1], анализ maxxUu(x)Uu(μ(u))
- Данная работа: эндогенная нормализация к границе Парето, анализ maxxV(C,x)−V(C,x)
Теорема 2 (основной результат): Не существует порядкового механизма μ такого, что
sup(X,⪰)∈MI^((X,⪰),μ(⪰))<2ln21sup(X,⪰)∈MI^((X,⪰),RSD(⪰))
Числовая интерпретация: 2ln21≈0.721, то есть:
- Гарантия робастной социальной неэффективности любого порядкового механизма составляет по крайней мере 72,1% от гарантии RSD
- Гарантия социальной неэффективности RSD не может быть улучшена более чем на 28%
Теорема 3 (нижняя граница): Для любого порядкового механизма μ и произвольного n:
sup⪰∈PnI^((X,⪰),μ(⪰))≥21−2n1
При n→∞ стремится к 21.
Теорема 4 (верхняя граница для RSD): Для произвольного n:
sup⪰∈PnI^((X,⪰),RSD(⪰))≤ln2≈0.693
Предложение 1 (полиномиальный алгоритм): Существует полиномиальный алгоритм (Algorithm 1) для вычисления социальной неэффективности для заданной задачи распределения благ.
Ключевая техника:
- Вычисление минимальной полезности индивида на границе Парето эквивалентно поиску наименее предпочитаемого блага этого индивида в ex-post эффективном паросочетании
- Может быть вычислено за полиномиальное время с использованием алгоритма максимального паросочетания (Hopcroft & Karp, 1973)
- Приближённая эффективность: Хотя RSD не является ex-ante эффективным, его социальная неэффективность ограничена (≤ln2), что доказывает его приближённую эффективность
- Ограниченные различия между механизмами: Различия в производительности между всеми правдивыми механизмами не превышают 28%, что указывает на ограниченное пространство выбора механизмов в смысле робастных гарантий
- Вычислительная осуществимость: Вычисление социальной неэффективности осуществимо, что позволяет использовать её для практической оценки механизмов
- Классические основания:
- Arrow (1951): отказ от межличностных сравнений полезности
- Harsanyi (1955): утилитаризм на основе аксиом vNM, но требует экзогенных весов
- Подход с экзогенной информацией:
- DeMeyer & Plott (1971), Maskin (1978), Sen (1970), Roberts (1980): предполагают экзогенно заданные функции полезности
- Отличие данной работы: зависит только от порядковых предпочтений vNM
- Подход с точками отсчёта:
- Kaneko & Nakamura (1979): функция социального благосостояния Нэша, требует «наихудшего состояния» в качестве точки отсчёта
- Dhillon & Mertens (1999): относительный утилитаризм, требует «достаточно богатого» множества альтернатив
- Отличие данной работы: использует эндогенную границу Парето в качестве точки отсчёта, без необходимости в экзогенной точке отсчёта
- Межситуационные сравнения:
- Fleurbaey & Tadenuma (2014): межсоциальные сравнения, но только порядковые
- Отличие данной работы: реализует кардинальные межситуационные сравнения
- Цена анархии (Price of Anarchy):
- Koutsoupias & Papadimitriou (1999): определяется как отношение эффективности в равновесии к оптимальной
- Roughgarden & Tardos (2002): применение к играм с перегруженностью
- Отличие данной работы: обеспечивает экономико-теоретическое обоснование, не зависящее от экзогенной нормализации
- PoA в распределении благ:
- Filos-Ratsikas et al. (2014): анализ PoA для RSD
- Вклад данной работы: адаптирует методы доказательства для анализа социальной неэффективности (разность вместо отношения)
- Переговоры по Нэшу:
- Nash (1953): IIA относительно точки разногласия
- Roth (1977): эндогенные точки отсчёта (идеальная точка, минимальная ожидаемая точка)
- Применение в данной работе: IIA относительно двух эндогенных точек отсчёта
- Теория паросочетаний:
- Abdulkadiroğlu & Sönmez (1998): механизм RSD
- Zhou (1990), Bogomolnaia & Moulin (2001): неэффективность RSD ex-ante
- Вклад данной работы: количественная оценка приближённой эффективности RSD
- Теоретические вклады:
- Семь аксиом однозначно характеризуют функцию кардинальной социальной неэффективности (с точностью до глобальной единицы)
- Функция имеет естественную интерпретацию: среднедушевые потери полезности на основе эндогенной нормализации
- Не требует экзогенных межличностных сравнений или точек отсчёта
- Результаты применения:
- Гарантия социальной неэффективности RSD ≤ln2≈0.693
- Ни один правдивый механизм не может улучшить RSD более чем на 28%
- Социальная неэффективность может быть вычислена за полиномиальное время
- Методологические вклады:
- Обеспечение экономико-теоретического обоснования для теорем приближения в компьютерной науке
- Демонстрация потенциала междисциплинарного подхода
- Обработка бесконечной неэффективности:
- Допущение бесконечной неэффективности, хотя необходимое (Лемма 1), может быть недостаточно точным в некоторых приложениях
- Возникает только при наличии индивидов, безразличных на границе, что на практике встречается редко
- Спорность выбора аксиом:
- Как отмечают авторы, любая аксиоматизация может быть подвергнута критике
- Особенно ослабленная форма IIA (относительно двух эндогенных точек отсчёта) может требовать дополнительного обоснования
- Область применения:
- Применение к распределению благ рассматривает только правдивые механизмы
- Для нестратегических механизмов необходимо учитывать влияние стратегического поведения
- Вычислительная сложность:
- Хотя предоставлен полиномиальный алгоритм, для крупномасштабных задач он может быть вычислительно дорогостоящим
- Сложность алгоритма составляет O(n3) (на основе алгоритма максимального паросочетания)
- Расширение на другие цели:
- Аксиоматизация функции кардинальной социальной несправедливости
- Аксиоматизация функции кардинального социального неравенства
- Доказательство гарантий приближения для этих целей
- Применение в других областях:
- Теория голосования
- Рынки двусторонних паросочетаний (например, выбор школ, обмен почками)
- Проектирование аукционов
- Улучшение границ:
- Гарантия социальной неэффективности RSD может быть дополнительно уточнена
- Исследование лучших границ для специфических структур предпочтений
- Проектирование механизмов:
- Разработка механизмов, явно оптимизирующих социальную неэффективность
- Исследование компромиссов между социальной неэффективностью и другими целями (например, справедливостью)
- Теоретическая строгость:
- Полная аксиоматизация с подробными доказательствами (основные результаты и все леммы)
- Логическая независимость аксиом (раздел 4.2) усиливает достоверность характеризации
- Высокий уровень математического мастерства, особенно в обработке бесконечной неэффективности
- Инновационность:
- Впервые реализована кардинальная функция социального благосостояния на основе порядковых предпочтений с кардинальной межситуационной сравнимостью
- Метод эндогенной нормализации (через границу Парето) чрезвычайно инновационен
- Построение моста между экономической теорией и компьютерной наукой открывает новые направления для большого количества теорем приближения
- Практическая ценность:
- Предоставлен вычислимый алгоритм (полиномиальное время)
- Применение к реальным задачам (распределение благ) с значимыми результатами
- Методология универсальна и применима к различным экономическим сценариям
- Качество изложения:
- Ясная структура: от мотивации к аксиомам, к характеризации, к приложениям
- Диаграммы (Figure 1, 2) способствуют пониманию
- Полный обзор связанных работ, точное позиционирование вклада
- Междисциплинарный вклад:
- Предоставляет инструменты количественной оценки для экономистов
- Обеспечивает экономико-теоретическое обоснование для компьютерных учёных
- Демонстрирует потенциал исследований на пересечении EconCS
- Интуитивность аксиом:
- Экономическая интуиция IIP (независимость от нерелевантных предпочтений) менее ясна, чем у других аксиом
- Стабильность по размеру популяции, хотя математически элегантна, может требовать более убедительного экономического обоснования необходимости
- Глубина применения:
- Применение к распределению благ в основном адаптирует существующие доказательства (Filos-Ratsikas et al. 2014), с ограниченной технической инновацией
- Отсутствуют численные эксперименты или применение к реальным данным
- Практическая значимость 28% пространства для улучшения недостаточно обсуждена
- Сравнительные ориентиры:
- Отсутствует эмпирическое сравнение с другими возможными функциями социального благосостояния (например, функция социального благосостояния Нэша)
- Недостаёт систематического сравнения различных функций социальной неэффективности, вытекающих из различных выборов аксиом
- Случай безразличия на границе:
- Хотя доказана необходимость бесконечной неэффективности, практическое значение и частота этого случая недостаточно обсуждены
- Отсутствуют рекомендации по обработке или избеганию этого случая в практических приложениях
- Вычислительная сложность:
- Хотя алгоритм полиномиален, O(n3) может быть неэффективным для крупномасштабных задач
- Не обсуждаются возможности приближённых вычислений или эвристических алгоритмов
- Вклад в область:
- Значительный теоретический вклад: решение давней проблемы теории социального выбора (кардинальная агрегация)
- Может инициировать новое направление исследований: теория кардинального социального выбора
- Предоставляет новый инструмент оценки для проектирования механизмов
- Практическая ценность:
- Применимо к оценке политики и сравнению механизмов
- Предоставляет инструменты количественной оценки для рынков без денежного обмена (выбор школ, обмен органов)
- Потенциально широкое применение (голосование, паросочетания, распределение ресурсов)
- Воспроизводимость:
- Теоретические результаты полностью воспроизводимы (полные доказательства)
- Алгоритм ясно описан (Algorithm 1)
- Код не предоставлен, но алгоритм легко реализуется
- Потенциальное влияние:
- Высокий потенциал цитирования (пересечение экономики и компьютерной науки)
- Вероятно, станет основополагающей работой в теории кардинального социального выбора
- Может вдохновить множество последующих исследований
- Идеальные сценарии:
- Распределение ресурсов без денежного обмена (распределение благ, обмен органов)
- Проектирование механизмов, требующее количественной оценки потерь эффективности
- Оценка политики, требующая межситуационных сравнений
- Задачи принятия решений с чётко определённой границей Парето
- Неприменимые сценарии:
- Рынки с естественной денежной мерой (в этом случае традиционные методы проще)
- Сложные среды, где границу Парето сложно определить
- Задачи, требующие учёта динамики или неполной информации
- Ситуации, где индивиды, безразличные на границе, доминируют
- Потенциальные области расширения:
- Системы голосования и оценка их эффективности
- Двусторонние рынки паросочетаний (брачные рынки, рынки труда)
- Принятие решений по общественным благам
- Многоцелевая оптимизация с компромиссом между эффективностью и справедливостью
- Arrow, K. J. (1951). Social Choice and Individual Values. Yale University Press.
- Основополагающая работа в теории социального выбора
- Harsanyi, J. C. (1955). Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility. Journal of Political Economy, 63(4):309-321.
- Аксиоматическое обоснование утилитаризма
- Dhillon, A. and Mertens, J.-F. (1999). Relative utilitarianism. Econometrica, 67(3):471-498.
- Наиболее близкая предшествующая работа
- Filos-Ratsikas, A., Frederiksen, S. K. S., and Zhang, J. (2014). Social welfare in one-sided matchings: Random priority and beyond. SAGT.
- Техническая основа для применения к распределению благ
- Koutsoupias, E. and Papadimitriou, C. (1999). Worst-case equilibria. STACS.
- Пионерская работа по цене анархии
Общая оценка: Это выдающаяся теоретическая работа, достигшая значительного прорыва в теории социального выбора. Благодаря изящному методу эндогенной нормализации и строгой аксиоматизации, она решает давнюю проблему кардинальной агрегации. Статья не только имеет значительный теоретический вклад, но и демонстрирует практическую ценность через применение к распределению благ, а также открывает новые направления для синтеза экономической теории и компьютерной науки. Хотя есть возможности для улучшения в глубине применения и эмпирической проверке, её теоретическая инновационность и потенциальное влияние делают её важным вкладом в область. Ожидается публикация в ведущих журналах по экономике и компьютерной науке и инициирование волны последующих исследований.