CS Paper Radar

Certified Learning and Equilibrium Implementation under Opaque Partial Commitment

Shuyang Zhang, Xiangtian Li

cs.GT econ.TH ·submitted 2026-08-21 06:04 UTC · v1
theory

Abstract

As an extension of existing Bayesian persuasion framework with inadequate message mechanism, we study direct recommendation when a sender is bound by an installed information policy only with probability $ρ$, the realization of binding is hidden, and the receiver does not observe the persistent structural environment. The receiver first sees a payoff-neutral, nonmanipulable calibration sample and then faces a fresh, non-certified deployment interaction. In common, the calibration law identifies only the receiver-facing reduced form, not the latent binding and discretionary kernels. We characterize type-wise $ρ$-implementability, construct the receiver's posterior over the full deployment node, and prove a static direct-following implementation theorem. After every calibration history that passes a posterior-predictive obedience test, the deployment assessment is an exact perfect Bayesian equilibrium: Bayes consistency, receiver sequential rationality, sender sequential rationality, and off-path completion are all verified. Under finite-type separation, common recommendation support, and a positive obedience margin, the test activates such an equilibrium with high probability. Our results keep statistical failure probability distinct from equilibrium approximation. Finally, we embed the original robust value frontier, support-wise linear-programming algorithm, and binary-action fractional-knapsack specialization into this implementation framework

Closest papers

Nearest neighbours by meaning across the whole index.

Truth Revelation, Information Hiding, or Misinformation: Characterization of Equilibrium Outcomes in Signaling Games

cs.GT cs.ITmath.OC ·2026-08-25 ·Ertan Kazıklı, Sinan Gezici, Serdar Yüksel
similarity 0.64
Abstract · 18 pages and 4 figures

In signaling games where a sender and a receiver have misaligned criteria, equilibrium behavior may lead to fully revealing, quantized, or randomized policies. Notably, the first arises in statistical decision theory and classical communication theoretic problems involving a fully aligned sensor and receiver, the second arises in Nash theoretic simultaneous signaling games, and the last may appear in Stackelberg type (leader-follower) Bayesian signaling games. In this paper, we investigate the Bayesian persuasion problem involving a receiver that tries to estimate the source. We show that for certain payoff structures, the equilibrium solution is such that a source observation is mapped to distinct messages with nonzero probabilities. More specifically, we completely characterize conditions under which the sender requires randomization for the Bayesian persuasion problem involving general sources with finite cardinality. In particular, regardless of whether the equilibrium solution under a deterministic policy restriction is fully revealing, quantized or noninformative, there exists a randomized sender policy that improves the sender's payoff under certain conditions characterized in the paper. Moreover, we provide an algorithmic procedure to obtain the Bayesian persuasion solution, where the algorithm compares the payoffs with finitely many posterior probability combinations. We also consider fully aligned and completely misaligned payoff structures, where the solutions respectively involve a fully revealing sender and a noninformative sender. Then, we unify these results by proving that if the sender's expected payoff with respect to posterior distributions is continuous, then the equilibrium solution involves either a fully revealing sender or a noninformative sender.

0.20

A Bayesian Correlated Equilibrium for Early Insider-Threat Detection

cs.CR cs.GT ·2026-09-02 ·Javed M. Shah, Ian A. Kash, Natalie Parde
publishedtheory similarity 0.60
Abstract · Accepted in GameSec 2026

We model insider threat detection as a dynamic Bayesian game in which a platform coordinates a committee of strategic certifiers to sustain equilibrium among honest users and detect malicious deviations before exfiltration. Certifiers and users operate under a Bayesian Temporal Correlated Equilibrium (BTCE), where a sealed-envelope correlating device issues private recommendations over time and obedience is verified at every on-path information state. Unlike Stackelberg formulations, BTCE coordinates heterogeneous certifiers without requiring commitment power. We incorporate present bias and loss aversion to capture impulsive escalation dynamics, enabling 1.7--4.5 days earlier detection than rational baselines. We prove three guarantees: (1) calibrated intervention losses make recommended behavior a current-self best response despite behavioral biases, (2) controlled evidence accumulation guarantees intervention in bounded expected time before exfiltration, and (3) median aggregation confines implemented actions to the honest recommendation range when fewer than half of certifiers are Byzantine. On CERT r6.2 our mechanism achieves up to 28.3% pre-exfiltration detection with false positives below 1.6%, while both a transformer baseline and a streaming provenance approximation (HOLMESLite) achieve near-zero pre-exfiltration detection under comparable constraints.

