Pith. sign in

REVIEW 3 major objections 4 minor 155 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read For subadditive valuations, a universally truthful budget-feasible mechanism achieves a constant approximation (factor C+ε, C below 86.399) in polynomial time via demand queries, refuting the conjecture that constant approximation…

desk verdict A strong paper with a genuinely new structural lemma; the polynomial-time mechanism's tail analysis has a corrupted display that needs a careful referee, but the math appears to hold. read the letter →

arxiv 2608.04337 v2 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 91B2668W2591A10
keywords budget-feasiblemechanismdesigncompensationsubadditivevaluationsself-boundingfunctionssmoothinglemmademandqueriespriceofstabilityuniversaltruthfulness
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

Budget-feasible mechanism design asks how much of the optimal value a buyer can secure from strategic sellers while staying within a hard budget and keeping truthful reporting dominant. The paper's central claim is that for subadditive valuations — the most general complement-free class — a constant factor is achievable, and even computable: for every fixed $\epsilon>0$, a universally truthful, individually rational, budget-feasible mechanism runs in polynomial time via demand queries and approximates the optimum within a factor $C+\epsilon$, with $C<86.399$. The engine is an indirect, non-truthful game called compensation design with marginal-contribution payments, whose equilibrium analysis (a constant price of stability) is converted into truthful direct mechanisms. The load-bearing structural discovery is a smoothing lemma: every monotone subadditive valuation is $2$-approximated by a self-bounding function. If the paper is right, the 2011 conjecture that constant approximation requires exponentially many demand queries is false, and the best-known approximation ratios for submodular, XOS, and subadditive valuations all improve.

What carries the argument

The argument is carried by the potential function $\Phi^F_b(S)=F(S)\prod_{i\in S}(1-b_i/B)_+$ for a normalized monotone proxy $F$ that is self-bounding, meaning the sum of the final marginal contributions $\sum_{i\in S}(F(S)-F(S\setminus\{i\}))$ is at most $F(S)$. A global maximizer of $\Phi^F_b$ is a pure Nash equilibrium of the game induced by the marginal-contribution payment rule $p^F_i(S)=B\,(F(S)-F(S\setminus\{i\}))/F(S)$, and the same maximizer, endowed with Myerson threshold payments, becomes a truthful and budget-feasible direct mechanism: an agent whose bid exceeded its marginal payment would break the equilibrium, so thresholds are bounded by marginals, and the self-bounding property bounds the sum of thresholds by the budget. Because subadditive functions need not be self-bounding, the smoothing operator $\widetilde{v}(S)=\int_0^1\mathbb{E}[v(R_q(S))]\,dq$, which keeps each element of $S$ with probability $q$ and averages over $q$, produces a self-bounding $\widetilde{v}$ with $\frac{1}{2}v(S)\le\widetilde{v}(S)\le v(S)$, via the identity $\sum_{i\in S}(\widetilde{v}(S)-\widetilde{v}(S\setminus\{i\}))=v(S)-\widetilde{v}(S)$. The polynomial-time implementation approximates the potential by a core-tail decomposition (enumerating the $\ell$ most expensive agents and handling the light tail through random partitioning, one demand query, and uniform thinning at rate $q=\nu/v(D)$), an empirically sampled proxy $\widehat{v}_m$, and a filtering step that certifies budget feasibility of the final threshold payments.

What would settle it

On a small subadditive example such as $v(\emptyset)=0$, $v(T)=1$ for every nonempty proper $T$, and $v(N)=2$, compute the smoothed value exactly from $\widetilde{v}(S)=\sum_{T\subseteq S}v(T)\,\frac{k!(|S|-k)!}{(|S|+1)!}$ and check the identity $\sum_{i\in S}(\widetilde{v}(S)-\widetilde{v}(S\setminus\{i\}))=v(S)-\widetilde{v}(S)$ and the variance bound $\mathrm{Var}(\widetilde{v}(T^*_0))\le(\widetilde{M}_{T^*}/2)\,\mathbb{E}[\widetilde{v}(T^*_0)]$ for the random half $T^*_0$ of any budget-feasible tail $T^*$. A single violated instance of either inequality refutes the factor-2 smoothing claim or the tail concentration (Lemma D.3), and with them the constant-factor potential allocator of Theorem 5.2 and the $C+\epsilon$ mechanism.

Watch

Extended reading notes

Core claim

