acceptodds
Under review as a conference paper at ICLR 2027

The Recoverability Gap in Coordination with Private Objectives

Abstract

Accurate local optimization responses need not reveal the objective differences that matter for a shared decision. We define the recoverability gap as the excess expected loss of the best transcript policy relative to the best instance-aware planner under the same protocol. For strongly convex objectives, we identify changes that preserve every allowed local response yet alter the shared optimum. When response maps coincide, the gap is the cost of choosing one common allocation rather than instance-specific optima. It vanishes precisely when the instances share an optimum almost surely. The result covers continuous priors and boundary optima. Constrained sensitivity quantifies the loss from small hidden changes. Local messages can select an optimum within a known family or certify a proposed allocation without a candidate list. Controlled eight-party experiments test the predicted loss and recovery using the same posterior-optimal decision rule. In generated resource-allocation tasks without inserted hidden perturbations, a record search finds decision-relevant ambiguity in short transcripts. Greater tested depths remain unresolved. These results link the differences an interface conceals to the shared decisions it can support.

Primary area:
optimization
Keywords:
distributed optimization, adaptive decision making, partial information, information-theoretic lower bounds, value of information

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_2SULOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies information limitations in coordination with private objectives. It constructs strongly convex instances with identical responses to permitted local queries but different globally optimal allocations, and characterizes the resulting decision loss. It also examines supplementary local messages and optimality certificates, with experiments on resource-allocation tasks.

Critical strengths

None

Critical weaknesses
  • The problem and main conclusions appear largely straightforward. The central result, Theorem 4.1, uses a simple indistinguishability construction with an elementary proof and an unsurprising conclusion. I find the technical and conceptual contributions insufficient for ICLR.
  • The paper is unnecessarily long and lacks focus. The core proof occupies roughly two pages, while numerous loosely connected auxiliary results obscure the main argument, leaving the central message and intuition unclear.
Questions for authors

None

2 comments

W1: Theorem 4.1 is intentionally a simple construction, designed to make the underlying information limitation transparent. Its contribution is not the indistinguishability argument itself, but the mechanism it reveals: all permitted local queries return solutions in a region where the private objectives agree, while the shared constraint requires allocations in a different region where those objectives disagree. Consequently, even exact local optimization cannot reveal the information needed for the globally optimal decision. Theorem 4.1 establishes this phenomenon, but it does not explain when it occurs more generally or which hidden differences actually matter. These are the questions addressed by the subsequent results. Theorem 4.2 characterizes the decision loss for general strongly convex objectives with identical response maps and establishes exactly when this loss vanishes. Corollary 4.3 goes further: indistinguishable objectives do not necessarily imply different optimal decisions or positive decision loss. Whether they do depends on how the hidden differences interact with the shared constraints. The corollary provides necessary and sufficient conditions for this distinction and quantifies the resulting loss, including cases with active constraints. Thus, the theoretical contribution is not an elementary indistinguishability argument, but a characterization of when locally invisible objective differences become globally consequential and how much decision loss they cause.

W2: We have reorganized the paper around this progression: when local responses are insufficient, how much decision loss results, and what additional information can help? Theorem 4.1 now serves as an intuitive starting example, followed by the general results in Theorem 4.2 and Corollary 4.3. Section 5 then examines two ways to use additional local information: selecting the optimal allocation within a known family and certifying the quality of a proposed allocation without a candidate list. We have also simplified the introduction and section transitions, and reduced the emphasis on auxiliary protocol and query-scheduling studies so that the central theoretical argument is easier to follow.

Thanks for the reply, I still feel that the submission is clearly below the standards of ICLR, so I keep my score.

Reviewer_PhDyOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the recoverability gap in coordination with private objectives.

Critical strengths

None.

Critical weaknesses

My main concern is the presentation, which makes the paper extremely difficult to read and assess. The problems begin in the abstract, where the model and main contributions are difficult to identify.

Moreover, although I'm not very familiar with this topic, the preliminaries should provide enough information to understand the model and the questions under study. The paper clearly does not achieve this. For instance, too much terminology is introduced without sufficient explanation. For example,, terms such as "query-invisible", "party-specific" and "public price domain" are not clearly defined.

