Una Acción Demasiadas: Inaproximabilidad de Contratos Combinatorios Presupuestados

Información Básica

• ID del Artículo: 2511.20110
• Título: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
• Autores: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (Universidad de Tel Aviv)
• Clasificación: cs.GT (Teoría de Juegos)
• Fecha de Publicación/Conferencia: ITCS 2026 (versión preimpresa: 26 de noviembre de 2025)
• Enlace del Artículo: https://arxiv.org/abs/2511.20110

Resumen

Este artículo estudia el problema del diseño de contratos de acciones combinatorias multiagente con restricciones presupuestarias, dirigido a una amplia clase de funciones objetivo que incluyen ganancia, recompensa y bienestar. Los resultados principales incluyen: (1) Inaproximabilidad fuerte: Para funciones de recompensa submodulares, ningún algoritmo aleatorio de tiempo polinomial puede aproximar el valor óptimo factible presupuestario dentro de cualquier factor finito, incluso con acceso a oráculo de demanda; (2) Resultados positivos: Para funciones de recompensa de sustitutos brutos (una subclase estricta de funciones submodulares), existe un algoritmo determinista de tiempo polinomial que proporciona una aproximación O(1), requiriendo solo consultas de valor; (3) FPTAS: Para funciones de recompensa aditivas, existe un FPTAS bajo cualquier presupuesto, siendo este el primer FPTAS en la configuración de acciones combinatorias multiagente. La investigación distingue por primera vez explícitamente entre configuraciones con y sin restricciones presupuestarias, e identifica la propiedad de sustitutos brutos como la frontera de tratabilidad.

Antecedentes de Investigación y Motivación

1. Problema de Investigación

Este artículo estudia el problema del diseño de contratos de acciones combinatorias multiagente, cuyo desafío central es: cuando un principal enfrenta restricciones presupuestarias, ¿cómo diseñar contratos de incentivos para que múltiples agentes seleccionen combinaciones apropiadas de acciones, optimizando el objetivo del principal (ganancia, recompensa o bienestar)?

2. Importancia del Problema

• Significado teórico: La teoría de contratos es un campo central de la microeconomía, como lo demuestra la concesión del Premio Nobel de Economía 2016 a Hart y Hölmstrom
• Valor práctico: Ampliamente aplicable en mercados computacionales modernos, tales como:
  • Startups incentivando equipos de ingenieros mediante opciones sobre acciones
  • Plataformas de crowdsourcing diseñando mecanismos de recompensa de tareas
  • Diseño de contratos en subcontratación de proyectos

3. Limitaciones de Métodos Existentes

La literatura contiene dos clases de resultados positivos:

• (i) Sin restricción presupuestaria + acciones combinatorias: DEFK25 proporciona aproximación de factor constante para funciones submodulares
• (ii) Con restricción presupuestaria + acciones binarias: FGPS25, AHT25 proporciona aproximación de factor constante para funciones submodulares

Sin embargo, la combinación de ambas (restricción presupuestaria + acciones combinatorias) permanece desconocida en términos de aproximabilidad.

4. Motivación de la Investigación

Observación clave: La monotonía de mejor respuesta en la configuración de acciones binarias falla bajo acciones combinatorias. Cuando los agentes pueden elegir subconjuntos de acciones, la reducción de acciones por otros agentes puede llevar a que este agente también reduzca sus acciones, y esta no-monotonía es la fuente de la complejidad.

Contribuciones Principales

1. Teorema de Inaproximabilidad (Teorema 3.1):
   • Para funciones de recompensa submodulares, bajo cualquier presupuesto B ∈ (0,1), ningún algoritmo aleatorio de tiempo polinomial (incluso con acceso a oráculo de demanda) puede aproximar el objetivo BEST dentro de cualquier factor finito
   • El resultado de dureza es ajustado: requiere solo n-1 agentes con acciones binarias + 1 agente con una acción adicional
2. Aproximación de Factor Constante para Funciones de Sustitutos Brutos (Teorema 4.1 y Corolario 4.2):
   • Para funciones de recompensa de sustitutos brutos, existe un algoritmo determinista de tiempo polinomial que proporciona una aproximación O(1)
   • Requiere solo consultas de valor (sin necesidad de oráculo de demanda)
   • Aplicable a cualquier presupuesto y todos los objetivos BEST
3. FPTAS para Funciones Aditivas (Teorema 5.1):
   • Para funciones de recompensa aditivas, existen FPTAS para objetivos de ganancia, recompensa y bienestar
   • Este es el primer FPTAS en la configuración de acciones combinatorias multiagente (incluso sin restricciones presupuestarias)
4. Separación Teórica:
   • Primera distinción explícita entre configuraciones con y sin restricciones presupuestarias en contratos combinatorios en términos de complejidad
   • Primera distinción entre funciones submodulares y funciones de sustitutos brutos en términos de aproximabilidad en contratos presupuestarios

