Pith. sign in

REVIEW 3 major objections 4 minor 3 cited by

Combinatorial Selection with Costly Information

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

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

Pith's one-line read The paper proves that local per-alternative approximations compose without loss into global bounds for costly-information combinatorial selection, yielding √2, 2, O(κ), and 0.582 guarantees for Pandora's Box variants.

desk verdict Ambitious and likely important framework, but the central lower-bound proof has a gap that needs a real fix. read the letter →

arxiv 2412.03860 v2 pith:RQXEHWJ4 submitted 2024-12-05 cs.DS

Shuchi Chawla , Dimitris Christou , Amit Harlev , Ziv Scully This is my paper · ORCID
classification cs.DS MSC 68W2590C2790C40
keywords combinatorialselectioncostlyinformationacquisitionbanditsuperprocessesPandora'sboxcommitmentgaplocalapproximationsurrogatecostsmatroidconstraints
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

This paper tries to establish a decomposition principle for combinatorial selection problems in which information about each alternative is acquired through a sequence of costly steps, modeled as a finite-horizon Markov decision process. The key claim is that the global 'commitment gap'—the loss from fixing all local inspection decisions in advance—is governed entirely by per-alternative, local conditions: if each MDP admits an α-local commitment, then the whole matroid-constrained instance has commitment gap at most α. This is made possible by a novel cost amortization that assigns each alternative a surrogate cost whose distribution is independent of the chosen inspection strategy. A sympathetic reader would care because prior solutions existed only for narrow special cases, whereas this framework applies to arbitrary acyclic MDPs under matroid (and frugal) constraints and yields the first approximation guarantees for several Pandora's Box variants: √2 for Partial Inspection, 2 for Additive Pandora's Box, O(κ) for a new Weighing Scale problem, and 0.582 for matroid-constrained Optional Inspection in the maximization setting, the first efficient committing policy provably better than 0.5.

What carries the argument

The load-bearing object is the water-filling surrogate cost W*_M, a random variable extracted from an MDP's optimality curve fM(y) by the relation fM(y) = E[min(y, W*_M)]; it is the MDP-level generalization of the surrogate costs familiar from Pandora's Box analysis. For Markov chains, W*_M is generated by a bottom-up water-filling amortization that distributes each action's cost onto the cheapest downstream trajectories; the paper's novel step is Lemma 3.5, which extends this to general acyclic MDPs by showing that for every deterministic commitment π there exists an amortized cost function ρπ on trajectories—with cost-sharing and cost-dominance properties—whose induced distribution over surrogate costs is exactly W*_M, independent of π. This action independence is what makes both the global lower bound and the composition theorem work: the interaction between global and local decision-making is severed, so an α-local approximation condition on each MDP alone (f_{Mπ}(αy) ≤ α f_M(y) for all outside options y) suffices to bound the commitment gap of the whole instance by α. Each application then boils down to finding such local commitments: peeking-versus-opening for PBPI, a minimum-index static probing order for APB, One-Sided Halving for WS, and a semilocal (α, β) approximation plus a matroid-greedy composition argument for PBOI.

What would settle it

Solve, by exhaustive dynamic programming, a small matroid-min-CICS instance (e.g., two finite acyclic MDPs under a rank-1 matroid) for the true optimal cost OPT(I) and compare it with the expected minimum surrogate cost E[min_{S∈F} Σ_{i∈S} W*_{Mi}], where each W*_{Mi} is read off the optimality curve fM(y) = E[min(y, W*_M)] per Definition 7. Theorem 3.4 asserts OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}]; one instance where the strict reverse inequality holds would refute the amortization foundation and, with it, all the composition results.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that the commitment gap of a Costly Information Combinatorial Selection instance can be bounded by local approximation ratios of its constituent information-acquisition MDPs. For each MDP M, Whittle's local game (M, y)—the choice between advancing M and accepting an outside option of cost y—defines an optimality curve fM(y), which in turn defines a water-filling surrogate cost W*_M via fM(y) = E[min(y, W*_M)]. The paper proves a lower bound on the unrestricted optimum, OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}] (Theorem 3.4), using a new amortization lemma (Lemma 3.5) showing that for every deterministic commitment, action costs can be shifted onto terminal outcomes so that the induced surrogate-cost distribution equals W*_M regardless of the commitment—action independence. It then proves the composition theorem (Theorem 4.1): if each Mi admits an α-local approximation (f_{Mπ_i}(αy) ≤ α f_{Mi}(y) for all y), the global commitment gap is at most α. The four applications—√2 for matroid-PBPI, 2 for matroid-APB, O(κ) for matroid-WS with the One-Sided Halving commitment, and 0.582 for matroid-max-PBOI via a semilocal approximation—are instantiations of this recipe.