These presentation issues make it impossible to access the technical contribution of the paper.

Questions for authors

None.

2 comments

We have substantially revised the abstract, introduction, and preliminaries to make the problem and main contributions easier to follow.

The paper asks a simple question: If every party accurately solves its local optimization problem, does the coordinator receive enough information to make the best global decision?

Our main finding is that the answer can be no. Two sets of private objectives may produce exactly the same local responses, even though they require different globally optimal allocations. We measure the resulting decision loss through the recoverability gap.

We now explain the theoretical results in a clearer sequence:

  1. Theorem 4.1 illustrates the problem with a concrete two-party example.
  2. Theorem 4.2 measures the resulting decision loss for a general class of strongly convex objectives.
  3. Corollary 4.3 explains which hidden differences change the global optimum and how much loss they cause.
  4. Section 5 examines how additional local information can help select or evaluate a global allocation.

We have also simplified Section 3 by introducing the public protocol, private objectives, and local responses before defining the two policy classes. Technical terms such as "query-invisible", "party-specific queries", and "public price domain" are explained when first introduced.

Thank you for your response. While the presentation of the paper has improved, I believe that most of my concerns remain valid. Therefore, I will maintain my original score.

Reviewer_THFFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

I interpret this paper as a theoretical study of whether “local information is sufficient to support global decision-making.” The coordinator can only request that each participant perform local optimization and cannot directly observe their private objectives; the authors use the “recoverability gap” to measure the resulting loss of global optimality and investigate when identical local responses correspond to different optimal allocations. To me, this is primarily a problem in information-constrained distributed optimization; forcing every concept into RL terminology would be misleading.

Critical strengths

S1: I acknowledge that Theorem 4.2 provides a precise characterization of the Bayesian decision-making loss caused by missing information; Corollary 4.3, meanwhile, illustrates that indistinguishable private objectives do not necessarily alter the final decision—it also depends on whether the hidden direction is correlated with the direction of feasible allocations. This distinction is more valuable than simply providing a counterexample of indistinguishability.

Critical weaknesses

W1: I was initially unconvinced by the query domain restrictions. In the central example, the price that clears the shared constraint can actually be calculated from public parameters, yet it is excluded from the allowed query range. If the permitted price range already covered the clearing price, what would be the effect of information loss? I would like the paper to explain more specifically why real-world interfaces would have such access restrictions, and what exactly the general theorem adds to our understanding.

W2: Another concern is whether the certificates are usable. Although all 640 certificates covered the true excess loss, none met the predefined termination tolerance. I believe that “the upper bound is valid” and “being tight enough to be used to terminate or accept an allocation” are entirely different matters.

Questions for authors

Q1: I would like to know when real-world price caps, query permissions, or privacy restrictions would actually prevent the coordinator from accessing the clearing price.

Q2: I hope the authors can provide realizable certificates that meet the preset tolerance in resource allocation tasks without artificially inserting invisible perturbations.

2 comments

W1: Theorem 4.2 characterizes the exact Bayes decision loss under common response maps, covering continuous priors and boundary optima. Corollary 4.3 identifies which response-invisible objective perturbations alter the shared optimum, using local and terminal normal-cone conditions, and quantifies the resulting loss through constrained sensitivity analysis. The key insight is the distinction between response invisibility and decision relevance. Identical local responses can conceal objective differences, but these differences contribute to the recoverability gap only when they change the optimal allocation along feasible directions. This connects the information exposed by an optimization interface to the geometry of globally optimal decisions. The interface assumption is further characterized by complementary results: Appendix C.4 extends the indistinguishability construction to prescribed bounded price intervals, while Appendix L.9 establishes that an admissible clearing price yields an optimal allocation.

