CCS Concepts
• Theory of computation → Algorithmic mechanism design;
• Information systems → Online advertising.
Introduction
“The medium is the message.”
— Marshall McLuhan, Understanding Media (1964)
The medium through which people access online information is undergoing a fundamental transformation. For decades, internet interfaces have largely organized information by retrieving, ranking, and presenting content that already exists. Search engines return ranked results; recommendation systems select items from a collection. Generative AI introduces a different mode of information access. Rather than simply choosing what to present, AI-native interfaces synthesize responses dynamically around user intent, with the content itself taking shape as the interaction unfolds. The medium is no longer merely organizing information; it is generating it.
Advertising has historically been built around the structure of the medium in which it appears. In traditional internet interfaces, this has led to a simple but powerful abstraction: the slot. Whether it is a sponsored-search position, a reserved display placement, or a promoted position in a recommendation feed, the commercial opportunity can typically be defined in advance and then assigned to advertisers. But this abstraction becomes less natural when the surrounding content is itself generated. As shown in Figure 1 , a product may become relevant only as an answer develops in a particular direction, and only a generation choice can make a later brand mention either natural or jarring. In such settings, generation does more than fill an advertising opportunity—it can help create one. The advertising opportunity is no longer merely a slot inside generated content; it can be shaped by the generation process itself.
Figure 1. In generation-native advertising, ad opportunities are no longer predefined slots: when they emerge, which advertisers are shown, and how they are presented jointly shape user experience and marketing effectiveness.
This shift calls for a corresponding change in mechanism design. Traditional advertising mechanisms largely separate two questions: what opportunities exist, and who should receive them? Auction theory has developed powerful tools for the latter, typically taking the former as given. This separation is natural when the advertising slot exists before the auction begins, but begins to break down when the generation trajectory itself determines whether and how an advertiser can be meaningfully incorporated. Thus, a mechanism that only allocates predefined opportunities leaves an important part of the generative medium outside the allocation process.
Recent work has begun to rethink what constitutes an advertising opportunity in generative interfaces. Rather than relying only on fixed slots, some approaches define opportunities over segments or context-dependent positions within generated text, while others first construct complete candidate responses and then select, aggregate, or insert sponsored content at the response level. These abstractions make advertising substantially more adaptive to generated context: where an ad can appear, or which sponsored response is appropriate, may now depend on the content produced by the model. Yet the mechanism typically operates on an opportunity that has already been identified—a segment, a position, or a completed response. Generation shapes the opportunity, but is not itself the allocation process.
In this paper, we take the next step and formulate a generation-native paradigm for computational advertising, in which advertising is directly embedded into the generation process. Advertisers are treated as strategic participants whose messages can influence how the response evolves, while the platform jointly determines generated content, advertising allocation, and payments. Within this broader paradigm, we study a particularly native instantiation at the token level: advertisers may influence the response at every generation step. A user query initializes a sequential process, and at each generated prefix, the platform combines advertiser messages with the reference language model and the current mechanism state to determine what token to generate next and how the advertising allocation should evolve. The goal is to incorporate advertiser incentives and platform monetization into generation while preserving the naturalness and usefulness of the generated content.
Making advertising a native part of generation introduces several technical challenges. Most importantly, incentive design becomes inherently sequential: a report submitted at one prefix can change the future generation trajectory, which in turn changes the advertiser’s subsequent opportunities and eventual payoff. Truthful behavior must therefore remain optimal not only at the beginning of generation, but also after any reachable future states. Advertiser influence must also be balanced against the reference language model so that monetization does not come at the expense of response quality. At the same time, language model inference already incurs substantial serving latency, requiring the mechanism to introduce only minimal additional overhead. Finally, a tractable mechanism should still admit a meaningful efficiency guarantee relative to an ideal welfare-maximizing benchmark.
To address these challenges, we propose the Latent Advertiser Mixture Auction (LAMA) for the fundamental single-winner setting. At each prefix, advertisers’ local reports induce advertiser-specific next-token policies, and LAMA generates next token from a latent mixture of these policies. The mixture weights evolve as a Bayesian allocation posterior as tokens are observed, linking the generation trajectory to the eventual advertising allocation. Once generation terminates, this posterior determines the final allocation, together with payments designed for the sequential setting. We show that LAMA satisfies Markov dominant-strategy incentive compatibility and individual rationality. Moreover, it achieves near-optimal KL-regularized welfare, with the optimality gap vanishing as the regularization diminishes.
We further develop a practical implementation that avoids explicitly reasoning over the full token tree or requiring advertisers to compute complex reports themselves. The platform provides reporting as a learned service: a shared advertiser-conditioned model recovers local signals along the realized generation path and anchors them with an advertiser-specific root estimate, allowing the reports required by LAMA to be reconstructed online. This design turns the theoretical sequential mechanism into a lightweight serving-time procedure that can operate over a small candidate set of advertisers with modest additional language-model computation.
We evaluate LAMA in simulation on real-world query splits with model-predicted impression values. We compare against heuristic mechanisms that allocate advertising either before or after generation, as well as a representative response-level aggregation mechanism. Across the evaluated settings, LAMA achieves the strongest platform welfare and revenue while maintaining high advertiser value and user-side response quality. These results provide an initial proof of concept for the generation-native advertising paradigm: allowing advertisers to participate directly in the token-level generation process can improve monetization while preserving high-quality generated responses.
Our contributions are summarized as follows.
(1) Generation-native advertising. We develop a token-level formulation of generation-native advertising, where advertiser participation is embedded directly into the sequential generation process and jointly shapes the response and eventual allocation.
(2) Token-level mechanism design. We propose LAMA for the fundamental single-winner setting and establish Markov DSIC and IR, together with near-optimal KL-regularized welfare, with an additive gap of at most β log ∣ V ∣ \beta\log|\mathcal{V}| β log ∣ V ∣ .
(3) Practical implementation. We develop a learning-based implementation that reconstructs the reports required by LAMA online and supports efficient serving.
(4) Proof-of-concept evaluation. Experiments on real-world search query splits show that LAMA improves platform welfare and revenue while maintaining advertiser value and user-facing response quality.
Model
We model token-level advertising as a sequential mechanism embedded in the generation process of a language model. A user query initializes a token-level decision process. At each non-terminal prefix, advertisers may submit local reports based on the publicly observed state, and the platform uses these reports together with its privately observed history to choose the next token distribution, the advertising allocation, and payments. The central distinction from classical sponsored-search models is that the advertising opportunity is not an exogenously given slot. Instead, it is endogenously shaped by the generated trajectory itself.
Context space and reference generation. Let V \mathcal{V} V be the token vocabulary and let L L L be the maximum generation length.2 The context space is S : = V ≤ L = ⋃ t = 0 L V t \mathcal{S} := \mathcal{V}^{\le L} = \bigcup_{t=0}^{L} \mathcal{V}^{t} S := V ≤ L = ⋃ t = 0 L V t , where V 0 = { ∅ } \mathcal{V}^{0} = \{\emptyset\} V 0 = { ∅ } . For two contexts x 1 , x 2 ∈ S x_{1},x_{2} \in\mathcal{S} x 1 , x 2 ∈ S , we write [ x 1 , x 2 ] [x_{1},x_{2}] [ x 1 , x 2 ] for their concatenation whenever the resulting sequence has length at most L L L . A user query q ∈ S q \in\mathcal{S} q ∈ S is drawn from a query distribution D \mathcal{D} D and serves as the initial state.
The platform has an organic language-model policy π r e f ( ⋅ ∣ s ) ∈ Δ + + ( V ) \pi_{\mathrm{ref}}(\cdot\mid s) \in\Delta_{++}(\mathcal{V}) π ref ( ⋅ ∣ s ) ∈ Δ ++ ( V ) , s ∈ S s \in\mathcal{S} s ∈ S , which describes the next-token distribution in the absence of advertising intervention3 . We also write π 0 \pi_0 π 0 for π r e f \pi_{\mathrm{ref}} π ref . A trajectory from query q q q is τ = ( s 0 = q , a 0 , s 1 , a 1 , … , s T τ ) \tau=(s_0=q,a_0,s_1,a_1,\ldots,s_{T_\tau}) τ = ( s 0 = q , a 0 , s 1 , a 1 , … , s T τ ) , s t + 1 = [ s t , a t ] s_{t+1}=[s_t,a_t] s t + 1 = [ s t , a t ] . Let EOS ∈ V \in\mathcal{V} ∈ V denote the end-of-sequence token. A state is terminal if it contains EOS or reaches the maximum length. We denote the terminal set by S T \mathcal{S}_T S T , and write L ( s ) ⊆ S T L(s)\subseteq\mathcal{S}_T L ( s ) ⊆ S T for the set of terminal descendants of a non-terminal state s s s . For a trajectory τ \tau τ , its realized terminal state is denoted by ℓ ( τ ) = s T τ \ell(\tau)=s_{T_\tau} ℓ ( τ ) = s T τ .
Advertisers and private types. There are n ≥ 2 n\ge2 n ≥ 2 advertisers, indexed by N = [ n ] = { 1 , … , n } \mathcal{N}=[n]=\{1,\ldots,n\} N = [ n ] = { 1 , … , n } . Each advertiser i i i has a private terminal reward function r i : S T → R ≥ 0 r_i:\mathcal{S}_T\to\mathbb{R}_{\ge0} r i : S T → R ≥ 0 . The value r i ( ℓ ) r_i(\ell) r i ( ℓ ) represents advertiser i i i ’s value from receiving the advertising opportunity when the generated response terminates at ℓ \ell ℓ . We write r = ( r 1 , … , r n ) r=(r_1,\ldots,r_n) r = ( r 1 , … , r n ) for the type profile and r − i r_{-i} r − i for the profile excluding advertiser i i i .
The allocation of the advertising opportunity is represented by a vector λ ∈ Λ ⊆ [ 0 , 1 ] n \lambda\in\Lambda\subseteq[0,1]^n λ ∈ Λ ⊆ [ 0 , 1 ] n , where Λ \Lambda Λ is an exogenously given feasible allocation set. For example, Λ \Lambda Λ may encode slot-capacity constraints or exposure constraints. This paper focuses on the fundamental single-winner setting: the advertising opportunity is endogenously shaped by the generation process, but the eventual sponsored outcome is assigned to a single advertiser. Thus, Λ = Δ ( N ) \Lambda=\Delta(\mathcal{N}) Λ = Δ ( N ) . The realized gross value of advertiser i i i on trajectory τ \tau τ is therefore λ i r i ( ℓ ( τ ) ) \lambda_i r_i(\ell(\tau)) λ i r i ( ℓ ( τ )) .
Platform histories. To describe a mechanism that operates during generation, we introduce the history privately observed by the platform. A platform history at time t t t is
h t = ( s 0 , m 0 , a 0 , … , s t − 1 , m t − 1 , a t − 1 , s t ) , h_t=(s_0,m_0,a_0,\ldots,s_{t-1},m_{t-1},a_{t-1},s_t), h t = ( s 0 , m 0 , a 0 , … , s t − 1 , m t − 1 , a t − 1 , s t ) ,
where s 0 = q s_0=q s 0 = q , a t ∈ V a_t\in\mathcal{V} a t ∈ V is the token generated at time t t t , and m t = ( m 1 , t , … , m n , t ) m_t=(m_{1,t},\ldots,m_{n,t}) m t = ( m 1 , t , … , m n , t ) denotes the profile of messages submitted by the advertisers at time t t t . Advertisers observe only the current state s t s_t s t , which is public, whereas the platform observes the entire history. The state evolves deterministically according to s t + 1 = [ s t , a t ] s_{t+1}=[s_t,a_t] s t + 1 = [ s t , a t ] . Let H \mathcal{H} H denote the set of non-terminal platform histories, and let s ( h ) s(h) s ( h ) be the current state at the end of history h h h . A terminal platform history is denoted by h T = ( s 0 , m 0 , a 0 , … , s T − 1 , m T − 1 , a T − 1 , s T ) h_T=(s_0,m_0,a_0,\ldots,s_{T-1},m_{T-1},a_{T-1},s_T) h T = ( s 0 , m 0 , a 0 , … , s T − 1 , m T − 1 , a T − 1 , s T ) , where s T ∈ S T s_T\in\mathcal{S}_T s T ∈ S T . We write τ ( h T ) \tau(h_T) τ ( h T ) for the token trajectory induced by the terminal history h T h_T h T , and ℓ ( h T ) = s T \ell(h_T)=s_T ℓ ( h T ) = s T for its terminal state.
Sequential mechanisms. A sequential mechanism for token-level advertising is a tuple
Γ = ( { M i ( h ) } i ∈ N , h ∈ H , x , λ , p ) . \Gamma=\left(\{M_i(h)\}_{i\in\mathcal{N},h\in\mathcal{H}},x,\lambda,p\right). Γ = ( { M i ( h ) } i ∈ N , h ∈ H , x , λ , p ) .
For each non-terminal platform history h h h , M i ( h ) M_i(h) M i ( h ) is advertiser i i i ’s feasible message space after that history. Given h ∈ H h\in\mathcal{H} h ∈ H and a joint message m = ( m 1 , … , m n ) ∈ M ( h ) = ∏ i ∈ N M i ( h ) m=(m_1,\ldots,m_n)\in M(h)=\prod_{i\in\mathcal{N}}M_i(h) m = ( m 1 , … , m n ) ∈ M ( h ) = ∏ i ∈ N M i ( h ) , the next-token rule is x ( ⋅ ∣ h , m ) ∈ Δ ( V ) x(\cdot\mid h,m)\in\Delta(\mathcal{V}) x ( ⋅ ∣ h , m ) ∈ Δ ( V ) . The instantaneous payment rule is p i ( h , m , a ) ∈ R p_i(h,m,a)\in\mathbb{R} p i ( h , m , a ) ∈ R , which specifies advertiser i i i ’s payment when token a a a is generated after history h h h under report profile m m m . The final allocation is λ ( h T ) ∈ Λ \lambda(h_T)\in\Lambda λ ( h T ) ∈ Λ . Thus, the feasible message spaces, token-generation rule, payments, and final allocation may depend on the entire platform history4 . In particular, history-dependent message spaces allow the platform to check a new report against values previously recorded in its report ledger.
The timing is as follows.
The user query q ∼ D q\sim\mathcal{D} q ∼ D initializes the process at s 0 = q s_0=q s 0 = q .
At each non-terminal state s t s_t s t , each advertiser i i i submits a message m i , t ∈ M i ( h t ) m_{i,t}\in M_i(h_t) m i , t ∈ M i ( h t ) . Let m t = ( m 1 , t , … , m n , t ) m_t=(m_{1,t},\ldots,m_{n,t}) m t = ( m 1 , t , … , m n , t ) .
The mechanism chooses a next-token distribution x ( ⋅ ∣ h t , m t ) x(\cdot\mid h_t,m_t) x ( ⋅ ∣ h t , m t ) , draws a t ∼ x ( ⋅ ∣ h t , m t ) a_t\sim x(\cdot\mid h_t,m_t) a t ∼ x ( ⋅ ∣ h t , m t ) , and charges p i ( h t , m t , a t ) p_i(h_t,m_t,a_t) p i ( h t , m t , a t ) for each i ∈ N i\in\mathcal{N} i ∈ N .
The state updates deterministically as s t + 1 = [ s t , a t ] s_{t+1}=[s_t,a_t] s t + 1 = [ s t , a t ] . If s t + 1 ∈ S T s_{t+1}\in\mathcal{S}_T s t + 1 ∈ S T , the process terminates and the mechanism implements the feasible allocation λ ( h T ) ∈ Λ \lambda(h_T)\in\Lambda λ ( h T ) ∈ Λ .
Direct mechanisms are a special case as the platform can ask each advertiser to submit its entire reward function. However, such mechanisms are impractical for online generation because full reporting may be slow and may reveal private information about trajectories that are never realized. Our definition therefore emphasizes lightweight reports, and we will see that they suffice to achieve strong performance for the platform.
Strategies and induced policies. Let Θ i \Theta_i Θ i denote advertiser i i i ’s type space. A strategy of advertiser i i i maps its type and each non-terminal public state to a message: σ i : Θ i × ( S ∖ S T ) → ⋃ h ∈ H M i ( h ) \sigma_i:\Theta_i\times(\mathcal{S}\setminus\mathcal{S}_T)\to\bigcup_{h\in\mathcal{H}}M_i(h) σ i : Θ i × ( S ∖ S T ) → ⋃ h ∈ H M i ( h ) . A strategy is feasible if σ i ( r i , s ( h ) ) ∈ M i ( h ) \sigma_i(r_i,s(h))\in M_i(h) σ i ( r i , s ( h )) ∈ M i ( h ) at every history at which it is used. Given σ = ( σ 1 , … , σ n ) \sigma=(\sigma_1,\ldots,\sigma_n) σ = ( σ 1 , … , σ n ) and type profile r r r , the induced joint report at history h h h is m σ , r ( h ) : = ( σ 1 ( r 1 , s ( h ) ) , … , σ n ( r n , s ( h ) ) ) m^{\sigma,r}(h):=(\sigma_1(r_1,s(h)),\ldots,\sigma_n(r_n,s(h))) m σ , r ( h ) := ( σ 1 ( r 1 , s ( h )) , … , σ n ( r n , s ( h ))) . Together with the mechanism Γ \Gamma Γ , these reports determine the continuation token policy π σ , r Γ ( a ∣ h ) : = x ( a ∣ h , m σ , r ( h ) ) , a ∈ V \pi^{\Gamma}_{\sigma,r}(a\mid h):=x(a\mid h,m^{\sigma,r}(h)),\ a\in\mathcal{V} π σ , r Γ ( a ∣ h ) := x ( a ∣ h , m σ , r ( h )) , a ∈ V , and hence a distribution P σ , r Γ ( ⋅ ∣ h ) \mathbb{P}^{\Gamma}_{\sigma,r}(\cdot\mid h) P σ , r Γ ( ⋅ ∣ h ) over terminal histories extending h h h .
Utilities. Advertisers have standard quasi-linear utilities. At a terminal history h T h_T h T , advertiser i i i ’s realized utility is u i Γ ( h T ; r i ) = λ i ( h T ) r i ( ℓ ( h T ) ) − ∑ t = 0 T − 1 p i ( h t , m t , a t ) u_i^\Gamma(h_T;r_i)=\lambda_i(h_T)r_i(\ell(h_T))-\sum_{t=0}^{T-1}p_i(h_t,m_t,a_t) u i Γ ( h T ; r i ) = λ i ( h T ) r i ( ℓ ( h T )) − ∑ t = 0 T − 1 p i ( h t , m t , a t ) . For a non-terminal platform history h h h , a type profile r r r , and opponent strategies σ − i \sigma_{-i} σ − i , the continuation expected utility U i Γ ( h ; r i , σ i , σ − i ; r − i ) U_i^\Gamma(h;r_i,\sigma_i,\sigma_{-i};r_{-i}) U i Γ ( h ; r i , σ i , σ − i ; r − i ) is
E h T ∼ P σ , r Γ ( ⋅ ∣ h ) [ λ i ( h T ) r i ( ℓ ( h T ) ) − ∑ t = t ( h ) T − 1 p i ( h t , m t , a t ) ] . \mathbb{E}_{h_T\sim\mathbb{P}^{\Gamma}_{\sigma,r}(\cdot\mid h)}
\left[
\lambda_i(h_T)r_i(\ell(h_T))-\sum_{t=t(h)}^{T-1}p_i(h_t,m_t,a_t)
\right]. E h T ∼ P σ , r Γ ( ⋅ ∣ h ) λ i ( h T ) r i ( ℓ ( h T )) − t = t ( h ) ∑ T − 1 p i ( h t , m t , a t ) .
Truthful reporting. The truthful report is specified by a mechanism-specific type-related reporting rule η i : Θ i × ( S ∖ S T ) → ⋃ h ∈ H M i ( h ) \eta_i:\Theta_i\times(\mathcal{S}\setminus\mathcal{S}_T)\to\bigcup_{h\in\mathcal{H}}M_i(h) η i : Θ i × ( S ∖ S T ) → ⋃ h ∈ H M i ( h ) . For example, the sub-tree reporting rule η i ( r i ; s ) = r i ∣ L ( s ) \eta_i(r_i;s)=r_i|_{L(s)} η i ( r i ; s ) = r i ∣ L ( s ) and the value function reporting rule η i ( s ; r i ) = ( V i r i ( s , a ) ) a ∈ V \eta_i(s;r_i)=(V_i^{r_i}(s,a))_{a\in\mathcal{V}} η i ( s ; r i ) = ( V i r i ( s , a ) ) a ∈ V . It defines the truthful strategy σ i t r ( r i , s ) : = η i ( s ; r i ) \sigma_i^{\mathrm{tr}}(r_i,s):=\eta_i(s;r_i) σ i tr ( r i , s ) := η i ( s ; r i ) .
Because a sequential mechanism allows advertisers to report information dynamically, incentive compatibility requires that an advertiser cannot wait for a favorable generated prefix and then manipulate its future reports. Formally,
Definition 1 (Markov DSIC and IR). The mechanism Γ \Gamma Γ is Markov dominant-strategy incentive compatible (Markov DSIC) if, for every advertiser i i i , type profile r r r , feasible opponent strategy profile σ − i \sigma_{-i} σ − i , reachable platform history h h h after advertiser i i i has reported truthfully along the prefix, and feasible continuation deviation σ i ′ \sigma_i' σ i ′ , U i Γ ( h ; r i , σ i t r , σ − i ; r − i ) ≥ U i Γ ( h ; r i , σ i ′ , σ − i ; r − i ) U_i^\Gamma(h;r_i,\sigma_i^{\mathrm{tr}},\sigma_{-i};r_{-i})\ge U_i^\Gamma(h;r_i,\sigma_i',\sigma_{-i};r_{-i}) U i Γ ( h ; r i , σ i tr , σ − i ; r − i ) ≥ U i Γ ( h ; r i , σ i ′ , σ − i ; r − i ) . It is individually rational (IR) if, truthful participation from the initial state s 0 = q s_0=q s 0 = q gives nonnegative expected utility: U i Γ ( q ; r i , σ i t r , σ − i ; r − i ) ≥ 0 U_i^\Gamma(q;r_i,\sigma_i^{\mathrm{tr}},\sigma_{-i};r_{-i})\ge0 U i Γ ( q ; r i , σ i tr , σ − i ; r − i ) ≥ 0 .
KL-regularized social welfare. The platform’s objective is to generate native and useful content while allocating advertising opportunities efficiently. For a query q q q , type profile r r r , generation policy π \pi π , define the KL-regularized social welfare SW β ( π , λ ∣ q , r ) \operatorname{SW}_{\beta}(\pi,\lambda\mid q,r) SW β ( π , λ ∣ q , r ) as
E τ ∼ π ( ⋅ ∣ q ) [ ∑ i ∈ N λ i ( h T ) r i ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log π ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] \mathbb{E}_{\tau\sim\pi(\cdot\mid q)}\left[\sum_{i \in\mathcal{N}}\lambda_i(h_T)r_i(\ell(\tau))-\beta\sum_{t=0}^{T_{\tau}-1}\log\frac{\pi(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right] E τ ∼ π ( ⋅ ∣ q ) [ i ∈ N ∑ λ i ( h T ) r i ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) π ( a t ∣ s t ) ]
The first term is gross advertiser value under the generated content and realized allocation. The divergence term penalizes deviation from the organic policy, which optimizes user experience.5 Thus β > 0 \beta> 0 β > 0 controls the balance between monetization and content naturalness. When the query is also random, the expected welfare is E q ∼ D [ SW β ( π , λ ∣ q , r ) ] \mathbb{E}_{q\sim\mathcal{D}}[\operatorname{SW}_{\beta}(\pi,\lambda\mid q,r)] E q ∼ D [ SW β ( π , λ ∣ q , r )] .
Mechanism design problem. For each query-type pair ( q , r ) (q,r) ( q , r ) , a sequential mechanism Γ \Gamma Γ and its truthful reporting rule induce a token policy π q , r Γ \pi^{\Gamma}_{q,r} π q , r Γ and allocation rule λ q , r Γ \lambda^{\Gamma}_{q,r} λ q , r Γ from the initial state. The platform chooses the mechanism to maximize induced welfare:
max Γ E q ∼ D , r ∼ F ( ⋅ ∣ q ) [ SW β ( π q , r Γ , λ q , r Γ ∣ q , r ) ] \max_{\Gamma}\quad\mathbb{E}_{q\sim\mathcal{D},\,r\sim F(\cdot\mid q)}\left[\operatorname{SW}_{\beta}\left(\pi^{\Gamma}_{q,r},\lambda^{\Gamma}_{q,r}\mid q,r\right)\right] Γ max E q ∼ D , r ∼ F ( ⋅ ∣ q ) [ SW β ( π q , r Γ , λ q , r Γ ∣ q , r ) ]
s.t. Γ is Markov DSIC and IR, \text{s.t.}\quad\Gamma\text{ is Markov DSIC and IR,} s.t. Γ is Markov DSIC and IR,
λ q , r Γ ( τ ) ∈ Λ , ∀ q , r , τ . \lambda^{\Gamma}_{q,r}(\tau)\in\Lambda,\ \forall q,r,\tau. λ q , r Γ ( τ ) ∈ Λ , ∀ q , r , τ .
Here F ( ⋅ ∣ q ) F(\cdot\mid q) F ( ⋅ ∣ q ) denotes the conditional distribution over the type profiles of advertisers recalled for query q q q . For ex-post analysis, the same objective can be studied pointwise for each realized ( q , r ) (q,r) ( q , r ) .
Latent Advertiser Mixture Auction
We propose Latent Advertiser Mixture Auction (LAMA) to tackle this challenge. The key idea is to view the generation process as Bayesian sequential decision making that identifies the advertiser who values the generation opportunity most. As we will see, this perspective leads to a simple algorithm that is both fast and efficient.
Sequential reports. At a non-terminal state s s s , advertiser i i i reports a child-value vector V ^ i s = ( V ^ i s ( [ s , a ] ) ) a ∈ V \widehat{V}^{s}_{i}=(\widehat{V}^{s}_{i}([s,a]))_{a\in\mathcal{V}} V i s = ( V i s ([ s , a ]) ) a ∈ V . The intended truthful report is η i ( s ; r i ) = ( V i ∗ ( [ s , a ] ) ) a ∈ V \eta_i(s;r_i)=(V_i^{*}([s,a]))_{a\in\mathcal{V}} η i ( s ; r i ) = ( V i ∗ ([ s , a ]) ) a ∈ V , where V i ∗ V_i^{*} V i ∗ is the optimal soft value function induced by advertiser i i i ’s terminal reward r i r_i r i :
V i ∗ ( s ) = max π E τ ∼ π ( ⋅ ∣ s ) [ r i ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log π ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] . V_i^{*}(s)=\max_{\pi}\mathbb{E}_{\tau\sim\pi(\cdot\mid s)}\left[r_i(\ell(\tau))-\beta\sum_{t=0}^{T_{\tau}-1}\log\frac{\pi(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]. V i ∗ ( s ) = π max E τ ∼ π ( ⋅ ∣ s ) [ r i ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) π ( a t ∣ s t ) ] .
Given a reported child-value vector, define advertiser i i i ’s induced local policy by
π ^ i ( a ∣ s ; V ^ i s ) : = π r e f ( a ∣ s ) exp ( V ^ i s ( [ s , a ] ) / β ) ∑ a ′ ∈ V π r e f ( a ′ ∣ s ) exp ( V ^ i s ( [ s , a ′ ] ) / β ) . \widehat{\pi}_i(a\mid s;\widehat{V}^{s}_i):=\frac{\pi_{\mathrm{ref}}(a\mid s)\exp\left(\widehat{V}^{s}_i([s,a])/\beta\right)}{\sum_{a'\in\mathcal{V}}\pi_{\mathrm{ref}}(a'\mid s)\exp\left(\widehat{V}^{s}_i([s,a'])/\beta\right)}. π i ( a ∣ s ; V i s ) := ∑ a ′ ∈ V π ref ( a ′ ∣ s ) exp ( V i s ([ s , a ′ ]) / β ) π ref ( a ∣ s ) exp ( V i s ([ s , a ]) / β ) .
This is the next-token policy that would be optimal if advertiser i i i ’s reported truthfully.
Allocation posterior and next-token rule. The mechanism maintains an allocation posterior ρ ( s ) ∈ Δ ( N ) \rho(s)\in\Delta(\mathcal{N}) ρ ( s ) ∈ Δ ( N ) . At the query q q q , after receiving the first child-value reports, initialize Z i ( q ) : = ∑ a ∈ V π r e f ( a ∣ q ) exp ( V ^ i q ( [ q , a ] ) / β ) Z_i(q):=\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid q)\exp(\widehat{V}^{q}_i([q,a])/\beta) Z i ( q ) := ∑ a ∈ V π ref ( a ∣ q ) exp ( V i q ([ q , a ]) / β ) , and set ρ i ( q ) : = Z i ( q ) ∑ j ∈ N Z j ( q ) \rho_i(q):=\frac{Z_i(q)}{\sum_{j\in\mathcal{N}}Z_j(q)} ρ i ( q ) := ∑ j ∈ N Z j ( q ) Z i ( q ) .
At a reached non-terminal state s s s , after receiving reports V ^ s = ( V ^ 1 s , … , V ^ n s ) \widehat{V}^{s}=(\widehat{V}^{s}_1,\ldots,\widehat{V}^{s}_n) V s = ( V 1 s , … , V n s ) , the mechanism samples hierarchically: first sample a latent advertiser I ∼ ρ ( s ) I\sim\rho(s) I ∼ ρ ( s ) and then generate the next token from that advertiser’s induced policy, a ∼ π ^ I ( ⋅ ∣ s ; V ^ I s ) a\sim\widehat{\pi}_I(\cdot\mid s;\widehat{V}^{s}_I) a ∼ π I ( ⋅ ∣ s ; V I s ) . Marginally, this sampling rule induces the mixture next-token distribution
χ ( a ∣ s , V ^ s , ρ ( s ) ) : = ∑ i ∈ N ρ i ( s ) π ^ i ( a ∣ s ; V ^ i s ) . \chi(a\mid s,\widehat{V}^{s},\rho(s)):=\sum_{i\in\mathcal{N}}\rho_i(s)\widehat{\pi}_i(a\mid s;\widehat{V}^{s}_i). χ ( a ∣ s , V s , ρ ( s )) := i ∈ N ∑ ρ i ( s ) π i ( a ∣ s ; V i s ) .
The subsequent posterior update is precisely Bayesian inference about this latent advertiser after observing the realized token. After token a a a is realized, the posterior is updated by Bayes’ rule:
ρ i ( [ s , a ] ) = ρ i ( s ) π ^ i ( a ∣ s ; V ^ i s ) χ ( a ∣ s , V ^ s , ρ ( s ) ) . \rho_i([s,a])=\frac{\rho_i(s)\widehat{\pi}_i(a\mid s;\widehat{V}^{s}_i)}{\chi(a\mid s,\widehat{V}^{s},\rho(s))}. ρ i ([ s , a ]) = χ ( a ∣ s , V s , ρ ( s )) ρ i ( s ) π i ( a ∣ s ; V i s ) .
If a terminal history h T h_T h T is reached, the final allocation rule is λ ( h T ) = ρ ( h T ) ∈ Δ ( N ) \lambda(h_T)=\rho(h_T)\in\Delta(\mathcal{N}) λ ( h T ) = ρ ( h T ) ∈ Δ ( N ) .
Payment rule. The payment rule has two components. First, after the initial reports at the query prefix q q q , advertiser i i i pays an entry fee p i ( q ; V ^ ) p_i(q;\widehat{V}) p i ( q ; V ) :
ρ i ( q ) V ^ i ( q ) − β log ∑ j ∈ N exp ( V ^ j ( q ) / β ) + β log ( 1 + ∑ j ≠ i exp ( V ^ j ( q ) / β ) ) , \rho_i(q)\widehat{V}_i(q)-\beta\log\sum_{j\in\mathcal{N}}\exp(\widehat{V}_j(q)/\beta)+\beta\log\left(1+\sum_{j\ne i}\exp(\widehat{V}_j(q)/\beta)\right), ρ i ( q ) V i ( q ) − β log j ∈ N ∑ exp ( V j ( q ) / β ) + β log 1 + j = i ∑ exp ( V j ( q ) / β ) ,
where V ^ i ( q ) = β log Z i ( q ) \widehat{V}_i(q)=\beta\log Z_i(q) V i ( q ) = β log Z i ( q ) is the root value induced by the initial child-value report. Second, along the generated path, the mechanism charges advertisers according to the change in their posterior-weighted reported continuation value. At a transition s → [ s , a ] s\to[s,a] s → [ s , a ] , define the instantaneous payment
p i ( s , V ^ s , a ) : = ρ i ( [ s , a ] ) V ^ i s ( [ s , a ] ) − ρ i ( s ) V ^ i ( s ) , p_i(s,\widehat{V}^{s},a):=\rho_i([s,a])\widehat{V}^{s}_i([s,a])-\rho_i(s)\widehat{V}_i(s), p i ( s , V s , a ) := ρ i ([ s , a ]) V i s ([ s , a ]) − ρ i ( s ) V i ( s ) ,
where the parent value V ^ i ( s ) \widehat{V}_i(s) V i ( s ) is the value previously recorded in the platform ledger. Thus, the mechanism charges advertiser i i i when the realized token makes its continuation prospects more favorable, and subsidizes it when situation gets worse, preserving its incentive to continue participating after an unfavorable transition.
Feasible message space. We require reports to satisfy the soft Bellman recursion. This is easy to verify online: for each advertiser, the platform only needs to store a scalar, i.e. the value previously reported for the current state, and compare it with the soft Bellman aggregation of the newly reported child values. Formally,
Definition 2 (Bellman consistency). At a history h h h with current state s = s ( h ) s=s(h) s = s ( h ) , let V ^ i ( s ) \widehat{V}_i(s) V i ( s ) be advertiser i i i ’s value for s s s already stored in the ledger. The feasible message space is
M i ( h ) : = { R ∣ V ∣ , s = q , { v ∈ R ∣ V ∣ : β log ∑ a ∈ V π r e f ( a ∣ s ) e v a / β = V ^ i ( s ) } , s ≠ q . \mathcal{M}_i(h):=
\begin{cases}
\mathbb{R}^{|\mathcal{V}|}, & s=q,\\
\left\{v\in\mathbb{R}^{|\mathcal{V}|}:\beta\log\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)e^{v_a/\beta}=\widehat{V}_i(s)\right\}, & s\ne q.
\end{cases} M i ( h ) := { R ∣ V ∣ , { v ∈ R ∣ V ∣ : β log ∑ a ∈ V π ref ( a ∣ s ) e v a / β = V i ( s ) } , s = q , s = q .
Here v a v_a v a is the reported value of the child state [ s , a ] [s,a] [ s , a ] in V ^ i s \widehat{V}^{s}_i V i s .
We now ready to show the main incentive guarantee.
Theorem 1 (Markov DSIC and IR of LAMA). The LAMA with Bellman-consistent message spaces is Markov DSIC and IR for the truthful reporting rule η i ( s ; r i ) = ( V i ∗ ( [ s , a ] ) ) a ∈ V \eta_i(s;r_i)=(V_i^{*}([s,a]))_{a\in\mathcal{V}} η i ( s ; r i ) = ( V i ∗ ([ s , a ]) ) a ∈ V .
Proof sketch. First consider globally Bellman-consistent direct reports and write z i ( s ) = exp ( V ^ i ( s ) / β ) z_i(s)=\exp(\widehat{V}_i(s)/\beta) z i ( s ) = exp ( V i ( s ) / β ) and z ( s ) = ∑ j z j ( s ) z(s)=\sum_j z_j(s) z ( s ) = ∑ j z j ( s ) . Bellman consistency makes each z i z_i z i harmonic under π r e f \pi_{\mathrm{ref}} π ref . Substituting this identity into the Bayesian update yields ρ i ( s ) = z i ( s ) / z ( s ) \rho_i(s)=z_i(s)/z(s) ρ i ( s ) = z i ( s ) / z ( s ) and χ ( a ∣ s ) = π r e f ( a ∣ s ) z ( [ s , a ] ) / z ( s ) \chi(a\mid s)=\pi_{\mathrm{ref}}(a\mid s)z([s,a])/z(s) χ ( a ∣ s ) = π ref ( a ∣ s ) z ([ s , a ]) / z ( s ) . The factors telescope along a path, so the joint probability that terminal state ℓ \ell ℓ is generated and allocated to advertiser i i i is
α i , ℓ ( V ^ ) = P 0 ( ℓ ∣ q ) exp ( V ^ i ( ℓ ) / β ) ∑ ℓ ′ P 0 ( ℓ ′ ∣ q ) ∑ j exp ( V ^ j ( ℓ ′ ) / β ) . \alpha_{i,\ell}(\widehat{V}) = \frac{P_0(\ell\mid q)\exp(\widehat{V}_i(\ell)/\beta)}{\sum_{\ell'} P_0(\ell' \mid q)\sum_j \exp(\widehat{V}_j(\ell')/\beta)}. α i , ℓ ( V ) = ∑ ℓ ′ P 0 ( ℓ ′ ∣ q ) ∑ j exp ( V j ( ℓ ′ ) / β ) P 0 ( ℓ ∣ q ) exp ( V i ( ℓ ) / β ) .
This is exactly the gradient, with respect to terminal reports, of the convex log-sum-exp potential Φ q \Phi_q Φ q defined in the appendix. The telescoping LAMA payment is the corresponding potential-based payment, so the convex supporting hyperplane inequality gives direct truthfulness. Nonnegative rewards imply z ( q ) ≥ 1 z^{(q)} \ge1 z ( q ) ≥ 1 , which makes truthful utility nonnegative relative to the outside option.
It remains to connect online reports to this direct construction. Fix a reached state s s s after a truthful prefix. Any feasible continuation deviation defines a Bellman-consistent value function inside the subtree rooted at s s s . When s ≠ q s \ne q s = q , feasibility forces its root value to equal the truthful value already stored at s s s ; when s = q s=q s = q , there are no ancestors to preserve. Use the deviating values inside the subtree and V i ∗ V_i^* V i ∗ everywhere else. The result is a globally Bellman-consistent direct report with the same continuation policy, allocation, and payments as the online deviation. Direct DSIC and IR then immediately imply Markov DSIC and IR for the sequential mechanism. □
Efficiency. LAMA also provides strong efficiency guarantee. Intuitively, it implements two soft lotteries: one over generated responses through KL-regularized decoding and one over advertisers through entropy-regularized allocation. The resulting welfare loss is at most β log ∣ N ∣ \beta\log|\mathcal{N}| β log ∣ N ∣ relative to the optimal KL-regularized benchmark, and the mechanism approaches first-best welfare as β → 0 + \beta\to0^+ β → 0 + .
Theorem 2 (Optimization objective and asymptotic efficiency). Fix a query q q q and a type profile r r r . Let ( x β , λ β ) (x^\beta,\lambda^\beta) ( x β , λ β ) be the truthful policy and terminal allocation induced by LAMA. Then ( x β , λ β ) (x^\beta,\lambda^\beta) ( x β , λ β ) maximizes the entropy-relaxed welfare:
E τ ∼ x ( ⋅ ∣ q ) [ ∑ i ∈ N λ i ( τ ) r i ( ℓ ( τ ) ) + β H ( λ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] . \mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[\sum_{i\in\mathcal{N}}\lambda_i(\tau)r_i(\ell(\tau))+\beta H(\lambda(\tau))-\beta\sum_{t=0}^{T_{\tau}-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]. E τ ∼ x ( ⋅ ∣ q ) [ i ∈ N ∑ λ i ( τ ) r i ( ℓ ( τ )) + β H ( λ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] .
Moreover, relative to the optimal KL-regularized welfare in the simplex allocation setting, sup π , λ S W β ( π , λ ∣ q , r ) \sup_{\pi,\lambda} SW_\beta(\pi,\lambda\mid q,r) sup π , λ S W β ( π , λ ∣ q , r ) , the welfare loss of the Latent Advertiser Mixture mechanism is bounded by
0 ≤ sup π , λ S W β ( π , λ ∣ q , r ) − S W β ( x β , λ β ∣ q , r ) ≤ β log ∣ N ∣ . 0 \le\sup_{\pi,\lambda} SW_\beta(\pi,\lambda\mid q,r)-SW_\beta(x^\beta,\lambda^\beta\mid q,r)\le\beta\log|\mathcal{N}|. 0 ≤ π , λ sup S W β ( π , λ ∣ q , r ) − S W β ( x β , λ β ∣ q , r ) ≤ β log ∣ N ∣.
Thus, lim β → 0 + S W β ( x β , λ β ∣ q , r ) = max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) \lim_{\beta\to0^+}SW_\beta(x^\beta,\lambda^\beta\mid q,r)=\max_{\ell\in L(q)}\max_{i\in\mathcal{N}}r_i(\ell) lim β → 0 + S W β ( x β , λ β ∣ q , r ) = max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) . The same welfare-gap bound holds after taking expectation over q ∼ D q\sim\mathcal{D} q ∼ D .
Practical Implementation
In practice, computing the reports required by LAMA is generally beyond the capabilities of individual advertisers. At each non-terminal state s s s , advertiser i i i would need to submit the continuation vector ( V i ∗ ( s , a ) ) a ∈ V (V_i^*(s,a))_{a\in\mathcal{V}} ( V i ∗ ( s , a ) ) a ∈ V . Doing so requires both high-quality user feedback data and considerable computational resources. We therefore provide reporting as a platform-side service analogous to auto-bidding 2 : the platform learns value reports from advertising feedback and serves them on advertisers’ behalf.
As we will show, the platform can avoid learning the full soft value function through reinforcement learning by decomposing reporting into two simpler stages. It learns local soft advantages, which determine changes in value between adjacent prefixes, and a root value which anchors the absolute scale. These two outputs are then assembled into the required report along the realized path. Both stages can use standard supervised signals and be implemented by advertiser-conditioned services shared across advertisers.
Value Decomposition
For a prefix s s s and next token a a a , the optimal soft advantage for advertiser i i i satisfies A i ∗ ( s , a ) = V i ∗ ( [ s , a ] ) − V i ∗ ( s ) A_i^*(s,a)=V_i^*( [s,a])-V_i^*(s) A i ∗ ( s , a ) = V i ∗ ([ s , a ]) − V i ∗ ( s ) .3 For a completed response y = ( a 0 , … , a T y − 1 ) y=(a_0,\ldots,a_{T_y-1}) y = ( a 0 , … , a T y − 1 ) , let s t = [ q , a < t ] s_t=[q,a_{<t}] s t = [ q , a < t ] , ℓ y = [ q , y ] \ell_y=[q,y] ℓ y = [ q , y ] . Then the value of every prefix can be obtained from the root value by telescoping: V i ∗ ( s t ) = V i ∗ ( q ) + ∑ k = 0 t − 1 A i ∗ ( s k , a k ) V_i^*(s_t)=V_i^*(q)+\sum_{k=0}^{t-1}A_i^*(s_k,a_k) V i ∗ ( s t ) = V i ∗ ( q ) + ∑ k = 0 t − 1 A i ∗ ( s k , a k ) . Thus, to construct the truthful child-value report at any reachable state, it is enough to know the root value V i ∗ ( q ) V_i^*(q) V i ∗ ( q ) and the local advantages A i ∗ ( s , a ) A_i^*(s,a) A i ∗ ( s , a ) .
We now present the learning objectives for these two functions. Define r i ( ℓ y ) r_i(\ell_y) r i ( ℓ y ) as advertiser i i i ’s population value for receiving the advertising impression opportunity from response y y y . Let D \mathcal{D} D denote the population comparison distribution over ( i , q , y , y ′ ) (i,q,y,y') ( i , q , y , y ′ ) , and use D ( ⋅ ∣ i , q ) \mathcal{D}(\cdot\mid i,q) D ( ⋅ ∣ i , q ) for its single-response marginal when only y y y is needed.
I. Local advantages. For any policy π i \pi_i π i , define the cumulative response score as G i π ( q , y ) : = β log π i ( y ∣ q ) π r e f ( y ∣ q ) = β ∑ t = 0 T y − 1 log π i ( a t ∣ s t ) π r e f ( a t ∣ s t ) G_i^{\pi}(q,y):=\beta\log\frac{\pi_i(y\mid q)}{\pi_{\mathrm{ref}}(y\mid q)}=\beta\sum_{t=0}^{T_y-1}\log\frac{\pi_i(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)} G i π ( q , y ) := β log π ref ( y ∣ q ) π i ( y ∣ q ) = β ∑ t = 0 T y − 1 log π ref ( a t ∣ s t ) π i ( a t ∣ s t ) . To learn these token-level log-ratios, the platform samples paired responses y y y and y ′ y' y ′ under the same advertiser-query pair ( i , q ) (i,q) ( i , q ) . From their scalar rewards, it constructs the Bradley-Terry 4 win rate
ω i ( q ; y , y ′ ) : = Pr ( y ≻ y ′ ∣ i , q ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ ) ) . \omega_i(q;y,y'):=\Pr(y\succ y'\mid i,q)=\sigma(r_i(\ell_y)-r_i(\ell_{y'})). ω i ( q ; y , y ′ ) := Pr ( y ≻ y ′ ∣ i , q ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ )) .
Let Δ i π ( q ; y , y ′ ) : = G i π ( q , y ) − G i π ( q , y ′ ) \Delta_i^\pi(q;y,y'):=G_i^\pi(q,y)-G_i^\pi(q,y') Δ i π ( q ; y , y ′ ) := G i π ( q , y ) − G i π ( q , y ′ ) . The ideal local-advantage objective is therefore the binary cross-entropy,
L ( π ) : = − E ( i , q , y , y ′ ) ∼ D [ ω i ( q ; y , y ′ ) log σ ( Δ i π ( q ; y , y ′ ) ) + ( 1 − ω i ( q ; y , y ′ ) ) log σ ( − Δ i π ( q ; y , y ′ ) ) ] . \mathcal{L}(\pi):=-\mathbb{E}_{(i,q,y,y')\sim\mathcal{D}}\left[\omega_i(q;y,y')\log\sigma(\Delta_i^\pi(q;y,y'))+(1-\omega_i(q;y,y'))\log\sigma(-\Delta_i^\pi(q;y,y'))\right]. L ( π ) := − E ( i , q , y , y ′ ) ∼ D [ ω i ( q ; y , y ′ ) log σ ( Δ i π ( q ; y , y ′ )) + ( 1 − ω i ( q ; y , y ′ )) log σ ( − Δ i π ( q ; y , y ′ )) ] .
As we will show later, under the usual regularity conditions, the population minimizer π ∗ \pi^* π ∗ matches the Bradley-Terry log-odds and therefore identifies reward differences between completed responses under the same ( i , q ) (i,q) ( i , q ) . In the soft-control view, the corresponding local log-ratio A ^ i ∗ ( s , a ) : = β log π i ∗ ( a ∣ s ) π r e f ( a ∣ s ) \widehat{A}_i^*(s,a):=\beta\log\frac{\pi_i^*(a\mid s)}{\pi_{\mathrm{ref}}(a\mid s)} A i ∗ ( s , a ) := β log π ref ( a ∣ s ) π i ∗ ( a ∣ s ) recovers the local soft advantage A i ∗ ( s , a ) A_i^*(s,a) A i ∗ ( s , a ) .
II. Root values. The root value is anchored separately from scalar rewards. Since a terminal state has value V i ∗ ( ℓ y ) = r i ( ℓ y ) V_i^*(\ell_y)=r_i(\ell_y) V i ∗ ( ℓ y ) = r i ( ℓ y ) , telescoping gives, for every completed response,
V i ∗ ( q ) = r i ( ℓ y ) − ∑ t = 0 T y − 1 A i ∗ ( s t , a t ) . V_i^*(q)=r_i(\ell_y)-\sum_{t=0}^{T_y-1}A_i^*(s_t,a_t). V i ∗ ( q ) = r i ( ℓ y ) − t = 0 ∑ T y − 1 A i ∗ ( s t , a t ) .
Averaging this residual over population responses for the same ( i , q ) (i,q) ( i , q ) recovers the root value. The two ideal learning tasks are therefore: learn local advantages from BT-weighted pairwise differences, and thereby anchor the root value with terminal rewards.
The next theorem shows that the population local-advantage optimum identifies both the local soft advantages and a residual formula for the root value. The ledger recursion is then enabled to reconstruct the optimal soft value on every reached prefix, formally justifying the value decomposition above.
Theorem 3 (Exact recovery). Suppose D \mathcal{D} D has full comparison support 6 . Then the optimal token policy π ∗ \pi^* π ∗ is the unique minimizer of the local-advantage objective L L L . Relatedly, the recovered log-ratio A ^ i ∗ ( s , a ) : = β log π i ∗ ( a ∣ s ) π r e f ( a ∣ s ) \widehat{A}_i^*(s,a) := \beta\log\frac{\pi_i^*(a\mid s)}{\pi_{\mathrm{ref}}(a\mid s)} A i ∗ ( s , a ) := β log π ref ( a ∣ s ) π i ∗ ( a ∣ s ) equals A i ∗ ( s , a ) A_i^*(s,a) A i ∗ ( s , a ) . Also, the root value v i ∗ ( q ) : = E y ∼ D ( ⋅ ∣ i , q ) [ r i ( ℓ y ) − ∑ t = 0 T y − 1 A ^ i † ( s t , a t ) ] v_i^*(q) := \mathbb{E}_{y\sim\mathcal{D}(\cdot\mid i,q)}\left[r_i(\ell_y)-\sum_{t=0}^{T_y-1}\widehat{A}_i^\dagger(s_t,a_t)\right] v i ∗ ( q ) := E y ∼ D ( ⋅ ∣ i , q ) [ r i ( ℓ y ) − ∑ t = 0 T y − 1 A i † ( s t , a t ) ] equals V i ∗ ( q ) V_i^*(q) V i ∗ ( q ) .
Finally, initialize V ^ i ( q ) : = v i ∗ ( q ) \widehat{V}_i(q):=v_i^*(q) V i ( q ) := v i ∗ ( q ) and recursively define V ^ i ( [ s , a ] ) : = V ^ i ( s ) + A ^ i ∗ ( s , a ) \widehat{V}_i([s,a]):=\widehat{V}_i(s)+\widehat{A}_i^*(s,a) V i ([ s , a ]) := V i ( s ) + A i ∗ ( s , a ) . Then V ^ i ( s ) = V i ∗ ( s ) \widehat{V}_i(s)=V_i^*(s) V i ( s ) = V i ∗ ( s ) at every reachable prefix. Consequently, the resulting child-value vector is exactly the truthful soft-value report required by LAMA.
Shared report model. Motivated by this recovery result, and to reduce the cost of training and serving separate models, the platform instantiates the two learned components with a single shared pretrained backbone. All advertisers share the parameters, while information specific to each advertiser i i i enters only through a conditioning prompt κ i \kappa_i κ i , which contains its identity and campaign information, such as the creative, landing page, and targeting context. For any generation prefix s s s , the same model is run on the concatenated context [ κ i , s ] [\kappa_i,s] [ κ i , s ] and produces next-token logits z θ ( a ∣ [ κ i , s ] ) z_\theta(a\mid[\kappa_i,s]) z θ ( a ∣ [ κ i , s ]) . The policy for advertiser i i i is the softmax of these logits:
π θ , i ( a ∣ s ) : = softmax a z θ ( a ∣ [ κ i , s ] ) = exp z θ ( a ∣ [ κ i , s ] ) ∑ b ∈ V exp z θ ( b ∣ [ κ i , s ] ) . \pi_{\theta,i}(a\mid s):=\operatorname{softmax}_{a}z_\theta(a\mid[\kappa_i,s])=\frac{\exp z_\theta(a\mid[\kappa_i,s])}{\sum_{b\in\mathcal{V}}\exp z_\theta(b\mid[\kappa_i,s])}. π θ , i ( a ∣ s ) := softmax a z θ ( a ∣ [ κ i , s ]) = ∑ b ∈ V exp z θ ( b ∣ [ κ i , s ]) exp z θ ( a ∣ [ κ i , s ]) .
And the root anchor is produced by a fine-tuned scalar value head attached to the same shared representation:
v ϕ , i ( q ) : = v ϕ ( [ κ i , q ] ) . v_{\phi,i}(q):=v_\phi([\kappa_i,q]). v ϕ , i ( q ) := v ϕ ([ κ i , q ]) .
The deployed object is therefore a single shared model that produces advertiser-specific outputs: next-token logits for local reports and a scalar root value for initializing the ledger. Appendix A gives the practical finite-sample training procedure in Algorithm 2.
Serving-time Procedure
Figure 2 provides an intuitive overview of LAMA. At serving time, the learned objects above are exposed as a single report service. For each query q q q , the platform first retrieves a small candidate set of advertisers through the standard advertising funnel. For each retrieved advertiser i i i , it builds the advertiser prefix κ i \kappa_i κ i , evaluates the root value, and initializes the value ledger by V ^ i ( s 0 ) : = v ϕ , i ( q ) \widehat{V}_i(s_0):=v_{\phi,i}(q) V i ( s 0 ) := v ϕ , i ( q ) . The same root values initialize the allocation posterior. After each non-terminal prefix s t s_t s t , the service returns advertiser-conditioned logits. The platform converts them into local advantages A ^ θ , i ( s t , a ) : = β log ( π θ , i ( a ∣ s t ) / π r e f ( a ∣ s t ) ) \widehat{A}_{\theta,i}(s_t,a):=\beta\log(\pi_{\theta,i}(a\mid s_t)/\pi_{\mathrm{ref}}(a\mid s_t)) A θ , i ( s t , a ) := β log ( π θ , i ( a ∣ s t ) / π ref ( a ∣ s t )) and therefore into child-value reports V ^ i s t ( [ s t , a ] ) = V ^ i ( s t ) + A ^ θ , i ( s t , a ) \widehat{V}_i^{s_t}([s_t,a])=\widehat{V}_i(s_t)+\widehat{A}_{\theta,i}(s_t,a) V i s t ([ s t , a ]) = V i ( s t ) + A θ , i ( s t , a ) .7 The remaining steps follow the theoretical mechanism directly. Since the candidate advertiser set is typically small, LAMA incurs only a small constant-factor overhead in language model forward passes relative to generating a reference answer, keeping online serving lightweight. Algorithm 1 formally summarizes the serving procedure.
Figure 2. Overview of the Latent Advertiser Mixture Auction (LAMA). (1) Report: Advertisers report soft values for the current child states, and the platform verifies Bellman consistency against the value stored in its ledger. (2) Next-token generation: The platform samples an advertiser from its current belief, whose optimal policy generates the next token. (3) Update: After the context changes, the platform updates the ledger and its belief over the optimal advertiser via Bayes’ rule. (4) Settlement: Once the response is complete, the platform samples a winning advertiser from the posterior; the winner pays the corresponding charge and receives the hyperlink placement. See Figure 3 for additional impression formats.
Notably, the fractional form of LAMA may charge an advertiser that does not ultimately receive the advertising opportunity. We therefore use the equivalent randomized settlement in Algorithm 1: after the final posterior is formed, the platform samples the winner I ∗ ∼ ρ ( s T ) I^*\sim\rho(s_T) I ∗ ∼ ρ ( s T ) , settles only with that winner, and charges zero to all non-winners. Because this preserves expected utilities, the incentive-compatibility guarantees carry over directly. It also yields outcome IR while preserving expected weak budget balance, even though individual payment transfers may have either sign.
Proposition 1 (Outcome IR and expected WBB). If the served reports are exact, then the winner-settled LAMA implementation in Algorithm 1 is outcome individually rational: for every realized terminal state and sampled winner, non-winners pay zero and the winning advertiser i i i obtains non-negative realized utility. Moreover, conditional on the query and candidate advertiser set, the platform is weakly budget balanced in expectation: E [ ∑ i ∈ N P i ( s T , T ∗ ) ] ≥ 0 \mathbb{E}[\sum_{i\in\mathcal{N}}P_i(s_T,T^*)]\ge0 E [ ∑ i ∈ N P i ( s T , T ∗ )] ≥ 0 .
Algorithm 1 Latent Advertiser Mixture Auction (LAMA)
Require: Query q q q , Candidate advertisers N = { 1 , … , n } \mathcal{N} = \{1, \ldots, n\} N = { 1 , … , n } , Reference policy π r e f \pi_{\mathrm{ref}} π ref , Shared report model ( π θ , v ϕ ) (\pi_\theta, v_\phi) ( π θ , v ϕ ) , Temperature β \beta β
1: Initialize: Context s 0 ← q s_0 \gets q s 0 ← q , Step t ← 0 t \gets0 t ← 0 , Allocation posterior ρ i ( s 0 ) ← exp ( v ϕ , i ( q ) / β ) ∑ j ∈ N exp ( v ϕ , j ( q ) / β ) \rho_i(s_0) \gets\frac{\exp(v_{\phi,i}(q)/\beta)}{\sum_{j \in\mathcal{N}} \exp(v_{\phi,j}(q)/\beta)} ρ i ( s 0 ) ← ∑ j ∈ N e x p ( v ϕ , j ( q ) / β ) e x p ( v ϕ , i ( q ) / β ) for all i ∈ N i \in\mathcal{N} i ∈ N
2: Initialize Ledger: V ^ i ( s 0 ) ← v ϕ , i ( q ) \hat{V}_i(s_0) \gets v_{\phi,i}(q) V ^ i ( s 0 ) ← v ϕ , i ( q ) for all i ∈ N i \in\mathcal{N} i ∈ N
3: while s t s_t s t is not terminal do
4: for each advertiser i ∈ N i \in\mathcal{N} i ∈ N do
5: // Compute local advantage and consistent child-value reports
6: A ^ θ , i ( s t , a ) ← β log π θ , i ( a ∣ s t ) π r e f ( a ∣ s t ) ∀ a ∈ V \hat{A}_{\theta,i}(s_t, a) \gets\beta\log\frac{\pi_{\theta,i}(a \mid s_t)}{\pi_{\mathrm{ref}}(a \mid s_t)} \quad\forall a \in\mathcal{V} A ^ θ , i ( s t , a ) ← β log π ref ( a ∣ s t ) π θ , i ( a ∣ s t ) ∀ a ∈ V
7: V ^ i s t ( [ s t , a ] ) ← V ^ i ( s t ) + A ^ θ , i ( s t , a ) ∀ a ∈ V \hat{V}_i^{s_t}([s_t,a]) \gets\hat{V}_i(s_t) + \hat{A}_{\theta,i}(s_t,a) \quad\forall a \in\mathcal{V} V ^ i s t ([ s t , a ]) ← V ^ i ( s t ) + A ^ θ , i ( s t , a ) ∀ a ∈ V
8: end for
9: // Hierarchical Sampling Process
10: Sample a latent advertiser I ∼ ρ ( s t ) I \sim\rho(s_t) I ∼ ρ ( s t ) ▷ Choose guiding advertiser
11: Sample next token a t ∼ π ^ I ( ⋅ ∣ s t ) a_t \sim\hat{\pi}_I(\cdot\mid s_t) a t ∼ π ^ I ( ⋅ ∣ s t ) ▷ Generate token from that advertiser’s policy
12: // Update state and Bayesian allocation posterior
13: s t + 1 ← [ s t , a t ] s_{t+1} \gets[s_t,a_t] s t + 1 ← [ s t , a t ]
14: for each advertiser i ∈ N i \in\mathcal{N} i ∈ N do
15: ρ i ( s t + 1 ) ← ρ i ( s t ) ⋅ π θ , i ( a t ∣ s t ) x ( a t ∣ s t , V ^ s t , ρ ( s t ) ) \rho_i(s_{t+1}) \gets\frac{\rho_i(s_t) \cdot\pi_{\theta,i}(a_t \mid s_t)}{x(a_t \mid s_t,\hat{V}^{s_t},\rho(s_t))} ρ i ( s t + 1 ) ← x ( a t ∣ s t , V ^ s t , ρ ( s t )) ρ i ( s t ) ⋅ π θ , i ( a t ∣ s t ) ▷ Posterior update
16: V ^ i ( s t + 1 ) ← V ^ i ( s t ) + A ^ θ , i ( s t , a t ) \hat{V}_i(s_{t+1}) \gets\hat{V}_i(s_t) + \hat{A}_{\theta,i}(s_t,a_t) V ^ i ( s t + 1 ) ← V ^ i ( s t ) + A ^ θ , i ( s t , a t ) ▷ Update value ledger
17: end for
18: t ← t + 1 t \gets t + 1 t ← t + 1
19: end while
20: Terminal State Reached: Let s T s_T s T be the terminal state, Total tokens generated T T T
21: // Winner-Pay Settlement: Sample a single winner from the final posterior
22: Sample a winner I ∗ ∼ ρ ( s T ) I^* \sim\rho(s_T) I ∗ ∼ ρ ( s T )
23: for each advertiser i ∈ N i \in\mathcal{N} i ∈ N do
24: if i = I ∗ i = I^* i = I ∗ then
25: // Telescoped trajectory-level payment
26: P i ← ρ i ( s T ) V ^ i ( s T ) − β log ∑ j ∈ N exp ( V ^ j ( s 0 ) / β ) + β log ( 1 + ∑ j ≠ i exp ( V ^ j ( s 0 ) / β ) ) P_i \gets\rho_i(s_T)\hat{V}_i(s_T) - \beta\log\sum_{j \in\mathcal{N}} \exp(\hat{V}_j(s_0)/\beta) + \beta\log\left(1 + \sum_{j \ne i} \exp(\hat{V}_j(s_0)/\beta)\right) P i ← ρ i ( s T ) V ^ i ( s T ) − β log ∑ j ∈ N exp ( V ^ j ( s 0 ) / β ) + β log ( 1 + ∑ j = i exp ( V ^ j ( s 0 ) / β ) )
27: P i ← ρ i ( s T ) − 1 P i P_i \gets\rho_i(s_T)^{-1}P_i P i ← ρ i ( s T ) − 1 P i ▷ Adjust by winning probability
28: else
29: P i ← 0 P_i \gets0 P i ← 0 ▷ Non-winners pay nothing
30: end if
31: end for
32: return Generated sequence s T s_T s T , Winner I ∗ I^* I ∗ , Payments ( P 1 , … , P n ) (P_1,\ldots,P_n) ( P 1 , … , P n )
Experiments
In this section, we empirically evaluate the proposed LAMA in generation-native advertising settings. The goal is to test whether token-level participation of advertisers can improve monetization while preserving the quality and naturalness of generated responses.
Setup
We evaluate mechanisms across representative advertising verticals. Each vertical consists of a set of user queries, candidate advertisers and advertiser descriptions. We use a reference language model (Qwen3-14B) [29 ] , advertiser-shared report models (trained LoRA heads) [18 ] , and a prediction model for oracle impression value [21 , 31 ] . The main experiments cover three verticals constructed from real-world commercial search query splits in the Webis Generated Native Ads 2024 dataset [24 ] : Workout, Vacation, and Car . Each vertical contains three heterogeneous advertisers.
Baselines. We first compare against six heuristic incentive-compatible baselines obtained by combining two auction rules with three generation rules. The auction rules are: (i) Before. The winner is chosen before generation uniformly at random, and the advertiser pays nothing. (ii) After. The candidate responses are generated first. Then advertisers are scored using predicted impression value, and a second-price auction is applied. The generation rules are: (i) Original. Generate only with the reference model. (ii) Edit. Use a no-ad reference response as the base and insert sponsored content of an advertiser through a fused editing process. (iii) Policy. Each advertiser submits its preferred response, i.e., the content it expects to maximize its impression value. We approximate this response using best-of-K K K sampling from the advertiser’s optimal policy, with candidates ranked by self-predicted impression value.
We also compare against MOSAIC [25 ] , a representative response-level aggregation mechanism. It generates M M M complete context-aware candidate responses, scores each candidate by aggregate advertiser value, and selects a final response via a weighted lottery.
Metrics. Our evaluation considers three perspectives: the platform, the advertiser, and the user. On the platform side, we report (i) Welfare , defined as the realized advertising value minus the KL regularization term that captures the user-experience cost, and (ii) Revenue , defined as the payment collected from the winning advertiser. On the advertiser side, we measure (i) Value , namely the impression value obtained by the winning advertiser. On the user side, we evaluate (i) Quality . Since the KL penalty alone does not fully reflect the actual user experience of the generated text, we adopt the evaluation rubrics from the GEM-Bench [19 ] to assess user utility. Specifically, Quality aggregates multiple dimensions, including answer relevance, informativeness, fluency and coherence, ad naturalness, ad factuality, and intrusiveness.
Main Results
Table 1 summarizes the main results. LAMA achieves the strongest overall performance among the compared methods, attaining the highest mean platform welfare (0.5205), revenue (0.8305), advertiser value (0.8568), and user quality (66.5239). Relative to the allocate-after policy baseline, LAMA delivers a clear improvement in revenue, together with further gains in welfare and advertiser value. At the same time, it preserves user-facing response quality, matching the best-performing baseline on this dimension. Appendix D provides additional experimental evidence, including case studies and token-level analyses for complementary and competing advertisers, latency measurements, value prediction accuracy and calibration, and bid-offset sweeps of allocation, payment, and advertiser utility.
Table 1. Main results on three representative verticals from Webis. Smaller gray values denote 95% bootstrap errors.
Taken together, these results provide an initial proof of concept for LAMA: token-level advertiser participation can improve monetization without sacrificing response quality, suggesting the potential of generation-native advertising as a viable paradigm.
Classical online advertising auctions typically allocate exogenously defined inventory, such as sponsored-search or display slots, through mechanisms including GSP and VCG [? , 27 ]. Subsequent work incorporates cascade effects, ad externalities, and richer click-through-rate structures [2 , 7 , 11 ] , and studies the joint optimization of advertising and organic content across search, recommendation, e-commerce, and contextual advertising [3 , 6 , 12 , 13 , 14 , 20 ] . Despite richer interactions with users and surrounding content, these models largely retain a common abstraction: the mechanism allocates pre-existing slots, items, or positions whose advertising opportunities are defined before allocation.
Generative interfaces challenge this abstraction because advertising opportunities may depend on the response being generated. More broadly, recent work studies mechanisms in which strategic agents influence LLM outputs through next-token distributions or preferences, making generation itself part of the mechanism outcome [8 , 9 , 25 ] . In LLM advertising, some works define opportunities over discourse segments or context-dependent position–creative pairs [4 , 15 ] , while others study response-level ad insertion [28 ] . More LLM-native approaches incorporate response-quality constraints [16 ] , allocate advertising through the model’s output distribution [32 ] , or explore opportunities arising from retrieval decisions and internal model representations [26 , 30 ] . Together, these works progressively move advertising allocation from fixed slots toward the generation process itself.
Our work takes a further step toward generation-native advertising by allowing advertisers to influence generation at token-level granularity. Rather than allocating an opportunity identified before or after generation, LAMA operates over the generation trajectory: advertiser influence evolves with the current prefix, posterior beliefs, and continuation values. Thus, the advertising opportunity itself emerges dynamically through generation, shifting the mechanism-design problem from allocating sponsored content within generated responses to governing how advertiser influence shapes the response-generation process.
Conclusion
In this work, we introduced generation-native advertising, where advertising opportunities are shaped during generation rather than allocated only after they have been formed. LAMA instantiates this idea at token level, achieving Markov DSIC and IR with bounded welfare loss, together with a practical learning-based implementation. Proof-of-concept experiments show that LAMA can improve monetization while maintaining user-facing response quality. More broadly, our results point toward a new direction for advertising mechanism design in generative interfaces, where mechanisms govern not only who receives an advertising opportunity, but also how that opportunity emerges through generation.
Report-Model Training
Algorithm 2 gives a practical implementation of the decomposed two learning tasks in Section 4.1.
Figure 3 presents three representative business formats for applying LAMA in the single-winner setting: a hyperlink embedded in the generated response, a clickable response block, and a sponsored card displayed alongside the response.
Figure 3. Potential commercialization formats for LAMA. (a) Hyperlink: the winning advertiser’s brand name in the generated response is hyperlinked to its landing page; this is the format used in our experiments. (b) Clickable Block: the entire response block links to the advertiser’s landing page. (c) Sponsored Card: an advertisement card is displayed below the generated response, a format currently adopted by platforms such as ChatGPT Go, Google AI Overviews, and Baidu AI Smart Answers.
Proofs
Lemma 1 (Optimal soft Bellman recursion). Consider a finite-horizon token MDP with deterministic transition s t + 1 = [ s t , a t ] s_{t+1} = [s_t, a_t] s t + 1 = [ s t , a t ] , reference policy π r e f \pi_{\mathrm{ref}} π ref , and terminal reward r : S T → R r : S_T \to\mathbb{R} r : S T → R . For every state s s s , define the optimal KL-regularized continuation value
V ∗ ( s ) : = sup π ∈ Π ( ⋅ ∣ s ) E τ ∼ π ( ⋅ ∣ s ) [ r ( s T ) − β ∑ t = 0 T T − 1 log π ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] . V^*(s) := \sup_{\pi\in\Pi(\cdot\mid s)} \mathbb{E}_{\tau\sim\pi(\cdot\mid s)} \left[ r(s_T) - \beta\sum_{t=0}^{T_T-1} \log\frac{\pi(a_t \mid s_t)}{\pi_{\mathrm{ref}}(a_t \mid s_t)} \right]. V ∗ ( s ) := π ∈ Π ( ⋅ ∣ s ) sup E τ ∼ π ( ⋅ ∣ s ) [ r ( s T ) − β t = 0 ∑ T T − 1 log π ref ( a t ∣ s t ) π ( a t ∣ s t ) ] .
Assume π r e f ( a ∣ s ) > 0 \pi_{\mathrm{ref}}(a \mid s) > 0 π ref ( a ∣ s ) > 0 for every feasible action a a a at every non-terminal state s s s . Then V ∗ V^* V ∗ satisfies the terminal boundary condition V ∗ ( ℓ ) = r ( ℓ ) V^*(\ell) = r(\ell) V ∗ ( ℓ ) = r ( ℓ ) , ℓ ∈ S T \ell\in S_T ℓ ∈ S T , and the soft Bellman recursion
V ∗ ( s ) = β log ∑ a ∈ V π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) β ) , s ∉ S T . V^*(s) = \beta\log\sum_{a \in\mathcal{V}} \pi_{\mathrm{ref}}(a \mid s) \exp\left( \frac{V^*([s,a])}{\beta} \right), \quad s \notin S_T. V ∗ ( s ) = β log a ∈ V ∑ π ref ( a ∣ s ) exp ( β V ∗ ([ s , a ]) ) , s ∈ / S T .
Moreover, the optimal continuation policy is
π ∗ ( a ∣ s ) = π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) / β ) ∑ a ′ ∈ V π r e f ( a ′ ∣ s ) exp ( V ∗ ( [ s , a ′ ] ) / β ) . \pi^*(a \mid s) = \frac{\pi_{\mathrm{ref}}(a \mid s) \exp\left(V^*([s,a])/\beta\right)}{\sum_{a' \in\mathcal{V}} \pi_{\mathrm{ref}}(a' \mid s) \exp\left(V^*([s,a'])/\beta\right)}. π ∗ ( a ∣ s ) = ∑ a ′ ∈ V π ref ( a ′ ∣ s ) exp ( V ∗ ([ s , a ′ ]) / β ) π ref ( a ∣ s ) exp ( V ∗ ([ s , a ]) / β ) .
Proof. The terminal condition is immediate. If s = ℓ ∈ S T s = \ell\in S_T s = ℓ ∈ S T , the process has already terminated and no further KL penalty is incurred, so
V ∗ ( ℓ ) = r ( ℓ ) . V^*(\ell) = r(\ell). V ∗ ( ℓ ) = r ( ℓ ) .
Now fix a non-terminal state s s s . Any continuation policy can be decomposed into its first-step action distribution
μ ( a ) : = π ( a ∣ s ) ∈ Δ ( V ) \mu(a) := \pi(a \mid s) \in\Delta(\mathcal{V}) μ ( a ) := π ( a ∣ s ) ∈ Δ ( V )
and continuation policies after each child state [ s , a ] [s,a] [ s , a ] . Hence, by the principle of optimality,
V ∗ ( s ) = max μ ∈ Δ ( V ) { ∑ a ∈ V μ ( a ) V ∗ ( [ s , a ] ) − β ∑ a ∈ V μ ( a ) log μ ( a ) π r e f ( a ∣ s ) } . V^*(s) = \max_{\mu\in\Delta(\mathcal{V})} \left\{ \sum_{a \in\mathcal{V}} \mu(a)V^*([s,a]) - \beta\sum_{a \in\mathcal{V}} \mu(a) \log\frac{\mu(a)}{\pi_{\mathrm{ref}}(a \mid s)} \right\}. V ∗ ( s ) = μ ∈ Δ ( V ) max { a ∈ V ∑ μ ( a ) V ∗ ([ s , a ]) − β a ∈ V ∑ μ ( a ) log π ref ( a ∣ s ) μ ( a ) } .
This is a strictly concave optimization problem over the simplex. Introduce a Lagrange multiplier ξ \xi ξ for the constraint ∑ a ∈ V μ ( a ) = 1 \sum_{a \in\mathcal{V}} \mu(a) = 1 ∑ a ∈ V μ ( a ) = 1 . The Lagrangian is
L ( μ , ξ ) = ∑ a ∈ V μ ( a ) V ∗ ( [ s , a ] ) − β ∑ a ∈ V μ ( a ) log μ ( a ) π r e f ( a ∣ s ) + ξ ( ∑ a ∈ V μ ( a ) − 1 ) . (1) \mathcal{L}(\mu,\xi) = \sum_{a \in\mathcal{V}} \mu(a)V^*([s,a]) - \beta\sum_{a \in\mathcal{V}} \mu(a) \log\frac{\mu(a)}{\pi_{\mathrm{ref}}(a \mid s)}
+ \xi\left(\sum_{a \in\mathcal{V}} \mu(a) - 1\right). \tag*{(1)} L ( μ , ξ ) = a ∈ V ∑ μ ( a ) V ∗ ([ s , a ]) − β a ∈ V ∑ μ ( a ) log π ref ( a ∣ s ) μ ( a ) + ξ ( a ∈ V ∑ μ ( a ) − 1 ) . (1)
For every action a a a with μ ( a ) > 0 \mu(a)>0 μ ( a ) > 0 , the first-order condition gives
∂ L ∂ μ ( a ) = V ∗ ( [ s , a ] ) − β ( log μ ( a ) π r e f ( a ∣ s ) + 1 ) + ξ = 0. \frac{\partial\mathcal{L}}{\partial\mu(a)}=V^{*}([s,a])-\beta\left(\log\frac{\mu(a)}{\pi_{\mathrm{ref}}(a\mid s)}+1\right)+\xi=0. ∂ μ ( a ) ∂ L = V ∗ ([ s , a ]) − β ( log π ref ( a ∣ s ) μ ( a ) + 1 ) + ξ = 0.
Therefore
log μ ( a ) π r e f ( a ∣ s ) = V ∗ ( [ s , a ] ) + ξ − β β , \log\frac{\mu(a)}{\pi_{\mathrm{ref}}(a\mid s)}=\frac{V^{*}([s,a])+\xi-\beta}{\beta}, log π ref ( a ∣ s ) μ ( a ) = β V ∗ ([ s , a ]) + ξ − β ,
or equivalently
μ ( a ) = π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) β ) exp ( ξ − β β ) . \mu(a)=\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{V^{*}([s,a])}{\beta}\right)\exp\left(\frac{\xi-\beta}{\beta}\right). μ ( a ) = π ref ( a ∣ s ) exp ( β V ∗ ([ s , a ]) ) exp ( β ξ − β ) .
The final exponential factor is independent of a a a , so normalization gives
μ ∗ ( a ) = π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) / β ) ∑ a ′ ∈ V π r e f ( a ′ ∣ s ) exp ( V ∗ ( [ s , a ′ ] ) / β ) . \mu^{*}(a)=\frac{\pi_{\mathrm{ref}}(a\mid s)\exp\left(V^{*}([s,a])/\beta\right)}{\sum_{a'\in\mathcal{V}}\pi_{\mathrm{ref}}(a'\mid s)\exp\left(V^{*}([s,a'])/\beta\right)}. μ ∗ ( a ) = ∑ a ′ ∈ V π ref ( a ′ ∣ s ) exp ( V ∗ ([ s , a ′ ]) / β ) π ref ( a ∣ s ) exp ( V ∗ ([ s , a ]) / β ) .
This is the optimal continuation policy π ∗ ( a ∣ s ) \pi^{*}(a\mid s) π ∗ ( a ∣ s ) .
It remains to compute the optimal value. Let
Z ( s ) : = ∑ a ∈ V π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) β ) . Z(s):=\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{V^{*}([s,a])}{\beta}\right). Z ( s ) := a ∈ V ∑ π ref ( a ∣ s ) exp ( β V ∗ ([ s , a ]) ) .
From the expression for μ ∗ \mu^{*} μ ∗ ,
log μ ∗ ( a ) π r e f ( a ∣ s ) = V ∗ ( [ s , a ] ) β − log Z ( s ) . \log\frac{\mu^{*}(a)}{\pi_{\mathrm{ref}}(a\mid s)}=\frac{V^{*}([s,a])}{\beta}-\log Z(s). log π ref ( a ∣ s ) μ ∗ ( a ) = β V ∗ ([ s , a ]) − log Z ( s ) .
Substituting this identity into the one-step objective gives
V ∗ ( s ) = ∑ a μ ∗ ( a ) V ∗ ( [ s , a ] ) − β ∑ a μ ∗ ( a ) log μ ∗ ( a ) π r e f ( a ∣ s ) = ∑ a μ ∗ ( a ) V ∗ ( [ s , a ] ) − β ∑ a μ ∗ ( a ) ( V ∗ ( [ s , a ] ) β − log Z ( s ) ) = β log Z ( s ) . \begin{aligned}
V^{*}(s)&=\sum_a\mu^{*}(a)V^{*}([s,a])-\beta\sum_a\mu^{*}(a)\log\frac{\mu^{*}(a)}{\pi_{\mathrm{ref}}(a\mid s)}\\
&=\sum_a\mu^{*}(a)V^{*}([s,a])-\beta\sum_a\mu^{*}(a)\left(\frac{V^{*}([s,a])}{\beta}-\log Z(s)\right)\\
&=\beta\log Z(s).
\end{aligned} V ∗ ( s ) = a ∑ μ ∗ ( a ) V ∗ ([ s , a ]) − β a ∑ μ ∗ ( a ) log π ref ( a ∣ s ) μ ∗ ( a ) = a ∑ μ ∗ ( a ) V ∗ ([ s , a ]) − β a ∑ μ ∗ ( a ) ( β V ∗ ([ s , a ]) − log Z ( s ) ) = β log Z ( s ) .
Hence
V ∗ ( s ) = β log ∑ a ∈ V π r e f ( a ∣ s ) exp ( V ∗ ( [ s , a ] ) β ) , V^{*}(s)=\beta\log\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{V^{*}([s,a])}{\beta}\right), V ∗ ( s ) = β log a ∈ V ∑ π ref ( a ∣ s ) exp ( β V ∗ ([ s , a ]) ) ,
which proves the soft Bellman recursion. □
Lemma 2 (Convexity and gradient of weighted log-sum-exp). Let β > 0 \beta>0 β > 0 , let K \mathcal{K} K be a finite index set, and let { w k } k ∈ K \{w_k\}_{k\in\mathcal{K}} { w k } k ∈ K be nonnegative weights, not all zero. Define
F β ( x ) = β log ( ∑ k ∈ K w k exp ( x k β ) ) , x ∈ R K . F_\beta(x)=\beta\log\left(\sum_{k\in\mathcal{K}}w_k\exp\left(\frac{x_k}{\beta}\right)\right),\qquad x\in\mathbb{R}^{\mathcal{K}}. F β ( x ) = β log ( k ∈ K ∑ w k exp ( β x k ) ) , x ∈ R K .
Then F β F_\beta F β is convex on R K \mathbb{R}^{\mathcal{K}} R K . Moreover, F β F_\beta F β is differentiable and, for each k ∈ K k\in\mathcal{K} k ∈ K ,
∂ F β ( x ) ∂ x k = w k exp ( x k / β ) ∑ k ′ ∈ K w k ′ exp ( x k ′ / β ) . \frac{\partial F_\beta(x)}{\partial x_k}=\frac{w_k\exp(x_k/\beta)}{\sum_{k'\in\mathcal{K}}w_{k'}\exp(x_{k'}/\beta)}. ∂ x k ∂ F β ( x ) = ∑ k ′ ∈ K w k ′ exp ( x k ′ / β ) w k exp ( x k / β ) .
Proof. Let
Z β ( x ) = ∑ k ∈ K w k exp ( x k β ) , Z_\beta(x)=\sum_{k\in\mathcal{K}}w_k\exp\left(\frac{x_k}{\beta}\right), Z β ( x ) = k ∈ K ∑ w k exp ( β x k ) ,
and define
p k ( x ) = w k exp ( x k / β ) Z β ( x ) . p_k(x)=\frac{w_k\exp(x_k/\beta)}{Z_\beta(x)}. p k ( x ) = Z β ( x ) w k exp ( x k / β ) .
Since the weights are nonnegative and not all zero, Z β ( x ) > 0 Z_\beta(x)>0 Z β ( x ) > 0 for every x x x . Hence p ( x ) = ( p k ( x ) ) k ∈ K p(x)=(p_k(x))_{k\in\mathcal{K}} p ( x ) = ( p k ( x ) ) k ∈ K is a probability vector over K \mathcal{K} K . Direct differentiation gives
∂ F β ( x ) ∂ x k = β 1 Z β ( x ) w k 1 β exp ( x k β ) = p k ( x ) . \frac{\partial F_\beta(x)}{\partial x_k}=\beta\frac{1}{Z_\beta(x)}w_k\frac{1}{\beta}\exp\left(\frac{x_k}{\beta}\right)=p_k(x). ∂ x k ∂ F β ( x ) = β Z β ( x ) 1 w k β 1 exp ( β x k ) = p k ( x ) .
Therefore,
∇ F β ( x ) = p ( x ) . \nabla F_\beta(x)=p(x). ∇ F β ( x ) = p ( x ) .
We next compute the Hessian. For any k , k ′ ∈ K k,k'\in\mathcal{K} k , k ′ ∈ K ,
∂ p k ( x ) ∂ x k ′ = 1 β p k ( x ) ( 1 { k = k ′ } − p k ′ ( x ) ) . \frac{\partial p_k(x)}{\partial x_{k'}}=\frac{1}{\beta}p_k(x)\left(\mathbf{1}\{k=k'\}-p_{k'}(x)\right). ∂ x k ′ ∂ p k ( x ) = β 1 p k ( x ) ( 1 { k = k ′ } − p k ′ ( x ) ) .
Thus
∇ 2 F β ( x ) = 1 β ( diag ( p ( x ) ) − p ( x ) p ( x ) T ) . \nabla^2F_\beta(x)=\frac{1}{\beta}\left(\operatorname{diag}(p(x))-p(x)p(x)^{\mathsf{T}}\right). ∇ 2 F β ( x ) = β 1 ( diag ( p ( x )) − p ( x ) p ( x ) T ) .
For any vector v ∈ R K v\in\mathbb{R}^{\mathcal{K}} v ∈ R K ,
v T ∇ 2 F β ( x ) v = 1 β [ ∑ k ∈ K p k ( x ) v k 2 − ( ∑ k ∈ K p k ( x ) v k ) 2 ] . v^{\mathsf{T}}\nabla^2F_\beta(x)v=\frac{1}{\beta}\left[\sum_{k\in\mathcal{K}}p_k(x)v_k^2-\left(\sum_{k\in\mathcal{K}}p_k(x)v_k\right)^2\right]. v T ∇ 2 F β ( x ) v = β 1 k ∈ K ∑ p k ( x ) v k 2 − ( k ∈ K ∑ p k ( x ) v k ) 2 .
Table 2.
The term inside the brackets is the variance of the random variable that takes value v k v_k v k with probability p k ( x ) p_k(x) p k ( x ) . Hence it is nonnegative. Since β > 0 \beta>0 β > 0 , we have
v T ∇ 2 F β ( x ) v ≥ 0 v^\mathsf{T}\nabla^2F_\beta(x)v\ge0 v T ∇ 2 F β ( x ) v ≥ 0
for every v ∈ R K v\in\mathbb{R}^K v ∈ R K . Therefore,
∇ 2 F β ( x ) ⪰ 0 , \nabla^2F_\beta(x)\succeq0, ∇ 2 F β ( x ) ⪰ 0 ,
which implies that F β F_\beta F β is convex. □
Lemma 3 (Desirability Representation). Fix an initial context q q q . Let V ^ = ( V ^ i ( u ) ) i ∈ N , u ⪰ q \widehat{V}=(\widehat{V}_i(u))_{i\in\mathbb{N},\,u\succeq q} V = ( V i ( u ) ) i ∈ N , u ⪰ q be a globally Bellman-consistent report ledger on the subtree rooted at q q q . Define
z ^ i ( u ) : = exp ( V ^ i ( u ) β ) , z ‾ ( u ; V ^ ) : = ∑ j ∈ N z ^ j ( u ) . \widehat{z}_i(u):=\exp\left(\frac{\widehat{V}_i(u)}{\beta}\right),\qquad\overline{z}(u;\widehat{V}):=\sum_{j\in\mathbb{N}}\widehat{z}_j(u). z i ( u ) := exp ( β V i ( u ) ) , z ( u ; V ) := j ∈ N ∑ z j ( u ) .
Then the online decision rule is equivalently represented by
ρ i ( u ; V ^ ) = z ^ i ( u ) z ‾ ( u ; V ^ ) , x V ^ ( a ∣ u ) = π r e f ( a ∣ u ) z ‾ ( [ u , a ] ; V ^ ) z ‾ ( u ; V ^ ) \rho_i(u;\widehat{V})=\frac{\widehat{z}_i(u)}{\overline{z}(u;\widehat{V})},\qquad x_{\widehat{V}}(a\mid u)=\pi_{\mathrm{ref}}(a\mid u)\frac{\overline{z}([u,a];\widehat{V})}{\overline{z}(u;\widehat{V})} ρ i ( u ; V ) = z ( u ; V ) z i ( u ) , x V ( a ∣ u ) = π ref ( a ∣ u ) z ( u ; V ) z ([ u , a ] ; V )
for every reached non-terminal descendant u ⪰ q u\succeq q u ⪰ q . In particular, if the rollout terminates at ℓ ∈ S T \ell\in S_T ℓ ∈ S T , then the terminal ad allocation is
λ i ( ℓ ; V ^ ) = ρ i ( ℓ ; V ^ ) = z ^ i ( ℓ ) z ‾ ( ℓ ; V ^ ) . \lambda_i(\ell;\widehat{V})=\rho_i(\ell;\widehat{V})=\frac{\widehat{z}_i(\ell)}{\overline{z}(\ell;\widehat{V})}. λ i ( ℓ ; V ) = ρ i ( ℓ ; V ) = z ( ℓ ; V ) z i ( ℓ ) .
Proof. Global Bellman consistency implies that, for every non-terminal descendant u ⪰ q u\succeq q u ⪰ q ,
z ^ i ( u ) = ∑ a ∈ V π r e f ( a ∣ u ) z ^ i ( [ u , a ] ) . \widehat{z}_i(u)=\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid u)\widehat{z}_i([u,a]). z i ( u ) = a ∈ V ∑ π ref ( a ∣ u ) z i ([ u , a ]) .
Hence the advertiser-specific token rule can be rewritten as
π ^ i ( a ∣ u ) = π r e f ( a ∣ u ) z ^ i ( [ u , a ] ) z ^ i ( u ) . \widehat{\pi}_i(a\mid u)=\pi_{\mathrm{ref}}(a\mid u)\frac{\widehat{z}_i([u,a])}{\widehat{z}_i(u)}. π i ( a ∣ u ) = π ref ( a ∣ u ) z i ( u ) z i ([ u , a ]) .
We prove the representation by induction along the realized path. At the root, the initialization gives
ρ i ( q ; V ^ ) = z ^ i ( q ) z ‾ ( q ; V ^ ) . \rho_i(q;\widehat{V})=\frac{\widehat{z}_i(q)}{\overline{z}(q;\widehat{V})}. ρ i ( q ; V ) = z ( q ; V ) z i ( q ) .
Suppose the claim holds at a reached non-terminal state u u u . Then
x V ^ ( a ∣ u ) = ∑ i ∈ N ρ i ( u ; V ^ ) π ^ i ( a ∣ u ) = ∑ i ∈ N z ^ i ( u ) z ‾ ( u ; V ^ ) ⋅ π r e f ( a ∣ u ) z ^ i ( [ u , a ] ) z ^ i ( u ) = π r e f ( a ∣ u ) z ‾ ( [ u , a ] ; V ^ ) z ‾ ( u ; V ^ ) . \begin{aligned}
x_{\widehat{V}}(a\mid u)=\sum_{i\in\mathbb{N}}\rho_i(u;\widehat{V})\widehat{\pi}_i(a\mid u) \\
&=\sum_{i\in\mathbb{N}}\frac{\widehat{z}_i(u)}{\overline{z}(u;\widehat{V})}\cdot\pi_{\mathrm{ref}}(a\mid u)\frac{\widehat{z}_i([u,a])}{\widehat{z}_i(u)} \\
&=\pi_{\mathrm{ref}}(a\mid u)\frac{\overline{z}([u,a];\widehat{V})}{\overline{z}(u;\widehat{V})}.
\end{aligned} x V ( a ∣ u ) = i ∈ N ∑ ρ i ( u ; V ) π i ( a ∣ u ) = i ∈ N ∑ z ( u ; V ) z i ( u ) ⋅ π ref ( a ∣ u ) z i ( u ) z i ([ u , a ]) = π ref ( a ∣ u ) z ( u ; V ) z ([ u , a ] ; V ) .
The Bayesian posterior update then gives
ρ i ( [ u , a ] ; V ^ ) = ρ i ( u ; V ^ ) π ^ i ( a ∣ u ) x V ^ ( a ∣ u ) = z ^ i ( [ u , a ] ) z ‾ ( [ u , a ] ; V ^ ) . \begin{aligned}
\rho_i([u,a];\widehat{V})=\frac{\rho_i(u;\widehat{V})\widehat{\pi}_i(a\mid u)}{x_{\widehat{V}}(a\mid u)} \\
&=\frac{\widehat{z}_i([u,a])}{\overline{z}([u,a];\widehat{V})}.
\end{aligned} ρ i ([ u , a ] ; V ) = x V ( a ∣ u ) ρ i ( u ; V ) π i ( a ∣ u ) = z ([ u , a ] ; V ) z i ([ u , a ]) .
Thus the representation is preserved after every realized transition. The terminal expression follows by applying the same posterior representation at ℓ \ell ℓ . □
Lemma 4 (Joint Allocation Probability). For every globally Bellman-consistent report ledger V ^ \widehat{V} V , advertiser i ∈ N i\in\mathbb{N} i ∈ N , and terminal state ℓ ∈ L ( q ) \ell\in L(q) ℓ ∈ L ( q ) , the joint allocation mass assigned to advertiser i i i at terminal state ℓ \ell ℓ is
α i , ℓ ( V ^ ) : = Pr x V ^ ( S T = ℓ ∣ q ) λ i ( ℓ ; V ^ ) = P 0 ( ℓ ∣ q ) exp ( V ^ i ( ℓ ) / β ) z ‾ ( q ; V ^ ) . \alpha_{i,\ell}(\widehat{V}):=\Pr_{x_{\widehat{V}}}(S_T=\ell\mid q)\lambda_i(\ell;\widehat{V})=P_0(\ell\mid q)\frac{\exp(\widehat{V}_i(\ell)/\beta)}{\overline{z}(q;\widehat{V})}. α i , ℓ ( V ) := x V Pr ( S T = ℓ ∣ q ) λ i ( ℓ ; V ) = P 0 ( ℓ ∣ q ) z ( q ; V ) exp ( V i ( ℓ ) / β ) .
where P 0 ( ℓ ∣ q ) P_0(\ell\mid q) P 0 ( ℓ ∣ q ) is the probability of reaching ℓ \ell ℓ from q q q under the reference policy π r e f \pi_{\mathrm{ref}} π ref . Equivalently,
α i , ℓ ( V ^ ) = P 0 ( ℓ ∣ q ) exp ( V ^ i ( ℓ ) / β ) ∑ ℓ ′ ∈ L ( q ) P 0 ( ℓ ′ ∣ q ) ∑ j ∈ N exp ( V ^ j ( ℓ ′ ) / β ) . \alpha_{i,\ell}(\widehat{V}) =
\frac{P_0(\ell\mid q)\exp(\widehat{V}_i(\ell)/\beta)}
{\sum_{\ell' \in L(q)} P_0(\ell' \mid q)\sum_{j \in\mathcal{N}}\exp(\widehat{V}_j(\ell')/\beta)}. α i , ℓ ( V ) = ∑ ℓ ′ ∈ L ( q ) P 0 ( ℓ ′ ∣ q ) ∑ j ∈ N exp ( V j ( ℓ ′ ) / β ) P 0 ( ℓ ∣ q ) exp ( V i ( ℓ ) / β ) .
Proof. Let the unique path from q = s 0 q=s_0 q = s 0 to ℓ = s T \ell=s_T ℓ = s T be
s t + 1 = [ s t , a t ] , t = 0 , … , T − 1. s_{t+1}=[s_t,a_t],\quad t=0,\ldots,T-1. s t + 1 = [ s t , a t ] , t = 0 , … , T − 1.
By Lemma 3,
x V ^ ( a t ∣ s t ) = π r e f ( a t ∣ s t ) z ˉ ( s t + 1 ; V ^ ) z ˉ ( s t ; V ^ ) . x_{\widehat{V}}(a_t\mid s_t)=\pi_{\mathrm{ref}}(a_t\mid s_t)\frac{\bar{z}(s_{t+1};\widehat{V})}{\bar{z}(s_t;\widehat{V})}. x V ( a t ∣ s t ) = π ref ( a t ∣ s t ) z ˉ ( s t ; V ) z ˉ ( s t + 1 ; V ) .
Therefore,
Pr x V ^ ( s T = ℓ ∣ q ) = ∏ t = 0 T − 1 x V ^ ( a t ∣ s t ) = ∏ t = 0 T − 1 π r e f ( a t ∣ s t ) ∏ t = 0 T − 1 z ˉ ( s t + 1 ; V ^ ) z ˉ ( s t ; V ^ ) = P 0 ( ℓ ∣ q ) z ˉ ( ℓ ; V ^ ) z ˉ ( q ; V ^ ) . \begin{aligned}
\Pr_{x_{\widehat{V}}}(s_T=\ell\mid q)
&=\prod_{t=0}^{T-1}x_{\widehat{V}}(a_t\mid s_t)\\
&=\prod_{t=0}^{T-1}\pi_{\mathrm{ref}}(a_t\mid s_t)\prod_{t=0}^{T-1}\frac{\bar{z}(s_{t+1};\widehat{V})}{\bar{z}(s_t;\widehat{V})}\\
&=P_0(\ell\mid q)\frac{\bar{z}(\ell;\widehat{V})}{\bar{z}(q;\widehat{V})}.
\end{aligned} x V Pr ( s T = ℓ ∣ q ) = t = 0 ∏ T − 1 x V ( a t ∣ s t ) = t = 0 ∏ T − 1 π ref ( a t ∣ s t ) t = 0 ∏ T − 1 z ˉ ( s t ; V ) z ˉ ( s t + 1 ; V ) = P 0 ( ℓ ∣ q ) z ˉ ( q ; V ) z ˉ ( ℓ ; V ) .
The terminal allocation equals the final posterior:
λ i ( ℓ ; V ^ ) = ρ i ( ℓ ; V ^ ) = z ^ i ( ℓ ) z ˉ ( ℓ ; V ^ ) = exp ( V ^ i ( ℓ ) / β ) z ˉ ( ℓ ; V ^ ) . \lambda_i(\ell;\widehat{V})=\rho_i(\ell;\widehat{V})=\frac{\widehat{z}_i(\ell)}{\bar{z}(\ell;\widehat{V})}=\frac{\exp(\widehat{V}_i(\ell)/\beta)}{\bar{z}(\ell;\widehat{V})}. λ i ( ℓ ; V ) = ρ i ( ℓ ; V ) = z ˉ ( ℓ ; V ) z i ( ℓ ) = z ˉ ( ℓ ; V ) exp ( V i ( ℓ ) / β ) .
Multiplying the two identities gives
α i , ℓ ( V ^ ) = P 0 ( ℓ ∣ q ) exp ( V ^ i ( ℓ ) / β ) z ˉ ( q ; V ^ ) . \alpha_{i,\ell}(\widehat{V})=P_0(\ell\mid q)\frac{\exp(\widehat{V}_i(\ell)/\beta)}{\bar{z}(q;\widehat{V})}. α i , ℓ ( V ) = P 0 ( ℓ ∣ q ) z ˉ ( q ; V ) exp ( V i ( ℓ ) / β ) .
Finally, Bellman consistency implies the leaf representation
z ˉ ( q ; V ^ ) = ∑ j ∈ N z ^ j ( q ) = ∑ ℓ ′ ∈ L ( q ) P 0 ( ℓ ′ ∣ q ) ∑ j ∈ N exp ( V ^ j ( ℓ ′ ) / β ) , \bar{z}(q;\widehat{V})=\sum_{j\in\mathcal{N}}\widehat{z}_j(q)=\sum_{\ell'\in L(q)}P_0(\ell'\mid q)\sum_{j\in\mathcal{N}}\exp(\widehat{V}_j(\ell')/\beta), z ˉ ( q ; V ) = j ∈ N ∑ z j ( q ) = ℓ ′ ∈ L ( q ) ∑ P 0 ( ℓ ′ ∣ q ) j ∈ N ∑ exp ( V j ( ℓ ′ ) / β ) ,
which gives the equivalent normalized form. □
Lemma 5 (Gradient Representation). Define the soft potential Φ q ( V ^ ) : = β log z ˉ ( q ; V ^ ) \Phi_q(\widehat{V}):=\beta\log\bar{z}(q;\widehat{V}) Φ q ( V ) := β log z ˉ ( q ; V ) . Then the joint allocation rule is the gradient of this potential with respect to terminal reported values: ∇ Φ q ( V ^ ) = α ( V ^ ) \nabla\Phi_q(\widehat{V})=\alpha(\widehat{V}) ∇ Φ q ( V ) = α ( V ) , or equivalently, for every i ∈ N i\in\mathcal{N} i ∈ N and ℓ ∈ L ( q ) \ell\in L(q) ℓ ∈ L ( q ) , ∂ Φ q ( V ^ ) ∂ V ^ i ( ℓ ) = α i , ℓ ( V ^ ) \frac{\partial\Phi_q(\widehat{V})}{\partial\widehat{V}_i(\ell)}=\alpha_{i,\ell}(\widehat{V}) ∂ V i ( ℓ ) ∂ Φ q ( V ) = α i , ℓ ( V ) . Consequently, α \alpha α is cyclically monotone.
Proof. By the leaf representation of the induced desirability functions,
z ˉ ( q ; V ^ ) = ∑ j ∈ N z ^ j ( q ) = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) ∑ j ∈ N exp ( V ^ j ( ℓ ) β ) . \bar{z}(q;\widehat{V})=\sum_{j\in\mathcal{N}}\widehat{z}_j(q)
=\sum_{\ell\in L(q)}P_0(\ell\mid q)\sum_{j\in\mathcal{N}}\exp\left(\frac{\widehat{V}_j(\ell)}{\beta}\right). z ˉ ( q ; V ) = j ∈ N ∑ z j ( q ) = ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) j ∈ N ∑ exp ( β V j ( ℓ ) ) .
Thus
Φ q ( V ^ ) = β log [ ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) ∑ j ∈ N exp ( V ^ j ( ℓ ) β ) ] . \Phi_q(\widehat{V})=\beta\log\left[\sum_{\ell\in L(q)}P_0(\ell\mid q)\sum_{j\in\mathcal{N}}\exp\left(\frac{\widehat{V}_j(\ell)}{\beta}\right)\right]. Φ q ( V ) = β log ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) j ∈ N ∑ exp ( β V j ( ℓ ) ) .
Differentiating directly with respect to V ^ i ( ℓ ) \widehat{V}_i(\ell) V i ( ℓ ) gives
∂ Φ q ( V ^ ) ∂ V ^ i ( ℓ ) = β P 0 ( ℓ ∣ q ) 1 β exp ( V ^ i ( ℓ ) / β ) z ˉ ( q ; V ^ ) = P 0 ( ℓ ∣ q ) exp ( V ^ i ( ℓ ) / β ) z ˉ ( q ; V ^ ) = α i , ℓ ( V ^ ) , \begin{aligned}
\frac{\partial\Phi_q(\widehat{V})}{\partial\widehat{V}_i(\ell)}
=\beta\frac{P_0(\ell\mid q)\frac{1}{\beta}\exp(\widehat{V}_i(\ell)/\beta)}{\bar{z}(q;\widehat{V})} \\
&=P_0(\ell\mid q)\frac{\exp(\widehat{V}_i(\ell)/\beta)}{\bar{z}(q;\widehat{V})} \\
&=\alpha_{i,\ell}(\widehat{V}),
\end{aligned} ∂ V i ( ℓ ) ∂ Φ q ( V ) = β z ˉ ( q ; V ) P 0 ( ℓ ∣ q ) β 1 exp ( V i ( ℓ ) / β ) = P 0 ( ℓ ∣ q ) z ˉ ( q ; V ) exp ( V i ( ℓ ) / β ) = α i , ℓ ( V ) ,
where the last equality follows from Lemma 4. Finally, Φ q \Phi_q Φ q is a positive scalar multiple of a log-sum-exp function, and by Lemma 2, it is therefore convex. Since α = ∇ Φ q \alpha=\nabla\Phi_q α = ∇ Φ q , the allocation rule α \alpha α is cyclically monotone. □
Proposition 2 (Direct implementability of LAMA). For any prefix q q q , the direct latent-mixture allocation rule induced by globally Bellman-consistent reports is implementable with quasi-linear payments. Therefore truthful reporting V ^ i = V i ∗ \widehat{V}_i=V_i^* V i = V i ∗ is DSIC and IR.
Proof of Proposition 2. Fix advertiser i i i , true type r i r_i r i , opponent reports V ^ − i \widehat{V}_{-i} V − i , and an arbitrary globally Bellman-consistent report V ^ i \widehat{V}_i V i . Define the outside-option offset
Φ − i , q 0 ( V ^ − i ) : = β log ( 1 + ∑ j ≠ i z ^ j ( q ) ) . \Phi^0_{-i,q}(\widehat{V}_{-i}):=\beta\log\left(1+\sum_{j\ne i}\widehat{z}_j(q)\right). Φ − i , q 0 ( V − i ) := β log 1 + j = i ∑ z j ( q ) .
The direct payment corresponding to the pathwise LAMA payment rule is the terminal-settled charge
p i ( ℓ ; V ^ ) : = λ i ( ℓ ; V ^ ) V ^ i ( ℓ ) − Φ q ( V ^ ) + Φ − i , q 0 ( V ^ − i ) . p_i(\ell;\widehat{V}):=\lambda_i(\ell;\widehat{V})\widehat{V}_i(\ell)-\Phi_q(\widehat{V})+\Phi^0_{-i,q}(\widehat{V}_{-i}). p i ( ℓ ; V ) := λ i ( ℓ ; V ) V i ( ℓ ) − Φ q ( V ) + Φ − i , q 0 ( V − i ) .
Indeed, the sequential entry fee equals ρ i ( q ; V ^ ) V ^ i ( q ) − Φ q ( V ^ ) + Φ − i , q 0 ( V ^ − i ) \rho_i(q;\widehat{V})\widehat{V}_i(q)-\Phi_q(\widehat{V})+\Phi^0_{-i,q}(\widehat{V}_{-i}) ρ i ( q ; V ) V i ( q ) − Φ q ( V ) + Φ − i , q 0 ( V − i ) , while the subsequent continuation-value charges telescope to λ i ( ℓ ; V ^ ) V ^ i ( ℓ ) − λ i ( q ; V ^ ) V ^ i ( q ) \lambda_i(\ell;\widehat{V})\widehat{V}_i(\ell)-\lambda_i(q;\widehat{V})\widehat{V}_i(q) λ i ( ℓ ; V ) V i ( ℓ ) − λ i ( q ; V ) V i ( q ) .
Advertiser i i i ’s expected utility under report V ^ i \widehat{V}_i V i is therefore
U i ( q ; r i , V ^ i , V ^ − i ) = ∑ ℓ ∈ L ( q ) Pr x V ^ ( s T = ℓ ∣ q ) λ i ( ℓ ; V ^ ) ( r i ( ℓ ) − V ^ i ( ℓ ) ) + Φ q ( V ^ ) − Φ − i , q 0 ( V ^ − i ) = ∑ ℓ ∈ L ( q ) α i , ℓ ( V ^ ) ( r i ( ℓ ) − V ^ i ( ℓ ) ) + Φ q ( V ^ ) − Φ − i , q 0 ( V ^ − i ) . \begin{aligned}
U_i(q;r_i,\widehat{V}_i,\widehat{V}_{-i})
=\sum_{\ell\in L(q)}\Pr_{x_{\widehat{V}}}(s_T=\ell\mid q)\lambda_i(\ell;\widehat{V})(r_i(\ell)-\widehat{V}_i(\ell))+\Phi_q(\widehat{V})-\Phi^0_{-i,q}(\widehat{V}_{-i}) \\
&=\sum_{\ell\in L(q)}\alpha_{i,\ell}(\widehat{V})(r_i(\ell)-\widehat{V}_i(\ell))+\Phi_q(\widehat{V})-\Phi^0_{-i,q}(\widehat{V}_{-i}).
\end{aligned} U i ( q ; r i , V i , V − i ) = ℓ ∈ L ( q ) ∑ x V Pr ( s T = ℓ ∣ q ) λ i ( ℓ ; V ) ( r i ( ℓ ) − V i ( ℓ )) + Φ q ( V ) − Φ − i , q 0 ( V − i ) = ℓ ∈ L ( q ) ∑ α i , ℓ ( V ) ( r i ( ℓ ) − V i ( ℓ )) + Φ q ( V ) − Φ − i , q 0 ( V − i ) .
By Lemma 5,
α i , ℓ ( V ^ ) = ∂ Φ q ( V ^ ) ∂ V ^ i ( ℓ ) . \alpha_{i,\ell}(\widehat{V})=\frac{\partial\Phi_q(\widehat{V})}{\partial\widehat{V}_i(\ell)}. α i , ℓ ( V ) = ∂ V i ( ℓ ) ∂ Φ q ( V ) .
Hence, with the inner product taken over terminal states L ( q ) L(q) L ( q ) ,
U i ( q ; r i , V ^ i , V ^ − i ) = Φ q ( V ^ i , V ^ − i ) + ⟨ ∇ i Φ q ( V ^ i , V ^ − i ) , r i − V ^ i ∣ L ( q ) ⟩ − Φ − i , q 0 ( V ^ − i ) . U_i(q;r_i,\widehat{V}_i,\widehat{V}_{-i})=\Phi_q(\widehat{V}_i,\widehat{V}_{-i})+\left\langle\nabla_i\Phi_q(\widehat{V}_i,\widehat{V}_{-i}),r_i-\widehat{V}_i|_{L(q)}\right\rangle-\Phi^0_{-i,q}(\widehat{V}_{-i}). U i ( q ; r i , V i , V − i ) = Φ q ( V i , V − i ) + ⟨ ∇ i Φ q ( V i , V − i ) , r i − V i ∣ L ( q ) ⟩ − Φ − i , q 0 ( V − i ) .
Since Φ q \Phi_q Φ q is convex in advertiser i i i ’s terminal reported values when V ^ − i \widehat{V}_{-i} V − i is fixed, and since the truthful Bellman-consistent report V i ∗ V_i^* V i ∗ satisfies V i ∗ ( ℓ ) = r i ( ℓ ) V_i^*(\ell)=r_i(\ell) V i ∗ ( ℓ ) = r i ( ℓ ) for every ℓ ∈ L ( q ) \ell\in L(q) ℓ ∈ L ( q ) ,
Φ q ( V i ∗ , V ^ − i ) ≥ Φ q ( V ^ i , V ^ − i ) + ⟨ ∇ i Φ q ( V ^ i , V ^ − i ) , r i − V ^ i ∣ L ( q ) ⟩ . \Phi_q(V_i^*,\widehat{V}_{-i})\ge\Phi_q(\widehat{V}_i,\widehat{V}_{-i})+\left\langle\nabla_i\Phi_q(\widehat{V}_i,\widehat{V}_{-i}),r_i-\widehat{V}_i|_{L(q)}\right\rangle. Φ q ( V i ∗ , V − i ) ≥ Φ q ( V i , V − i ) + ⟨ ∇ i Φ q ( V i , V − i ) , r i − V i ∣ L ( q ) ⟩ .
Therefore,
U i ( q ; r i , V ^ i , V ^ − i ) ≤ Φ q ( V i ∗ , V ^ − i ) − Φ − i , q 0 ( V ^ − i ) . U_i(q;r_i,\widehat{V}_i,\widehat{V}_{-i})\le\Phi_q(V_i^*,\widehat{V}_{-i})-\Phi^0_{-i,q}(\widehat{V}_{-i}). U i ( q ; r i , V i , V − i ) ≤ Φ q ( V i ∗ , V − i ) − Φ − i , q 0 ( V − i ) .
When V ^ i = V i ∗ \widehat{V}_i=V_i^* V i = V i ∗ , the inequality is tight, so truthful reporting is a dominant strategy.
The same argument also gives strict dominance under the full-support conditions. Since ∣ N ∣ ≥ 2 |\mathcal{N}|\ge2 ∣ N ∣ ≥ 2 and P 0 ( ℓ ∣ q ) > 0 P_0(\ell\mid q)>0 P 0 ( ℓ ∣ q ) > 0 for every ℓ ∈ L ( q ) \ell\in L(q) ℓ ∈ L ( q ) . Fixing V ^ − i \widehat{V}_{-i} V − i , write
B − i ( V ^ − i ) : = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) ∑ j ≠ i exp ( V ^ j ( ℓ ) / β ) . B_{-i}(\widehat{V}_{-i}):=\sum_{\ell\in L(q)}P_0(\ell\mid q)\sum_{j\ne i}\exp(\widehat{V}_j(\ell)/\beta). B − i ( V − i ) := ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) j = i ∑ exp ( V j ( ℓ ) / β ) .
Then B − i ( V ^ − i ) > 0 B_{-i}(\widehat{V}_{-i})>0 B − i ( V − i ) > 0 , and as a function of advertiser i i i ’s terminal report y = ( y ℓ ) ℓ ∈ L ( q ) y=(y_\ell)_{\ell\in L(q)} y = ( y ℓ ) ℓ ∈ L ( q ) ,
Φ q ( y , V ^ − i ) = β log ( B − i ( V ^ − i ) + ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( y ℓ / β ) ) . \Phi_q(y,\widehat{V}_{-i})=\beta\log\left(B_{-i}(\widehat{V}_{-i})+\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp(y_\ell/\beta)\right). Φ q ( y , V − i ) = β log B − i ( V − i ) + ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) exp ( y ℓ / β ) .
Following the proof of Lemma 2, its Hessian is 1 β ( diag ( p ) − p p ⊤ ) \frac{1}{\beta}\left(\operatorname{diag}(p)-pp^\top\right) β 1 ( diag ( p ) − p p ⊤ ) , where
p ℓ = P 0 ( ℓ ∣ q ) exp ( y ℓ / β ) B − i ( V ^ − i ) + ∑ ℓ ′ P 0 ( ℓ ′ ∣ q ) exp ( y ℓ ′ / β ) . p_\ell=\frac{P_0(\ell\mid q)\exp(y_\ell/\beta)}{B_{-i}(\widehat{V}_{-i})+\sum_{\ell'}P_0(\ell'\mid q)\exp(y_{\ell'}/\beta)}. p ℓ = B − i ( V − i ) + ∑ ℓ ′ P 0 ( ℓ ′ ∣ q ) exp ( y ℓ ′ / β ) P 0 ( ℓ ∣ q ) exp ( y ℓ / β ) .
For any non-zero vector z = ( z ℓ ) ℓ ∈ L ( q ) z=(z_\ell)_{\ell\in L(q)} z = ( z ℓ ) ℓ ∈ L ( q ) , we have
z ⊤ ( diag ( p ) − p p ⊤ ) z = ∑ ℓ p ℓ z ℓ 2 − ( ∑ ℓ p ℓ z ℓ ) 2 . z^\top\left(\operatorname{diag}(p)-pp^\top\right)z=\sum_\ell p_\ell z_\ell^2-\left(\sum_\ell p_\ell z_\ell\right)^2. z ⊤ ( diag ( p ) − p p ⊤ ) z = ℓ ∑ p ℓ z ℓ 2 − ( ℓ ∑ p ℓ z ℓ ) 2 .
Let s = ∑ ℓ p ℓ < 1 s=\sum_\ell p_\ell<1 s = ∑ ℓ p ℓ < 1 , p ˉ ℓ = p ℓ / s \bar{p}_\ell=p_\ell/s p ˉ ℓ = p ℓ / s , then
∑ ℓ p ℓ z ℓ 2 − ( ∑ ℓ p ℓ z ℓ ) 2 = s ∑ ℓ p ˉ ℓ z ℓ 2 − s 2 ( ∑ ℓ p ˉ ℓ z ℓ ) 2 = s Var p ˉ ( z ) + s ( 1 − s ) ( E p ˉ [ z ] ) 2 > 0. \sum_\ell p_\ell z_\ell^2-\left(\sum_\ell p_\ell z_\ell\right)^2
=s\sum_\ell\bar{p}_\ell z_\ell^2-s^2\left(\sum_\ell\bar{p}_\ell z_\ell\right)^2
=s\operatorname{Var}_{\bar{p}}(z)+s(1-s)\left(\mathbb{E}_{\bar{p}}[z]\right)^2>0. ℓ ∑ p ℓ z ℓ 2 − ( ℓ ∑ p ℓ z ℓ ) 2 = s ℓ ∑ p ˉ ℓ z ℓ 2 − s 2 ( ℓ ∑ p ˉ ℓ z ℓ ) 2 = s Var p ˉ ( z ) + s ( 1 − s ) ( E p ˉ [ z ] ) 2 > 0.
Thus this Hessian is positive definite. Hence the convexity inequality above is strict whenever V ^ i ∣ L ( q ) ≠ r i \widehat{V}_{i|L(q)}\ne r_i V i ∣ L ( q ) = r i . Since global Bellman consistency uniquely determines V ∗ V^* V ∗ from terminal values, truthful reporting strictly dominates every distinct globally Bellman-consistent report.
Finally, truthful utility is
U i ( q ; r i , V i ∗ , V ^ − i ) = Φ q ( V i ∗ , V ^ − i ) − Φ − i , q 0 ( V ^ − i ) . U_i(q;r_i,V_i^*,\widehat{V}_{-i})=\Phi_q(V_i^*,\widehat{V}_{-i})-\Phi^0_{-i,q}(\widehat{V}_{-i}). U i ( q ; r i , V i ∗ , V − i ) = Φ q ( V i ∗ , V − i ) − Φ − i , q 0 ( V − i ) .
Because r i ( ℓ ) ≥ 0 r_i(\ell)\ge0 r i ( ℓ ) ≥ 0 , Bellman consistency gives
z i ∗ ( q ) = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) ≥ 1. z_i^*(q)=\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp(r_i(\ell)/\beta)\ge1. z i ∗ ( q ) = ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) ≥ 1.
Thus
z ˉ ( q ; V i ∗ , V ^ − i ) = z i ∗ ( q ) + ∑ j ≠ i z ^ j ( q ) ≥ 1 + ∑ j ≠ i z ^ j ( q ) . \bar{z}(q;V_i^*,\widehat{V}_{-i})=z_i^*(q)+\sum_{j\ne i}\widehat{z}_j(q)\ge1+\sum_{j\ne i}\widehat{z}_j(q). z ˉ ( q ; V i ∗ , V − i ) = z i ∗ ( q ) + j = i ∑ z j ( q ) ≥ 1 + j = i ∑ z j ( q ) .
Since β log ( ⋅ ) \beta\log(\cdot) β log ( ⋅ ) is increasing,
Φ q ( V i ∗ , V ^ − i ) ≥ Φ − i , q 0 ( V ^ − i ) , \Phi_q(V_i^*,\widehat{V}_{-i})\ge\Phi^0_{-i,q}(\widehat{V}_{-i}), Φ q ( V i ∗ , V − i ) ≥ Φ − i , q 0 ( V − i ) ,
and truthful expected utility is nonnegative. □
Lemma 6 (Subtree patching). Fix a reachable platform history h h h with current non-terminal state s s s , after advertiser i i i has reported truthfully before h h h . Every feasible continuation deviation σ i ′ \sigma_i' σ i ′ from h h h can be embedded in a globally Bellman-consistent direct report V ~ i \widetilde{V}_i V i on the full tree rooted at q q q : the report V ~ i \widetilde{V}_i V i agrees with V i ∗ V_i^* V i ∗ outside the subtree rooted at s s s and reproduces σ i ′ \sigma_i' σ i ′ inside that subtree. Holding opponents fixed, conditional on h h h , the patched report induces the same continuation token distribution, terminal allocation, and future payments as σ i ′ \sigma_i' σ i ′ .
Proof of Lemma 6. For every non-terminal u ⪰ s u\succeq s u ⪰ s , let V ~ i σ i ′ ( [ u , a ] ) \widetilde{V}_i^{\sigma_i'}([u,a]) V i σ i ′ ([ u , a ]) be the a a a -component submitted by σ i ′ \sigma_i' σ i ′ at u u u , and define the value at s s s by its soft Bellman aggregate. Feasibility implies that these values are Bellman-consistent on the subtree rooted at s s s . If s ≠ q s\ne q s = q , it also implies V ~ i σ i ′ ( s ) = V i ∗ ( s ) \widetilde{V}_i^{\sigma_i'}(s)=V_i^*(s) V i σ i ′ ( s ) = V i ∗ ( s ) , because the latter is the value already stored in the ledger after the truthful prefix.
Now patch this subtree into the truthful direct report:
V ~ i ( u ) : = { V ~ i σ i ′ ( u ) , u ⪰ s , V i ∗ ( u ) , u ⋡ s . \widetilde{V}_i(u):=
\begin{cases}
\widetilde{V}_i^{\sigma_i'}(u), & u\succeq s,\\
V_i^*(u), & u\nsucceq s.
\end{cases} V i ( u ) := { V i σ i ′ ( u ) , V i ∗ ( u ) , u ⪰ s , u ⋡ s .
Lemma 1 gives Bellman consistency of V i ∗ V_i^* V i ∗ . When s ≠ q s\ne q s = q , the equality at s s s leaves every ancestor’s Bellman equation unchanged; when s = q s=q s = q , there are no ancestors. Feasibility gives every Bellman equation within the patched subtree. Hence V ~ i \widetilde{V}_i V i is globally Bellman-consistent on the tree rooted at q q q .
Before reaching s s s , the patched and truthful ledgers coincide. From s s s onward, the patched child values are exactly those submitted by σ i ′ \sigma_i' σ i ′ . Therefore, against fixed opponent reports, the posterior at h h h is unchanged, and Lemma 3 gives the same continuation token rule and terminal allocation. The instantaneous payment rule then gives the same payment on every continuation transition. This proves the claimed conditional equivalence. □
Proof of Theorem 1. Lemma 1 first shows that the truthful child-value reports are feasible. Fix advertiser i i i , opponents’ feasible strategies σ − i \sigma_{-i} σ − i , and a reachable history h h h with current state s s s , after i i i has reported truthfully before h h h . Recursively recording the child values submitted by each opponent gives a globally Bellman-consistent direct ledger V ^ − i \widehat{V}_{-i} V − i . By Lemma 3 and the telescoping payment rule, the sequential mechanism is pathwise equivalent to the direct implementation under these ledgers.
Let σ i ′ \sigma_i' σ i ′ be any feasible continuation deviation. By Lemma 6, it induces a globally Bellman-consistent direct report V ~ i \widetilde{V}_i V i that differs from V i ∗ V_i^* V i ∗ only on the subtree rooted at s s s . Proposition 2 therefore implies
0 ≤ U i ( q ; r i , V i ∗ , V ~ − i ) − U i ( q ; r i , V ~ i , V ~ − i ) = Pr ( h ) [ U i Γ ( h ; r i , σ i t r , σ − i ; r − i ) − U i Γ ( h ; r i , σ i ′ , σ − i ; r − i ) ] . \begin{aligned}
0\le U_i(q;r_i,V_i^*,\widetilde{V}_{-i})-U_i(q;r_i,\widetilde{V}_i,\widetilde{V}_{-i}) \\
&=\Pr(h)\left[U_i^\Gamma(h;r_i,\sigma_i^{\mathrm{tr}},\sigma_{-i};r_{-i})-U_i^\Gamma(h;r_i,\sigma_i',\sigma_{-i};r_{-i})\right].
\end{aligned} 0 ≤ U i ( q ; r i , V i ∗ , V − i ) − U i ( q ; r i , V i , V − i ) = Pr ( h ) [ U i Γ ( h ; r i , σ i tr , σ − i ; r − i ) − U i Γ ( h ; r i , σ i ′ , σ − i ; r − i ) ] .
Here Pr ( h ) \Pr(h) Pr ( h ) is the common probability of reaching h h h . The equality holds because the two direct reports coincide before h h h and on every branch not passing through s s s ; past payments cancel, and conditional on h h h the patched report reproduces σ i ′ \sigma_i' σ i ′ . Since h h h is reachable, Pr ( h ) > 0 \Pr(h)>0 Pr ( h ) > 0 , so the bracketed continuation-utility difference is nonnegative. This proves Markov DSIC.
Finally, from the initial query, the truthful sequential outcome and payments are pathwise equivalent to the direct report ( V i ∗ , V ^ − i ) (V_i^*,\widehat{V}_{-i}) ( V i ∗ , V − i ) . The IR part of Proposition 2 therefore gives U i Γ ( q ; r i , σ i t r , σ − i ; r − i ) ≥ 0 U_i^\Gamma(q;r_i,\sigma_i^{\mathrm{tr}},\sigma_{-i};r_{-i})\ge0 U i Γ ( q ; r i , σ i tr , σ − i ; r − i ) ≥ 0 , proving IR. □
Proof of Theorem 2. For every terminal state ℓ ∈ L ( q ) \ell\in L(q) ℓ ∈ L ( q ) , define
G β ( ℓ ) : = β log ( ∑ i ∈ N exp ( r i ( ℓ ) β ) ) . G_\beta(\ell):=\beta\log\left(\sum_{i\in\mathcal{N}}\exp\left(\frac{r_i(\ell)}{\beta}\right)\right). G β ( ℓ ) := β log ( i ∈ N ∑ exp ( β r i ( ℓ ) ) ) .
We first characterize the terminal allocation induced by LAMA. Under truthful reporting, the terminal boundary condition of each advertiser-specific value function is
V i ∗ ( ℓ ) = r i ( ℓ ) . V_i^*(\ell)=r_i(\ell). V i ∗ ( ℓ ) = r i ( ℓ ) .
Therefore, by Lemma 3, the terminal posterior, and hence the terminal allocation, is
λ i β ( ℓ ) = exp ( V i ∗ ( ℓ ) / β ) ∑ j ∈ N exp ( V j ∗ ( ℓ ) / β ) = exp ( r i ( ℓ ) / β ) ∑ j ∈ N exp ( r j ( ℓ ) / β ) . \lambda_i^\beta(\ell)=\frac{\exp(V_i^*(\ell)/\beta)}{\sum_{j\in\mathcal{N}}\exp(V_j^*(\ell)/\beta)}=\frac{\exp(r_i(\ell)/\beta)}{\sum_{j\in\mathcal{N}}\exp(r_j(\ell)/\beta)}. λ i β ( ℓ ) = ∑ j ∈ N exp ( V j ∗ ( ℓ ) / β ) exp ( V i ∗ ( ℓ ) / β ) = ∑ j ∈ N exp ( r j ( ℓ ) / β ) exp ( r i ( ℓ ) / β ) .
This allocation is precisely the optimizer of the entropy-regularized terminal allocation problem. Indeed, relative to the uniform distribution on N \mathcal{N} N ,
D K L ( λ ∥ U ( N ) ) = log ∣ N ∣ − H ( λ ) , D_{\mathrm{KL}}(\lambda\mathbin\Vert U(\mathcal{N}))=\log|\mathcal{N}|-\mathcal{H}(\lambda), D KL ( λ ∥ U ( N )) = log ∣ N ∣ − H ( λ ) ,
and hence
∑ i ∈ N λ i r i ( ℓ ) + β H ( λ ) = ∑ i ∈ N λ i r i ( ℓ ) − β D K L ( λ ∥ U ( N ) ) + β log ∣ N ∣ . \sum_{i\in\mathcal{N}}\lambda_i r_i(\ell)+\beta\mathcal{H}(\lambda)=\sum_{i\in\mathcal{N}}\lambda_i r_i(\ell)-\beta D_{\mathrm{KL}}(\lambda\mathbin\Vert U(\mathcal{N}))+\beta\log|\mathcal{N}|. i ∈ N ∑ λ i r i ( ℓ ) + β H ( λ ) = i ∈ N ∑ λ i r i ( ℓ ) − β D KL ( λ ∥ U ( N )) + β log ∣ N ∣.
Thus the entropy-regularized objective differs by the constant β log ∣ N ∣ \beta\log|\mathcal{N}| β log ∣ N ∣ from the KL-regularized one-step problem in Lemma 1, with action set N \mathcal{N} N and terminal reward r i ( ℓ ) r_i(\ell) r i ( ℓ ) for action i i i . Applying the lemma and adding the same constant to its optimal value gives
G β ( ℓ ) = max λ ∈ Δ ( N ) { ∑ i ∈ N λ i r i ( ℓ ) + β H ( λ ) } , (2) G_\beta(\ell)=\max_{\lambda\in\Delta(\mathcal{N})}\left\{\sum_{i\in\mathcal{N}}\lambda_i r_i(\ell)+\beta\mathcal{H}(\lambda)\right\}, \tag*{(2)} G β ( ℓ ) = λ ∈ Δ ( N ) max { i ∈ N ∑ λ i r i ( ℓ ) + β H ( λ ) } , (2)
G β ( ℓ ) = ∑ i ∈ N λ i β ( ℓ ) r i ( ℓ ) + β H ( λ β ( ℓ ) ) . G_\beta(\ell)=\sum_{i\in\mathcal{N}}\lambda_i^\beta(\ell)r_i(\ell)+\beta\mathcal{H}(\lambda^\beta(\ell)). G β ( ℓ ) = i ∈ N ∑ λ i β ( ℓ ) r i ( ℓ ) + β H ( λ β ( ℓ )) .
The maximizer is unique because Shannon entropy is strictly concave on the simplex.
We next characterize the token policy. Define
W β ( u ) : = β log ( ∑ i ∈ N exp ( V i ∗ ( u ) β ) ) . W_\beta(u):=\beta\log\left(\sum_{i\in\mathcal{N}}\exp\left(\frac{V_i^*(u)}{\beta}\right)\right). W β ( u ) := β log ( i ∈ N ∑ exp ( β V i ∗ ( u ) ) ) .
At a terminal state ℓ \ell ℓ , the terminal boundary condition gives
W β ( ℓ ) = G β ( ℓ ) . W_\beta(\ell)=G_\beta(\ell). W β ( ℓ ) = G β ( ℓ ) .
Moreover, Lemma 1 implies, at every non-terminal state u u u ,
exp ( W β ( u ) β ) = ∑ a ∈ V π r e f ( a ∣ u ) exp ( W β ( [ u , a ] ) β ) . (3) \exp\left(\frac{W_\beta(u)}{\beta}\right)=\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid u)\exp\left(\frac{W_\beta([u,a])}{\beta}\right). \tag*{(3)} exp ( β W β ( u ) ) = a ∈ V ∑ π ref ( a ∣ u ) exp ( β W β ([ u , a ]) ) . (3)
Indeed, this follows by exponentiating each advertiser-specific soft Bellman recursion and then summing over advertisers. By Lemma 3, the truthful LAMA token policy is
x β ( a ∣ u ) = π r e f ( a ∣ u ) exp ( W β ( [ u , a ] ) / β ) ∑ a ′ ∈ V π r e f ( a ′ ∣ u ) exp ( W β ( [ u , a ′ ] ) / β ) . x^\beta(a\mid u)=\frac{\pi_{\mathrm{ref}}(a\mid u)\exp(W_\beta([u,a])/\beta)}{\sum_{a'\in\mathcal{V}}\pi_{\mathrm{ref}}(a'\mid u)\exp(W_\beta([u,a'])/\beta)}. x β ( a ∣ u ) = ∑ a ′ ∈ V π ref ( a ′ ∣ u ) exp ( W β ([ u , a ′ ]) / β ) π ref ( a ∣ u ) exp ( W β ([ u , a ]) / β ) .
Together with the terminal boundary condition, (3) identifies W β W_\beta W β as the optimal soft value function for terminal reward G β G_\beta G β . Hence Lemma 1 gives
x β ∈ arg max x E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] . (4) x^\beta\in\arg\max_x\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[G_\beta(\ell(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]. \tag*{(4)} x β ∈ arg x max E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] . (4)
Combining the terminal optimization with the outer token-control problem proves the first claim. Indeed, for any fixed token policy x x x , the choice of λ ( τ ) \lambda(\tau) λ ( τ ) is separable across terminal trajectories. By (2) ,
max λ E τ ∼ x ( ⋅ ∣ q ) [ ∑ i ∈ N λ i ( τ ) r i ( ℓ ( τ ) ) + β H ( λ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] = E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] . \begin{aligned}
\max_{\lambda}\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[\sum_{i\in\mathcal{N}}\lambda_i(\tau)r_i(\ell(\tau))+\beta\mathcal{H}(\lambda(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right] \\
&=\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[G_\beta(\ell(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right].
\end{aligned} λ max E τ ∼ x ( ⋅ ∣ q ) [ i ∈ N ∑ λ i ( τ ) r i ( ℓ ( τ )) + β H ( λ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] = E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] .
The inner maximizer is λ β \lambda^\beta λ β , while (4) shows that the outer maximizer is x β x^\beta x β . Hence ( x β , λ β ) (x^\beta,\lambda^\beta) ( x β , λ β ) maximizes the stated entropy-regularized welfare.
We now prove the welfare bound. For every λ ∈ Δ ( N ) \lambda\in\Delta(\mathcal{N}) λ ∈ Δ ( N ) , each term − λ i log λ i -\lambda_i\log\lambda_i − λ i log λ i is nonnegative, while
log ∣ N ∣ − H ( λ ) = D K L ( λ ∥ U ( N ) ) ≥ 0. \log|\mathcal{N}|-\mathcal{H}(\lambda)=D_{\mathrm{KL}}(\lambda\mathbin\Vert U(\mathcal{N}))\ge0. log ∣ N ∣ − H ( λ ) = D KL ( λ ∥ U ( N )) ≥ 0.
Therefore, in particular,
0 ≤ H ( λ β ( ℓ ) ) ≤ log ∣ N ∣ . 0\le\mathcal{H}(\lambda^\beta(\ell))\le\log|\mathcal{N}|. 0 ≤ H ( λ β ( ℓ )) ≤ log ∣ N ∣.
Moreover, for every i ∈ N i\in\mathcal{N} i ∈ N ,
G β ( ℓ ) = β log ∑ j ∈ N exp ( r j ( ℓ ) β ) ≥ β log exp ( r i ( ℓ ) β ) = r i ( ℓ ) . G_\beta(\ell)=\beta\log\sum_{j\in\mathcal{N}}\exp\left(\frac{r_j(\ell)}{\beta}\right)
\ge\beta\log\exp\left(\frac{r_i(\ell)}{\beta}\right)=r_i(\ell). G β ( ℓ ) = β log j ∈ N ∑ exp ( β r j ( ℓ ) ) ≥ β log exp ( β r i ( ℓ ) ) = r i ( ℓ ) .
Taking the maximum over i i i gives G β ( ℓ ) ≥ max i ∈ N r i ( ℓ ) G_\beta(\ell)\ge\max_{i\in\mathcal{N}}r_i(\ell) G β ( ℓ ) ≥ max i ∈ N r i ( ℓ ) . Using Equations (1) and (3), we obtain
SW β ( x β , λ β ∣ q , r ) = sup x E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] − β E τ ∼ x β ( ⋅ ∣ q ) [ H ( λ β ( τ ) ) ] ≥ sup x E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] − β log ∣ N ∣ ≥ sup x E τ ∼ x ( ⋅ ∣ q ) [ max i ∈ N r i ( ℓ ( τ ) ) − β ∑ t = 0 T τ − 1 log x ( a t ∣ s t ) π r e f ( a t ∣ s t ) ] − β log ∣ N ∣ = sup π , λ SW β ( π , λ ∣ q , r ) − β log ∣ N ∣ . \begin{aligned}
\operatorname{SW}_\beta(x^\beta,\lambda^\beta\mid q,r)
=\sup_x\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[G_\beta(\ell(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]
-\beta\mathbb{E}_{\tau\sim x^\beta(\cdot\mid q)}[\mathcal{H}(\lambda^\beta(\tau))] \\
&\ge\sup_x\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[G_\beta(\ell(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]-\beta\log|\mathcal{N}| \\
&\ge\sup_x\mathbb{E}_{\tau\sim x(\cdot\mid q)}\left[\max_{i\in\mathcal{N}}r_i(\ell(\tau))-\beta\sum_{t=0}^{T_\tau-1}\log\frac{x(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}\right]-\beta\log|\mathcal{N}| \\
&=\sup_{\pi,\lambda}\operatorname{SW}_\beta(\pi,\lambda\mid q,r)-\beta\log|\mathcal{N}|.
\end{aligned} SW β ( x β , λ β ∣ q , r ) = x sup E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] − β E τ ∼ x β ( ⋅ ∣ q ) [ H ( λ β ( τ ))] ≥ x sup E τ ∼ x ( ⋅ ∣ q ) [ G β ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] − β log ∣ N ∣ ≥ x sup E τ ∼ x ( ⋅ ∣ q ) [ i ∈ N max r i ( ℓ ( τ )) − β t = 0 ∑ T τ − 1 log π ref ( a t ∣ s t ) x ( a t ∣ s t ) ] − β log ∣ N ∣ = π , λ sup SW β ( π , λ ∣ q , r ) − β log ∣ N ∣.
The last equality follows because, conditional on each terminal state, the simplex first-best assigns the opportunity to an advertiser with maximal value. Since ( x β , λ β ) (x^\beta,\lambda^\beta) ( x β , λ β ) is itself feasible for the original simplex-allocation problem,
SW β ( x β , λ β ∣ q , r ) ≤ sup π , λ SW β ( π , λ ∣ q , r ) . \operatorname{SW}_\beta(x^\beta,\lambda^\beta\mid q,r)\le\sup_{\pi,\lambda}\operatorname{SW}_\beta(\pi,\lambda\mid q,r). SW β ( x β , λ β ∣ q , r ) ≤ π , λ sup SW β ( π , λ ∣ q , r ) .
Combining the last two displays gives
0 ≤ sup π , λ SW β ( π , λ ∣ q , r ) − SW β ( x β , λ β ∣ q , r ) ≤ β log ∣ N ∣ . 0\le\sup_{\pi,\lambda}\operatorname{SW}_\beta(\pi,\lambda\mid q,r)-\operatorname{SW}_\beta(x^\beta,\lambda^\beta\mid q,r)\le\beta\log|\mathcal{N}|. 0 ≤ π , λ sup SW β ( π , λ ∣ q , r ) − SW β ( x β , λ β ∣ q , r ) ≤ β log ∣ N ∣.
Finally, let ℓ ∗ \ell^* ℓ ∗ be a maximizing terminal state satisfying P 0 ( ℓ ∗ ∣ q ) > 0 P_0(\ell^*\mid q)>0 P 0 ( ℓ ∗ ∣ q ) > 0 . Applying Lemma 1 to the terminal reward max i ∈ N r i ( ℓ ∗ ) \max_{i\in\mathcal{N}}r_i(\ell^*) max i ∈ N r i ( ℓ ∗ ) gives
sup π , λ SW β ( π , λ ∣ q , r ) = β log ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( max i ∈ N r i ( ℓ ) β ) . \sup_{\pi,\lambda} \operatorname{SW}_{\beta}(\pi,\lambda\mid q,r)=\beta\log\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp\left(\frac{\max_{i\in\mathbb{N}}r_i(\ell)}{\beta}\right). π , λ sup SW β ( π , λ ∣ q , r ) = β log ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) exp ( β max i ∈ N r i ( ℓ ) ) .
It follows that
max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) + β log P 0 ( ℓ ∗ ∣ q ) ≤ sup π , λ SW β ( π , λ ∣ q , r ) ≤ max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) . \max_{\ell\in L(q)}\max_{i\in\mathbb{N}}r_i(\ell)+\beta\log P_0(\ell^*\mid q)
\le\sup_{\pi,\lambda}\operatorname{SW}_{\beta}(\pi,\lambda\mid q,r)\le\max_{\ell\in L(q)}\max_{i\in\mathbb{N}}r_i(\ell). ℓ ∈ L ( q ) max i ∈ N max r i ( ℓ ) + β log P 0 ( ℓ ∗ ∣ q ) ≤ π , λ sup SW β ( π , λ ∣ q , r ) ≤ ℓ ∈ L ( q ) max i ∈ N max r i ( ℓ ) .
Both bounds converge to max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) \max_{\ell\in L(q)}\max_{i\in\mathbb{N}}r_i(\ell) max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) as β → 0 + \beta\to0^+ β → 0 + . Together with the welfare-gap bound, the squeeze theorem yields
SW β ( x β , λ β ∣ q , r ) → max ℓ ∈ L ( q ) max i ∈ N r i ( ℓ ) . \operatorname{SW}_{\beta}(x^{\beta},\lambda^{\beta}\mid q,r)\to\max_{\ell\in L(q)}\max_{i\in\mathbb{N}}r_i(\ell). SW β ( x β , λ β ∣ q , r ) → ℓ ∈ L ( q ) max i ∈ N max r i ( ℓ ) .
The welfare-gap inequality is pointwise in q q q , so taking expectation over q ∼ D q\sim\mathcal{D} q ∼ D preserves the same β log ∣ N ∣ \beta\log|\mathcal{N}| β log ∣ N ∣ bound. □
Proof of Theorem 3. Fix an advertiser-query pair ( i , q ) (i,q) ( i , q ) , and let π i † \pi_i^\dagger π i † be any population minimizer of the local-advantage objective. Define
A ^ i † ( s , a ) : = β log π i † ( a ∣ s ) π r e f ( a ∣ s ) . \widehat{A}_i^\dagger(s,a):=\beta\log\frac{\pi_i^\dagger(a\mid s)}{\pi_{\mathrm{ref}}(a\mid s)}. A i † ( s , a ) := β log π ref ( a ∣ s ) π i † ( a ∣ s ) .
For a completed response y = ( a 0 , … , a T y − 1 ) y=(a_0,\ldots,a_{T_y-1}) y = ( a 0 , … , a T y − 1 ) , where s 0 = q s_0=q s 0 = q , s t + 1 = [ s t , a t ] s_{t+1}=[s_t,a_t] s t + 1 = [ s t , a t ] , and s T y = ℓ y s_{T_y}=\ell_y s T y = ℓ y , define its cumulative score
G i † ( q , y ) : = ∑ t = 0 T y − 1 A ^ i † ( s t , a t ) . G_i^\dagger(q,y):=\sum_{t=0}^{T_y-1}\widehat{A}_i^\dagger(s_t,a_t). G i † ( q , y ) := t = 0 ∑ T y − 1 A i † ( s t , a t ) .
By autoregressive factorization,
G i † ( q , y ) = ∑ t = 0 T y − 1 β log π i † ( a t ∣ s t ) π r e f ( a t ∣ s t ) = β log π i † ( y ∣ q ) π r e f ( y ∣ q ) . G_i^\dagger(q,y)=\sum_{t=0}^{T_y-1}\beta\log\frac{\pi_i^\dagger(a_t\mid s_t)}{\pi_{\mathrm{ref}}(a_t\mid s_t)}
=\beta\log\frac{\pi_i^\dagger(y\mid q)}{\pi_{\mathrm{ref}}(y\mid q)}. G i † ( q , y ) = t = 0 ∑ T y − 1 β log π ref ( a t ∣ s t ) π i † ( a t ∣ s t ) = β log π ref ( y ∣ q ) π i † ( y ∣ q ) .
For a comparison pair ( y , y ′ ) (y,y') ( y , y ′ ) , let
Δ i † ( q ; y , y ′ ) : = G i † ( q , y ) − G i † ( q , y ′ ) . \Delta_i^\dagger(q;y,y'):=G_i^\dagger(q,y)-G_i^\dagger(q,y'). Δ i † ( q ; y , y ′ ) := G i † ( q , y ) − G i † ( q , y ′ ) .
The Bradley-Terry target is
ω i ( q ; y , y ′ ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ ) ) . \omega_i(q;y,y')=\sigma\left(r_i(\ell_y)-r_i(\ell_{y'})\right). ω i ( q ; y , y ′ ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ ) ) .
For a predicted logit Δ \Delta Δ , abbreviate p : = ω i ( q ; y , y ′ ) p:=\omega_i(q;y,y') p := ω i ( q ; y , y ′ ) and p ^ Δ : = σ ( Δ ) \widehat{p}_{\Delta}:=\sigma(\Delta) p Δ := σ ( Δ ) . Since σ ( − Δ ) = 1 − p ^ Δ \sigma(-\Delta)=1-\widehat{p}_{\Delta} σ ( − Δ ) = 1 − p Δ , the binary cross-entropy satisfies
− p log p ^ Δ − ( 1 − p ) log ( 1 − p ^ Δ ) = [ − p log p − ( 1 − p ) log ( 1 − p ) ] + p log p p ^ Δ + ( 1 − p ) log 1 − p 1 − p ^ Δ = H ( Bern ( p ) ) + D K L ( Bern ( p ) ∥ Bern ( p ^ Δ ) ) . -p\log\widehat{p}_{\Delta}-(1-p)\log(1-\widehat{p}_{\Delta})
=[-p\log p-(1-p)\log(1-p)]
+p\log\frac{p}{\widehat{p}_{\Delta}}+(1-p)\log\frac{1-p}{1-\widehat{p}_{\Delta}}
=\mathcal{H}(\operatorname{Bern}(p))+D_{\mathrm{KL}}(\operatorname{Bern}(p)\parallel\operatorname{Bern}(\widehat{p}_{\Delta})). − p log p Δ − ( 1 − p ) log ( 1 − p Δ ) = [ − p log p − ( 1 − p ) log ( 1 − p )] + p log p Δ p + ( 1 − p ) log 1 − p Δ 1 − p = H ( Bern ( p )) + D KL ( Bern ( p ) ∥ Bern ( p Δ )) .
The middle equality adds and subtracts the Bernoulli entropy terms. By nonnegativity of the KL divergence, the loss is minimized exactly when p ^ Δ = p \widehat{p}_{\Delta}=p p Δ = p .
By Lemma 1, the optimal policy satisfies
β log π i † ( a ∣ s ) π r e f ( a ∣ s ) = V i ∗ ( [ s , a ] ) − V i ∗ ( s ) . \beta\log\frac{\pi_i^\dagger(a\mid s)}{\pi_{\mathrm{ref}}(a\mid s)}=V_i^*([s,a])-V_i^*(s). β log π ref ( a ∣ s ) π i † ( a ∣ s ) = V i ∗ ([ s , a ]) − V i ∗ ( s ) .
Telescoping along a completed response gives
β log π i † ( y ∣ q ) π r e f ( y ∣ q ) = r i ( ℓ y ) − V i ∗ ( q ) . \beta\log\frac{\pi_i^\dagger(y\mid q)}{\pi_{\mathrm{ref}}(y\mid q)}=r_i(\ell_y)-V_i^*(q). β log π ref ( y ∣ q ) π i † ( y ∣ q ) = r i ( ℓ y ) − V i ∗ ( q ) .
Hence π i † \pi_i^\dagger π i † induces the target logit r i ( ℓ y ) − r i ( ℓ y ′ ) r_i(\ell_y)-r_i(\ell_{y'}) r i ( ℓ y ) − r i ( ℓ y ′ ) . Because π i † \pi_i^\dagger π i † is feasible, the pointwise lower bound is attainable, so every population minimizer satisfies
σ ( Δ i † ( q ; y , y ′ ) ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ ) ) \sigma\left(\Delta_i^\dagger(q;y,y')\right)=\sigma\left(r_i(\ell_y)-r_i(\ell_{y'})\right) σ ( Δ i † ( q ; y , y ′ ) ) = σ ( r i ( ℓ y ) − r i ( ℓ y ′ ) )
for every pair of completed responses. Since σ \sigma σ is injective,
G i † ( q , y ) − G i † ( q , y ′ ) = r i ( ℓ y ) − r i ( ℓ y ′ ) . G_i^\dagger(q,y)-G_i^\dagger(q,y')=r_i(\ell_y)-r_i(\ell_{y'}). G i † ( q , y ) − G i † ( q , y ′ ) = r i ( ℓ y ) − r i ( ℓ y ′ ) .
Therefore there exists a constant c i ( q ) c_i(q) c i ( q ) such that
G i † ( q , y ) = r i ( ℓ y ) + c i ( q ) . (5) G_i^\dagger(q,y)=r_i(\ell_y)+c_i(q). \tag*{(5)} G i † ( q , y ) = r i ( ℓ y ) + c i ( q ) . (5)
Equation (4) identifies cumulative scores up to the query-specific constant c i ( q ) c_i(q) c i ( q ) . We next determine this constant from token-policy normalization.
Normalization of π i † \pi_i^\dagger π i † implies, at every reachable non-terminal prefix s s s ,
∑ a ∈ V π r e f ( a ∣ s ) exp ( A ^ i † ( s , a ) β ) = ∑ a ∈ V π i † ( a ∣ s ) = 1. (6) \sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{\widehat{A}_i^\dagger(s,a)}{\beta}\right)
=\sum_{a\in\mathcal{V}}\pi_i^\dagger(a\mid s)=1. \tag*{(6)} a ∈ V ∑ π ref ( a ∣ s ) exp ( β A i † ( s , a ) ) = a ∈ V ∑ π i † ( a ∣ s ) = 1. (6)
Because token states are prefixes, every reachable state has a unique path from the root. For s t = [ q , a < t ] s_t=[q,a_{<t}] s t = [ q , a < t ] , define
V ~ i ( s t ) : = − c i ( q ) + ∑ k = 0 t − 1 A ^ i † ( s k , a k ) , \widetilde{V}_i(s_t):=-c_i(q)+\sum_{k=0}^{t-1}\widehat{A}_i^\dagger(s_k,a_k), V i ( s t ) := − c i ( q ) + k = 0 ∑ t − 1 A i † ( s k , a k ) ,
V ~ i ( [ s , a ] ) : = V ~ i ( s ) + A ^ i † ( s , a ) . (7) \widetilde{V}_i([s,a]):=\widetilde{V}_i(s)+\widehat{A}_i^\dagger(s,a). \tag*{(7)} V i ([ s , a ]) := V i ( s ) + A i † ( s , a ) . (7)
At a terminal state ℓ y \ell_y ℓ y , Equation (4) gives
V ~ i ( ℓ y ) = − c i ( q ) + G i † ( q , y ) = r i ( ℓ y ) . \widetilde{V}_i(\ell_y)=-c_i(q)+G_i^\dagger(q,y)=r_i(\ell_y). V i ( ℓ y ) = − c i ( q ) + G i † ( q , y ) = r i ( ℓ y ) .
For every non-terminal prefix s s s , Equations (5) and (6) imply
β log ∑ a ∈ V π r e f ( a ∣ s ) exp ( V ~ i ( [ s , a ] ) β ) = V ~ i ( s ) + β log ∑ a ∈ V π r e f ( a ∣ s ) exp ( A ^ i † ( s , a ) β ) = V ~ i ( s ) . \beta\log\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{\widetilde{V}_i([s,a])}{\beta}\right)
=\widetilde{V}_i(s)+\beta\log\sum_{a\in\mathcal{V}}\pi_{\mathrm{ref}}(a\mid s)\exp\left(\frac{\widehat{A}_i^\dagger(s,a)}{\beta}\right)
=\widetilde{V}_i(s). β log a ∈ V ∑ π ref ( a ∣ s ) exp ( β V i ([ s , a ]) ) = V i ( s ) + β log a ∈ V ∑ π ref ( a ∣ s ) exp ( β A i † ( s , a ) ) = V i ( s ) .
Thus V ~ i \widetilde{V}_i V i satisfies the soft Bellman system in Lemma 1. Its finite-horizon solution is unique by backward induction from the terminal boundary, so
V ~ i ( s ) = V i ∗ ( s ) \widetilde{V}_i(s)=V_i^*(s) V i ( s ) = V i ∗ ( s )
at every reachable state. In particular,
− c i ( q ) = V ~ i ( q ) = V i ∗ ( q ) . (8) -c_i(q)=\widetilde{V}_i(q)=V_i^*(q). \tag*{(8)} − c i ( q ) = V i ( q ) = V i ∗ ( q ) . (8)
We can now identify the local scores. For a fixed pair ( s , a ) (s,a) ( s , a ) , write a continuation trajectory from the child state as τ = ( u 0 , b 0 , … , u T τ ) \tau=(u_0,b_0,\ldots,u_{T_\tau}) τ = ( u 0 , b 0 , … , u T τ ) , where u 0 = [ s , a ] u_0=[s,a] u 0 = [ s , a ] . The optimal soft advantage A i ∗ ( s , a ) A_i^*(s,a) A i ∗ ( s , a ) of committing to a a a at s s s is commonly defined as
sup π E π ∼ π ( ⋅ ∣ u 0 ) [ r i ( u T τ ) − β ∑ k = 0 T τ − 1 log π ( b k ∣ u k ) π r e f ( b k ∣ u k ) ] − V i ∗ ( s ) . \sup_{\pi}\mathbb{E}_{\pi\sim\pi(\cdot\mid u_0)}
\left[r_i(u_{T_\tau})-\beta\sum_{k=0}^{T_\tau-1}\log\frac{\pi(b_k\mid u_k)}{\pi_{\mathrm{ref}}(b_k\mid u_k)}\right]-V_i^*(s). π sup E π ∼ π ( ⋅ ∣ u 0 ) [ r i ( u T τ ) − β k = 0 ∑ T τ − 1 log π ref ( b k ∣ u k ) π ( b k ∣ u k ) ] − V i ∗ ( s ) .
Because the transition is deterministic and there are no intermediate rewards, the supremum is V i ∗ ( [ s , a ] ) V_i^*([s,a]) V i ∗ ([ s , a ]) . Thus A i ∗ ( s , a ) = V i ∗ ( [ s , a ] ) − V i ∗ ( s ) A_i^*(s,a)=V_i^*([s,a])-V_i^*(s) A i ∗ ( s , a ) = V i ∗ ([ s , a ]) − V i ∗ ( s ) , and Equation (6) gives
A ^ i † ( s , a ) = V ~ i ( [ s , a ] ) − V ~ i ( s ) = V i ∗ ( [ s , a ] ) − V i ∗ ( s ) = A i ∗ ( s , a ) . (9) \widehat{A}_i^\dagger(s,a)=\widetilde{V}_i([s,a])-\widetilde{V}_i(s)=V_i^*([s,a])-V_i^*(s)=A_i^*(s,a). \tag*{(9)} A i † ( s , a ) = V i ([ s , a ]) − V i ( s ) = V i ∗ ([ s , a ]) − V i ∗ ( s ) = A i ∗ ( s , a ) . (9)
Using the policy formula in Lemma 1, the definition of A ^ i † \hat{A}_i^\dagger A ^ i † , and (9) ,
π i ∗ ( a ∣ s ) = π r e f ( a ∣ s ) exp ( A ^ i † ( s , a ) β ) = π r e f ( a ∣ s ) exp ( A i ∗ ( s , a ) β ) = π i ∗ ( a ∣ s ) . \begin{aligned}
\pi_i^*(a \mid s) = \pi_{\mathrm{ref}}(a \mid s) \exp\left(\frac{\hat{A}_i^\dagger(s,a)}{\beta}\right) \\
&= \pi_{\mathrm{ref}}(a \mid s) \exp\left(\frac{A_i^*(s,a)}{\beta}\right) \\
&= \pi_i^*(a \mid s).
\end{aligned} π i ∗ ( a ∣ s ) = π ref ( a ∣ s ) exp ( β A ^ i † ( s , a ) ) = π ref ( a ∣ s ) exp ( β A i ∗ ( s , a ) ) = π i ∗ ( a ∣ s ) .
Thus π ^ i ∗ = π i ∗ \hat{\pi}_i^*=\pi_i^* π ^ i ∗ = π i ∗ . Since ( i , q ) (i,q) ( i , q ) was arbitrary, the population minimizer is unique in induced policy space.
It remains to identify the root value used to initialize the ledger. Combining (5) and (7) gives, for every completed response y y y ,
r i ( ℓ y ) − ∑ t = 0 T y − 1 A ^ i † ( s t , a t ) = r i ( ℓ y ) − G i ∗ ( q , y ) = − c i ( q ) = V i ∗ ( q ) . r_i(\ell_y)-\sum_{t=0}^{T_y-1}\hat{A}_i^\dagger(s_t,a_t)=r_i(\ell_y)-G_i^*(q,y)=-c_i(q)=V_i^*(q). r i ( ℓ y ) − t = 0 ∑ T y − 1 A ^ i † ( s t , a t ) = r i ( ℓ y ) − G i ∗ ( q , y ) = − c i ( q ) = V i ∗ ( q ) .
The residual is pointwise equal to V i ∗ ( q ) V_i^*(q) V i ∗ ( q ) . Taking its conditional expectation therefore gives
v ^ i † ( q ) = E y ∼ D ( ⋅ ∣ i , q ) [ r i ( ℓ y ) − ∑ t = 0 T y − 1 A ^ i † ( s t , a t ) ] = V i ∗ ( q ) . \hat{v}_i^\dagger(q)=\mathbb{E}_{y\sim\mathcal{D}(\cdot\mid i,q)}\left[r_i(\ell_y)-\sum_{t=0}^{T_y-1}\hat{A}_i^\dagger(s_t,a_t)\right]=V_i^*(q). v ^ i † ( q ) = E y ∼ D ( ⋅ ∣ i , q ) r i ( ℓ y ) − t = 0 ∑ T y − 1 A ^ i † ( s t , a t ) = V i ∗ ( q ) .
Thus the population root value is recovered on the training support. With the root value identified, initialize the serving-time ledger by
V ^ i ( q ) : = v ^ i † ( q ) = V i ∗ ( q ) \hat{V}_i(q):=\hat{v}_i^\dagger(q)=V_i^*(q) V ^ i ( q ) := v ^ i † ( q ) = V i ∗ ( q )
and update it recursively according to
V ^ i ( [ s , a ] ) : = V ^ i ( s ) + A ^ i † ( s , a ) . \hat{V}_i([s,a]):=\hat{V}_i(s)+\hat{A}_i^\dagger(s,a). V ^ i ([ s , a ]) := V ^ i ( s ) + A ^ i † ( s , a ) .
If V ^ i ( s ) = V i ∗ ( s ) \hat{V}_i(s)=V_i^*(s) V ^ i ( s ) = V i ∗ ( s ) , then
V ^ i ( [ s , a ] ) = V ^ i ( s ) + A ^ i † ( s , a ) = V i ∗ ( s ) + V i ∗ ( [ s , a ] ) − V i ∗ ( s ) = V i ∗ ( [ s , a ] ) . \begin{aligned}
\hat{V}_i([s,a])&=\hat{V}_i(s)+\hat{A}_i^\dagger(s,a)\\
&=V_i^*(s)+V_i^*([s,a])-V_i^*(s)=V_i^*([s,a]).
\end{aligned} V ^ i ([ s , a ]) = V ^ i ( s ) + A ^ i † ( s , a ) = V i ∗ ( s ) + V i ∗ ([ s , a ]) − V i ∗ ( s ) = V i ∗ ([ s , a ]) .
Induction over prefix length gives V ^ i ( s ) = V i ∗ ( s ) \hat{V}_i(s)=V_i^*(s) V ^ i ( s ) = V i ∗ ( s ) at every reachable state, so the constructed child-value vector is the optimal soft-value report required by LAMA. □ \square □
Proof of Proposition 1. Fix a query q q q and candidate advertiser set N N N . Under exact reporting, specialize the desirability notation of Lemma 3 to the truthful value profile:
z i ∗ ( q ) : = exp ( V i ∗ ( q ) β ) , z ˉ ( q ; V ∗ ) : = ∑ j ∈ N z j ∗ ( q ) . z_i^*(q):=\exp\left(\frac{V_i^*(q)}{\beta}\right),\qquad\bar{z}(q;V^*):=\sum_{j\in N}z_j^*(q). z i ∗ ( q ) := exp ( β V i ∗ ( q ) ) , z ˉ ( q ; V ∗ ) := j ∈ N ∑ z j ∗ ( q ) .
The initial allocation posterior therefore satisfies
ρ i ( q ) = z i ∗ ( q ) z ˉ ( q ; V ∗ ) . \rho_i(q)=\frac{z_i^*(q)}{\bar{z}(q;V^*)}. ρ i ( q ) = z ˉ ( q ; V ∗ ) z i ∗ ( q ) .
For a realized terminal state s T s_T s T , let
p i f r a c ( s T ) : = ρ i ( s T ) r i ( s T ) − β log z ˉ ( q ; V ∗ ) + β log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) p_i^{\mathrm{frac}}(s_T):=\rho_i(s_T)r_i(s_T)-\beta\log\bar{z}(q;V^*)+\beta\log\left(1+\bar{z}(q;V^*)-z_i^*(q)\right) p i frac ( s T ) := ρ i ( s T ) r i ( s T ) − β log z ˉ ( q ; V ∗ ) + β log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) )
denote advertiser i i i ’s telescoped fractional payment before the winner-probability adjustment in Algorithm 1. The winner-settled payment is therefore
P i ( s T , I ∗ ) = 1 { I ∗ = i } p i f r a c ( s T ) ρ i ( s T ) , I ∗ ∼ ρ ( s T ) . P_i(s_T,I^*)=\mathbf{1}\{I^*=i\}\frac{p_i^{\mathrm{frac}}(s_T)}{\rho_i(s_T)},\qquad I^*\sim\rho(s_T). P i ( s T , I ∗ ) = 1 { I ∗ = i } ρ i ( s T ) p i frac ( s T ) , I ∗ ∼ ρ ( s T ) .
We first prove outcome individual rationality. Because terminal values are nonnegative, Lemma 1 gives
z i ∗ ( q ) = exp ( V i ∗ ( q ) β ) = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) β ) ≥ 1. z_i^*(q)=\exp\left(\frac{V_i^*(q)}{\beta}\right)=\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp\left(\frac{r_i(\ell)}{\beta}\right)\ge1. z i ∗ ( q ) = exp ( β V i ∗ ( q ) ) = ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) exp ( β r i ( ℓ ) ) ≥ 1.
Consequently, z ˉ ( q ; V ∗ ) ≥ 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) \bar{z}(q;V^*)\ge1+\bar{z}(q;V^*)-z_i^*(q) z ˉ ( q ; V ∗ ) ≥ 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) . Suppose advertiser i i i is the sampled winner at terminal state s T s_T s T . By exactness of the terminal report, V i ∗ ( s T ) = r i ( s T ) V_i^*(s_T)=r_i(s_T) V i ∗ ( s T ) = r i ( s T ) , so its realized utility is
r i ( s T ) − P i ( s T , i ) = β ρ i ( s T ) log ( z ˉ ( q ; V ∗ ) 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) ≥ 0 , r_i(s_T)-P_i(s_T,i)=\frac{\beta}{\rho_i(s_T)}\log\left(\frac{\bar{z}(q;V^*)}{1+\bar{z}(q;V^*)-z_i^*(q)}\right)\ge0, r i ( s T ) − P i ( s T , i ) = ρ i ( s T ) β log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) z ˉ ( q ; V ∗ ) ) ≥ 0 ,
where the inequality follows from the preceding desirability bound. Thus the winner’s payment does not exceed its realized gain. If advertiser i i i is not selected, it receives no advertising opportunity and pays zero, so its realized utility is also zero. Therefore outcome IR holds pointwise for every realized terminal state and every sampled winner.
We next prove expected weak budget balance. Conditional on a realized terminal state s T s_T s T , taking expectation only over the sampled winner gives
E I ∗ ∼ ρ ( s T ) [ P i ( s T , I ∗ ) ∣ s T ] = ρ i ( s T ) p i f r a c ( s T ) ρ i ( s T ) = p i f r a c ( s T ) . \mathbb{E}_{I^*\sim\rho(s_T)}[P_i(s_T,I^*)\mid s_T]=\rho_i(s_T)\frac{p_i^{\mathrm{frac}}(s_T)}{\rho_i(s_T)}=p_i^{\mathrm{frac}}(s_T). E I ∗ ∼ ρ ( s T ) [ P i ( s T , I ∗ ) ∣ s T ] = ρ i ( s T ) ρ i ( s T ) p i frac ( s T ) = p i frac ( s T ) .
Thus it suffices to show that the expected fractional payments are nonnegative. By the definition of p i f r a c p_i^{\mathrm{frac}} p i frac ,
1 β E s T ∼ χ β [ p i f r a c ( s T ) ] = 1 β E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] − log z ˉ ( q ; V ∗ ) + log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) . \frac{1}{\beta}\mathbb{E}_{s_T\sim\chi^\beta}\left[p_i^{\mathrm{frac}}(s_T)\right]=\frac{1}{\beta}\mathbb{E}_{s_T\sim\chi^\beta}\left[\rho_i(s_T)r_i(s_T)\right]-\log\bar{z}(q;V^*)+\log\left(1+\bar{z}(q;V^*)-z_i^*(q)\right). β 1 E s T ∼ χ β [ p i frac ( s T ) ] = β 1 E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] − log z ˉ ( q ; V ∗ ) + log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) .
The last two terms are deterministic, so the only random term that must be controlled is the expected allocation-weighted value. By Lemma 4,
E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] = 1 z ˉ ( q ; V ∗ ) ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) β ) r i ( ℓ ) . \mathbb{E}_{s_T\sim\chi^\beta}\left[\rho_i(s_T)r_i(s_T)\right]=\frac{1}{\bar{z}(q;V^*)}\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp\left(\frac{r_i(\ell)}{\beta}\right)r_i(\ell). E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] = z ˉ ( q ; V ∗ ) 1 ℓ ∈ L ( q ) ∑ P 0 ( ℓ ∣ q ) exp ( β r i ( ℓ ) ) r i ( ℓ ) .
To normalize this sum, define the terminal distribution
ν i ( ℓ ) : = P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) z i ∗ ( q ) . \nu_i(\ell):=\frac{P_0(\ell\mid q)\exp(r_i(\ell)/\beta)}{z_i^*(q)}. ν i ( ℓ ) := z i ∗ ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) .
This is a probability distribution because the leaf representation above gives z i ∗ ( q ) = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) z_i^*(q)=\sum_{\ell\in L(q)}P_0(\ell\mid q)\exp(r_i(\ell)/\beta) z i ∗ ( q ) = ∑ ℓ ∈ L ( q ) P 0 ( ℓ ∣ q ) exp ( r i ( ℓ ) / β ) . The expected allocation-weighted value can now be written as
E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] = z i ∗ ( q ) z ˉ ( q ; V ∗ ) E ℓ ∼ ν i [ r i ( ℓ ) ] . \mathbb{E}_{s_T\sim\chi^\beta}\left[\rho_i(s_T)r_i(s_T)\right]=\frac{z_i^*(q)}{\bar{z}(q;V^*)}\mathbb{E}_{\ell\sim\nu_i}[r_i(\ell)]. E s T ∼ χ β [ ρ i ( s T ) r i ( s T ) ] = z ˉ ( q ; V ∗ ) z i ∗ ( q ) E ℓ ∼ ν i [ r i ( ℓ )] .
It remains to lower-bound the expectation under ν i \nu_i ν i . For every ℓ \ell ℓ with ν i ( ℓ ) > 0 \nu_i(\ell)>0 ν i ( ℓ ) > 0 , the definition of ν i \nu_i ν i implies
log ν i ( ℓ ) P 0 ( ℓ ∣ q ) = r i ( ℓ ) β − log z i ∗ ( q ) . \log\frac{\nu_i(\ell)}{P_0(\ell\mid q)}=\frac{r_i(\ell)}{\beta}-\log z_i^*(q). log P 0 ( ℓ ∣ q ) ν i ( ℓ ) = β r i ( ℓ ) − log z i ∗ ( q ) .
Taking expectation under ν i \nu_i ν i and rearranging gives
E ℓ ∼ ν i [ r i ( ℓ ) ] − β D K L ( ν i ∥ P 0 ( ⋅ ∣ q ) ) = β log z i ∗ ( q ) = V i ∗ ( q ) . \mathbb{E}_{\ell\sim\nu_i}[r_i(\ell)]-\beta D_{\mathrm{KL}}(\nu_i\Vert P_0(\cdot\mid q))=\beta\log z_i^*(q)=V_i^*(q). E ℓ ∼ ν i [ r i ( ℓ )] − β D KL ( ν i ∥ P 0 ( ⋅ ∣ q )) = β log z i ∗ ( q ) = V i ∗ ( q ) .
Since the KL divergence is nonnegative,
E ℓ ∼ ν i [ r i ( ℓ ) ] ≥ V i ∗ ( q ) = β log z i ∗ ( q ) . \mathbb{E}_{\ell\sim\nu_i}[r_i(\ell)] \ge V_i^*(q)=\beta\log z_i^*(q). E ℓ ∼ ν i [ r i ( ℓ )] ≥ V i ∗ ( q ) = β log z i ∗ ( q ) .
Combining the last inequality with the representation of the allocation-weighted value yields
E s T ∼ x β [ ρ i ( s T ) r i ( s T ) ] ≥ β z i ∗ ( q ) z ˉ ( q ; V ∗ ) log z i ∗ ( q ) . \mathbb{E}_{s_T\sim x^\beta}\left[\rho_i(s_T)r_i(s_T)\right]\ge\beta\frac{z_i^*(q)}{\bar z(q;V^*)}\log z_i^*(q). E s T ∼ x β [ ρ i ( s T ) r i ( s T ) ] ≥ β z ˉ ( q ; V ∗ ) z i ∗ ( q ) log z i ∗ ( q ) .
Substituting this bound into the payment decomposition gives
1 β E [ P i f r a c ( s T ) ] ≥ z i ∗ ( q ) z ˉ ( q ; V ∗ ) log z i ∗ ( q ) − log z ˉ ( q ; V ∗ ) + log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) . \frac{1}{\beta}\mathbb{E}\left[P_i^{\mathrm{frac}}(s_T)\right]\ge\frac{z_i^*(q)}{\bar z(q;V^*)}\log z_i^*(q)-\log\bar z(q;V^*)+\log\left(1+\bar z(q;V^*)-z_i^*(q)\right). β 1 E [ P i frac ( s T ) ] ≥ z ˉ ( q ; V ∗ ) z i ∗ ( q ) log z i ∗ ( q ) − log z ˉ ( q ; V ∗ ) + log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) .
It remains to show that the right-hand side is nonnegative. Since 0 < z i ∗ ( q ) / z ˉ ( q ; V ∗ ) ≤ 1 0<z_i^*(q)/\bar z(q;V^*)\le1 0 < z i ∗ ( q ) / z ˉ ( q ; V ∗ ) ≤ 1 , the weighted arithmetic-geometric mean inequality gives
1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) z ˉ ( q ; V ∗ ) = ( 1 − z i ∗ ( q ) z ˉ ( q ; V ∗ ) ) ⋅ 1 + z i ∗ ( q ) z ˉ ( q ; V ∗ ) ⋅ 1 z i ∗ ( q ) ≥ 1 1 − z i ∗ ( q ) / z ˉ ( q ; V ∗ ) ( 1 z i ∗ ( q ) ) z i ∗ ( q ) / z ˉ ( q ; V ∗ ) = z i ∗ ( q ) − z i ∗ ( q ) / z ˉ ( q ; V ∗ ) . \begin{aligned}
\frac{1+\bar z(q;V^*)-z_i^*(q)}{\bar z(q;V^*)}
&=\left(1-\frac{z_i^*(q)}{\bar z(q;V^*)}\right)\cdot1+\frac{z_i^*(q)}{\bar z(q;V^*)}\cdot\frac{1}{z_i^*(q)}\\
&\ge1^{1-z_i^*(q)/\bar z(q;V^*)}\left(\frac{1}{z_i^*(q)}\right)^{z_i^*(q)/\bar z(q;V^*)}\\
&=z_i^*(q)^{-z_i^*(q)/\bar z(q;V^*)}.
\end{aligned} z ˉ ( q ; V ∗ ) 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) = ( 1 − z ˉ ( q ; V ∗ ) z i ∗ ( q ) ) ⋅ 1 + z ˉ ( q ; V ∗ ) z i ∗ ( q ) ⋅ z i ∗ ( q ) 1 ≥ 1 1 − z i ∗ ( q ) / z ˉ ( q ; V ∗ ) ( z i ∗ ( q ) 1 ) z i ∗ ( q ) / z ˉ ( q ; V ∗ ) = z i ∗ ( q ) − z i ∗ ( q ) / z ˉ ( q ; V ∗ ) .
Taking logarithms,
log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) − log z ˉ ( q ; V ∗ ) ≥ − z i ∗ ( q ) z ˉ ( q ; V ∗ ) log z i ∗ ( q ) . \log\left(1+\bar z(q;V^*)-z_i^*(q)\right)-\log\bar z(q;V^*)\ge-\frac{z_i^*(q)}{\bar z(q;V^*)}\log z_i^*(q). log ( 1 + z ˉ ( q ; V ∗ ) − z i ∗ ( q ) ) − log z ˉ ( q ; V ∗ ) ≥ − z ˉ ( q ; V ∗ ) z i ∗ ( q ) log z i ∗ ( q ) .
Therefore, E [ P i f r a c ( s T ) ] ≥ 0 \mathbb{E}[P_i^{\mathrm{frac}}(s_T)]\ge0 E [ P i frac ( s T )] ≥ 0 for every i ∈ N i\in\mathcal{N} i ∈ N .
Finally, taking expectations in the conditional payment identity above and summing over advertisers gives
E s T , I ∗ [ ∑ i ∈ N P i ( s T , I ∗ ) ] = ∑ i ∈ N E s T [ P i f r a c ( s T ) ] ≥ 0. \mathbb{E}_{s_T,I^*}\left[\sum_{i\in\mathcal{N}}P_i(s_T,I^*)\right]
=\sum_{i\in\mathcal{N}}\mathbb{E}_{s_T}\left[P_i^{\mathrm{frac}}(s_T)\right]
\ge0. E s T , I ∗ [ i ∈ N ∑ P i ( s T , I ∗ ) ] = i ∈ N ∑ E s T [ P i frac ( s T ) ] ≥ 0.
The expectation is over both token-generation randomness and the terminal winner draw, conditional on the query and candidate advertiser set. Hence the winner-settled implementation is weakly budget balanced in expectation. □
Additional Experiment Results
This appendix provides supporting experimental details and diagnostics. Table 2 summarizes the evaluated verticals and their advertisers, and Table 3 –5 present representative generated responses for each vertical. Table 6 and 7 illustrate how the generated response changes with bids for complementary and competing advertiser pairs, respectively. Table 8 compares the end-to-end latency of LAMA with reference-answer generation. Table 9 and Figure 4 report the prediction and calibration errors of the learned shared report model, while Figure 5 empirically evaluates its monotonicity under bid perturbations.
Table 2. Vertical overview and advertiser metadata used in the experiments.
Table 3. Case Study 1: Workout vertical. In the generated content, the winning advertiser is shown in bold, and the highlighted sentence is the span allocated to the hyperlink.
Table 6. Car vertical, query “used cars”, with participating advertisers Kelley Blue Book (KBB) and CARFAX. KBB primarily contributes used-car pricing and market-value guidance, while CARFAX contributes vehicle-history and title/service-record evidence; the pair is mainly complementary for used-car shopping, with limited overlap as automotive information resources. KBB- and CARFAX-generated tokens are underlined in their respective colors. In the generated content, the winning advertiser is shown in bold, and the highlighted sentence is the span allocated to the hyperlink.
Table 8. Latency and seconds-per-token ratios (LAMA/Reference) across verticals. These ratios are close to the theoretical prediction (∣ N ∣ + 1 \lvert\mathcal{N}\rvert+ 1 ∣ N ∣ + 1 )
Table 9. Impression-value prediction and calibration performance across verticals. In our experiments, impression values lie in [0, 1] and are defined as click-through rates multiplied by a unit cost per click. The current experimental setup (Qwen3-14B + LoRA fine-tuning) already yields reasonably good recovery accuracy.
Figure 4. Quantile-binned calibration curves for the value model r ^ \hat{r} r ^ across the three verticals. Each panel corresponds to one vertical, and each point represents one of 50 equal-frequency bins sorted by predicted impression value. The x-axis reports the mean predicted impression value within the bin, while the y-axis reports the mean ground-truth impression value for the same examples.
Figure 5. Bid-offset sweep for the LAMA token auction across the three verticals. For each vertical, we select one target advertiser and add a constant offset to its truthful value v ( q ) v(q) v ( q ) while leaving the other advertisers’ bids unchanged. The target advertisers are CARFAX for car, ClassPass for workout, and Tripadvisor for vacation. The sweep ranges from − 0.3 -0.3 − 0.3 to + 0.3 +0.3 + 0.3 , while the advantage model settings remain fixed to the vertical-specific configuration. The four panels report the mean target token share, final allocation probability, expected payment, and true expected utility. Across all three verticals, increasing the bid offset monotonically increases token share, allocation, and payment. In contrast, true utility peaks at the truthful bid for all three verticals, then declines under overbidding as higher payments offset the additional allocation. This pattern provides qualitative evidence that the mechanism rewards truthful bidding while still allowing bids to control token-level allocation.
Token-Level Advertising
Table 4. Case study 2: Vacation vertical. In the generated content, the winning advertiser is shown in bold, and the highlighted sentence is the span allocated to the hyperlink.
Table 5. Case Study 3: Car vertical. In the generated content, the winning advertiser is shown in bold, and the highlighted sentence is the span allocated to the hyperlink.
Table 7. Car vertical, query “used cars”, with participating advertisers Kelley Blue Book (KBB) and Edmunds . Both advertisers can answer used-car research and pricing-comparison intent, so the pair is more competitive than KBB–CARFAX ; they are partially complementary because KBB emphasizes valuation while Edmunds emphasizes reviews, model research, and shopping guidance. KBB - and Edmunds -generated tokens are underlined in their respective colors. In the generated content, the winning advertiser is shown in bold, and the highlighted sentence is the span allocated to the hyperlink.