The paper claims three main results. Without computational constraints, universally truthful budget-feasible mechanisms achieve approximation ratios of $3$ for monotone submodular valuations, $e+1\approx 3.718$ for nonmonotone submodular and for XOS valuations, and $2e+1\approx 6.436$ for subadditive valuations, with deterministic large-market versions approaching $2$, $e$, and $2e$; these improve the previous best of $3.798$, $9.742$, $28$, and $33$. For subadditive valuations, a new mechanism (PolyRMC) runs in polynomial time via demand queries and achieves factor $C+\epsilon$ with $C=1+2e\rho_0<86.399$, where $\rho_0\approx 15.7083$ comes from the potential-approximation analysis; this resolves the long-standing question attached to the Dobzinski–Papadimitriou–Singer conjecture, which asserted that a constant approximation requires exponentially many demand queries. Beyond the complement-free hierarchy, the paper claims an $e\beta+o_\lambda(1)$ deterministic approximation for $\beta$-self-bounding valuations in large markets, and an impossibility result: without the large-market assumption, no universally truthful mechanism achieves a bounded approximation even for $\beta=2$. The same smoothing lemma yields a $2e$-approximate restrained core for multiwinner elections under subadditive utilities, answering an open question in that literature.

Load-bearing premise

The polynomial-time mechanism collapses if the smoothed value of a random half of the optimal tail does not concentrate as claimed: the proof needs the variance of that random half to be at most half its typical value times the largest single-item smoothed value (Lemma D.3), and the displayed statement of the lemma that converts this into a usable lower bound (Lemma 5.6) appears corrupted in the provided text, making this the hardest premise to verify.

Editorial extensions

If this is right

  • The Dobzinski–Papadimitriou–Singer conjecture is false: a constant approximation for subadditive valuations uses only polynomially many demand queries, not exponentially many.
  • Without computational constraints, universally truthful mechanisms achieve ratios of $3$ (monotone submodular), $e+1$ (XOS and nonmonotone submodular), and $2e+1$ (subadditive), and these become deterministic near-$2$, near-$e$, and near-$2e$ in large markets.
  • Fair multiwinner elections gain a $2e$-approximate restrained core for subadditive voter utilities, settling an open question about proportionality under general valuations.
  • For $\beta$-self-bounding valuations, the paper proves an $e\beta$ large-market approximation; for $\beta\ge 2$, outside large markets, no universally truthful mechanism has a bounded approximation, so the frontier of universal truthfulness runs through the complement-free hierarchy as far as these results go.
  • Through the monotone closure — whose optimal value equals the original optimum — the XOS and subadditive guarantees extend to nonmonotone valuations, so the improved ratios apply to the full classes claimed.

Reading between the lines

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

  • The paper says no attempt was made to optimize the constant; since $C=1+2e\rho_0$ with $\rho_0\approx 15.7083$ determined by a single quadratic-combination lemma, tightening that lemma or the core-tail mixing would lower $C$ directly, so the true gap between polynomial-query and exponential-query mechanisms may be far smaller than the distance from $86.4$ to $6.436$.
  • The smoothing lemma replaces the classical $\Theta(\log n)$-distortion embedding of subadditive functions into XOS with a constant-distortion embedding into self-bounding functions; other algorithmic-game-theory problems whose bottleneck is subadditive-to-XOS conversion could inherit this factor-2 substitute, an application the paper only gestures at in its conclusions.
  • The $\beta=2$ impossibility rests on an extreme two-agent complementarity instance, so it marks a clean dividing line: constant-factor universal truthfulness lives exactly within the complement-free hierarchy, and any positive result for complements must come from large markets, different solution concepts, or weaker incentive guarantees.
  • The query count for fixed $\epsilon$ is a high-degree polynomial — enumerating $O(n^\ell)$ subsets with $\ell=\ell(\epsilon)$ plus $m=O(n^4(n+\log(1/\epsilon))/\epsilon^2)$ empirical evaluations — so 'polynomial time' here carries parameter dependence the paper does not optimize.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper develops a unified framework, based on non-truthful compensation design, for constructing truthful budget-feasible mechanisms. It establishes constant price-of-stability bounds for marginal-contribution payment rules over self-bounding proxies, proves a new smoothing lemma showing that every monotone subadditive function admits a self-bounding 2-approximation, and translates these results into universally truthful mechanisms. The information-theoretic results improve the state of the art for monotone submodular (3), nonmonotone submodular (e+1), XOS (e+1), and subadditive (2e+1) valuations, with deterministic large-market improvements. The main result is a universally truthful, individually rational, budget-feasible mechanism for subadditive valuations that runs in polynomial time using demand queries and achieves approximation factor C+epsilon with C<86.399, resolving the Dobzinski–Papadimitriou–Singer conjecture. The polynomial-time implementation is based on a core-tail decomposition, a nonbossy potential allocator, empirical estimation of the smoothed value, and a filtering step that restores budget feasibility.