W2: The controlled experiments establish the predicted recoverability gap and demonstrate recovery through decision-relevant local information. The original resource-allocation experiments additionally investigate objectives without inserted hidden perturbations. We extended the latter analysis with two certificate diagnostics on the same 40 tasks at 128 additional contacts. 31/40 allocations achieve an evaluated excess loss at most 10−310^{-3}. Using actual curvature coefficients reduces the mean residual-certificate bound by 52.64%. For primal-dual certification, an oracle optimal dual price yields 31/40 certificates meeting 10−310^{-3}, with the duality gap matching the evaluated excess loss to numerical precision (2.09×10−142.09\times10^{-14}). These results establish the tightness achievable with accurate dual information and identify dual-price accuracy as a key factor in effective certification. The oracle-price diagnostic is distinguished from the original response protocol, for which the tested local-price constructions do not meet the prescribed tolerance.

Q1: In practical coordination systems, the admissible query domain can be determined by operational price limits, prescribed communication interfaces, and restrictions on the information parties are permitted to disclose. These constraints define the information accessible to the coordinator and are therefore central to assessing whether a protocol supports globally optimal decisions. Our result applies to any prescribed bounded price interval with nonempty interior, not just the particular interval in Theorem 4.1. As established in Appendix C.4, one can construct smooth, strongly convex objectives whose responses coincide throughout the permitted domain while their globally optimal allocations differ. Thus, additional queries within the same domain cannot resolve the ambiguity. Appendix L.9 provides the complementary sufficiency condition: when an admissible price clears the shared constraint, the returned local allocations are globally optimal. Together, these results distinguish the information coverage of an interface from the computational effort required to find a suitable price. The two recovery mechanisms require different protocol capabilities. Expanded-price queries require access to a larger admissible domain, whereas the one-bit certificate requires a local marginal evaluation at a decision-relevant allocation and knowledge of the candidate family. Their applicability therefore depends on the information and query permissions supported by the coordination protocol.

Q2: We conducted two additional certificate diagnostics on the 40 original resource-allocation tasks without inserted hidden perturbations, retaining the same allocations after 128 additional contacts. First, 31/40 allocations achieve an evaluated excess loss at most 10−310^{-3}. For the list-free certificate in Proposition 5.2, replacing the public curvature lower bound with the actual curvature reduces the mean bound from 12.1919 to 5.7734 (52.64%). Exact subgradient analysis across 7,680 coordinates confirms that all corresponding subdifferentials are singletons. Second, we investigated primal-dual certification. Using the optimal dual price, the mean primal-dual gap is 6.32×10−46.32\times10^{-4}, agreeing with the evaluated excess loss to numerical precision (2.09×10−142.09\times10^{-14}). This yields 31/40 certificates meeting 10−310^{-3}. With prices constructed from the available local subgradients, the mean gaps are 0.235 (mean price) and 0.144 (median price), respectively. These experiments establish that tight optimality certification is attainable on the evaluated tasks and identify accurate dual-price information as a key requirement. The oracle-price results characterize the achievable tightness of primal-dual certification, while the local-price results quantify the additional information needed to realize it through a distributed interface.

My concerns regarding whether to accept the paper have not yet been resolved; I still need to continue discussing this with the other reviewers and the AC.

Reviewer_vxZmOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper mainly studies whether accurate local optimization responses are sufficient to support globally optimal decisions in distributed coordination. The authors propose a "recoverability gap" to measure the difference in optimal expected loss between a coordinator that only relies on the information obtained from interaction transcripts and a planner that has direct access to the private objective functions of all parties, under the same protocol and resource constraints. The paper proves that even increasing the number of queries will not necessarily eliminate this information gap when the query range is restricted. Then, the authors further analyze which hidden differences between objective functions can affect the global decision, and propose methods to recover the optimal allocation through additional local information and to certify the quality of a proposed allocation using local information. Finally, the authors evaluate the theoretical results through controlled experiments and generated resource allocation tasks.

Critical strengths

The core theoretical results provide a precise characterization of the decision loss caused by insufficient information, including an exact expression for the recoverability gap and a necessary and sufficient condition for it to be zero. These results clarify when hidden differences between objective functions cause decision loss under the conditions studied and quantify the magnitude of this loss.

Critical weaknesses

