Когда контракты становятся сложными: информационно-теоретические барьеры

Основная информация

• ID статьи: 2403.09794
• Название: When Contracts Get Complex: Information-Theoretic Barriers
• Авторы: Paul Dütting (Google Research), Michal Feldman (Tel Aviv University), Yoav Gal-Tzur (Tel Aviv University), Aviad Rubinstein (Stanford University)
• Классификация: cs.GT (Теория игр)
• Дата публикации/конференция: SODA 2026 (полная версия от 27 ноября 2025)
• Ссылка на статью: https://arxiv.org/abs/2403.09794

Аннотация

В данной работе исследуются информационно-теоретические барьеры в модели комбинаторных контрактов действий. В этой модели принципал поручает агенту выполнение сложного проекта, при этом агент может выбрать любое подмножество действий. Каждое множество действий создает затраты для агента (представленные функцией множества c) и приносит ожидаемую прибыль для принципала (представленная функцией множества f). Статья доказывает, что даже при использовании запросов спроса (demand queries) в случае субмодулярного f и аддитивного c поиск оптимального контракта требует экспоненциального числа запросов, что отрицательно отвечает на фундаментальный открытый вопрос в этой области. Исследование дополнительно расширяет результаты на различные комбинации субмодулярного/супермодулярного f и c, а также устанавливает экспоненциальные нижние границы в модели сложности коммуникации.

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема, исследуемая в этой работе, — это проектирование комбинаторных контрактов действий (combinatorial-action contract design):

• Принципал должен разработать контракт для стимулирования агента к выполнению сложного проекта
• Агент может выбрать любое подмножество S из n действий
• Выбор множества действий S создает затраты c(S) и вероятность успеха f(S)
• Контракт определяет платеж α при успехе; цель принципала — максимизировать свою полезность

Важность проблемы

1. Теоретическое значение: Проектирование контрактов является одной из опор экономической теории (Нобелевская премия по экономике 2016 года присуждена Харту и Хольмстрёму), а модель принципал-агент со скрытыми действиями является её основой
2. Вычислительная сложность: Комбинаторные функции обычно требуют экспоненциального числа бит для представления, поэтому необходим доступ через запросы
3. Фундаментальный открытый вопрос: После представления этой модели на FOCS'21 центральным нерешённым вопросом стало: могут ли запросы спроса сделать задачу разрешимой?

Ограничения существующих подходов

• Известные положительные результаты:
  • Когда f — это gross-substitutes, можно решить за полиномиальное число запросов стоимости
  • Когда f супермодулярна, а c субмодулярна, можно решить за полиномиальное число запросов стоимости
• Известные отрицательные результаты:
  • При использовании запросов стоимости нет константного приближения для субмодулярного f и аддитивного c (EFS24)
  • Вычисление оптимального контракта является NP-трудным
• Критический пробел: Могут ли запросы спроса преодолеть ограничения запросов стоимости?

Исследовательская мотивация

Запросы спроса имеют естественную интерпретацию в экономике и более мощны, чем запросы стоимости (один запрос спроса может вернуть множество действий, максимизирующее полезность агента). Определение границ возможностей запросов спроса критически важно для понимания фундаментальной сложности комбинаторной задачи контрактов.

Основные вклады

Основные вклады статьи включают:

1. Трудность запросов спроса (Основной результат 1): Доказано, что при субмодулярном f и аддитивном c любой алгоритм вычисления оптимального контракта требует экспоненциального числа запросов спроса, что отрицательно отвечает на открытый вопрос из FOCS'21
2. Трудность запросов предложения: Двойственно доказано, что при аддитивном f и супермодулярном c требуется экспоненциальное число запросов предложения (supply queries)
3. Нижние границы сложности коммуникации (Основной результат 2): В модели коммуникации, где f и c распределены между двумя сторонами, даже при разрешении полиномиального числа запросов наилучшего ответа вычисление оптимального контракта требует экспоненциальной коммуникации:
   • Субмодулярные f и c
   • Супермодулярные f и c
   • Субмодулярные f и супермодулярные c
4. Новая техническая база: Предложены два ключевых свойства как чёрный ящик для установления нижних границ:
   • Конструкция равной прибыли (Equal-Revenue): Экспоненциально много различных контрактов являются оптимальными
   • Разреженный спрос (Sparse Demand): Для любого вектора цен число приблизительно оптимальных множеств полиномиально