Significance. If the central claims are correct, the paper resolves a long-standing open problem in budget-feasible mechanism design and substantially advances the state of the art for submodular, XOS, and subadditive valuations. The smoothing lemma, showing that every subadditive function is 2-approximated by a self-bounding function, is an elegant structural result with independent applications, including the multiwinner-elections core question. The proof strategy, moving from compensation design to truthful direct mechanisms through potential arguments, is conceptually novel and well explained. The information-theoretic theorems are supported by clean, largely self-contained proofs, and the paper provides explicit constants and query bounds for the polynomial-time mechanism. The main caveat is that the most intricate part of the polynomial-time analysis, specifically the concentration lemma that underlies the tail approximation, cannot be fully audited from the typeset text due to corrupted displayed formulas.

major comments (3)
  1. [§5.1.2, Lemma 5.6, equation (18)] Equation (18) is the load-bearing bridge between the concentration estimate (17), the grid estimator H-hat_b, and the constant-factor tail approximation in Theorem 5.2, but the displayed formula contains unreadable glyphs (for example '⌟roo⟪⟪op') in the cross-term. The proof text suggests the intended inequality is E[ν] ≥ (1/(2(1+η))) Φ(T*) − (1/(2(1+η))) sqrt( max_{|S|≤ℓ} Φ(S) · Φ(T*) ), but this is a reconstruction rather than a reading of the manuscript. A wrong coefficient or sign in the cross-term would change the constant and potentially invalidate the claimed polynomial-time approximation. This corruption must be repaired and the exact inequality stated cleanly before the central result can be certified.
  2. [§5.1.3, display (19), and Theorem 5.2] The same corrupted square-root notation reappears in the lower bound for the expected potential of the tail branch and in the proof of Theorem 5.2. Since the randomization between the core and tail branches (Lemma 5.8) is applied to this expression, the entire constant-factor computation for the potential allocator depends on the exact algebraic form of the cross-term. The authors should re-typeset these displays and include the intermediate algebra explicitly.
  3. [§D.3, Lemma D.3 and proof of Lemma 5.6] The variance bound Var(v-tilde(T*_0)) ≤ (M/2) E[v-tilde(T*_0)] is a crucial step: it produces the square-root cross-term in Lemma 5.6. Although the Efron–Stein argument is plausible and the final bound is stated without corruption, the surrounding proof of Lemma 5.6 contains corrupted symbols in the passage using that variance estimate. Given that this is the least secure link in the polynomial-time analysis, the derivation should be rewritten with every step displayed, including the monotonicity argument for the function z ↦ z − sqrt(M z)/2 on [v-tilde(T*)/2,∞).
minor comments (4)
  1. [Definition 2.1] The monotonicity definition contains a corrupted arrow symbol 'b_i' ≤ b_i /Leftr⫯g⊸tl⫯ne⇒'; this should be typeset as a standard logical implication.
  2. [§5.2.1] The sampling trick is described as drawing a random permutation of 'N ∪ {/⊙◇⊞}', but the marker symbol appears corrupted; the intended construction is a random permutation with a separator, and the notation should be cleaned up.
  3. [Table 1] The entry for β-self-bounding valuations in the general column reads 'unbounded(((β≥2)))', which appears to be a formatting artifact; the statement that the approximation is unbounded for β≥2 should be presented normally.
  4. [Mechanism 4.1] The threshold formulas use the notation 'Φ F_i,in' and 'Φ F_i,out' in a way that is understandable but visually cluttered; adding a short explanatory sentence or a displayed definition would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central new results are proved from first principles; self-citations appear only in a warm-up and are not load-bearing.

full rationale