Load-bearing premise

The entire framework rests on the action-independence lemma: for every way of committing to actions inside an alternative's (acyclic) information process, action costs can be shifted onto terminal outcomes so the resulting surrogate-cost distribution is exactly the one read off the MDP's optimality curve; if that fails—say for cyclic processes, which are explicitly excluded—the lower bound and all composition results collapse.

Editorial extensions

If this is right

  • For any matroid-CICS instance, constructing an α-approximation reduces to a per-MDP search for α-local commitments; the composed policy inherits the ratio with no dependence on the number of alternatives n.
  • Mixed instances containing partial-inspection, additive, and optional-inspection boxes together still have commitment gap at most 2, so heterogeneous inspection protocols no longer require bespoke algorithms.
  • The framework transfers to any feasibility constraint admitting a frugal approximation algorithm, with the global factor becoming the product of the local α and the frugal β (Corollary B.3).
  • Additive Pandora's Box—equivalently, Pandora's Shortest Path on disjoint s-t paths—has constant commitment gap 2 regardless of the number of components per box, though the achieving commitment in the proof is existential.
  • Matroid-max-PBOI attains the first efficiently computable committing policy strictly better than the trivial 0.5, namely 0.582, via semilocal approximation.

Reading between the lines

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

  • Because W*_M is strategy-independent, it functions as a canonical 'price of information' for an alternative; a natural (untested) conjecture is that index policies built from these surrogate costs remain near-optimal for constraints that are 'almost' greedy, such as laminar matroids, losing only a constant or poly-log factor.
  • The framework assumes known distributions and mutually independent MDPs; an extension the paper leaves implicit would replace true distributions by empirical estimates, with the water-filling construction suggesting that estimation error would propagate additively through the composition bound at an O(1/√n) rate per alternative.
  • Theorem 7.2 shows pointwise approximation for Weighing Scale cannot be constant, yet the paper leaves open whether the weaker local approximation notion yields a universal constant; the PBOI precedent (where local failed but semilocal succeeded) suggests the better WS bound may need a similarly non-pointwise condition.
  • The semilocal composition is the one place the framework exploits matroid structure beyond frugality; porting semilocal approximation to other MDP families with a grab-like deterministic-terminal action—flagged by the paper itself—would extend the 0.582-style gains to new domains.
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 defines Costly Information Combinatorial Selection (CICS), a class of stochastic selection problems in which each variable is inspected through an independent acyclic MDP, and proposes a framework for approximately optimal committing policies under matroid feasibility constraints (with an extension to frugal constraints). The main ingredients are an amortized surrogate-cost construction for MDPs, a Whittle-integral-style lower bound on the optimal adaptive cost, a notion of local approximation that composes into global approximation guarantees, and applications to four problems: Pandora's Box with Partial Inspection (a sqrt(2) commitment gap), Additive Pandora's Box (a 2-approximation), a new Weighing Scale problem (an O(kappa) gap), and matroid PBOI (a 0.582 approximation in the maximization setting). The paper also carries the framework through the maximization setting and to general frugal algorithms.

