Pith. sign in

REVIEW 5 minor 155 references

From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations

T0 review · 0 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that subadditive valuations admit a universally truthful, budget-feasible mechanism that runs in polynomial time via demand queries with a constant approximation ratio C+epsilon (C<86.399), refuting the conjecture that a…

desk verdict The main result is real: the paper delivers the first polynomial-query constant approximation for subadditive valuations, and the smoothing lemma behind it is a genuinely new and clean contribution. read the letter →

arxiv 2608.04337 v1 pith:KNRS3XKW submitted 2026-08-05 cs.GT cs.DS

Ioannis Anagnostides , Kshipra Bhawalkar , Christopher Liaw , Aranyak Mehta , Grigoris Velegkas , Weiqiang Zheng This is my paper · ORCID
classification cs.GTcs.DS MSC 91B0368W2591A1091B26
keywords budget-feasiblemechanismssubadditivevaluationsdemandqueriestruthfulnessself-boundingfunctionscompensationdesignpriceofstabilitysmoothinglemma
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims to resolve a long-standing open problem in budget-feasible mechanism design: for every subadditive valuation there is a universally truthful, individually rational, budget-feasible mechanism that runs in polynomial time using polynomially many demand queries and attains a constant approximation ratio C+epsilon, with C<86.399. If true, this contradicts the earlier conjecture that any constant approximation for subadditive valuations would require exponentially many demand queries. The load-bearing ingredient is a new smoothing lemma: every monotone subadditive function can be approximated within a factor of 2 by a self-bounding function, which makes marginal-contribution payments budget-feasible. The paper also improves the information-theoretic approximation ratios to 3 for monotone submodular, e+1 for XOS and nonmonotone submodular, and 2e+1 for subadditive valuations, with deterministic large-market improvements.

What carries the argument

The central object is the smoothed value function \tilde{v}(S)=\$int_0^{1}$ \mathbb{E}[v(R_q(S))]\,dq, where R_q(S) retains each element of S independently with probability q. The paper proves that for every normalized monotone subadditive v, \tilde{v} is monotone, subadditive, and self-bounding, with v(S)/2 \le \tilde{v}(S) \le v(S), where a function F is self-bounding when \sum_{i\in S}(F(S)-F(S\setminus\{i\})) \le F(S) for all S. The self-bounding property is exactly what makes the marginal-contribution payment rule p_i(S)=B(F(S)-F(S\setminus i))/F(S) budget-feasible, and the smoothing identity \sum_i(\tilde{v}(S)-\tilde{v}(S\setminus i))=v(S)-\tilde{v}(S) is the proof's hinge. The mechanism then works through the potential \Phi(S)=\tilde{v}(S)\prod_{i\in S}(1-b_i/B)_+, whose maximizer is a Nash equilibrium of the induced game; the polynomial implementation adds a core-tail decomposition, random partitioning, and uniform thinning to maximize the potential approximately without exact queries to \tilde{v}.

What would settle it

Take the subadditive valuation v(\emptyset)=0, v(T)=1 for every nonempty proper T, v(N)=2, and compute \tilde{v} from its explicit formula; checking whether \sum_{i\in N}(\tilde{v}(N)-\tilde{v}(N\setminus i)) equals v(N)-\tilde{v}(N) would confirm the smoothing identity, while any inequality would refute it. A second check is to run the PolyRMC mechanism on the same valuation and verify that the threshold payments never exceed the budget for any bid vector.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 5.1: for every fixed epsilon>0 there exists a randomized mechanism, called PolyRMC, that is universally truthful, individually rational, budget-feasible, runs in polynomial time using poly(n) demand queries for any normalized monotone subadditive valuation, and has approximation factor C+epsilon where C<86.399. The mechanism randomizes between a singleton branch that rewards the best individually affordable agent and a marginal-contribution branch whose allocation maximizes a potential over a smoothed proxy; threshold payments from the standard single-parameter characterization then make it dominant-strategy truthful. The argument converts an indirect non-truthful setting (compensation design) into a direct truthful one by showing that a potential maximizer is a pure Nash equilibrium of the marginal-contribution game and that this equilibrium property automatically keeps the threshold payments within the budget.

Load-bearing premise

If the smoothing lemma's factor-2 guarantee or the identity that sums the marginal drops of the smoothed value \tilde{v} to v(S)-\tilde{v}(S) failed for some subadditive valuation, the marginal-contribution payments would no longer be budget-feasible and the constant-approximation mechanism would collapse.

