pith. sign in

arxiv: 2507.20038 · v2 · submitted 2025-07-26 · 💻 cs.GT · cs.DS

An Algorithm-to-Contract Framework without Demand Queries

Ilan Doron-Arad , Hadas Shachnai , Gilad Shmerler , Inbal Talgam-Cohen This is my paper

Pith reviewed 2026-05-19 03:16 UTC · model grok-4.3

classification 💻 cs.GT cs.DS
keywords algorithm-to-contract frameworkcontract designbudgeted maximizationFPTAScombinatorial constraintsincentive compatibilitydemand problem
0
0 comments X

The pith

A framework lifts classic FPTAS algorithms for budgeted maximization directly into approximately incentive-compatible contracts for the same constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an algorithm-to-contract framework that converts standard approximation algorithms for combinatorial problems into mechanisms for designing contracts under identical constraints. It avoids the demand oracle assumption common in prior work by using a local-to-global method: the local step approximately solves a two-sided strengthened version of the demand problem, and the global step assembles these solutions into an approximately optimal contract. For budgeted maximization, this produces an FPTAS for approximately-IC contracts that matches the best possible guarantee. The same approach extends to multi-dimensional budgets, budgeted matroids, and budgeted matchings while preserving the underlying algorithmic approximation quality. A separate method yields the first approximation schemes for multi-agent contract problems that exceed additive reward functions.

Core claim

The local-to-global framework transforms an FPTAS for a combinatorial optimization problem into an FPTAS for the corresponding contract design problem by approximately solving a two-sided strengthened demand variant locally and then using those solutions to construct the global contract; this yields the best-possible approximately-IC FPTAS for budgeted maximization and matches the best algorithmic approximations for budgeted matroids and budgeted matchings without requiring demand oracle access.

What carries the argument

The local-to-global framework, whose local step approximately solves a two-sided strengthened variant of the demand problem to enable the global construction of an approximately optimal contract.

If this is right

  • Budgeted matroid problems inherit an FPTAS for approximately-IC contracts that matches the best pure algorithmic guarantee.
  • Budgeted matching problems receive the same approximation transfer from their algorithmic FPTAS.
  • Multi-dimensional budget constraints admit the lifted FPTAS for contract design.
  • Multi-agent contract settings beyond additive rewards obtain the first approximation schemes via the separate method.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend to other problems that admit FPTAS under combinatorial constraints by verifying the local demand variant can be solved efficiently.
  • Contract design in dynamic or online settings could potentially reuse the same local-to-global structure if the local step remains tractable.
  • The framework suggests that incentive compatibility need not degrade approximation quality beyond what the underlying algorithm already achieves.

Load-bearing premise

The local step of approximately solving the two-sided strengthened demand problem can be performed efficiently for the given combinatorial constraints.

What would settle it

A concrete combinatorial constraint where no efficient approximate algorithm exists for the two-sided strengthened demand problem, which would prevent the local-to-global lifting from producing the claimed contract approximation.

read the original abstract

Consider costly and time-consuming tasks that add up to the success of a project, and must be fitted into a given time-frame. This is an instance of the classic budgeted maximization (knapsack) problem, which admits an FPTAS. Now assume an agent is performing these tasks on behalf of a principal, who is the one to reap the rewards if the project succeeds. The principal must design a contract to incentivize the agent. Is there still an approximation scheme? In this work we lay the foundations for an algorithm-to-contract framework, which transforms algorithms for combinatorial problems to handle contract design problems subject to the same combinatorial constraints. Our approach diverges from previous works in avoiding the assumption of demand oracle access. As an example, for budgeted maximization, we show how to "lift" the classic FPTAS to the best-possible (approximately-IC) FPTAS for the contract problem. We establish this through our local-to-global framework, in which the local step is to approximately solve a two-sided strengthened variant of the demand problem. The global step then utilizes the local one to find the approximately optimal contract. We apply our framework to a host of combinatorial constraints: multi-dimensional budgets, budgeted matroid, and budgeted matching constraints. In all cases we essentially match the best purely algorithmic approximation. Separately, we also develop a method for multi-agent contract settings. Our method yields the first approximation schemes for multi-agent contract settings that go beyond additive reward functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces an algorithm-to-contract framework that converts approximation algorithms for combinatorial optimization problems (such as budgeted maximization) into approximately incentive-compatible (IC) contracts for the same constraints, without relying on demand oracles. For budgeted maximization, it claims to lift the classic FPTAS to a best-possible approximately-IC FPTAS via a local-to-global construction: the local step approximately solves a two-sided strengthened variant of the demand problem, and the global step uses this to produce the contract. The framework is applied to multi-dimensional budgets, budgeted matroids, and budgeted matchings (matching the best algorithmic approximations), with a separate extension to multi-agent contract settings yielding the first approximation schemes beyond additive rewards.