The claimed derivation chain is self-contained for every result presented as new. Main Result 4 (the smoothing lemma) defines v-tilde in Definition 3.1 via an integral of expected random-subset values; the 2-approximation follows by integrating v(S) <= v(R_q(S)) + v(S\R_q(S)), and the self-bounding inequality follows from the proved identity in Lemma 3.5, sum_i (v-tilde(S)-v-tilde(S\{i})) = v(S)-v-tilde(S). No step defines v-tilde in terms of the target inequality, and the calculus identity is proved rather than assumed. The price-of-stability bounds (Theorems 3.3, 3.4, 3.6) are derived from the potential function with explicit constants such as eta/e, e+1, and 2e+1; these constants are analytic consequences, not fitted parameters. The RMC translation (Lemma 4.1 and Theorem 4.1) uses Myerson's characterization and a self-bounding budget-feasibility argument, both proved in the text. The polynomial-time mechanism (Theorems 5.1 and 5.2) is built from a core-tail decomposition, an enumerated core, a demand-query tail estimator with grid search (Lemma 5.3), concentration bounds (Lemma 5.6), uniform thinning (Lemma 5.7), and a filtering step; the approximation factor C+epsilon is an analytic combination of those bounds, not a parameter chosen to match a target value. The only self-citation appears in the warm-up: Theorem 3.1 and Corollary 3.1 are recalled from Anagnostides et al. (2026) and then used for the monotone-submodular bullet of Theorem 4.1. That is a prior, parameter-free theorem about marginal-contribution games, and it is not the load-bearing premise of the paper's central claims. The corrupted typesetting of Lemma 5.6(18) and parts of Lemma D.3 is a verifiability concern, not evidence of an input-output equivalence; the surrounding proof text reconstructs the intended inequality without importing the conclusion.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central derivation uses standard probabilistic and game-theoretic tools (Myerson's lemma, Hoeffding's inequality, Efron-Stein inequality, potential-function arguments) and domain assumptions (normalized monotone subadditive/self-bounding valuations, private costs, budget feasibility, demand-oracle access with fixed tie-breaking). The large-market assumption is needed for deterministic improvements and for the positive result on beta-MPH, and the paper proves this is necessary for beta=2. No invented entities are introduced; the smoothed function v-tilde is defined from v and its properties are proven, not postulated.

free parameters (4)
  • mixing probability alpha in RMC = 1/3 (submodular), 1/(e+1) (XOS), 1/(2e+1) (subadditive)
    Chosen analytically to balance the singleton branch (value M) and the marginal-contribution branch (value about (OPT-M)/e or (OPT-M)/(2e)); not fitted to data.
  • core size ell = ell(epsilon) = constant depending on epsilon, left unspecified
    Any sufficiently large constant yields the polynomial-time bound; it trades off enumeration cost O(n^ell) against the approximation factor, so it is an accuracy/efficiency parameter.
  • sampling and accuracy parameters delta, epsilon-hat, m, B_epsilon-hat = epsilon-hat = delta/(4n^2), delta = epsilon/(64e(rho0+1)), m = O(n^4/epsilon^2 (n + log(1/epsilon)))
    Chosen in (31)-(32) so that the empirical estimate v-hat_m is a (1 +/- epsilon-hat)-approximation of v-tilde with probability at least 1-delta; these parameters affect only the constant C and the poly(n) query count.
  • thinning probability q = nu/v(D) = computed per instance from demand and value queries
    Retains each element of the demand set D with probability q to convert a high-value set D into one with high potential value; the choice q = nu/v(D) is data-dependent but not used to fit constants.
assumptions (7)
  • standard math Myerson's payment characterization for single-parameter truthful mechanisms (Lemma 2.1)
    Turns monotone allocation rules into truthful, individually rational mechanisms via threshold payments.
  • standard math Potential-function theorem for pure Nash equilibria (Monderer and Shapley)
    Global maximizers of the potential are pure equilibria of the marginal-contribution game (Theorem 3.2).
  • standard math Hoeffding's inequality
    Used to prove the uniform sampling approximation of v-tilde (Lemma 5.9).
  • standard math Efron-Stein inequality
    Used to bound the variance of a random half of the optimal tail (Lemma D.3).
  • domain assumption Budget-feasible mechanism design model: private costs, additive utilities, ex post IR and budget feasibility
    The standard Singer framework the paper operates in, as defined in Section 1.
  • domain assumption Oracle model: value and demand oracles with fixed tie-breaking
    The query model for the polynomial-time mechanism; tie-breaking is critical for nonbossiness (Remark 2.1).
  • domain assumption Large-market condition for deterministic and beta-self-bounding results
    Theorems C.3 and 3.4(2)-(3) and Main Result 2 require lambda << 1 or M/OPT approximately 0; the impossibility in Section C.5 shows some such condition is necessary.

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 universally truthful budget-feasible 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 ↗

Review history (3 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

155 extracted references · 10 linked inside Pith

  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 15, 2026 · model on record in the stance chip above.