Editorial extensions

If this is right

  • Resolves the conjecture that constant approximation for subadditive valuations in budget-feasible design requires exponentially many demand queries by giving a polynomial-query mechanism with ratio 86.399+epsilon.
  • Information-theoretically, the approximations improve to 3 (monotone submodular), e+1 (XOS and nonmonotone submodular), and 2e+1 (subadditive); in large markets the guarantees become deterministic 2+o(1), e+o(1), and 2e+o(1).
  • The smoothing lemma gives a 2e-approximate restrained core for subadditive utilities in multiwinner elections, resolving an open question in that line.
  • For beta-self-bounding valuations, including beta-MPH, a deterministic large-market truthful mechanism attains e*beta approximation; without the large-market assumption no universally truthful mechanism can have a bounded approximation even for beta=2.
  • The compensation-design-to-mechanism translation shows a general recipe: any self-bounding proxy F with eta*v <= F <= v yields a universally truthful budget-feasible mechanism with ratio e/eta + 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The factor-2 smoothing lemma may be reusable wherever subadditive functions appear with value queries, such as welfare maximization or pricing, by first replacing the objective with its smooth proxy and then optimizing the potential instead of the value.
  • The uniform-thinning step suggests a broader trick for converting high-value but high-cost solutions into high-potential solutions: scale each selected item's bid effect by a random retention probability, trading value for potential at a constant rate.
  • If the factor-2 bound in the smoothing lemma is tight, then improving the information-theoretic 2e+1 for subadditive valuations below that constant would require either a different payment rule or a potential analysis not based on the smoothed proxy.
  • The constant 86.399 is not optimized; the authors state no attempt was made, so a careful parameter tuning of the core size, grid precision, and mixture weight may bring the polynomial mechanism much closer to the exponential-time 2e+1 ratio.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. This paper studies budget-feasible mechanism design with private costs. The authors introduce a framework based on compensation design, a non-truthful indirect game with cost-oblivious marginal-contribution payments, and show that global maximizers of a natural potential are pure Nash equilibria with good price-of-stability guarantees whenever the objective admits a self-bounding proxy. The main structural result (Theorem 3.5) is that every monotone subadditive valuation has a monotone, subadditive, self-bounding proxy tilde-v with v/2 <= tilde-v <= v, obtained by smoothing. This yields information-theoretic universally truthful mechanisms with approximation ratios 3 for monotone submodular, e+1 for XOS, and 2e+1 for subadditive valuations, with deterministic large-market improvements. The central computational result (Theorem 5.1) is a randomized mechanism PolyRMC that is universally truthful, individually rational, budget-feasible, achieves approximation C+epsilon with C<86.399 for every fixed epsilon>0, and runs in polynomial time using poly(n) demand queries for subadditive valuations, resolving a conjecture of Dobzinski, Papadimitriou, and Singer. The paper also proves an impossibility result for beta-MPH valuations without large markets and gives an e*beta approximation in large markets.

Significance. This is a major advance. If correct, it settles the long-standing question of whether a constant approximation for subadditive valuations can be obtained with polynomially many demand queries, and it substantially improves the state of the art for information-theoretic mechanisms across the complement-free hierarchy. The framework is conceptually novel and likely to be influential: it converts price-of-stability guarantees in an indirect, non-truthful compensation game into dominant-strategy truthful mechanisms with budget feasibility, using Myerson threshold payments bounded by marginal contributions. The smoothing lemma (Theorem 3.5) is a clean and independent contribution, and the application to approximate cores in multiwinner elections is a nice bonus. The proof of the polynomial mechanism is long but essentially self-contained, with explicit constants and query bounds; the load-bearing Lemma 3.5 identity is correct, and the core-tail decomposition, concentration bounds, and threshold characterizations in Appendix D withstand scrutiny. No constants are fitted to data, and the main claims are proved from stated assumptions.