Significance. If the lower-bound theorem and composition theorem were fully established, this would be a substantive contribution: it offers a unified decomposition for bandit superprocesses beyond indexable settings, gives new approximation bounds for several variants of Pandora's Box, introduces a natural new problem (the Weighing Scale problem), and provides the first efficient policy that beats 0.5 for matroid-PBOI. The appendix contains substantial, mostly self-contained proofs, and the action-independence/water-filling construction is a genuinely novel technical idea. The significance, however, is contingent on repairing the proof of the central Whittle-integral lower bound (Theorem 3.4), because the PBPI, APB, WS, and PBOI results are all derived through it.

major comments (3)
  1. [Appendix D.2, proof of Claim 4] The claim that the expected cost of following commitment pi is at least E[X(pi) W*_M] is reduced to proving E[W*_{Mpi}] >= E[W*_M]. The displayed calculation proves only the unconditional expectation comparison. The indicator X(pi) is correlated with the realized trajectory, because the global policy's stopping decision depends on realized terminal values, so E[X W*_{Mpi}] >= E[X W*_M] does not follow. Since inequality (8) in Theorem 3.4 and hence the Whittle-integral lower bound, Theorem 4.1, and the ratios sqrt(2), 2, O(kappa), and 0.582 all depend on this step, the submitted proof is incomplete. A possible repair is to apply Lemma 3.1 directly to the amortization supplied by Lemma 3.5; the paper should supply that argument, or an equivalent coupling, rather than the unconditional comparison given in the current text.
  2. [Lemma 3.5 and its proof] The lemma states that the cost-sharing vector b^pi is non-negative, but the proof defines b^pi_{sigma tau} = E[rho^pi(tau)] - E[rho^{pi|s}(tau_s)]. Lemma 3.6 only guarantees E[m(z)] <= z for each z; it does not imply E[m(g_j vee rho^{pi|s}(tau_s))] >= E[rho^{pi|s}(tau_s)], so individual entries can be negative even though the aggregate over tau is non-negative. The lemma statement and the Markov-chain amortization definition in Definition 4 require b_{s tau} >= 0. This is not merely cosmetic: Lemma 3.1's proof retains terms of the form b_{s tau}(Pr[I(s)]Pr[R(tau)|R(s)] - Pr[A cap R(tau)]), which can change sign if b_{s tau} < 0. The proof should establish entrywise non-negativity, or the subsequent uses of the lemma should be reformulated.
  3. [Section 5.2, Claims 1-2] The two claims are stated for all y in R with alpha equal to (c_o/c_p)(1 - c_o/g_p) and 1 + min(c_p/c_o, c_o/g_p), respectively. Neither claim states the regime assumption g_p < g_o < tau that the preceding paragraph introduces, and the first alpha can be less than 1 in general; for a deterministic value X = 0 it becomes c_o/(c_o + c_p) < 1. Because Definition 8 and Theorem 4.1 require alpha >= 1, the claims need to include the regime in their statements or explicitly split off the complementary case in which opening the box is 1-locally optimal. Without this, the derivation of the sqrt(2) bound at the end of Section 5.2 is not complete.
minor comments (4)
  1. [Section 3.3, proof of Lemma 3.5] In several places the proof writes rho^{pi|sigma} and b^{pi|sigma} where the intended objects are rho^{pi|s} and b^{pi|s}, the restrictions of the commitment after transitioning to state s; this should be corrected.
  2. [Section 8.3 and Appendix I] The semilocal composition algorithm is numbered Algorithm 2 in the main text and Algorithm 3 in Appendix I; the numbering should be made consistent.
  3. [Section 7, Theorem 7.1] The parameter kappa_i = mu_i/M_i + log(mu_i/g_i) is undefined when M_i = 0 or g_i = 0; the statement should give the quantile convention for the median and the assumptions required for g_i > 0.
  4. [Definition 1] The definition says that the terminal accept action 'results in a value v(s)', but in the minimization setting that value is a cost and in the maximization setting it is a reward; the sign convention should be made explicit at the definition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's bounds are derived from explicitly proven amortization and local-approximation theorems, not from self-referential definitions or fitted predictions.

full rationale