0.34

Knowing When to Ask for Help: Bayesian Self-Escalation in Hierarchical LLM Agents

cs.LG cs.AIstat.ML ·2026-08-25 ·Nadeem Shaikh
code/data similarity 0.57
Abstract · 21 pages, 5 figures. Code and data: https://github.com/nadeem-shaikh/llm-self-escalation . Associated record: https://doi.org/10.5281/zenodo…

Current LLM agent systems decide delegation before reasoning begins (a router picks a model) or after a response is complete (a verifier scores it and may retry). We study a third regime: an agent that recognises, during its own reasoning, that it is unlikely to succeed and transfers control to a stronger model. We formulate intra-generation delegation as a Bayesian optimal-stopping problem over a learned competence posterior -- an online estimate of the agent's eventual task success whose sufficient statistics are learned from labelled trajectories, not read off raw entropy. We derive the myopic escalation threshold in closed form, characterise the optimal policy via dynamic programming, and prove that the optimal policy is a time-varying threshold with no shape assumption on the raw signal. We further prove exponential separation of the oracle belief at the Chernoff-information rate of the signal, a regret bound governed by the calibration of the posterior, and a finite-sample guarantee: with n labelled calibration trajectories the deployed plug-in policy's regret decays as 1/sqrt(n). A controlled simulation study confirms each prediction of the theory, including the predicted 1/sqrt(n) rate. We additionally report a real-model validation on a Qwen2.5-Coder 1.5B->7B code cascade (MBPP, 257 tasks), confirming two of three pre-registered predictions: the escalation frontier dominates post-hoc routing at equal cost, and the cumulative competence belief's discrimination rises over generation.

0.62

Simultaneous Gradient Learning in First-Price Auctions

cs.GT econ.TH ·2026-10-28 ·Janik Bürgermeister, Julius Durmann, Martin Bichler, Mete Şeref Ahunbay, Bary Pradelski +1 more
top venue similarity 0.56
Abstract · accepted for publication at NeurIPS 2026

We study equilibrium learning in discretized Bayesian games, focusing on first-price auctions as a testbed for gradient-based learning dynamics under private information. While the symmetric independent private values model admits a unique Bayesian correlated equilibrium (BCE) in the continuous limit, standard convergence guarantees for gradient-based learners do not apply: classical no-regret theory predicts convergence only to Bayesian coarse correlated equilibria (BCCE), which can remain large and far from the competitive equilibrium even under fine discretizations. To bridge this gap, we introduce the notion of Bayesian semicoarse correlated equilibrium (BSCCE), an equilibrium concept that refines BCCE by restricting deviations to probability-preserving transformations consistent with projected gradient dynamics. We provide a linear programming characterization of BSCCE with polynomially many variables and constraints and establish the inclusion hierarchy $BCE \subseteq BSCCE \subseteq BCCE$. Our main finding is that the BSCCE set contracts in many cases as the discretization of the Bayesian game is refined. Even with priors for which BCCE fails to concentrate, the diameter of the BSCCE polytope shrinks toward zero, indicating convergence to the unique continuous-game Bayes-Nash equilibrium. These results provide a principled explanation for the observed robustness of gradient-based learning in discretized Bayesian games, showing that these dynamics select a smaller equilibrium set than standard no-regret theory predicts.

0.43

How Far Can an Agent Push? Trust-Safety Margins in Live Language-Based Economic Games

cs.MA cs.GT ·2026-10-18 ·Dima Galat, Marian-Andrei Rizoiu
benchmark similarity 0.56
Abstract

Game theory identifies when a strategic action should be accepted, but not how long a live, language-based counterpart will continue to accept it. We entered the GLEE competition in its final week with one protected agent, Milton, and four instrument agents that ran deterministic, per-game randomized trials of policy changes; Milton received changes only through pre-specified gates or registered, rollback-guarded production rules. In negotiation, learned pricing improves adjusted percentile by 0.071 (n=21,168); in bargaining, a continuation model conditioned on the rejected offer did not improve on a recency-weighted incumbent and was retired. In persuasion, a preregistered five-dose experiment (7,391 assigned games, blinded until a fixed stop) shows that recommending every unit raises sales by 0.194 of the maximum (95% CI [0.147, 0.241]) where the receiver's slack makes obedience rational (52% of the Bayesian benchmark), lowers them where it does not (-0.067), and produces a larger early-to-late purchase decline than honest recommendations (-0.123). A rule fixed before unblinding now routes Milton's dose per cell. Milton stood 11th of 460 agents in bargaining at the fixed stop; we also report the close, where the final day's pool shift moved all five agents' bargaining ratings together while their play was unchanged, and three dispatch defects were found by checking delivered behavior against the design.