5. Плотность: Все результаты нижних границ плотны при представлении экземпляра размером poly(n), что соответствует известным алгоритмам FPTAS

Подробное описание методов

Определение задачи

Задача оптимального контракта (Определение 1):

• Вход: Тройка ⟨n, f, c⟩
  • n: количество действий
  • f: 2^n → 0,1 (функция награды/вероятности успеха)
  • c: 2^n → ℝ≥0 (функция затрат)
• Выход: Оптимальный контракт α* ∈ 0,1, максимизирующий полезность принципала
  • Полезность агента: u_a(α, S) = αf(S) - c(S)
  • Полезность принципала: u_p(α, S) = (1-α)f(S)
  • Агент выбирает S_α = argmax_S u_a(α, S)
  • Оптимальный контракт: α* = argmax_α u_p(α, S_α)

Модели запросов:

1. Запрос стоимости (Value Query): На входе множество S возвращает f(S) или c(S)
2. Запрос спроса (Demand Query): На входе вектор цен p возвращает argmax_S(f(S) - Σp_i)
3. Запрос предложения (Supply Query): На входе вектор цен p возвращает argmax_S(Σp_i - c(S))
4. Запрос наилучшего ответа (Best-Response Query): На входе контракт α возвращает argmax_S(αf(S) - c(S))

Основная техническая база

Доказательство построено на трёх уровнях конструкции:

Первый уровень: Конструкция равной прибыли (Раздел 3)

Определение (Определение 5): Экземпляр ⟨n, f, c⟩ имеет равную прибыль если:

1. Каждое непустое множество может быть стимулировано
2. Существует 2^n-1 различных оптимальных контрактов {α_t}, каждый приносящий одинаковую полезность принципалу

Метод конструкции (Теорема 1 - субмодулярное f и аддитивное c):

• Установка затрат: c_i = 2^(i-1), так что c(S_t) = t (t — двоичное представление S)
• Рекурсивное определение ключевых значений: α_0 = 0, α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1)
• Определение награды: f_t = f(S_t) = 1/(1-α_t)

Ключевые свойства:

• Лемма 1: α_t строго возрастает и α_t < 1
• Лемма 2: Дискретная производная f_(t+1) - f_t убывает (подразумевает субмодулярность)
• Предложение 2: f монотонно субмодулярна

Изящество этой конструкции заключается в:

1. Использовании экспоненциальных затрат и двоичного кодирования для идеального индексирования множеств
2. Рекурсивном соотношении, гарантирующем, что каждое ключевое значение удовлетворяет условию равной прибыли
3. Монотонности дискретной производной, естественно приводящей к субмодулярности

Второй уровень: Свойство разреженного спроса (Раздел 4.3)

Определение (Определение 6): Функция f имеет σ-разреженный спрос если для любого вектора цен p размер σ-приблизительного множества спроса D_{σ,p} = {S | max_T(f(T) - Σp_i) - (f(S) - Σp_i) ≤ σ} полиномиален от n.

Основная лемма (Лемма 3): Определим нечёткие интервалы l_i, r_i, где:

• r_i = max{t | S_t ∈ D_{σ,p}, i ∈ S_t}
• l_i = max{r_i - 2^i, 0}

Для любого S_t ∈ D_{σ,p}:

• Если t > r_i, то i ∉ S_t
• Если t < l_i, то i ∈ S_t

Идея доказательства:

1. Использование свойства равной прибыли: существует контракт α_{S_t{i}} такой, что предельная награда < предельные затраты
2. Поэтому p_i < c_i/α_{S_t{i}} + σ
3. Для множеств S_{t'} с индексом, намного меньшим t, если i ∉ S_{t'}, то p_i сделает S_{t'}∪{i} более оптимальным
4. Это создаёт эффект "принудительного включения"

Комбинаторный аргумент (Лемма 4):

• Отображение каждого приблизительно оптимального множества S_t на минимальное действие i такое, что t ∈ l_i, r_i
• Каждое действие i соответствует максимум O(n) множествам
• Всего O(n²) приблизительно оптимальных множеств

Предложение 6: Построенная функция f имеет σ-разреженный спрос (для подходящего малого σ)

Третий уровень: От равной прибыли к трудности запросов

Трудность запросов стоимости (Предложение 5):

• Конструкция семейства возмущений I = {⟨n, f_k, c⟩}, где f_k(S_k) = f(S_k) + ε
• Использование аргумента "скрытого специального множества"
• Любой детерминированный алгоритм должен запросить 2^(n-1) множеств для поиска возмущённого множества
• Ожидаемое число запросов ≥ 2^(n-2)

Трудность запросов спроса (Теорема 3): Ключевое наблюдение: если алгоритм знает исходную f, он может моделировать запросы спроса за poly число запросов стоимости

• Множество, возвращаемое запросом спроса на вектор цен p, должно быть в приблизительном спросе D_{ε,p}
• D_{ε,p} не зависит от идентичности f_k и может быть предварительно вычислено
• Использование |D_{ε,p}| ≤ poly(n) запросов стоимости для поиска оптимального множества
• Поэтому запросы спроса не сильнее запросов стоимости (максимум полиномиальный множитель)
• Из нижней границы запросов стоимости получаем нижнюю границу запросов спроса

Конструкция сложности коммуникации (Раздел 5)

Модель: Алиса владеет f, Боб владеет c, обе стороны могут общаться и обращаться к оракулу наилучшего ответа

Шаги конструкции:

1. Возмущение функции затрат (делает c строго субмодулярной):
   • c̃(S) = c(S) - δ|S|²
   • Выбор δ так, чтобы сохранить 2^n-1 ключевых значений
   • Предложение 9: Ĩ = ⟨n, f, c̃⟩ имеет разреженный наилучший ответ
2. Добавление (n+1)-го действия: Параметризация предельной награды и затрат векторами x_f, x_c ∈ {0,1}^(n choose n/2):

   f̂(n+1 | S_t) = z/4  если |S_t|=n/2 ∧ S_t ∈ x_f
                  0    иначе (для |S_t|≥n/2)
   
   ĉ(n+1 | S_t) = αt·z/4  если |S_t|=n/2 ∧ S_t ∈ x_c  
                  z/2      иначе
   

3. Редукция к DISJ:
   • Наблюдение 5: Множество вида S_t∪{n+1} может быть стимулировано ⟺ |S_t|=n/2 ∧ S_t ∈ x_f∩x_c
   • Предложение 12: Если x_f∩x_c ≠ ∅, то оптимальный контракт стимулирует некоторый S_t∪{n+1}
   • Следствие 3: Поиск оптимального контракта требует решения DISJ_{(n choose n/2)}
   • По Факту 1 (KS92, Raz92): DISJ_k требует Ω(k) коммуникации
   • Получаем нижнюю границу Ω(2^n/√n) коммуникации

Ключевые технические моменты:

• Выбор z = min{ϕ_c̃, ψ_c̃, ϕ_f, ψ_f, ζ, σ} гарантирует субмодулярность и разреженность
• Тщательный дизайн предельных затрат обеспечивает, что только специальные множества могут быть стимулированы вместе с n+1
• Предложение 13: Даже с оракулом наилучшего ответа можно моделировать за poly коммуникацию (используя разреженность)

Экспериментальная установка

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

Методы теоретической верификации

1. Верификация конструкции: Проверка свойств конструкции равной прибыли через математическую индукцию и доказательства неравенств
2. Доказательство нижних границ: Использование информационно-теоретических аргументов (принцип минимакса Яо) и техник редукции
3. Анализ плотности: Сравнение с известными верхними границами алгоритмов (FPTAS)

Результаты исследования

Основные теоретические результаты

Таблица 1 - Сводка:

Где:

• Трудность запроса спроса/предложения: Требует exp(n) запросов
• Трудность CC+BR: Требует Ω(2^n/√n) коммуникации (даже с poly запросами наилучшего ответа)
• Полиномиальное время: Существует эффективный алгоритм (DFG24)

Ключевые формулировки теорем

Теорема 2 (Трудность запроса спроса): При субмодулярном f и аддитивном c любой алгоритм вычисления оптимального контракта требует экспоненциального числа запросов спроса.

Теорема 4 (Сложность коммуникации - субмодулярные f и c): При субмодулярных f и c, даже при разрешении poly(n) запросов наилучшего ответа, вычисление оптимального контракта требует Ω(2^n/√n) бит коммуникации.

Теорема 8 (Трудность запроса предложения): При аддитивном f и супермодулярном c любой алгоритм вычисления оптимального контракта требует экспоненциального числа запросов предложения.

Теоремы 10, 11 (Сложность коммуникации для других комбинаций):

• Субмодулярное f и супермодулярное c: Ω(2^n/√n) коммуникации
• Супермодулярные f и c: Ω(2^n/√n) коммуникации

Результаты плотности

1. Соответствие с FPTAS: DEFK21 предоставляет FPTAS, работающий за полиномиальное время при представлении экземпляра в poly(n) бит. Жёсткие экземпляры данной работы также представимы в poly(n) бит (Приложение H), поэтому нижние границы плотны.
2. Разрешимость для субаддитивных затрат: Приложение B показывает, что FPTAS из DEFK25 расширяется на субаддитивные c, поэтому результаты плотны и в расширенной модели для этого семейства функций.

Технические особенности

1. Универсальность конструкции равной прибыли: Одна и та же техника конструкции применима к:
   • Субмодулярное f + аддитивное c (Раздел 3)
   • Аддитивное f + супермодулярное c (Приложение D)
2. Робастность свойства разреженного спроса:
   • Сохраняется при возмущениях (Предложение 9)
   • Расширяется на разреженный наилучший ответ (Определение 10)
3. Модульная структура доказательства:
   • Равная прибыль → трудность запроса стоимости (чёрный ящик)
   • Равная прибыль + разреженный спрос → трудность запроса спроса (чёрный ящик)
   • Возмущение + добавление действия → трудность сложности коммуникации (чёрный ящик)

Связанные работы

Проектирование комбинаторных контрактов

1. DEFK21 (FOCS'21):
   • Представление модели комбинаторных контрактов действий
   • Субмодулярное f с gross-substitutes решается за полиномиальное число запросов стоимости
   • Субмодулярное f является NP-трудным
   • Открытый вопрос о разрешимости запросов спроса
2. EFS24 (ITCS'24):
   • Доказательство отсутствия константного приближения при запросах стоимости (при P≠NP)
   • Данная работа усиливает результат до информационно-теоретической нижней границы для запросов спроса
3. DFG24 (SODA'24):
   • Супермодулярное f + субмодулярное c решается за полиномиальное число запросов стоимости
   • Данная работа доказывает трудность других комбинаций
4. DEFK25 (SODA'25):
   • Сильно полиномиальный FPTAS для монотонного f + аддитивного c
   • Расширяется на субаддитивное c (данная работа, Приложение B)

Многоагентные контракты

1. BFN06a, BFNW12: Многоагентные + булевы функции
2. DEFK23: Многоагентные + XOS награды с константным приближением
3. DDPP24: Нижние границы приближения для супермодулярных наград

Сложность запросов и коммуникации

1. NS06: Требования коммуникации в проектировании механизмов
2. Dob11: Невозможность для субмодулярных оценок
3. EFN+19: Сложность коммуникации в комбинаторных аукционах

Данная работа является первой, устанавливающей результаты сложности коммуникации в литературе по контрактам.

Другие направления контрактов

• Простые vs оптимальные контракты (Car15, DRT19)
• Онлайн обучение (HSV14, ZBY+23)
• Типизированные агенты (GSW21, CMG22)
• Дизайн информации (BTCXZ24)

Заключение и обсуждение

Основные выводы

1. Ответ на открытый вопрос: Запросы спроса не могут сделать задачу проектирования контрактов с субмодулярным f и аддитивным c разрешимой; существуют фундаментальные информационно-теоретические барьеры
2. Полная характеризация: За исключением (супермодулярное f, субмодулярное c) и (аддитивное f, аддитивное c), все комбинации субмодулярного/супермодулярного сталкиваются с:
   • Барьерами сложности запросов (когда одна функция аддитивна)
   • Барьерами сложности коммуникации (когда обе функции комбинированы)
3. Технический вклад: Конструкция равной прибыли и свойство разреженного спроса предоставляют универсальные инструменты для исследования сложности комбинаторных контрактов

Ограничения

1. Открытые вопросы:
   • Допускает ли супермодулярное c приближение (даже при аддитивном f)? (Отмечено как открытое в Таблице 1)
   • Сложность коммуникации для строгих подклассов субмодулярного/супермодулярного (например, XOS, gross-substitutes)?
2. Предположения модели:
   • Линейные контракты (хотя известно, что они оптимальны во многих случаях)
   • Бинарные результаты (успех/неудача)
   • Одноагентная установка
3. Размер представления:
   • Основные результаты предполагают O(1) пространство представления
   • Приложение H расширяет на poly(n) бит представления
   • Модель с неограниченным размером представления может быть проще

Будущие направления

1. Сложность строгих подклассов:
   • Разрыв между gross-substitutes (известно разрешимо) и общим субмодулярным
   • Недавние расширения границ разрешимости (FY25)
2. Алгоритмы приближения:
   • Возможность приближения для супермодулярного c
   • Лучшая характеризация коэффициентов приближения
3. Уточнение модели коммуникации:
   • Способности различных протоколов коммуникации
   • Необходимость оракула наилучшего ответа
4. Расширение на многоагентов:
   • Могут ли техники данной работы расширяться на многоагентную установку?
   • DEFK25 уже имеет предварительные результаты
5. Практические алгоритмы:
   • Несмотря на наихудшую сложность, существуют ли алгоритмы, зависящие от экземпляра?
   • Гладкий анализ или средняя сложность

Глубокая оценка

Преимущества

1. Значительный теоретический прорыв:
   • Решение центрального открытого вопроса из FOCS'21
   • Установление первых результатов сложности коммуникации в этой области
   • Почти полная характеризация сложности (Таблица 1)
2. Техническая новизна:
   • Конструкция равной прибыли изящно использует экспоненциальные затраты и рекурсию
   • Свойство разреженного спроса — глубокое открытие с доказательством "принудительного включения" (Лемма 3)
   • Модульная база позволяет применять технику чёрным ящиком в различных установках
3. Элегантность доказательств:
   • Рекурсивное соотношение α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1) естественно порождает все свойства
   • Двоичное кодирование реализует идеальное индексирование
   • Конструкция редукции к DISJ чрезвычайно изящна
4. Полнота результатов:
   • Охватывает все комбинации субмодулярного/супермодулярного
   • Рассматривает модели запросов и коммуникации
   • Анализ плотности (соответствие FPTAS)
   • Расширение на poly(n) бит представления (Приложение H)
5. Качество изложения:
   • Ясная структура, прогрессирующая от простого к сложному
   • Полезный обзор техники (Раздел 1.2)
   • Обширные приложения с полными доказательствами

Недостатки

1. Технические ограничения:
   • Задача приближения для супермодулярного c остаётся нерешённой (явно отмечено как открытое)
   • Доказательство разреженного спроса хотя и корректно, но весьма техническое; интуиция не совсем прямая
   • Анализ округления для poly(n) бит представления (Приложение H) многословен и технически сложен
2. Практические соображения:
   • Чисто теоретические результаты без обсуждения приложений
   • Наихудший случай; реальные экземпляры могут быть проще
   • Не исследуются эвристические или приблизительные методы
3. Ограничения области:
   • Только линейные контракты
   • Одноагентная установка
   • Отсутствует детальный анализ других функциональных классов (XOS, subadditive)
4. Детали изложения:
   • Некоторые доказательства (например, Лемма 2) содержат громоздкие алгебраические манипуляции
   • Мотивация модели коммуникации (разделение f и c) могла быть более полной

Влияние

1. Теоретическое влияние:
   • Установление границ сложности проектирования комбинаторных контрактов
   • Конструкция равной прибыли и разреженный спрос могут стать стандартными инструментами
   • Открытие нового направления применения сложности коммуникации в теории контрактов
2. Вдохновение для будущих исследований:
   • Ясное указание на необходимость поиска новых структурных свойств для разрешимости
   • Важность исследования строгих подклассов
   • Систематический метод конструирования жёстких экземпляров
3. Методологический вклад:
   • Демонстрация синтеза конструкции равной прибыли и разреженности
   • Техника добавления одного действия для перехода от полукомбинаторного к полностью комбинаторному
   • Связь между информационно-теоретическими нижними границами и вычислительной сложностью
4. Воспроизводимость:
   • Все доказательства конструктивны
   • Жёсткие экземпляры явно конструируемы
   • Теоретические результаты не требуют экспериментальной верификации

Применимые сценарии

1. Теоретические исследования:
   • Нижние границы сложности в алгоритмической теории игр
   • Границы вычислимости в проектировании контрактов
   • Исследования сложности запросов и коммуникации
2. Руководство для разработки алгоритмов:
   • Ясное определение случаев, требующих алгоритмов приближения
   • Направление разработки эвристических методов
   • Определение сценариев, нуждающихся в дополнительных структурных предположениях
3. Экономическая теория:
   • Понимание роли информации в проектировании контрактов
   • Вычислительная перспектива проблемы принципал-агент
   • Информационные затраты в дизайне стимулов
4. Практические выводы:
   • Даже в кажущихся простыми случаях (субмодулярное + аддитивное) оптимальный контракт может быть вычислительно сложным
   • Необходимость компромисса между оптимальностью и вычислимостью
   • Простые контракты могут быть предпочтительнее на практике

Анализ технической глубины

Математическая красота конструкции равной прибыли

Вывод рекурсивного соотношения демонстрирует глубокое математическое понимание:

Из условий равной прибыли (1-α_t)f_t = 1 и условия ключевого значения α_(t+1) = 1/(f_(t+1)-f_t), получаем:

α_(t+1) = (1-α_(t+1))(1-α_t)/(α_(t+1)-α_t)

Решение этого уравнения обладает замечательными свойствами:

• Генерирует строго возрастающую последовательность
• Автоматически удовлетворяет α_t < 1
• Порождённая f_t естественно субмодулярна

Комбинаторный аргумент разреженного спроса

Доказательство Леммы 4 использует изящный комбинаторный аргумент:

1. Определение минимального нечёткого действия m(S_t) = min{i | t ∈ l_i, r_i}
2. Наблюдение, что для фиксированного i*, множества с m(S_t) = i* образуют "цепь": (S_t1 ∩ i*-1) ⊇ ... ⊇ (S_tk ∩ i*-1)
3. Длина цепи ≤ i*, поэтому всего ≤ Σi* · 4i* = O(n²) множеств

Открытие этой "структуры цепей" является ключом к доказательству разреженности.

Изящество редукции сложности коммуникации

Конструкция добавления (n+1)-го действия тщательно разработана так, чтобы:

• Только "специальные" множества размера n/2 могли быть стимулированы вместе с n+1
• Оптимальность строго зависит от того, пусто ли x_f ∩ x_c
• При этом сохраняются субмодулярность и разреженный наилучший ответ

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

Избранные ссылки

1. DEFK21 Dütting, Ezra, Feldman, Kesselheim. "Combinatorial Contracts." FOCS 2021. (Исходная модель)
2. EFS24 Ezra, Feldman, Schlesinger. "On the (In)Approximability of Combinatorial Contracts." ITCS 2024. (Трудность запроса стоимости)
3. DFG24 Dütting, Feldman, Gal-Tzur. "Combinatorial Contracts Beyond Gross Substitutes." SODA 2024. (Положительные результаты)
4. KS92 Kalyanasundaram, Schintger. "The Probabilistic Communication Complexity of Set Intersection." SIDMA 1992. (Нижняя граница DISJ)
5. DRT19 Dütting, Roughgarden, Talgam-Cohen. "Simple versus Optimal Contracts." EC 2019. (Простые контракты)

Общая оценка: Это выдающаяся теоретическая работа, которая посредством введения новых технических инструментов (конструкция равной прибыли и разреженный спрос) решает центральный открытый вопрос в области проектирования комбинаторных контрактов и устанавливает первые результаты сложности коммуникации в этой области. Техническая глубина, полнота результатов и ясность изложения достигают уровня топовых конференций. Хотя это чисто теоретическая работа, установленные границы сложности имеют важное значение для будущего развития этой области. Основные ограничения — нерешённая задача приближения для супермодулярного c и отсутствие обсуждения практических приложений, но это явно обозначены как будущие направления.