The central derivation chain is not circular. Theorem 3.4 lower-bounds OPT by E[min_{S∈F} Σ_i W*_{M_i}], where each W*_{M_i} is defined via the local-game optimality curve f_{M_i} (Definition 7), not via the global optimum or via the commitment being evaluated. Lemma 3.5 is an explicit inductive construction using the stochastic-dominance lemma (Lemma 3.6), which is itself proven in Appendix D.3; the action-independence property is derived, not assumed. The composition theorem (Theorem 4.1) is proven by repeated stochastic-dominance substitution using Definition 8 as a local inequality against f_M, and the paper explicitly notes that standard local α-approximation would give an exponential-in-n bound (Appendix C), which is exactly the kind of content check that rules out a merely definitional equivalence. The application-specific constants (√2 for PBPI, 2 for APB, O(κ) for WS, 0.582 for matroid-PBOI) are derived from these theorems with fixed parameters; no parameter is fitted to the quantity it later predicts. Self-citations to Scully and Doval [2024] and Gupta et al. [2019] are not load-bearing: the relevant Markov-chain optimality result is restated and reproved in Theorem 3.2 with a self-contained amortization argument, and the local-approximation composition is reproved as Theorem 4.1. Appendix I.1 cites Scully and Doval [2024, Theorem 5.4] only as a proof strategy while giving the full argument. The skeptical concern about Claim 4 in Appendix D.2 (the acceptance-weighted step E[X·W*_{Mπ}] ≥ E[X·W*_M] may not follow from the unconditional inequality) is a possible correctness gap, not circularity: it does not assume the target lower bound. Under the review rules, correctness risk is not circularity, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data. The paper's constructs (water filling surrogate costs, optimality curves, local approximation) are mathematically defined within the framework, not postulated entities with independent evidential weight. The load-bearing assumptions are the standard ones listed above; the most consequential is the action independence property of Lemma 3.5, which is proven but is intricate.

assumptions (5)
  • domain assumption Each costly information MDP is acyclic (finite horizon).
    Stated in Section 2: 'each costly information MDP MX is inherently acyclic... We will also assume a bounded horizon.' The framework's water filling and induction proofs rely on a topological order.
  • domain assumption Finite state, action, and value supports.
    Assumed for exposition in Section 2; the authors claim extension to continuous settings. The Weighing Scale section also argues a finite-horizon truncation is without loss.
  • domain assumption Independence of the constituent MDPs.
    Key assumption in Section 1: 'exploring one alternative does not affect the state of another.' All composition theorems require this.
  • domain assumption Known distributions for values and transitions.
    Each MDP's transition and value distributions are given; used throughout to compute water filling indices and optimality curves.
  • domain assumption Matroid (or frugal) feasibility constraint.
    Main results stated for matroids in Definition 3 and extended to frugal constraints in Appendix B. The index policy optimality for Markov chains uses the matroid greedy property.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Combinatorial Selection with Costly Information." pith.science (2026). https://pith.science/paper/RQXEHWJ4

@misc{pith2026241203860,
  author       = {Pith},
  title        = {Pith review of: Combinatorial Selection with Costly Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQXEHWJ4}},
  note         = {Machine review of arXiv:2412.03860}
}
read the original abstract

We consider a class of optimization problems over stochastic variables where the algorithm can learn information about the value of any variable through a series of costly steps; we model this information acquisition process as a Markov Decision Process (MDP). The algorithm's goal is to minimize the cost of its solution plus the cost of information acquisition, or alternately, maximize the value of its solution minus the cost of information acquisition. Such bandit superprocesses have been studied previously but solutions are known only for fairly restrictive special cases. We develop a framework for approximate optimization of bandit superprocesses that applies to arbitrary acyclic MDPs with a matroid feasibility constraint. Our framework establishes a bound on the optimal cost through a novel cost amortization; it then couples this bound with a notion of local approximation that allows approximate solutions for each component MDP in the superprocess to be composed without loss into a global approximation. We use this framework to obtain approximately optimal solutions for several variants of bandit superprocesses for both maximization and minimization. We obtain new approximations for combinatorial versions of the previously studied Pandora's Box with Optional Inspection and Pandora's Box with Partial Inspection; the less-studied Additive Pandora's Box problem; as well as a new problem that we call the Weighing Scale problem.

