Cover Image

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Feldman, Michal, Gal-Tzur, Yoav, Ponitka, Tomasz, Schlesinger, Maya
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Budget-Feasible Contracts
by: Feldman, Michal, et al.
Published: (2025)

Equal-Pay Contracts
by: Feldman, Michal, et al.
Published: (2026)

When Contracts Get Complex: Information-Theoretic Barriers
by: Dütting, Paul, et al.
Published: (2024)

Contract Design for Sequential Actions
by: Ezra, Tomer, et al.
Published: (2024)

Combinatorial Contracts Through Demand Types
by: Baldwin, Elizabeth, et al.
Published: (2026)

On Optimal Tradeoffs between EFX and Nash Welfare
by: Feldman, Michal, et al.
Published: (2023)

The Pseudo-Dimension of Contracts
by: Duetting, Paul, et al.
Published: (2025)

Combinatorial Contract Design: Recent Progress and Emerging Frontiers
by: Feldman, Michal
Published: (2025)

Combinatorial Contracts
by: Duetting, Paul, et al.
Published: (2021)

Proportionally Fair Makespan Approximation
by: Feldman, Michal, et al.
Published: (2024)

Multi-Agent Combinatorial Contracts
by: Duetting, Paul, et al.
Published: (2024)

Anonymous Contracts
by: Brustle, Johannes, et al.
Published: (2026)

Fair Division via Resource Augmentation
by: Akrami, Hannaneh, et al.
Published: (2025)

Ultra Efficient Contracts: Pushing the Boundaries of Tractable Contract Design
by: Feldman, Michal, et al.
Published: (2025)

Ambiguous Contracts
by: Dütting, Paul, et al.
Published: (2023)

The Panel Complexity of Sortition: Is 12 Angry Men Enough?
by: Brustle, Johannes, et al.
Published: (2025)

Multi-Agent Contracts
by: Duetting, Paul, et al.
Published: (2022)

Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?
by: Kulkarni, Pooja, et al.
Published: (2025)

Succinct Ambiguous Contracts
by: Duetting, Paul, et al.
Published: (2025)

Black-Box Lifting and Robustness Theorems for Multi-Agent Contracts
by: Dütting, Paul, et al.
Published: (2025)

Algorithmic Contract Theory: A Survey
by: Duetting, Paul, et al.
Published: (2024)

A Note on EFX Inapproximability for Chores
by: Christoforidis, Vasilis
Published: (2026)

Constant Inapproximability for PPA
by: Deligkas, Argyrios, et al.
Published: (2022)

Proportional Participatory Budgeting with Projects Interaction
by: Fairstein, Roy, et al.
Published: (2021)

Pandora's Problem with Combinatorial Cost
by: Berger, Ben, et al.
Published: (2023)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2026)

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
by: Byrka, Jarosław, et al.
Published: (2025)

Online Combinatorial Allocation with Interdependent Values
by: Feldman, Michal, et al.
Published: (2025)

Constant Inapproximability for Fisher Markets
by: Deligkas, Argyrios, et al.
Published: (2026)

Robust Temporal Guarantees in Budgeted Sequential Auctions
by: Fikioris, Giannis, et al.
Published: (2026)

Pure-Circuit: Tight Inapproximability for PPAD
by: Deligkas, Argyrios, et al.
Published: (2022)

Efficient Preference Elicitation in Iterative Combinatorial Auctions with Many Participants
by: Maruo, Ryota, et al.
Published: (2024)

Contract Design Beyond Hidden-Actions
by: Ezra, Tomer, et al.
Published: (2024)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

Polytime Algorithms for One-to-Many Matching Games
by: Garrido-Lucero, Felipe, et al.
Published: (2021)

Multi-Agent Contract Design beyond Binary Actions
by: Cacciamani, Federico, et al.
Published: (2024)

Agent-Designed Contracts: How to Sell Hidden Actions
by: Bernasconi, Martino, et al.
Published: (2024)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
by: Babichenko, Yakov, et al.
Published: (2015)

Learning in Budgeted Auctions with Spacing Objectives
by: Fikioris, Giannis, et al.
Published: (2024)