minor comments (5)
  1. [Section 2, Definition 2.1] The displayed implication in the definitions of monotonicity and nonbossiness contains a corrupted token ('/Leftr⫯g⊸tl⫯ne⇒') and must be restored so that the definitions are readable.
  2. [Section 5.1.2, Eqs. (17)-(19)] The square-root expressions in Lemma 5.6 and the derived potential approximation are replaced by placeholder tokens; since these statements are central to Theorem 5.2, the displayed formulas need to be repaired. The surrounding text indicates the intended formulas, and I found no mathematical error in the repaired versions.
  3. [Section 5.1.3, Eq. (22)] The definitions of u0 and rho0 are affected by the same glyph corruption in the square root; please repair the display so that the claimed constant C<86.399 can be verified directly.
  4. [Section 3.3.1, proof of Theorem 3.5] In the proof of the lower bound 2 tilde-v(S) >= v(S), the change of variables u = 1-q in the integral of E[v(R_{1-q}(S))] is implicit; adding this step would improve readability.
  5. [Section 5.3, Eq. (33) and Corollary D.1] The symbol rho is used both for the target constant 2e rho0 + epsilon and for a generic potential approximation factor; consider using distinct notation to avoid confusion.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the subadditive constant-approximation chain is self-contained; the only notable self-citation supports the submodular warm-up, not the central claim.

full rationale

The central derivation is internally sound. Theorem 3.5, the 2-approximation of subadditive valuations by self-bounding functions, is proved in the paper via the smoothing definition and Lemma 3.5's exact identity; the derivative argument in Lemma D.1 supplies the missing step. The budget-feasible threshold argument in Lemma 4.1 is proved using nonbossiness and the Nash-equilibrium property of the potential, not imported from the companion paper. The polynomial-time mechanism behind Theorem 5.1 is built from in-paper components: the nonbossy potential approximation in Theorem 5.2, the sampling estimates in Lemma 5.9, the filtering lemmas, and the exact threshold characterization in Proposition D.1. The constants u0, rho0, and C are computed from explicitly stated quadratic equations and inequalities, with no fitting to data. The only place the text relies on a same-author citation as a black box is the monotone-submodular warm-up: Theorem 4.1's 3-approximation invokes Corollary 3.1, whose proof cites Theorem 3.1 from Anagnostides et al. 2026. That self-citation is not load-bearing for the paper's central XOS, subadditive, or beta-self-bounding results, all of which are proven in this manuscript, nor for the polynomial-query constant approximation that resolves the Dobzinski-Papadimitriou-Singer question.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central proof is self-contained for the main new results except for standard mechanism-design tools and two cited building blocks. The only nonstandard external input is the companion 'Compensation design' paper, whose submodular potential result is used for the warm-up. The paper introduces no new physical entities, dimensions, or forces; the smoothed proxy, core-tail decomposition, and thinning process are analytical constructs defined inside the proof.

free parameters (2)
  • Mixing probability alpha for the RMC singleton branch = 1/3 for submodular; 1/(e+1) for XOS; 1/(2e+1) for subadditive
    Chosen in the proof to balance the singleton value M against the potential-branch value (OPT-M)/k from Theorem 3.3. It is a design parameter, not fitted to data.
  • PolyRMC accuracy parameters (ell, eta, delta, eps-hat, rho) = ell=ell(eps), eta=eta(eps), delta=eps/(64e(rho0+1)), eps-hat=delta/(4n^2), rho=2e rho0+eps
    Hand-tuned in Section 5.3 to keep the final approximation below C+eps and to make all error terms small. These are proof parameters, not empirically fitted values.
assumptions (3)
  • standard math Myerson's characterization for single-parameter truthful mechanisms (Lemma 2.1).
    Used throughout to convert monotone and nonbossy allocation rules into truthful mechanisms with threshold payments. This is a standard tool in mechanism design.
  • domain assumption Demand and value oracle model with a fixed, bid-independent tie-breaking convention (Section 2 and Remark 2.1).
    The polynomial mechanism assumes access to demand/value oracles and a lexicographic tie-breaking rule. These assumptions are explicit and standard in this literature.
  • standard math Theorem 3.1 of Anagnostides et al. [2026], the companion compensation-design paper, for the monotone submodular warm-up.
    Section 3.1 invokes the companion result that the marginal-contribution payment rule has potential maximizers as pure Nash equilibria and every pure Nash equilibrium has value at least (OPT-M)/2. This result is cited, not reproved here; it grounds the submodular 3-approximation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations." pith.science (2026). https://pith.science/paper/KNRS3XKW