Figures

Figures reproduced from arXiv: 2412.03860 by the authors.

Figure 1
Figure 1. Three examples of a Pandora’s Box style information acquisition protocol. (Left:) A classical PB [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The water filling amortization for Markov chains [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. We consider the same setting as in Example 1. The optimality curve for MDP [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: For an MDP M with a given optimality curve (left), we contrast two approximation notions: stan￾dard α-approximation (center) vs. α-local approximation (right). In both cases, achieving the approximation requires designing a commitment whose optimality curve lies below …
Figure 5
Figure 5. Figure 5: In PBPI, a peeking box B = (D, co , cp ) is initially closed. In order to learn the value realization realization X ∼ D, the decision maker can either peek into the box (at a cost of c p ) or open it (at a cost of c o ). To accept the box, the decision maker must first…
Figure 6
Figure 6. Figure 6: The optimality curves for a box B with opening cost c o = 0.5, value X = 0 with probability 0.5 and X = 2 with probability 0.5 and peeking cost c p = 0.4 (left) and c p = 0.1 (right). The optimality curve of B is given by the minimum of the three curves. Observe that t…
Figure 7
Figure 7. Figure 7: The indices g and h of the alternative can be obtained by the inverse CDF of the random value; the highlighted ares equal the weighing cost c. The figure on the right corresponds to the Markov chain for One-Sided Halving instantiated with threshold t1 = 2, t2 = 8 for a…
Figure 8
Figure 8. Figure 8: An optional inspection box B = (D, c) can me modeled as an MDP M with two actions, grab and open, incuring costs 0 and c and resulting to rewards E [X] and X respectively. On the right side, we demonstrate the optimality curves for the local game (M, y) for a box with …
Figure 9
Figure 9. Figure 9: The red and blue lines represent the optimality curves for grabbing [PITH_FULL_IMAGE:figures/full_fig_p032_9.png]
Figure 10
Figure 10. Figure 10: The MDPs M1 (left) and M2 (right). All the actions in M2 have a cost of 0. There are three committing policies for M2 with optimality curves f1(y) (blue), f23(y) (orange) and f24(y) (red). • We first consider the set of policies that start by taking the costly action …
Figure 11
Figure 11. Figure 11: The induction step. Random variables X and Z agree up to index 2. The line ℓ(y) extends the line-segment of fX(y) from x2 to x3 and cuts fZ(y) on some y = s ≥ x3. Let h(y) denote the highlighted curve. The random variable Z ′ that has curve fZ′ (y) = h(y) agrees with …
Figure 12
Figure 12. Figure 12: Here, J = {z2, z3}. At each step, we isolate the leftmost point of fZ(y) that is dominated by ℓ(y) and use our gadget to distribute it between a and the next point. Eventually, we recover a random variable with optimality curve min{fZ(y), ℓ(y)}. 47 [PITH_FULL_IMAGE:f…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Markovian Pandora's box

    cs.GT 2025-01 reject novelty 7.0 of 10

    For Pandora's box with Markovian reward correlations and order constraints, the paper claims optimal fully adaptive strategies for forest precedence graphs and fast static-transition approximations.

  2. T-TAMER: Provably Taming Trade-offs in ML Serving

    cs.LG 2025-09 reject novelty 3.0 of 10

    T-TAMER claims recall is necessary and sufficient for provably optimal early-exit and cascade serving policies, but the main extensions are under-derived and partly reduce to known Gittins-index results.

  3. The Gittins Index: A Design Principle for Decision-Making Under Uncertainty

    math.OC 2025-06 conditional novelty 2.0 of 10

    The Gittins index is presented as a general design principle that optimally solves many independent-chain decision problems and gives strong approximate solutions in Bayesian optimization and tail-latency scheduling.

Reference graph

Works this paper leans on

37 extracted references · 32 canonical work pages · cited by 3 Pith papers

  1. [1]

    The pandora's box problem with sequential inspections

    Ali Aouad, Jingwei Ji, and Yaron Shaposhnik. The pandora's box problem with sequential inspections. Available at SSRN 3726167, 2020

    work page 2020

  2. [2]

    Maximizing stochastic monotone submodular functions

    Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62 0 (8): 0 2374--2391, 2016

    work page 2016

  3. [3]

    Pandora's problem with combinatorial cost

    Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora's problem with combinatorial cost. Proceedings of the 24th ACM Conference on Economics and Computation, 2023

    work page 2023

  4. [4]

    Approximately-optimal mechanisms in auction design, search theory, and matching markets

    Hedyeh Beyhaghi. Approximately-optimal mechanisms in auction design, search theory, and matching markets. Cornell University, 2019

    work page 2019

  5. [5]

    Pandora’s problem with nonobligatory inspection: Optimal structure and a PTAS

    Hedyeh Beyhaghi and Linda Cai. Pandora’s problem with nonobligatory inspection: Optimal structure and a PTAS . Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2022

    work page 2022

  6. [6]

    Recent developments in pandora's box problem: Variants and applications

    Hedyeh Beyhaghi and Linda Cai. Recent developments in pandora's box problem: Variants and applications. SIGecom Exch., 21 0 (1): 0 20–34, October 2024

    work page 2024

  7. [7]

    Kleinberg

    Hedyeh Beyhaghi and Robert D. Kleinberg. Pandora's problem with nonobligatory inspection. Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

    work page 2019

  8. [8]

    Pandora's box problem with order constraints

    Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's box problem with order constraints. Proceedings of the 21st ACM Conference on Economics and Computation, 2020

    work page 2020

Show all 37 references
  1. [9]

    Matching with nested and bundled pandora boxes

    Robin Bowers and Bo Waggoner. Matching with nested and bundled pandora boxes. arXiv, abs/2406.08711, 2024 a

    2024 arXiv

  2. [10]

    High-welfare matching markets via descending price

    Robin Bowers and Bo Waggoner. High-welfare matching markets via descending price. In Web and Internet Economics: 19th International Conference, WINE 2023, Shanghai, China, December 4–8, 2023, Proceedings, page 59–76, 2024 b

    2023

  3. [11]

    Prophet inequalities for bandits, cabinets, and dags

    Robin Bowers, Elias Lindgren, and Bo Waggoner. Prophet inequalities for bandits, cabinets, and dags. arXiv, abs/2502.08976, 2025

    2025

  4. [12]

    Optimal sequential exploration: Bandits, clairvoyants, and wildcats

    David Brown and James Smith. Optimal sequential exploration: Bandits, clairvoyants, and wildcats. Operations Research, 61: 0 644--665, June 2013

    2013

  5. [13]

    Pandora's box with correlations: Learning and approximation

    Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora's box with correlations: Learning and approximation. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2019

    2020

  6. [14]

    Approximating pandora's box with correlations

    Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's box with correlations. In International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2021

    2021

  7. [15]

    Whether or not to open pandora's box

    Laura Doval. Whether or not to open pandora's box. Journal of Economic Theory, 175: 0 127--158, 2018

    2018

  8. [16]

    On playing golf with two balls

    Ioana Dumitriu, Prasad Tetali, and Peter Winkler. On playing golf with two balls. SIAM Journal on Discrete Mathematics, 16 0 (4): 0 604--615, 2003

    2003

  9. [17]

    Online pandora's boxes and bandits

    Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Brendan Lucier, and Michael Mitzenmacher. Online pandora's boxes and bandits. In AAAI Conference on Artificial Intelligence, 2019

    2019

  10. [18]

    Pandora box problem with nonobligatory inspection: Hardness and approximation scheme

    Hu Fu, Jia-Wen Li, and Daogao Liu. Pandora box problem with nonobligatory inspection: Hardness and approximation scheme. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2022

    2022

  11. [19]

    Stochastic Finance - An Introduction in Discrete Time

    Hans Föllmer and Alexander Schied. Stochastic Finance - An Introduction in Discrete Time. De Gruyter, 2016

    2016

  12. [20]

    Weitzman's rule for pandora's box with correlations

    Evangelia Gergatsouli and Christos Tzamos. Weitzman's rule for pandora's box with correlations. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2024

    2024

  13. [21]

    Bandit processes and dynamic allocation indices

    John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society Series B: Statistical Methodology, 41 0 (2): 0 148--164, 1979

    1979

  14. [22]

    Glazebrook

    Kevin D. Glazebrook. On a sufficient condition for superprocesses due to whittle. Journal of Applied Probability, 19: 0 99 -- 110, 1982

    1982

  15. [23]

    Information acquisition and exploitation in multichannel wireless networks

    Sudipto Guha, Kamesh Munagala, and Saswati Sarkar. Information acquisition and exploitation in multichannel wireless networks. arXiv, abs/0804.1724, 2008

    2008 arXiv

  16. [24]

    The Markovian Price of Information

    Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The Markovian Price of Information . In Conference on Integer Programming and Combinatorial Optimization, 2019

    2019

  17. [25]

    Dylan Hadfield-Menell and Stuart J. Russell. Multitasking: Optimal planning for bandit superprocesses. In Conference on Uncertainty in Artificial Intelligence, 2015

    2015

  18. [26]

    Threshold Testing and Semi-Online Prophet Inequalities

    Martin Hoefer and Kevin Schewior. Threshold Testing and Semi-Online Prophet Inequalities . In 31st Annual European Symposium on Algorithms (ESA), 2023

    2023

  19. [27]

    Stochastic probing with increasing precision

    Martin Hoefer, Kevin Schewior, and Daniel Schmand. Stochastic probing with increasing precision. SIAM Journal on Discrete Mathematics, 38 0 (1): 0 148--169, 2024

    2024

  20. [28]

    Ke and J

    T. Ke and J. Villas-Boas. Optimal learning before choice. Journal of Economic Theory, 180, 2019

    2019

  21. [29]

    Glen Weyl

    Bobby Kleinberg, Bo Waggoner, and E. Glen Weyl. Descending price optimally coordinates search. Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

    2016

  22. [30]

    P. Nash. Optimal Allocation of Resources Between Research Projects. University of Cambridge, 1973

    1973

  23. [31]

    Wojciech Olszewski and Richard R. Weber. A more general pandora rule? Journal of Economic Theory, 160: 0 429--437, 2015

    2015

  24. [32]

    Local hedging approximately solves pandora’s box problems with optional inspection

    Ziv Scully and Laura Doval. Local hedging approximately solves pandora’s box problems with optional inspection. arXiv, abs/2410.19011, 2024

    2024 arXiv

  25. [33]

    The price of information in combinatorial optimization

    Sahil Singla. The price of information in combinatorial optimization. In ACM-SIAM Symposium on Discrete Algorithms, 2017

    2017

  26. [34]

    Strassen

    V. Strassen. The Existence of Probability Measures with Given Marginals . The Annals of Mathematical Statistics, 36 0 (2): 0 423 -- 439, 1965

    1965

  27. [35]

    On the Gittins Index for Multiarmed Bandits

    Richard Weber. On the Gittins Index for Multiarmed Bandits . The Annals of Applied Probability, 2 0 (4): 0 1024 -- 1033, 1992

    1992

  28. [36]

    Optimal search for the best alternative

    Martin L Weitzman. Optimal search for the best alternative. Econometrica, pages 641--654, 1979

    1979

  29. [37]

    Multi-Armed Bandits and the Gittins Index

    Peter Whittle. Multi-Armed Bandits and the Gittins Index . Journal of the Royal Statistical Society: Series B (Methodological), 42 0 (2): 0 143--149, 1980

    1980

Pith tools

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