Одно действие слишком много: неприближаемость бюджетных комбинаторных контрактов

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

• ID статьи: 2511.20110
• Название: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
• Авторы: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (Тель-Авивский университет)
• Классификация: cs.GT (Теория игр)
• Время публикации/конференция: ITCS 2026 (препринт: 26 ноября 2025 г.)
• Ссылка на статью: https://arxiv.org/abs/2511.20110

Аннотация

В данной работе исследуется задача проектирования многоагентных комбинаторных контрактов действий с ограничениями по бюджету для широкого класса целевых функций, включая прибыль, вознаграждение и благосостояние. Основные результаты включают: (1) сильная неприближаемость: для субмодульных функций вознаграждения любой рандомизированный полиномиальный алгоритм не может приблизить оптимальное бюджетно-допустимое значение ни на какой конечный множитель, даже с доступом к оракулу спроса; (2) положительные результаты: для функций валовых заменителей (строгого подкласса субмодульных функций) существует детерминированный полиномиальный алгоритм O(1)-приближения, требующий только запросов значений; (3) FPTAS: для аддитивных функций вознаграждения существует FPTAS при любом бюджете, что является первым FPTAS в многоагентной комбинаторной постановке действий. Работа впервые четко разделяет сложность бюджетных и небюджетных постановок и определяет свойство валовых заменителей как границу разрешимости.

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

1. Исследуемая проблема

В данной работе исследуется задача проектирования многоагентных комбинаторных контрактов действий, основная сложность которой заключается в следующем: когда принципал (principal) сталкивается с ограничениями по бюджету, как спроектировать стимулирующий контракт, чтобы несколько агентов выбрали подходящие комбинации действий для оптимизации цели принципала (прибыль, вознаграждение или благосостояние)?

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

• Теоретическое значение: теория контрактов является центральной областью микроэкономики; Нобелевская премия по экономике 2016 г. была присуждена Харту и Хёльмстрёму, что подчеркивает её значимость
• Практическая ценность: широко применяется в современных вычислительных рынках, таких как:
  • Стартапы стимулируют команды инженеров через акционерные опционы
  • Платформы краудсорсинга проектируют механизмы вознаграждения за задачи
  • Проектирование контрактов при аутсорсинге проектов

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

В литературе существуют два класса положительных результатов:

• (i) Без ограничений по бюджету + комбинаторные действия: DEFK25 дает приближение с постоянным множителем для субмодульных функций
• (ii) С ограничениями по бюджету + бинарные действия: FGPS25, AHT25 дают приближение с постоянным множителем для субмодульных функций

Однако комбинация обоих (ограничения по бюджету + комбинаторные действия) остается неизученной.

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

Ключевое наблюдение: монотонность наилучшего ответа (best-response monotonicity) в постановке с бинарными действиями нарушается при комбинаторных действиях. Когда агент может выбирать подмножество действий, уменьшение действий другими агентами может привести к тому, что данный агент также уменьшит свои действия. Эта немонотонность является источником сложности.

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

1. Теорема неприближаемости (Theorem 3.1):
   • Для субмодульных функций вознаграждения при любом бюджете B ∈ (0,1) любой рандомизированный полиномиальный алгоритм (даже с доступом к оракулу спроса) не может приблизить цель BEST ни на какой конечный множитель
   • Результат о сложности является точным: достаточно n-1 агентов с бинарными действиями и 1 агента с одним дополнительным действием
2. Приближение с постоянным множителем для функций валовых заменителей (Theorem 4.1 & Corollary 4.2):
   • Для функций валовых заменителей существует детерминированный полиномиальный алгоритм O(1)-приближения
   • Требует только запросов значений (не требует оракула спроса)
   • Применим к любому бюджету и всем целям BEST
3. FPTAS для аддитивных функций (Theorem 5.1):
   • Для аддитивных функций вознаграждения существует FPTAS для целей прибыли, вознаграждения и благосостояния
   • Это первый FPTAS в многоагентной комбинаторной постановке действий (даже без ограничений по бюджету)
4. Теоретическое разделение:
   • Впервые четко разделены сложности бюджетных и небюджетных постановок в комбинаторных контрактах
   • Впервые разделены возможности приближения субмодульных функций и функций валовых заменителей в бюджетных контрактах

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

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

Экземпляр: ⟨A, {Ti}i∈A, f, c⟩