Significance. If the local approximation step is polynomial-time and the error propagation in the global step is controlled, the framework offers a general, oracle-free method for contract design under combinatorial constraints, achieving approximation ratios that match those of the underlying algorithmic problems. This strengthens prior contract design results by removing demand-query assumptions and provides new approximation schemes for multi-agent settings, with potential applications in incentivizing agents for budgeted projects or team tasks.

major comments (2)
  1. [§4] §4 (Local Step for Budgeted Matroids): The claim that the two-sided strengthened demand problem admits an FPTAS under budgeted matroid constraints is load-bearing for the overall lifting result, but the manuscript provides only a high-level reduction without an explicit algorithm, running-time analysis, or proof that the strengthening does not introduce additional NP-hardness (e.g., via the two-sided budget and IC constraints). A concrete FPTAS construction or reduction to the standard knapsack FPTAS is needed to verify the local solver runs in poly(n,1/ε) time.
  2. [§5] §5 (Global Step and Error Propagation): The global step asserts that feeding a (1-ε)-approximate local solution yields an overall (1-O(ε))-approximately-IC contract whose value matches the classic FPTAS guarantee. However, no explicit bound is given on how approximation errors from the local step accumulate in the contract parameters or the IC violation; this is required to confirm the final guarantee remains an FPTAS rather than degrading to a constant-factor approximation.
minor comments (2)
  1. [§3] The notation for the two-sided strengthened demand problem (e.g., the exact definition of the 'strengthened' constraints) is introduced without a dedicated preliminary subsection, making it hard to track across the local-to-global argument.
  2. Figure 1 (framework diagram) would benefit from explicit labels on the local and global arrows indicating the approximation factors passed between steps.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful and constructive review of our manuscript. The comments highlight important points where additional details will strengthen the presentation of the local-to-global framework. We address each major comment below and will incorporate the necessary clarifications in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (Local Step for Budgeted Matroids): The claim that the two-sided strengthened demand problem admits an FPTAS under budgeted matroid constraints is load-bearing for the overall lifting result, but the manuscript provides only a high-level reduction without an explicit algorithm, running-time analysis, or proof that the strengthening does not introduce additional NP-hardness (e.g., via the two-sided budget and IC constraints). A concrete FPTAS construction or reduction to the standard knapsack FPTAS is needed to verify the local solver runs in poly(n,1/ε) time.

    Authors: We agree that the local step for budgeted matroids requires a more explicit construction to make the FPTAS claim fully verifiable. In the revised manuscript we will add a dedicated subsection detailing a dynamic-programming algorithm for the two-sided strengthened demand problem. The algorithm adapts the classic knapsack FPTAS by using the matroid independence oracle to enforce feasibility at each DP state while simultaneously tracking the two-sided budget and incentive-compatibility constraints; both can be encoded as additional dimensions in the DP table without increasing the asymptotic complexity. We will include a complete running-time analysis establishing O(n^{O(1)} / ε^{O(1)}) time and a short argument showing that the strengthening does not introduce new NP-hardness, as all constraints remain polynomially checkable given the independence oracle. revision: yes

  2. Referee: [§5] §5 (Global Step and Error Propagation): The global step asserts that feeding a (1-ε)-approximate local solution yields an overall (1-O(ε))-approximately-IC contract whose value matches the classic FPTAS guarantee. However, no explicit bound is given on how approximation errors from the local step accumulate in the contract parameters or the IC violation; this is required to confirm the final guarantee remains an FPTAS rather than degrading to a constant-factor approximation.

    Authors: We thank the referee for emphasizing the need for explicit error propagation. In the revision we will insert a new lemma that bounds the accumulation of local approximation error. Specifically, we prove that a (1-ε)-approximate solution to the strengthened local problem produces a contract that is (1-3ε)-approximately incentive-compatible and whose expected value is at least (1-O(ε)) times the value of the optimal contract; the constant 3 arises from a straightforward triangle-inequality argument over the payment and allocation deviations. Because the local solver itself runs in polynomial time for any fixed ε, the overall procedure remains an FPTAS. The proof will be placed immediately after the description of the global step. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in local-to-global lifting