The writing and overall organization of the paper still need to be improved. First, the abstract contains numerous theoretical results and experimental findings, but it does not sufficiently distinguish between the core contributions and additional findings. At the same time, it introduces some technical terms without sufficient intuitive explanation, making it difficult for readers to quickly grasp the central ideas of the paper. Second, although the related work is organized around three themes, the comparisons with prior work remain rather general. The authors should explain more specifically what new theoretical insights this paper offers beyond existing research on the value of information and statistical indistinguishability. Finally, the connections among the different theoretical results in the main text are not sufficiently clear. For example, the research objectives and theoretical guarantees of Sections 5.1 and 5.2 differ. The authors should further clarify the role of these results and their relationship to the central questions of the paper, so as to improve the overall logical coherence.

Questions for authors

Section 4.1 shows, through a specific construction, that even if the coordinator makes any finite number of queries within the allowed price range, it remains unable to obtain information that distinguishes the two private instances, although their globally optimal allocations differ. This shows that even if the local optimization responses are exact, increasing the number of queries does not necessarily eliminate the information loss in the global decision, that is, the recoverability gap can be strictly positive. Can the authors further explain what specific conditions determine such price query restrictions in practical distributed coordination systems? The paper itself shows that, in this construction, the gap can be eliminated by querying a specific price outside the allowed range or adding one locally computed bit. In addition to the reported communication and computational overhead, are there any other practical constraints that limit the adoption of these methods?

2 comments

Weaknesses

(1) Presentation and organization. The central question is whether accurate local optimization responses contain sufficient information for globally optimal coordination. We organize the contributions around three questions: (i) how much decision loss can remain under indistinguishable responses (Theorem 4.2), (ii) which invisible objective differences affect the global optimum (Corollary 4.3), and (iii) how additional local information supports decision recovery or quality certification (Section 5). The revised presentation prioritizes this theoretical progression in the abstract and introduction, separates core results from supplementary experiments, and introduces the query interface and its terminology before the main construction. This makes the role of each theoretical result explicit.

(2) Distinction from prior work. Classical value-of-information theory characterizes how information affects optimal decisions, while statistical indistinguishability establishes limitations on distinguishing hidden instances. Our contribution identifies which objective differences are both invisible to local optimization interfaces and consequential for constrained global decisions. Specifically, Eq. (13) characterizes response-invisible perturbations through local optimality conditions. Corollary 4.3 determines whether these perturbations alter the shared optimum using terminal normal-cone conditions and quantifies their decision loss through constrained sensitivity. This connects response indistinguishability to the feasible geometry of the shared decision.

(3) Connections among theoretical results. Section 4 establishes when ordinary responses conceal decision-relevant information. Section 5 examines two ways additional local information can address this limitation. Theorem 4.1 provides an explicit construction, Theorem 4.2 characterizes its general Bayes decision loss, and Corollary 4.3 identifies the perturbations that change the shared optimum. Section 5.1 uses a locally computed bit to recover the instance-aware optimum within a known candidate family. Section 5.2 provides a list-free optimality certificate through local subgradient information. These mechanisms address complementary objectives: selecting the appropriate allocation and assessing the quality of a proposed allocation.

Questions

Admissible price ranges can reflect operational price limits and prescribed query permissions. Appendix C.4 establishes that response-invisible differences can persist over any prescribed bounded price interval, while Appendix L.9 shows that an admissible clearing price yields a globally optimal allocation. These results distinguish interface coverage from the effort required to find a clearing price. Expanded-price queries require authorization to access a larger price domain. Additional local messages require permission to reveal decision-relevant objective information and may introduce privacy or disclosure constraints. The one-bit mechanism also assumes a known candidate family and a locally identifiable action class. These considerations determine when each mechanism can be implemented under a given coordination protocol.

Thank you for the detailed response and the efforts made to improve the readability of the article. I have read the revised manuscript and find that the concerns about the abstract listing a large number of results without fully highlighting the core contributions have been substantially addressed. The related work section also positions the contributions of the paper more clearly compared to the original manuscript. Based on these improvements and taking into account the contributions and overall quality of this article, I have decided to raise my rating from 1 to 2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.