• A: множество n агентов
• Ti: множество доступных действий для агента i; агент может выбрать любое подмножество Si ⊆ Ti
• f: 2^T → 0,1: функция вознаграждения, отображающая комбинации действий в вероятность успеха
• c = {cj}j∈T: вектор стоимостей действий

Контракт: α = (α1,...,αn) ∈ 0,1^n, где αi — доля выплаты агенту i при успехе проекта

Ограничение по бюджету: ∑i∈A αi ≤ B

Цель: найти бюджетно-допустимый контракт α и равновесие Нэша S, максимизирующие целевую функцию φ(α,S), где φ принадлежит классу целей BEST:

• Прибыль: uP(α,S) = (1 - ∑αi)f(S)
• Вознаграждение: f(S)
• Благосостояние: f(S) - c(S)

Конструкция неприближаемости (Section 3)

Основная идея

Построение параметризованного семейства экземпляров I(A'), где A' ⊆ n и |A'| = n/2:

Конфигурация агентов:

• n агентов с бинарными действиями (действие i или бездействие)
• 1 специальный агент (n+1) с двумя действиями: G ("хорошее") и B ("плохое")

Проектирование функции вознаграждения: f^(A')(S) = f1(S) + f2(S) - f3(S,A'), где:

f1(S) = max(1/2 · 1[G∈S], ε · 1[B∈S])
f2(S) = ε · min(|S\{G}|, n/2+1)
f3(S,A') = (ε/2) · 1[S = {B}∪A']

Выбор параметров: ε < min((1-B)/(K(n)·(n+4)), 4n/B)

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

1. f^(A') является субмодульной (Lemma 3.4): проверка монотонности и субмодульности
2. Запросы спроса моделируются запросами значений (Lemma 3.5): любой запрос спроса может быть вычислен за 12 запросов значений
3. Существует хорошее равновесие (Lemma 3.6): существует бюджетно-допустимый контракт, стимулирующий A'∪{G}, с вознаграждением ≥ 1/2
4. Другие равновесия имеют низкое вознаграждение (Lemma 3.7): для любого бюджетно-допустимого равновесия S ≠ A'∪{G}, f(S) ≤ (n/2+2)ε

Стратегия доказательства

Шаг 1: доказательство того, что получение хорошего приближения требует стимулирования G

• Множества, содержащие G: f(S) ≥ 1/2
• Множества без G: f(S) ≤ (n/2+2)ε ≈ 0

Шаг 2: доказательство того, что стимулирование G требует одновременного стимулирования ровно A'

• Через член f3, предельное вознаграждение B снижается, когда S-{n+1} = A'
• Ограничение по бюджету означает, что стимулирование G возможно только при стимулировании правильных n/2 агентов

Шаг 3: информационно-теоретическая нижняя граница

• Кандидатов множеств A' имеется (n choose n/2) = 2^Ω(n)
• Полиномиальное число запросов не может с неничтожной вероятностью идентифицировать A'
• Использование принципа Яо: для равномерного распределения A', любой детерминированный алгоритм имеет плохую ожидаемую производительность

Положительные результаты для функций валовых заменителей (Section 4)

Ключевое свойство: монотонность наилучшего ответа

Lemma 4.3 (монотонность наилучшего ответа): для функции валовых заменителей f, если S является равновесием для контракта α, то для любого агента i и S'{-i} ⊆ S{-i} существует S'_i ⊇ S_i такой, что S'i является наилучшим ответом i на S'{-i}.

Схема доказательства:

1. Преобразование задачи наилучшего ответа в задачу спроса
2. Определение векторов цен p и q таких, что:
   • S_i является наилучшим ответом на S_{-i} ⟺ S является спросом относительно p
   • S'i является наилучшим ответом на S'{-i} ⟺ S' является спросом относительно q
3. Поскольку S'{-i} ⊆ S{-i}, имеем p ≤ q (поэлементно)
4. Применение свойства валовых заменителей: существует спрос S' ⊇ S с S'{-i} = S'{-i}

Лемма о снижении размерности (Lemma 4.5)

Для (α,S) ∈ C(B) и параметра M ≥ 3 можно за полиномиальное время найти (α',S') ∈ C(B) такой, что:

• f(S') ≥ f(S)/(2M-2)
• ∑α'_i ≤ (5/M)∑αi или существует i такой, что α' = α|_i

Алгоритм (Algorithm 2):

1. Идентификация множества агентов с высокой выплатой Z = {i: αi > p/M}
2. Если некоторый i∈Z вносит большой вклад отдельно, возврат одноагентного контракта
3. Иначе разбиение оставшихся агентов на группы, каждая с суммарной выплатой ≤ p/M
4. Поиск группы U с достаточным вознаграждением
5. Применение леммы удвоения (Lemma 2.2) для построения нового контракта

Теорема эквивалентности (Theorem 4.1)

Лемма о разложении (Lemma 4.8):

Max-φ(B) ≤ 2·Max-Reward-Bounded(B) + max_i Best-Single_i-φ(B)

Цепь редукций:

1. Max-φ(B) → Max-Reward-Bounded(B) (Lemma 4.10)
2. Max-Reward-Bounded(B) → Max-φ(B') (Lemma 4.11)
3. Одноагентная задача решается точно (Lemma 4.9)

FPTAS для аддитивных функций (Section 5)

Подход динамического программирования

Дискретизация:

• Установка δ = ε/|T|
• Определение f̃(S) = ∑_{a∈S} ⌊f({a})/(δb)⌋(δb)

Определение таблицы DP:

A^(φ)(j,x) = min_{S,α} {∑αi | f̃(S) ≥ x, S ∈ NE(α), S ⊆ T1∪...∪Tj}

Ключевое наблюдение (аддитивные функции):

• Наилучший ответ агента i является префиксом: включает все действия, удовлетворяющие c_a ≤ αi·f({a})
• Переход DP: A^(φ)(j,x) = min_{ℓ} {A(j-1, x-f̃({a1,...,aℓ})) + c_{aℓ}/f({aℓ})}

Гарантия приближения:

f̃(S*) ≥ (1-ε)f(S*)

Следовательно, возвращаемый контракт достигает (1-ε)-приближения.

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

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

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

1. Конструктивные доказательства: доказательство неприближаемости через явное построение сложных экземпляров
2. Проектирование алгоритмов: предоставление конкретных алгоритмов (Algorithm 1, 2) с доказательством гарантий производительности
3. Анализ сложности: анализ временной сложности и сложности запросов алгоритмов

Экспериментальные результаты

Не применимо (чисто теоретическая работа)

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

1. Комбинаторные контракты (Combinatorial Contracts)

Модель с бинарными действиями:

• BFN06a, BFNW12: введение модели с комбинаторными агентами
• DEFK23: приближение с постоянным множителем для функций XOS
• FGPS25, AHT25: бинарные действия с ограничениями по бюджету

Модель с комбинаторными действиями:

• DEFK21: одноагентные комбинаторные действия, функции валовых заменителей разрешимы
• DEFK25: многоагентные комбинаторные действия, O(1)-приближение для субмодульных функций (без бюджета)

2. Линейные контракты (Linear Contracts)

• Car15: робастность линейных контрактов
• DRT19: гарантии приближения линейных контрактов
• DFPS24: доказательства неоднозначности

3. Контракты с ограничениями по бюджету

• HG24: ограничения по бюджету для независимых задач
• DASSTC25: ограничения по бюджету агентов
• FGPS25: эквивалентность целей BEST

4. Преимущества данной работы

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

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

1. Трёхмерный барьер: неприближаемость возникает только при одновременном наличии трёх свойств:
   • Субмодульные функции вознаграждения
   • Ограничения по бюджету
   • Комбинаторные действия Любая комбинация двух свойств допускает приближение с постоянным множителем (Figure 1)
2. Граница валовых заменителей: свойство валовых заменителей является границей разрешимости для бюджетных комбинаторных контрактов
3. Особенность аддитивных функций: полностью полиномиальная схема приближения существует

Ограничения

1. Точность неприближаемости:
   • Требуется только n-1 агентов с бинарными действиями + 1 агент с 3 действиями
   • Но конструкция высокоискусственна, может быть редкой в практических приложениях
2. Предположение о валовых заменителях:
   • Более сильное предположение, чем субмодульность
   • Многие практические приложения могут его не удовлетворять
3. Ограничение целей BEST:
   • FPTAS применим только к целям прибыли, вознаграждения и благосостояния
   • Не применим ко всем целям BEST
4. Единственный бюджет:
   • Рассматривается только общее ограничение по бюджету
   • Не рассматриваются индивидуальные ограничения по бюджету

Направления будущих исследований

1. Вычислительная сложность:
   • Существует ли PTAS/FPTAS для функций валовых заменителей?
   • Точная сложность одноагентной задачи
2. Более богатые модели:
   • Многопроектная постановка ACC+25
   • Ограничения справедливости CCL25b
   • Приватная информация ADT21
3. Перспектива обучения:
   • Онлайн-проектирование контрактов ZBY+23
   • Сложность выборки DFPS25
4. Эмпирические исследования:
   • Характеристики классов функций в практических приложениях
   • Производительность эвристических алгоритмов

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

Достоинства

1. Теоретическая глубина:
   • Первое установление неприближаемости при ограничениях по бюджету
   • Точные результаты о сложности (минимизация сложных экземпляров)
   • Полная характеризация сложности (треугольник на Figure 1)
2. Технические инновации:
   • Точная характеризация немонотонности наилучшего ответа как источника сложности
   • Искусная конструкция сложности: реализация "скрытого множества" через член f3
   • Доказательство монотонности наилучшего ответа для функций валовых заменителей
3. Полнота результатов:
   • Отрицательные результаты (неприближаемость)
   • Положительные результаты (валовые заменители, аддитивные)
   • Согласованность алгоритмов и нижних границ
4. Ясность изложения:
   • Четкая мотивация (пример со стартапом)
   • Ясная техническая схема
   • Интуитивное представление основных результатов на Figure 1

Недостатки

1. Практические соображения:
   • Конструкция сложности высокоискусственна
   • Применимость предположения о валовых заменителях в практике не обсуждается
   • Отсутствуют примеры практических приложений
2. Технические ограничения:
   • FPTAS применим только к части целей BEST
   • Конкретные константы в приближениях с постоянным множителем не указаны
   • Одноагентный FPTAS требует оракула спроса
3. Теоретические пробелы:
   • Промежуточные классы между валовыми заменителями и субмодульностью?
   • Сложность индивидуальных ограничений по бюджету
   • Возможность рандомизированных контрактов
4. Сложность доказательств:
   • Некоторые доказательства весьма технические (например, Lemma 3.7)
   • Необходимость моделирования оракула спроса недостаточно интуитивна

Влияние

Теоретический вклад:

• Первое четкое разделение бюджетных и небюджетных постановок
• Установление валовых заменителей как границы разрешимости
• Предоставление ориентиров для последующих исследований

Методологическая ценность:

• Каркас анализа монотонности наилучшего ответа
• Паттерн проектирования леммы о снижении размерности
• Техники построения сложности

Практическая ценность:

• Руководство для практики проектирования контрактов: идентификация разрешимых случаев
• Предупреждение о рисках чрезмерного упрощения моделей
• Теоретические границы для проектирования приближенных алгоритмов

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

Подходящие приложения:

1. Сценарии валовых заменителей:
   • Команды с дополняющими навыками (различные специальности)
   • Задачи распределения ресурсов
   • Проектирование рынков
2. Аддитивные сценарии:
   • Краудсорсинг независимых задач
   • Простые механизмы стимулирования

Неподходящие приложения:

1. Задачи с сильной взаимодополняемостью (нарушение валовых заменителей)
2. Ситуации без ограничений по бюджету (доступны лучшие алгоритмы)
3. Сценарии, требующие точных решений

Ключевые ссылки

1. DEFK25 Dütting et al., "Multi-agent combinatorial contracts", SODA 2025
   • Непосредственное расширение данной работы
2. FGPS25 Feldman et al., "Budget-feasible contracts", EC 2025
   • Бюджетные контракты с бинарными действиями
3. DEFK21 Dütting et al., "Combinatorial contracts", FOCS 2021
   • Основополагающая работа по одноагентным комбинаторным действиям
4. Car15 Carroll, "Robustness and linear contracts", AER 2015
   • Теоретические основы линейных контрактов
5. Pae17 Paes Leme, "Gross substitutability: An algorithmic survey", GEB 2017
   • Обзор свойства валовых заменителей

Резюме

Это теоретически глубокая работа в области теории игр, которая вносит важный вклад в понимание границ сложности бюджетных комбинаторных контрактов путем точной характеризации их разрешимости. Ключевое прозрение работы заключается в том, что немонотонность наилучшего ответа является источником сложности, и через точную конструкцию сложности и согласованные положительные алгоритмы полностью характеризуется разрешимость задачи. Свойство валовых заменителей устанавливается как граница разрешимости для бюджетных комбинаторных контрактов, что имеет руководящее значение для последующих исследований. Несмотря на отсутствие эмпирических исследований, её теоретическая ценность и методологический вклад делают её важной работой в области алгоритмической теории контрактов.