full rationale

The paper defines a local-to-global framework in which the local step approximately solves a newly introduced two-sided strengthened demand problem under the given combinatorial constraints, and the global step then assembles an approximately-IC contract from those local solutions. This is a constructive reduction that does not reduce the final approximation guarantee to a fitted parameter, a self-referential definition, or a load-bearing self-citation chain; the local solver is presented as an independent algorithmic subroutine whose efficiency is established separately for budgeted matroids, matchings, and multi-dimensional budgets. The central claim therefore rests on external algorithmic content rather than on any equation or prior result that is equivalent to the target contract guarantee by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on the existence of FPTASes for the base combinatorial problems and on the ability to solve the strengthened local demand variant; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption The underlying combinatorial problem admits an FPTAS
    The lifting procedure presupposes that an FPTAS exists for the pure algorithmic version of the budgeted maximization or matroid problem.

pith-pipeline@v0.9.0 · 5810 in / 1235 out tokens · 43079 ms · 2026-05-19T03:16:22.064869+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

93 extracted references · 93 canonical work pages

  1. [1]

    Welfare and beyond in multi-agent contracts

    Gil Aharoni, Martin Hoefer, and Inbal Talgam-Cohen. Welfare and beyond in multi-agent contracts. In Proceedings of the 26th ACM Conference on Economics and Computation, EC , page 895. ACM, 2025

    work page 2025

  2. [2]

    Contracts with private cost per unit-of- effort

    Tal Alon, Paul D¨ utting, and Inbal Talgam-Cohen. Contracts with private cost per unit-of- effort. In EC 2021, pages 52–69, 2021

    work page 2021

  3. [3]

    Incomplete information VCG contracts for common agency

    Tal Alon, Inbal Talgam-Cohen, Ron Lavi, and Elisheva Shamash. Incomplete information VCG contracts for common agency. Operations Research, 72(1):288–299, 2024

    work page 2024

  4. [4]

    Combinatorial agency

    Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In Proceedings of the 7th ACM Conference on Electronic Commerce , pages 18–28, 2006

    work page 2006

  5. [5]

    Bayesian incentive compatibility via fractional assignments

    Xiaohui Bei and Zhiyi Huang. Bayesian incentive compatibility via fractional assignments. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages 720–733. SIAM, 2011

    work page 2011

  6. [6]

    Budgeted match- ing and budgeted matroid intersection via the gasoline puzzle

    Andr´ e Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Sch¨ afer. Budgeted match- ing and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming, 128(1):355–372, 2011

    work page 2011

  7. [7]

    Agent-designed contracts: How to sell hidden actions

    Martino Bernasconi, Matteo Castiglioni, and Andrea Celli. Agent-designed contracts: How to sell hidden actions. arXiv preprint arXiv:2402.16547 , 2024

    work page arXiv 2024

  8. [8]

    Approximation techniques for utilitarian mechanism design

    Patrick Briest, Piotr Krysta, and Berthold V¨ ocking. Approximation techniques for utilitarian mechanism design. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 39–48, 2005

    work page 2005

  9. [9]

    Multi-agent contract design beyond binary actions

    Federico Cacciamani, Martino Bernasconi, Matteo Castiglioni, and Nicola Gatti. Multi-agent contract design beyond binary actions. arXiv preprint arXiv:2402.13824 , 2024

    work page arXiv 2024

  10. [10]

    Matthew Weinberg

    Linda Cai, Clayton Thomas, and S. Matthew Weinberg. Implementation in advised strategies: Welfare guarantees from posted-price mechanisms when demand queries are np-hard. In 11th Innovations in Theoretical Computer Science Conference, ITCS , pages 61:1–61:32, 2020

    work page 2020

  11. [11]

    Papadimitriou

    Yang Cai, Constantinos Daskalakis, and Christos H. Papadimitriou. Optimum statistical estimation with strategic data sources. In COLT 2015, pages 280–296, 2015

    work page 2015

  12. [12]

    Mechanism design: A new algorithmic framework

    Yang Cai et al. Mechanism design: A new algorithmic framework . PhD thesis, Massachusetts Institute of Technology, 2013

    work page 2013

  13. [13]

    An efficient ε-BIC to BIC transformation and its application to black-box reduction in revenue maximization

    Yang Cai, Argyris Oikonomou, Grigoris Velegkas, and Mingfei Zhao. An efficient ε-BIC to BIC transformation and its application to black-box reduction in revenue maximization. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1337–

    work page 2021

  14. [14]

    Approximation algo- rithms for knapsack problems with cardinality constraints

    Alberto Caprara, Hans Kellerer, Ulrich Pferschy, and David Pisinger. Approximation algo- rithms for knapsack problems with cardinality constraints. European Journal of Operational Research, 123(2):333–345, 2000. 25

    work page 2000

  15. [15]

    Complexity of some parametric integer and network programming problems

    Patricia J Carstensen. Complexity of some parametric integer and network programming problems. Mathematical Programming, 26(1):64–75, 1983

    work page 1983

  16. [16]

    Hiring for an uncertain task: Joint design of informa- tion and contracts

    Matteo Castiglioni and Junjie Chen. Hiring for an uncertain task: Joint design of informa- tion and contracts. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1758–1794. SIAM, 2025

    work page 2025

  17. [17]

    Multi-agent contract design: How to commission multiple agents with individual outcomes

    Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Multi-agent contract design: How to commission multiple agents with individual outcomes. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 412–448, 2023

    work page 2023

  18. [18]

    Knapsack cover subject to a matroid constraint

    Venkatesan T Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R Natarajan, and Sambuddha Roy. Knapsack cover subject to a matroid constraint. In IARCS Annual Con- ference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013

    work page 2013

  19. [19]

    Multi-budgeted matchings and matroid intersection via dependent rounding

    Chandra Chekuri, Jan Vondr´ ak, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages 1080–1097, 2011

    work page 2011

  20. [20]

    A nearly quadratic-time fptas for knapsack

    Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. A nearly quadratic-time fptas for knapsack. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 283–294, 2024

    work page 2024

  21. [21]

    Are bounded contracts learnable and approximately optimal? In EC 2024, 2024

    Yurong Chen, Zhaohua Chen, Xiaotie Deng, and Zhiyi Huang. Are bounded contracts learnable and approximately optimal? In EC 2024, 2024

    work page 2024

  22. [22]

    Approximating knapsack and partition via dense sub- set sums

    Mingyang Deng, Ce Jin, and Xiao Mao. Approximating knapsack and partition via dense sub- set sums. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2961–2979. SIAM, 2023

    work page 2023

  23. [23]

    On supermodu- lar contracts and dense subgraphs

    Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, and Aditya Prasad. On supermodu- lar contracts and dense subgraphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 109–132. SIAM, 2024

    work page 2024

  24. [24]

    Unsplittable flow on a short path

    Ilan Doron-Arad, Fabrizio Grandoni, and Ariel Kulik. Unsplittable flow on a short path. IPEC, 2024

    work page 2024

  25. [25]

    Budgeted matroid maximization: a param- eterized viewpoint

    Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted matroid maximization: a param- eterized viewpoint. In 18th International Symposium on Parameterized and Exact Computation (IPEC), pages 13:1–13:17, 2023

    work page 2023

  26. [26]

    An EPTAS for budgeted matching and budgeted matroid intersection via representative sets

    Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for budgeted matching and budgeted matroid intersection via representative sets. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2023, July 10-14, 2023, Paderborn, Germany , 2023

    work page 2023

  27. [27]

    An EPTAS for budgeted matroid inde- pendent set

    Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for budgeted matroid inde- pendent set. In Symposium on Simplicity in Algorithms (SOSA) , pages 69–83. SIAM, 2023

    work page 2023

  28. [28]

    An FPTAS for budgeted laminar matroid independent set

    Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An FPTAS for budgeted laminar matroid independent set. Oper. Res. Lett., 51(6):632–637, 2023. 26

    work page 2023

  29. [29]

    Lower bounds for matroid optimization problems with a linear constraint

    Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Lower bounds for matroid optimization problems with a linear constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) . Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2024

    work page 2024

  30. [30]

    Tight bounds for budgeted maximum weight indepen- dent set in bipartite and perfect graphs

    Ilan Doron-Arad and Hadas Shachnai. Tight bounds for budgeted maximum weight indepen- dent set in bipartite and perfect graphs. Discrete Applied Mathematics, 361:453–464, 2025

    work page 2025

  31. [31]

    Multi-agent combi- natorial contracts

    Paul Duetting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combi- natorial contracts. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1857–1891. SIAM, 2025

    work page 2025

  32. [32]

    Combinatorial contracts

    Paul D¨ utting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 815–826. IEEE, 2022

    work page 2021

  33. [33]

    Multi-agent contracts

    Paul D¨ utting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1311–1324, 2023

    work page 2023

  34. [34]

    Multi-agent combi- natorial contracts

    Paul D¨ utting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combi- natorial contracts. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1857–1891. SIAM, 2025

    work page 2025

  35. [35]

    Combinatorial contracts beyond gross substitutes

    Paul D¨ utting, Michal Feldman, and Yoav Gal Tzur. Combinatorial contracts beyond gross substitutes. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 92–108. SIAM, 2024

    work page 2024

  36. [36]

    Ambiguous contracts

    Paul D¨ utting, Michal Feldman, Daniel Peretz, and Larry Samuelson. Ambiguous contracts. Econometrica, 92(6):1967–1992, 2024

    work page 1967

  37. [37]

    The pseudo-dimension of contracts

    Paul D¨ utting, Michal Feldman, Tomasz Ponitka, and Ermis Soumalias. The pseudo-dimension of contracts. In Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025, pages 514–539. ACM, 2025

    work page 2025

  38. [38]

    Algorithmic contract theory: A survey

    Paul D¨ utting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic contract theory: A survey. Foundations and Trends in Theoretical Computer Science , 16(3-4):211–412, 2024

    work page 2024

  39. [39]

    The query complexity of contracts

    Paul D¨ utting, Michal Feldman, Yoav Gal Tzur, and Aviad Rubinstein. The query complexity of contracts. Working paper, 2024

    work page 2024

  40. [40]

    Simple versus optimal contracts

    Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 369–387, 2019

    work page 2019

  41. [41]

    The complexity of contracts

    Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen. The complexity of contracts. SIAM Journal on Computing , 50(1):211–254, 2021

    work page 2021

  42. [42]

    Matroids and the greedy algorithm

    Jack Edmonds. Matroids and the greedy algorithm. Mathematical programming, 1:127–136, 1971

    work page 1971

  43. [43]

    On the (in)approximability of combi- natorial contracts

    Tomer Ezra, Michal Feldman, and Maya Schlesinger. On the (in)approximability of combi- natorial contracts. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss-Dagstuhl-Leibniz Zentrum f¨ ur Informatik, 2024. 27

    work page 2024

  44. [44]

    Contracts with inspections

    Tomer Ezra, Stefano Leonardi, and Matteo Russo. Contracts with inspections. Working paper, 2024

    work page 2024

  45. [45]

    Demand queries with preprocessing

    Uriel Feige and Shlomo Jozeph. Demand queries with preprocessing. In Automata, Languages, and Programming - 41st International Colloquium, ICALP , pages 477–488. Springer, 2014

    work page 2014

  46. [46]

    Budget-feasible contracts

    Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. Budget-feasible contracts. In Proceedings of the 26th ACM Conference on Economics and Computation, EC . ACM, 2025

    work page 2025

  47. [47]

    Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses

    Alan M Frieze, Michael RB Clarke, et al. Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses. European Journal of Operational Research, 15(1):100–109, 1984

    work page 1984

  48. [48]

    Optimality of weighted contracts for multi-agent contract design with a budget

    Sumit Goel and Wade Hann-Caruthers. Optimality of weighted contracts for multi-agent contract design with a budget. In Proceedings of the 25th ACM Conference on Economics and Computation, EC. ACM, 2024

    work page 2024

  49. [49]

    Gonczarowski and S

    Yannai A. Gonczarowski and S. Matthew Weinberg. The sample complexity of up-to- ϵ multi- dimensional revenue maximization. J. ACM, 68(3):15:1–15:28, 2021

    work page 2021

  50. [50]

    Principal-agent contracts meet a cardinality

    Qinqin Gong, Ling Gai, Yang Lv, and Ruiqi Yang. Principal-agent contracts meet a cardinality. Available at SSRN: https://ssrn.com/abstract=4581020, 2023

    work page 2023

  51. [51]

    Near-optimal communication lower bounds for approximate nash equilibria

    Mika G¨ o¨ os and Aviad Rubinstein. Near-optimal communication lower bounds for approximate nash equilibria. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 397–403. IEEE Computer Society, 2018

    work page 2018

  52. [52]

    Approximation schemes for multi-budgeted indepen- dence systems

    Fabrizio Grandoni and Rico Zenklusen. Approximation schemes for multi-budgeted indepen- dence systems. In European Symposium on Algorithms (ESA), pages 536–548. Springer, 2010

    work page 2010

  53. [53]

    An analysis of the principal-agent problem

    Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. In Foundations of Insurance Economics: Readings in Economics and Finance , pages 302–340. Springer, 1992

    work page 1992

  54. [54]

    Contracts under moral hazard and adverse selection

    Guru Guruganesh, Jon Schneider, and Joshua Wang. Contracts under moral hazard and adverse selection. In EC 2021, pages 563–582, 2021

    work page 2021

  55. [55]

    An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection

    Refael Hassin and Asaf Levin. An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM Journal on Computing, 33(2):261–268, 2004

    work page 2004

  56. [56]

    Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems

    Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. Journal of Artificial Intelligence Research, 55:317–359, 2016

    work page 2016

  57. [57]

    Moral hazard and observability

    Bengt Holmstr¨ om. Moral hazard and observability. The Bell journal of economics , pages 74–91, 1979

    work page 1979

  58. [58]

    A fully polynomial bicriteria ap- proximation scheme for the constrained spanning tree problem

    Sung-Pil Hong, Sung-Jin Chung, and Bum Hwan Park. A fully polynomial bicriteria ap- proximation scheme for the constrained spanning tree problem. Operations Research Letters, 32(3):233–239, 2004. 28

    work page 2004

  59. [59]

    FPT-algorithms for the-matchoid problem with a coverage objective

    Chien-Chung Huang and Justin Ward. FPT-algorithms for the-matchoid problem with a coverage objective. SIAM Journal on Discrete Mathematics , 37(2):1053–1078, 2023

    work page 2023

  60. [60]

    Fast approximation algorithms for the knapsack and sum of subset problems

    Oscar H Ibarra and Chul E Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM (JACM) , 22(4):463–468, 1975

    work page 1975

  61. [61]

    Reducibility among combinatorial problems

    Richard M Karp. Reducibility among combinatorial problems. Springer, 2010

    work page 2010

  62. [62]

    Kellerer, U

    H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004

    work page 2004

  63. [63]

    The multiple-choice knapsack problem

    Hans Kellerer, Ulrich Pferschy, and David Pisinger. The multiple-choice knapsack problem. In Knapsack Problems, pages 317–347. Springer, 2004

    work page 2004

  64. [64]

    There is no EPTAS for two-dimensional knapsack

    Ariel Kulik and Hadas Shachnai. There is no EPTAS for two-dimensional knapsack. Informa- tion Processing Letters, 110(16):707–710, 2010

    work page 2010

  65. [65]

    Combinatorial auctions with decreasing marginal utilities

    Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior , 55(2):270–296, 2006

    work page 2006

  66. [66]

    Discovering Prices: Auction Design in Markets with Complex Constraints

    Paul Milgrom. Discovering Prices: Auction Design in Markets with Complex Constraints . Columbia University Press, 2021

    work page 2021

  67. [67]

    Truthful approximation mechanisms for restricted combi- natorial auctions

    Ahuva Mu’Alem and Noam Nisan. Truthful approximation mechanisms for restricted combi- natorial auctions. Games and Economic Behavior , 64(2):612–631, 2008

    work page 2008

  68. [68]

    Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58–73, 1981

    work page 1981

  69. [69]

    Algorithmic mechanism design

    Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages 129–140, 1999

    work page 1999

  70. [70]

    On the approximability of trade-offs and optimal access of web sources

    Christos H Papadimitriou and Mihalis Yannakakis. On the approximability of trade-offs and optimal access of web sources. In Proceedings 41st annual symposium on foundations of com- puter science, pages 86–92. IEEE, 2000

    work page 2000

  71. [71]

    The knapsack problem with conflict graphs

    Ulrich Pferschy and Joachim Schauer. The knapsack problem with conflict graphs. Journal of Graph Algorithms and Applications , 13(2):233–249, 2009

    work page 2009

  72. [72]

    Twenty Lectures on Algorithmic Game Theory

    Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory . Cambridge University Press, 2016

    work page 2016

  73. [73]

    Incentivizing quality text generation via sta- tistical contracts

    Eden Saig, Ohad Einav, and Inbal Talgam-Cohen. Incentivizing quality text generation via sta- tistical contracts. In Annual Conference on Neural Information Processing Systems NeurIPS , 2024

    work page 2024

  74. [74]

    Budgeted matching via the gasoline puzzle.Gems of Combinatorial Optimiza- tion and Graph Algorithms , pages 49–57, 2015

    Guido Sch¨ afer. Budgeted matching via the gasoline puzzle.Gems of Combinatorial Optimiza- tion and Graph Algorithms , pages 49–57, 2015

    work page 2015

  75. [75]

    Matthew Weinberg

    S. Matthew Weinberg. Algorithms for strategic agents. PhD thesis, Massachusetts Institute of Technology (MIT), 2014

    work page 2014

  76. [76]

    local to global

    Shiliang Zuo. New perspectives in online contract design: Heterogeneous, homogeneous, non- myopic agents and team production. arXiv preprint arXiv:2403.07143 , 2024. 29 Appendix Organization A discussion of our results appears in Appendix A. Additional related work and preliminaries appear in Appendix B and Appendix C. Appendix D shows the hardness of con...

    work page arXiv 2024

  77. [77]

    and then for matroid intersection and matching constraints [26] using the representative set technique that was later generalized to other more general constraints [25, 24]. While for budgeted maximization on matroids an FPTAS is ruled out [29], there are FPTAS for special cases such as knapsack with a cardinality constraint [14] multiple-choice knapsack ...

    work page

  78. [78]

    an+1 ∈ S if and only if α ≥ 1 2

    work page

  79. [79]

    35 Proof

    For any α′ ∈ (0, 1), if α′ < 1 2 then Sα′ = S∗, and if α′ ≥ 1 2 then Sα′ = S∗ ∪ {an+1}. 35 Proof. The first property follows from the fact that when α < 1 2, the agent’s utility from selecting an+1 is negative: αpn+1 − cn+1 < 1 2 · pn+1 − 1 2 · pn+1 = 0. Therefore, a rational agent would never choose this action, ensuring an+1 /∈ S. For the second propert...

    work page

  80. [80]

    In particular, it holds also for α′ = 1

    The approximation guarantee of ALG implies that up(S, α) ≥ (1 − ε)up(Sα′, α′) for all α′ ∈ (0, 1). In particular, it holds also for α′ = 1

    work page

Showing first 80 references.