0.13

Bayesian Belief Layer for Controllable Opinion Dynamics in LLM Agents

cs.MA cs.AI ·2026-09-18 ·Hafsa Akbar, Daniel Platnick, Marjan Alirezaie, Hossein Rahnama, Alex 'Sandy' Pentland
similarity 0.56
Abstract · Accepted to The 2nd Workshop for Research on Agent Language Models (REALM) at EMNLP 2026

LLM agents in social simulation revise their opinions implicitly, in context: how open an agent is to persuasion can neither be specified nor verified, and collective outcomes inherit the model's training prior. We introduce Bayesian Chronicle Agents (BCA), a minimal belief layer separating what an agent believes from how it speaks. Each stance is a probability, updated by one Bayesian step per utterance heard. A single prior-strength parameter $κ$ encodes stubbornness, modeled after its role in Friedkin--Johnsen (FJ) opinion dynamics. We then sweep this parameter to yield three canonical regimes of opinion dynamics on demand (consensus, persistent disagreement, committed-minority influence), with persistent disagreement matching the FJ closed-form fixed points at $R^2\!=\!0.93$--$0.99$. We further show that prescribed $κ$ remains recoverable after the language round-trip, with perfect rank-order recovery across all four models. Explicit belief also makes simulation auditable: the layer surfaces systematic per-model stance biases that end-to-end simulation would silently absorb.

0.31

Designing Information in a Forest: Algorithmic Aspects

cs.GT econ.TH ·2026-11-12 ·Konstantin Zabarnyi
similarity 0.55
Abstract

The Bayesian persuasion framework models strategic information revelation by a sender to one or more receivers. We study an intricate version of the multi-receiver persuasion setting in which the communication hierarchy is a forest - i.e., some receivers observe more informative signals than others, and the partial ordering of the receivers according to the information they get is represented by a pre-specified directed forest. This model naturally captures interactions in hierarchical organizations, and it lies in between the two most commonly studied versions of Bayesian persuasion: private persuasion and public persuasion. Inspired by the classic model of private persuasion, we focus on a setting with a binary state of nature and binary-action heterogeneous receivers s.t. the sender's utility is a monotone function of the set of receivers taking a specific desirable action. We extend the computational tractability result for symmetric sender's utility from private persuasion to the forest hierarchy framework using methodology inspired by optimal transport theory. We further provide a polynomial-time algorithm when the sender's utility is modular. On the negative side, we show that, unlike in private persuasion, the case of a supermodular sender's utility function leads to an NP-hard optimization problem which further does not admit an FPTAS unless P=NP; this result holds even when each tree component of the forest is a chain of 3 receivers. To complement the hardness result, we provide a simple approximation algorithm with the approximation ratio depending linearly on the depth of the forest hierarchy. We further provide an analogous algorithm for the submodular utility case. Finally, beyond forest communication hierarchies, we rule out an FPTAS for the sender's optimal utility even in the symmetric utility case, unless P=NP.

0.20

Dynamic Persuasion: Managing Reputation under Censored Feedback

eess.SY ·2026-10-29 ·Ahmet E. Arcaklioglu, Ceyhun Eksin
published similarity 0.55
Abstract · 44 pages, 8 figures. A preliminary version of part of this work appears in Proc. IEEE CDC 2026

We study a long-run sender who repeatedly communicates about a state to a sequence of myopic receivers and whose credibility is a public score updated from past interactions. Receivers face a lemon loss and an opportunity loss, and their behavior depends on these only through a single index, the tolerance. Because the score records only detected misrepresentations, it rests above the sender's true honesty rate; we characterize this credibility premium in closed form. In a fluid limit in which the score adjusts slowly, no policy earns more than operating at a single credibility level, and the sender's gain from managing credibility equals the value of the premium: against receivers who correct for imperfect detection, that gain vanishes. At a fixed adjustment speed, every policy is bounded by the fluid value plus a term linear in the speed. We then study three policy classes, linear, (s,S), and threshold, obtain the optimal parameters of the linear and threshold classes in closed form, show how receiver losses shape them, and show that, under an approximation, the optimal (s,S) band collapses to a threshold. Simulations of the dynamics agree with the closed forms and indicate where the single-level conclusion stops: bands pay when switching modes is costly, and cycles pay when demand is seasonal.

0.36