Explicación Detallada de Métodos

Definición de Tareas

Instancia: ⟨A, {Ti}i∈A, f, c⟩

• A: conjunto de n agentes
• Ti: conjunto de acciones disponibles para el agente i, donde el agente puede elegir cualquier subconjunto Si ⊆ Ti
• f: 2^T → 0,1: función de recompensa, que mapea combinaciones de acciones a probabilidad de éxito
• c = {cj}j∈T: vector de costos de acciones

Contrato: α = (α1,...,αn) ∈ 0,1^n, donde αi es la proporción del pago al agente i si el proyecto tiene éxito

Restricción Presupuestaria: ∑i∈A αi ≤ B

Objetivo: Encontrar un contrato α factible presupuestariamente y un equilibrio de Nash S, maximizando la función objetivo φ(α,S), donde φ pertenece a la clase de objetivos BEST:

• Ganancia: uP(α,S) = (1 - ∑αi)f(S)
• Recompensa: f(S)
• Bienestar: f(S) - c(S)

Construcción de Inaproximabilidad (Sección 3)

Idea Central

Construir una familia parametrizada de instancias I(A'), donde A' ⊆ n y |A'| = n/2:

Configuración de Agentes:

• n agentes con acciones binarias (realizar acción i o no actuar)
• 1 agente especial (n+1) con dos acciones: G ("buena") y B ("mala")

Diseño de Función de Recompensa: f^(A')(S) = f1(S) + f2(S) - f3(S,A'), donde:

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']

Selección de Parámetros: ε < min((1-B)/(K(n)·(n+4)), 4n/B)

Propiedades Clave

1. f^(A') es submodular (Lema 3.4): Verificando monotonía y submodularidad
2. Consultas de demanda simulables por consultas de valor (Lema 3.5): Cualquier consulta de demanda puede calcularse con 12 consultas de valor
3. Existencia de equilibrio bueno (Lema 3.6): Existe un contrato factible presupuestariamente que incentiva A'∪{G}, con recompensa ≥ 1/2
4. Otros equilibrios tienen baja recompensa (Lema 3.7): Para cualquier equilibrio factible presupuestariamente S ≠ A'∪{G}, f(S) ≤ (n/2+2)ε

Estrategia de Prueba

Paso 1: Demostrar que obtener una buena aproximación requiere incentivar G

• Conjuntos que contienen G: f(S) ≥ 1/2
• Conjuntos que no contienen G: f(S) ≤ (n/2+2)ε ≈ 0

Paso 2: Demostrar que incentivar G requiere incentivar exactamente A'

• A través del término f3, el beneficio marginal de B se reduce cuando S-{n+1} = A'
• La restricción presupuestaria hace que solo incentivar los n/2 agentes correctos permita incentivar G

Paso 3: Cota inferior de teoría de la información

• Hay (n choose n/2) = 2^Ω(n) conjuntos candidatos A'
• Las consultas polinomiales no pueden identificar A' con probabilidad no despreciable
• Usar el principio de Yao: para una distribución uniforme de A', cualquier algoritmo determinista tiene rendimiento esperado pobre

Resultados Positivos para Funciones de Sustitutos Brutos (Sección 4)

Propiedad Clave: Monotonía de Mejor Respuesta

Lema 4.3 (Monotonía de Mejor Respuesta): Para funciones de sustitutos brutos f, si S es un equilibrio para el contrato α, para cualquier agente i y S'{-i} ⊆ S{-i}, existe S'_i ⊇ S_i tal que S'i es la mejor respuesta de i a S'{-i}.

Esquema de Prueba:

1. Transformar el problema de mejor respuesta en un problema de conjunto de demanda
2. Definir vectores de precio p y q tales que:
   • S_i es mejor respuesta a S_{-i} ⟺ S es conjunto de demanda respecto a p
   • S'i es mejor respuesta a S'{-i} ⟺ S' es conjunto de demanda respecto a q
3. Dado que S'{-i} ⊆ S{-i}, tenemos p ≤ q (por coordenadas)
4. Aplicar propiedad de sustitutos brutos: existe conjunto de demanda S' ⊇ S con S'{-i} = S'{-i}

Lema de Reducción de Dimensión (Lema 4.5)

Dado (α,S) ∈ C(B) y parámetro M ≥ 3, se puede encontrar en tiempo polinomial (α',S') ∈ C(B) tal que:

• f(S') ≥ f(S)/(2M-2)
• ∑α'_i ≤ (5/M)∑αi o existe i tal que α' = α|_i

Algoritmo (Algoritmo 2):

1. Identificar conjunto de agentes con alto pago Z = {i: αi > p/M}
2. Si algún i∈Z contribuye significativamente solo, devolver contrato de un solo agente
3. En caso contrario, particionar agentes restantes, cada grupo con pago total ≤ p/M
4. Encontrar grupo U con recompensa suficiente
5. Aplicar lema de duplicación (Lema 2.2) para construir nuevo contrato

Teorema de Equivalencia (Teorema 4.1)

Lema de Descomposición (Lema 4.8):

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

Cadena de Reducción:

1. Max-φ(B) → Max-Reward-Bounded(B) (Lema 4.10)
2. Max-Reward-Bounded(B) → Max-φ(B') (Lema 4.11)
3. Los problemas de un solo agente pueden resolverse exactamente (Lema 4.9)

FPTAS para Funciones Aditivas (Sección 5)

Enfoque de Programación Dinámica

Discretización:

• Establecer δ = ε/|T|
• Definir f̃(S) = ∑_{a∈S} ⌊f({a})/(δb)⌋(δb)

Definición de Tabla DP:

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

Observación Clave (Funciones Aditivas):

• La mejor respuesta del agente i es un prefijo: incluye todas las acciones satisfaciendo c_a ≤ αi·f({a})
• Transición DP: A^(φ)(j,x) = min_{ℓ} {A(j-1, x-f̃({a1,...,aℓ})) + c_{aℓ}/f({aℓ})}

Garantía de Aproximación:

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

Por lo tanto, el contrato devuelto logra una aproximación (1-ε).

Configuración Experimental

Este artículo es un trabajo puramente teórico que no incluye sección experimental. Todos los resultados son pruebas matemáticas.

Métodos de Verificación Teórica

1. Pruebas Constructivas: Demostrar inaproximabilidad mediante construcción explícita de instancias difíciles
2. Diseño de Algoritmos: Proporcionar algoritmos concretos (Algoritmo 1, 2) y demostrar garantías de rendimiento
3. Análisis de Complejidad: Analizar complejidad temporal y complejidad de consultas de los algoritmos

Resultados Experimentales

No aplicable (trabajo puramente teórico)

Trabajo Relacionado

1. Contratos Combinatorios (Combinatorial Contracts)

Modelo de Acciones Binarias:

• BFN06a, BFNW12: Introducen modelo de agentes combinatorios
• DEFK23: Aproximación de factor constante para funciones XOS
• FGPS25, AHT25: Acciones binarias bajo restricción presupuestaria

Modelo de Acciones Combinatorias:

• DEFK21: Acciones combinatorias de un solo agente, funciones de sustitutos brutos tratables
• DEFK25: Acciones combinatorias multiagente, aproximación O(1) para funciones submodulares (sin presupuesto)

2. Contratos Lineales (Linear Contracts)

• Car15: Robustez de contratos lineales
• DRT19: Garantías de aproximación de contratos lineales
• DFPS24: Prueba de ambigüedad

3. Contratos Bajo Restricción Presupuestaria

• HG24: Restricción presupuestaria en tareas independientes
• DASSTC25: Restricción presupuestaria de agentes
• FGPS25: Equivalencia de objetivos BEST

4. Ventajas Relativas de Este Artículo

Conclusiones y Discusión

Conclusiones Principales

1. Barrera Tridimensional: La inaproximabilidad solo ocurre cuando coexisten tres atributos:
   • Función de recompensa submodular
   • Restricción presupuestaria
   • Acciones combinatorias Cualquier combinación de dos atributos permite aproximación de factor constante (Figura 1)
2. Frontera de Sustitutos Brutos: La propiedad de sustitutos brutos es la frontera de tratabilidad para contratos combinatorios presupuestarios
3. Especialidad de Funciones Aditivas: Existe esquema de aproximación de tiempo polinomial completamente

Limitaciones

1. Ajuste de Inaproximabilidad:
   • Requiere solo n-1 agentes binarios + 1 agente con 3 acciones
   • Pero la construcción es altamente artificial, posiblemente infrecuente en aplicaciones reales
2. Suposición de Sustitutos Brutos:
   • Suposición más fuerte que submodularidad
   • Muchas aplicaciones prácticas pueden no satisfacerla
3. Limitación de Objetivos BEST:
   • FPTAS solo aplicable a objetivos de ganancia, recompensa, bienestar
   • No aplicable a todos los objetivos BEST
4. Presupuesto Único:
   • Solo considera restricción de presupuesto total
   • No considera restricciones de presupuesto individual

Direcciones Futuras

1. Complejidad Computacional:
   • ¿Existe PTAS/FPTAS bajo funciones de sustitutos brutos?
   • Complejidad exacta de problemas de un solo agente
2. Modelos Más Ricos:
   • Configuración multiproyecto ACC+25
   • Restricciones de equidad CCL25b
   • Información privada ADT21
3. Perspectiva de Aprendizaje:
   • Diseño de contratos en línea ZBY+23
   • Complejidad de muestra DFPS25
4. Investigación Empírica:
   • Características de clases de funciones en aplicaciones reales
   • Rendimiento de algoritmos heurísticos

Evaluación Profunda

Fortalezas

1. Profundidad Teórica:
   • Primera inaproximabilidad bajo restricción presupuestaria
   • Resultado de dureza ajustado (minimiza instancia difícil)
   • Caracterización completa de complejidad (triángulo en Figura 1)
2. Innovación Técnica:
   • Caracterización precisa de no-monotonía de mejor respuesta como fuente de dureza
   • Construcción de dureza ingeniosa: implementar "conjunto oculto" mediante término f3
   • Prueba de monotonía de mejor respuesta para funciones de sustitutos brutos
3. Completitud de Resultados:
   • Resultados negativos (inaproximabilidad)
   • Resultados positivos (sustitutos brutos, aditivos)
   • Coincidencia de algoritmos y cotas inferiores
4. Claridad de Escritura:
   • Motivación clara (ejemplo de startup)
   • Ruta técnica transparente
   • Figura 1 presenta intuitivamente resultados principales

Deficiencias

1. Consideraciones Prácticas:
   • Construcción de dureza altamente artificial
   • Aplicabilidad de suposición de sustitutos brutos en práctica no discutida
   • Falta de análisis de casos de aplicación real
2. Limitaciones Técnicas:
   • FPTAS solo aplicable a objetivos BEST parciales
   • Constantes específicas en aproximación de factor constante no proporcionadas
   • FPTAS de un solo agente requiere oráculo de demanda
3. Vacíos Teóricos:
   • ¿Clases intermedias entre sustitutos brutos y submodular?
   • Complejidad bajo restricciones de presupuesto individual
   • Posibilidad de contratos aleatorios
4. Complejidad de Prueba:
   • Algunas pruebas altamente técnicas (como Lema 3.7)
   • Necesidad de simulación de oráculo de demanda no suficientemente intuitiva

Impacto

Contribuciones Teóricas:

• Primera distinción explícita entre configuraciones con/sin presupuesto
• Establecimiento de sustitutos brutos como frontera de tratabilidad
• Proporciona referencia para investigación posterior

Valor Metodológico:

• Marco de análisis de monotonía de mejor respuesta
• Patrón de diseño de lema de reducción de dimensión
• Técnica de construcción de dureza

Valor Práctico:

• Guía diseño de contratos en práctica: identificar casos tratables
• Advertencia sobre riesgos de simplificación excesiva de modelos
• Proporciona límites teóricos para diseño de algoritmos de aproximación

Escenarios Aplicables

Aplicación Apropiada:

1. Escenarios de Sustitutos Brutos:
   • Equipos con habilidades complementarias (especialidades diferentes)
   • Problemas de asignación de recursos
   • Diseño de mercados
2. Escenarios Aditivos:
   • Crowdsourcing de tareas independientes
   • Mecanismos de incentivos simples

Aplicación Inapropiada:

1. Tareas con fuerte complementariedad (viola sustitutos brutos)
2. Situaciones sin restricción presupuestaria (existen mejores algoritmos)
3. Escenarios que requieren soluciones exactas

Referencias (Referencias Clave)

1. DEFK25 Dütting et al., "Multi-agent combinatorial contracts", SODA 2025
   • Trabajo que este artículo extiende directamente
2. FGPS25 Feldman et al., "Budget-feasible contracts", EC 2025
   • Contratos presupuestarios bajo acciones binarias
3. DEFK21 Dütting et al., "Combinatorial contracts", FOCS 2021
   • Fundamento de acciones combinatorias de un solo agente
4. Car15 Carroll, "Robustness and linear contracts", AER 2015
   • Fundamento teórico de contratos lineales
5. Pae17 Paes Leme, "Gross substitutability: An algorithmic survey", GEB 2017
   • Encuesta sobre propiedad de sustitutos brutos

Resumen

Este es un artículo de teoría de juegos con excelente profundidad teórica, que mediante caracterización precisa de la frontera de complejidad de contratos combinatorios presupuestarios, realiza contribuciones teóricas importantes. La intuición central del artículo es la no-monotonía de mejor respuesta como fuente de complejidad, y mediante construcción de dureza ajustada y algoritmos positivos coincidentes, caracteriza completamente la tratabilidad del problema. La propiedad de sustitutos brutos se establece como la frontera de tratabilidad para contratos combinatorios presupuestarios, hallazgo que tiene valor orientador para investigación posterior. Aunque carece de investigación empírica, su valor teórico y contribuciones metodológicas lo convierten en un trabajo importante en el campo de la teoría algorítmica de contratos.