@misc{pith2026260804337,
  author       = {Pith},
  title        = {Pith review of: From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KNRS3XKW}},
  note         = {Machine review of arXiv:2608.04337}
}
abstract

Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly advance the state of the art. First, without computational constraints, we show that there exists a budget-feasible universally truthful mechanism with the following approximation ratios: - $3$ for monotone submodular valuations and $e+1$ for nonmonotone submodular valuations, improving over $3.798$ and $9.742$, respectively. - $e+1$ for XOS valuations, improving over $28$. In large markets, our approximation can be improved deterministically to $e$. - $2e+1$ for subadditive valuations, improving over $33$. In large markets, our approximation can be improved deterministically to $2e$. Moreover, for subadditive valuations, we obtain a constant-approximation mechanism that runs in polynomial time using demand queries. This improves over the previous best approximation of $O(\log \log n)$, resolving a long-standing open problem going back to Dobzinski, Papadimitriou, and Singer, who conjectured that a constant approximation requires exponentially many demand queries. We obtain these results through a simple and unifying framework based on non-truthful indirect mechanisms, recently coined compensation design. In particular, through a potential argument, we establish constant price-of-stability bounds for compensation design based on marginal-contribution payment rules, which we then translate into truthful direct mechanisms. For subadditive valuations, the core of the argument is a new smoothing lemma showing that every subadditive function can be approximated within a factor of $2$ by a self-bounding function. This is also of independent interest, readily addressing an open question in multiwinner elections by showing the existence of a $2e$-approximate core even under subadditive valuations.

Figures

Figures reproduced from arXiv: 2608.04337 by the authors.

Figure 1
Figure 1. Overview of the polynomial implementation of the [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

155 extracted references · 68 canonical work pages

  1. [1]

    Proceedings of the ACM Conference on Electronic Commerce (EC) , year=

    Combinatorial agency , author=. Proceedings of the ACM Conference on Electronic Commerce (EC) , year=

  2. [2]

    Equal-Pay Contracts , author=

  3. [3]

    Multi-Agent Contracts , year =

    D\". Multi-Agent Contracts , year =

  4. [4]

    Wang and Zhun Deng and Hiroaki Chiba

    Jiachen T. Wang and Zhun Deng and Hiroaki Chiba. An Economic Solution to Copyright Challenges of Generative. arXiv:2404.13964 , year =

    arXiv

  5. [5]

    When contracts get complex: Information-theoretic barriers , author=

  6. [6]

    Contract design for sequential actions , author=

  7. [7]

    Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online , author=

  8. [8]

    Symposium on Discrete Algorithms (SODA) , year=

    Welfare guarantees for combinatorial auctions with item bidding , author=. Symposium on Discrete Algorithms (SODA) , year=

Show all 155 references
  1. [9]

    Budget feasible mechanisms: A survey , author=

  2. [10]

    SIAM Journal on Computing , volume=

    Combinatorial contracts , author=. SIAM Journal on Computing , volume=

  3. [11]

    American Economic Journal: Microeconomics , volume=

    Too much data: Prices and inefficiencies in data markets , author=. American Economic Journal: Microeconomics , volume=

  4. [12]

    Industrial and Corporate Change , volume=

    Markets for data , author=. Industrial and Corporate Change , volume=

  5. [13]

    and Monsieur, Geert and Van Den Heuvel, Willem-Jan , journal=

    Driessen, Stefan W. and Monsieur, Geert and Van Den Heuvel, Willem-Jan , journal=. Data Market Design: A Systematic Literature Review , year=

  6. [14]

    ACM Transactions on Economics and Computation , volume=

    Partial allocations in budget-feasible mechanism design: bridging multiple levels of service and divisible agents , author=. ACM Transactions on Economics and Computation , volume=

  7. [15]

    Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions , author=

  8. [16]

    arXiv:2511.20110 , year=

    One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts , author=. arXiv:2511.20110 , year=

  9. [17]

    Econometrica , volume=

    Ambiguous contracts , author=. Econometrica , volume=

  10. [18]

    arXiv:2510.15065 , year=

    Combinatorial contract design: Recent progress and emerging frontiers , author=. arXiv:2510.15065 , year=

  11. [19]

    Foundations and Trends

    Algorithmic contract theory: A survey , author=. Foundations and Trends

  12. [20]

    Journal of the ACM (JACM) , volume=

    A simple and approximately optimal mechanism for an additive buyer , author=. Journal of the ACM (JACM) , volume=

  13. [21]

    ACM Transactions on Economics and Computation (TEAC) , volume=

    Simple mechanisms for a subadditive buyer and applications to revenue monotonicity , author=. ACM Transactions on Economics and Computation (TEAC) , volume=

  14. [22]

    Proceedings of the National Academy of Sciences (PNAS) , volume=

    On revenue maximization for selling multiple independently distributed items , author=. Proceedings of the National Academy of Sciences (PNAS) , volume=

  15. [23]

    Constant approximation for private interdependent valuations , author=

  16. [24]

    Fair multiwinner elections with allocation constraints , author=

  17. [25]

    Tight bounds on low-degree spectral concentration of submodular and

    Feldman, Vitaly and Vondr. Tight bounds on low-degree spectral concentration of submodular and

  18. [26]

    arXiv:1005.2791 , year=

    A note on concentration of submodular functions , author=. arXiv:1005.2791 , year=

    arXiv

  19. [27]

    EC , year=

    Equilibrium Efficiency and Learning in Budgeted Procurement Marketplaces , author=. EC , year=

  20. [28]

    IEEE signal processing magazine , volume=

    Federated learning: Challenges, methods, and future directions , author=. IEEE signal processing magazine , volume=

  21. [29]

    Foundations and trends in machine learning , volume=

    Advances and open problems in federated learning , author=. Foundations and trends in machine learning , volume=

  22. [30]

    arXiv:2207.04557 , year=

    Mechanisms that incentivize data sharing in federated learning , author=. arXiv:2207.04557 , year=

    arXiv

  23. [31]

    IEEE Transactions on Emerging Topics in Computing , volume=

    A survey of incentive mechanism design for federated learning , author=. IEEE Transactions on Emerging Topics in Computing , volume=

  24. [32]

    arXiv:2106.15406 , year=

    A comprehensive survey of incentive mechanism for federated learning , author=. arXiv:2106.15406 , year=

    arXiv

  25. [33]

    arXiv:2205.10951 , year=

    Incentivizing federated learning , author=. arXiv:2205.10951 , year=

    arXiv

  26. [34]

    2023 , journal=

    Federated Learning Incentive Mechanism under Buyers' Auction Market , author=. 2023 , journal=

    2023

  27. [35]

    Budget feasible mechanisms , author=

  28. [36]

    On the approximability of budget feasible mechanisms , author=

  29. [37]

    Simple and efficient budget feasible mechanisms for monotone submodular valuations , author=

  30. [38]

    Mechanism design for crowdsourcing: An optimal 1-1/e competitive budget-feasible mechanism for large markets , author=

  31. [39]

    Operations Research , volume=

    Budget feasible procurement auctions , author=. Operations Research , volume=

  32. [40]

    SIAM Journal on Computing , volume=

    Worst-case mechanism design via bayesian analysis , author=. SIAM Journal on Computing , volume=

  33. [41]

    Journal of the ACM (JACM) , volume=

    Adwords and generalized online matching , author=. Journal of the ACM (JACM) , volume=

  34. [42]

    Optimal budget-feasible mechanisms for additive valuations , author=

  35. [43]

    A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations , year =

    Dobzinski, Shahar and Li, Wenzheng and Rubinstein, Aviad and Vondr. A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations , year =

  36. [44]

    D. An. SIAM Journal on Computing , volume=. 2022 , publisher=

    2022

  37. [45]

    Proceedings of the ACM conference on Electronic commerce (EC) , year=

    Mechanisms for complement-free procurement , author=. Proceedings of the ACM conference on Electronic commerce (EC) , year=

  38. [46]

    Innovations in Theoretical Computer Science Conference (ITCS) , year=

    Budget-feasible mechanism design: Simpler, better mechanisms and general payment constraints , author=. Innovations in Theoretical Computer Science Conference (ITCS) , year=

  39. [47]

    A competitive posted-price mechanism for online budget-feasible auctions , author=

  40. [48]

    Algorithmica , volume=

    Optimization with demand oracles , author=. Algorithmica , volume=

  41. [49]

    Mathematical programming , volume=

    An analysis of approximations for maximizing submodular set functions—I , author=. Mathematical programming , volume=

  42. [50]

    Operations Research Letters , volume=

    A note on maximizing a submodular set function subject to a knapsack constraint , author=. Operations Research Letters , volume=

  43. [51]

    Proceedings of the ACM conference on electronic commerce , year=

    Learning on a budget: posted price mechanisms for online procurement , author=. Proceedings of the ACM conference on electronic commerce , year=

  44. [52]

    American Economic Review , volume=

    Obviously strategy-proof mechanisms , author=. American Economic Review , volume=

  45. [53]

    2024 , howpublished =

    Reuters , title =. 2024 , howpublished =

    2024

  46. [54]

    2025 , howpublished =

    The Verge , title =. 2025 , howpublished =

    2025

  47. [55]

    Introducing Index by Parallel , year =

  48. [56]

    2026 , howpublished =

    Beatrice Nolan , title =. 2026 , howpublished =

    2026

  49. [57]

    Adaptive Contracts for Cost-Effective

    Saig, Eden and Garbuz, Tamar and Procaccia, Ariel D and Talgam-Cohen, Inbal and Tucker-Foltz, Jamie , booktitle=ICML, year=. Adaptive Contracts for Cost-Effective

  50. [58]

    The complexity of pure

    Fabrikant, Alex and Papadimitriou, Christos and Talwar, Kunal , booktitle=STOC, year=. The complexity of pure

  51. [59]

    Journal of Mathematical Economics , year =

    Robert Aumann , title =. Journal of Mathematical Economics , year =

  52. [60]

    Moulin and J.-P

    H. Moulin and J.-P. Vial , title =. International Journal of Game Theory , year =

  53. [61]

    Annals of mathematics , pages=

    Non-cooperative games , author=. Annals of mathematics , pages=

  54. [62]

    Agentomics: Economic Foundations for the Valuation, Attribution, and Pricing of

    Quanyan Zhu , year=. Agentomics: Economic Foundations for the Valuation, Attribution, and Pricing of

  55. [63]

    L. S. Shapley , publisher =. A Value for n-Person Games , booktitle =

  56. [64]

    1996 , author =

    Potential Games , journal =. 1996 , author =

    1996

  57. [65]

    2006 , author =

    Combinatorial auctions with decreasing marginal utilities , journal =. 2006 , author =

    2006

  58. [66]

    Composable and efficient mechanisms , author=

  59. [67]

    Econometrica , volume=

    Potential, value, and consistency , author=. Econometrica , volume=

  60. [68]

    Proceedings of the 2007 ACM CoNEXT conference , year=

    Internet Economics: The use of Shapley value for ISP settlement , author=. Proceedings of the 2007 ACM CoNEXT conference , year=

    2007

  61. [69]

    IEEE transactions on automation science and engineering , volume=

    A shapley value-based approach to discover influential nodes in social networks , author=. IEEE transactions on automation science and engineering , volume=

  62. [70]

    Top , volume=

    The class of microarray games and the relevance index for genes , author=. Top , volume=

  63. [71]

    Symposium on Logic in Computer Science (LICS) , year=

    Responsibility and verification: Importance value in temporal logics , author=. Symposium on Logic in Computer Science (LICS) , year=

  64. [72]

    arXiv:2212.07720 , year=

    The complexity of the Shapley value for regular path queries , author=. arXiv:2212.07720 , year=

    arXiv

  65. [73]

    A unified approach to interpreting model predictions , author=

  66. [74]

    Papadimitriou , journal =

    Xiaotie Deng and Christos H. Papadimitriou , journal =. On the Complexity of Cooperative Solution Concepts , volume =

  67. [75]

    International Conference on Algorithms and Complexity , year=

    On the power of nodes of degree four in the local max-cut problem , author=. International Conference on Algorithms and Complexity , year=

  68. [76]

    SIAM journal on Computing , volume=

    Simple local search problems that are hard to solve , author=. SIAM journal on Computing , volume=

  69. [77]

    Journal of computer and system sciences , volume=

    How easy is local search? , author=. Journal of computer and system sciences , volume=

  70. [78]

    On maximizing welfare when utility functions are subadditive , author=

  71. [79]

    Creator Economy Market Report 2026 , year =

    2026

  72. [80]

    The Creator Economy Could Approach Half-a-Trillion Dollars by 2027 , year =

    2027

  73. [81]

    Conference on Electronic Commerce (EC) , year=

    Bidding and allocation in combinatorial auctions , author=. Conference on Electronic Commerce (EC) , year=

  74. [82]

    Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions , author=

  75. [83]

    Procurement Auctions with Best and Final Offers , author=

  76. [84]

    The price of anarchy in auctions , year =

    Roughgarden, Tim and Syrgkanis, Vasilis and Tardos, \'. The price of anarchy in auctions , year =. Journal of Artificial Intelligence Research , pages =

  77. [85]

    Yoram Bachrach and Vasilis Syrgkanis and Milan Vojnovic , title =

  78. [86]

    European Symposium on Algorithms (ESA) , year=

    Profit sharing and efficiency in utility games , author=. European Symposium on Algorithms (ESA) , year=

  79. [87]

    Operations Research , volume=

    Distributed welfare games , author=. Operations Research , volume=

  80. [88]

    IEEE Transactions on Automatic Control , volume=

    Generalized efficiency bounds in distributed resource allocation , author=. IEEE Transactions on Automatic Control , volume=

  81. [89]

    Journal of the ACM (JACM) , volume=

    Intrinsic robustness of the price of anarchy , author=. Journal of the ACM (JACM) , volume=

  82. [90]

    Regret minimization and the price of total anarchy , author=

  83. [91]

    Budget-Feasible Contracts , author=

  84. [92]

    Welfare and Beyond in Multi-Agent Contracts , author=

  85. [93]

    SIAM journal on computing , volume=

    The price of stability for network design with fair cost allocation , author=. SIAM journal on computing , volume=

  86. [94]

    Incentivizing data collaboration: A mechanism design approach , author=

  87. [95]

    Econometrica: Journal of the Econometric Society , pages=

    Incentives in teams , author=. Econometrica: Journal of the Econometric Society , pages=

  88. [96]

    Public choice , pages=

    Multipart pricing of public goods , author=. Public choice , pages=

  89. [97]

    Conference on Artificial Intelligence (AAAI) , year=

    Budget feasible mechanisms over graphs , author=. Conference on Artificial Intelligence (AAAI) , year=

  90. [98]

    Conference on World Wide Web (WWW) , year=

    Bayesian budget feasibility with posted pricing , author=. Conference on World Wide Web (WWW) , year=

  91. [99]

    International conference on integer programming and combinatorial optimization , year=

    Budget feasible mechanisms on matroids , author=. International conference on integer programming and combinatorial optimization , year=

  92. [100]

    Symposium on Discrete Algorithms (SODA) , year=

    Simple mechanisms for non-linear agents , author=. Symposium on Discrete Algorithms (SODA) , year=

  93. [101]

    Tight Approximation for Unconstrained

    Filmus, Yuval and Kawase, Yasushi and Kobayashi, Yusuke and Yamaguchi, Yutaro , journal=. Tight Approximation for Unconstrained

  94. [102]

    Approximation algorithms for combinatorial auctions with complement-free bidders , author=

  95. [103]

    SIAM Journal on Computing , volume=

    On the computational power of demand queries , author=. SIAM Journal on Computing , volume=

  96. [104]

    arXiv:1811.09045 , year=

    Tight Approximation for Unconstrained XOS Maximization , author=. arXiv:1811.09045 , year=

    arXiv

  97. [105]

    Innovations in Theoretical Computer Science Conference (ITCS) , year =

    Rubinstein, Aviad and Zhao, Junyao , title =. Innovations in Theoretical Computer Science Conference (ITCS) , year =

  98. [106]

    2014 , note =

    Tim Roughgarden , title =. 2014 , note =

    2014

  99. [107]

    arXiv preprint arXiv:2506.21493 , year=

    From multi-allocations to allocations, with subadditive valuations , author=. arXiv preprint arXiv:2506.21493 , year=

    arXiv

  100. [108]

    The Journal of finance , volume=

    Counterspeculation, auctions, and competitive sealed tenders , author=. The Journal of finance , volume=

  101. [109]

    Proportionality and the limits of welfarism , author=

  102. [110]

    Proportional participatory budgeting with additive utilities , author=

  103. [111]

    Econometrica: Journal of the Econometric Society , pages=

    The core of an N person game , author=. Econometrica: Journal of the Econometric Society , pages=

  104. [112]

    Classics in the theory of public finance , pages=

    Just taxation—a positive solution , author=. Classics in the theory of public finance , pages=. 1958 , publisher=

    1958

  105. [113]

    Fair allocation of indivisible public goods , author=

  106. [114]

    Journal of the Statistical Society of London , volume=

    On methods of electing representatives , author=. Journal of the Statistical Society of London , volume=

  107. [115]

    Management Science , volume=

    The creator economy: Managing ecosystem supply, revenue sharing, and platform design , author=. Management Science , volume=

  108. [116]

    2026 , journal=

    In-Context Credit Assignment via the Core , author=. 2026 , journal=

    2026

  109. [117]

    Management Science , volume =

    Saeed Alaei and Ali Makhdoumi and Azarakhsh Malekian and Sasa Pekec , title =. Management Science , volume =

  110. [118]

    Yuan Deng and Vasilis Gkatzelis and Xizhi Tan and Grigoris Velegkas and Song Zuo , title =

  111. [119]

    Revenue Sharing at Music Streaming Platforms , journal =

    Berganti. Revenue Sharing at Music Streaming Platforms , journal =

  112. [120]

    Multidimensional budget-feasible mechanism design , author=

  113. [121]

    Budget feasible mechanism design: from prior-free to bayesian , author=

  114. [122]

    Operations Research , volume=

    Deterministic Budget-Feasible Clock Auctions , author=. Operations Research , volume=

  115. [123]

    Deterministic Budget-Feasible Clock Auctions , author=

  116. [124]

    Black-Box Lifting and Robustness Theorems for Multi-Agent Contracts , author=

  117. [125]

    2025 , author =

    Efficient and effective budget-feasible mechanisms for submodular valuations , journal =. 2025 , author =

    2025

  118. [126]

    On budget-feasible mechanism design for symmetric submodular objectives , author=

  119. [127]

    SIAM Journal on Computing , volume=

    A duality-based unified approach to bayesian mechanism design , author=. SIAM Journal on Computing , volume=

  120. [128]

    Symposium on Algorithmic Game Theory (SAGT) , year=

    Budget feasible mechanisms for procurement auctions with divisible agents , author=. Symposium on Algorithmic Game Theory (SAGT) , year=

  121. [129]

    ACM Web Conference (WWW) , year=

    Randomized pricing with deferred acceptance for revenue maximization with submodular objectives , author=. ACM Web Conference (WWW) , year=

  122. [130]

    International Conference on Web and Internet Economics , year=

    Improved Budget-Feasible Mechanisms for Submodular Valuations: Beating 4 Deterministically in Linear Time , author=. International Conference on Web and Internet Economics , year=

  123. [131]

    Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms , author=

  124. [132]

    Artificial Intelligence , volume=

    Efficient and effective budget-feasible mechanisms for submodular valuations , author=. Artificial Intelligence , volume=

  125. [133]

    Journal of Political Economy , volume=

    Clock auctions and radio spectrum reallocation , author=. Journal of Political Economy , volume=

  126. [134]

    Information processing letters , volume=

    The budgeted maximum coverage problem , author=. Information processing letters , volume=

  127. [135]

    2006 , publisher=

    Prediction, learning, and games , author=. 2006 , publisher=

    2006

  128. [136]

    Dynamics of profit-sharing games , author=

  129. [137]

    Mathematics of operations research , volume=

    Optimal auction design , author=. Mathematics of operations research , volume=

  130. [138]

    Designing menus of contracts efficiently: The power of randomization , author=

  131. [139]

    Contracts under moral hazard and adverse selection , author=

  132. [140]

    On supermodular contracts and dense subgraphs , author=

  133. [141]

    Multi-agent combinatorial contracts , author=

  134. [142]

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

  135. [143]

    Symposium on theoretical aspects of computer science (STACS) , year=

    Worst-case equilibria , author=. Symposium on theoretical aspects of computer science (STACS) , year=

  136. [144]

    2026 , journal=

    Compensation Design , author=. 2026 , journal=

    2026

  137. [145]

    The power of menus in contract design , author=

  138. [146]

    A reduction from multi-parameter to single-parameter Bayesian contract design , author=

  139. [147]

    arXiv:2211.06850 , year=

    Approximate optimality of linear contracts under uncertainty , author=. arXiv:2211.06850 , year=

    arXiv

  140. [148]

    Contracts with private cost per unit-of-effort , author=

  141. [149]

    arXiv:2209.01146 , year=

    Generalized principal-agency: Contracts, information, games and beyond , author=. arXiv:2209.01146 , year=

    arXiv

  142. [150]

    Boucheron, Stephane and Lugosi, Gabor and Massart, Pascal , title=

  143. [151]

    Journal of the American Statistical Association , volume=

    Hoeffding, Wassily , title=. Journal of the American Statistical Association , volume=

  144. [152]

    Neogi, Rian and Pashkovich, Kanstantsin and Swamy, Chaitanya , booktitle=EC, year=. An

  145. [153]

    Anonymous authors , title=

  146. [154]

    Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , pages=

    Feige, Uriel and Feldman, Michal and Immorlica, Nicole and Izsak, Rani and Lucier, Brendan and Syrgkanis, Vasilis , title=. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , pages=

  147. [155]

    Random Structures & Algorithms , volume=

    A sharp concentration inequality with applications , author=. Random Structures & Algorithms , volume=

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.