Truthful Aggregation of LLMs with an Application to Online Advertising

## Abstract

Abstract The next frontier of online advertising is revenue generation from LLM-generated content. We consider a setting where advertisers aim to influence the responses of an LLM to align with their interests, while platforms seek to maximize advertiser value and ensure user satisfaction. The challenge is that advertisers’ preferences generally conflict with those of the user, and advertisers may misreport their preferences. To address this, we introduce MOSAIC, an auction mechanism that ensures that truthful reporting is a dominant strategy for advertisers and that aligns the utility of each advertiser with their contribution to social welfare. Importantly, the mechanism operates without LLM fine-tuning or access to model weights and provably converges to the output of the optimally fine-tuned LLM as computational resources increase. Additionally, it can incorporate contextual information about advertisers, which significantly improves social welfare. Through experiments with a publicly available LLM, we show that MOSAIC leads to high advertiser value and platform revenue with low computational overhead. While our motivating application is online advertising, our mechanism can be applied in any setting with monetary transfers, making it a general-purpose solution for truthfully aggregating the preferences of self-interested agents over LLM-generated replies.

## 1 Introduction

Large language models (LLMs) are becoming ubiquitous – as coding assistants, as chat interfaces, and even as alternatives to search engines (Bommasani et al., ).
To ensure their usefulness, it is essential to closely align LLM outputs with user preferences.
However, in general, there may be multiple interested parties who disagree on the desired behavior of the same LLM.
This leads to the question of how to generate LLM replies given multiple conflicting preferences.

The motivating application for our work is online advertising, which is the main source of revenue for large tech companies such as Google, Meta, and Twitter. For example, in $2023$, Meta’s advertising revenue of $132$ billion USD was more than $97$% of its total revenue (Meta, ). Ad auctions are the workhorse mechanism to determine the placement and prices of commercial content (Varian, ; Edelman et al., ).
As platforms are now working on integrating advertisements into LLM-generated content (Criddle, ), new auction mechanisms are needed for this application.

We present a new auction mechanism for this problem, which we call MOSAIC (Mechanism for Optimally Sampling and Aggregating LLM Outputs with Incentive Compatibility). The advertisers are paying, not for some particular item or bundle, but rather to influence the output generated by an LLM in a direction closer to their own preferences.
Although our mechanism could be of interest whenever one has to aggregate the preferences of multiple self-interested agents over LLM behavior (as long as it is reasonable to charge monetary payments), we see online advertising as the most natural setting of interest.
For this reason, we refer to participants in the mechanism as advertisers.

### 1.1 Problem setting

Consider a situation where a user queries an LLM with a specific question.
We assume the following:

- •
There is a reference LLM that can produce useful replies to the user’s query.
- •
There are advertisers, each with their own LLM, who want to influence the reply to the user.

In our model, each advertiser is represented via her own LLM
or directly with a reward function, similar to the function used to fine-tune LLMs in the Reinforcement Learning from Human Feedback pipeline (Azar et al., ).
For this reason, we refer to an advertiser’s value for a reply as her reward.
The auctioneer’s task is, given the user’s query and the advertisers’ preferences, to produce a reply that is useful for the user while also generating high rewards for the advertisers.

##### Example.

A user queries an LLM *“What are effective ways to learn a musical instrument online?”*
There are two advertisers:
*MusicMastery*, which offers online music lessons, and
*InstaTune*, which sells musical instruments. MOSAIC merges the preferred replies from the advertisers’ LLMs and the reference LLM to produce one combined reply to the user:

> Effective ways to learn a musical instrument online include: 1. Online music lessons: Platforms like MusicMastery offer one-on-one virtual tutoring, group classes, and pre-recorded lessons. 2. Interactive learning tools: InstaTune offers a range of interactive learning tools, such as apps, software, and games, that make learning fun and engaging.

### 1.2 Overview of Contributions

In this paper, we present MOSAIC, an auction mechanism designed to aggregate the preferences of multiple self-interested advertisers over LLM-generated replies. The first challenge we address is that MOSAIC must produce replies for which the advertisers receive high rewards, but without steering the LLM’s behavior too far from that of the user-centric reference LLM. We address this by drawing a strong connection to the RLHF objective (e.g., Ziegler et al. ()), equipping MOSAIC with a hyperparameter that enables the auctioneer to balance between the usefulness of the produced reply to the user
and the advertisers in an interpretable and principled way (Section 3.1).

Second, leveraging an importance sampling-based technique, MOSAIC is the only mechanism in the literature that converges to the optimal distribution as computational resources increase (Corollary 4.1).
Third, MOSAIC can incorporate contextual information, similar to how sponsored search auctions utilize advertiser descriptions.
This accelerates convergence and increases value for the advertisers and revenue for the auctioneer (Section 6.2.1).

Fourth, we address technical feasibility and practicality. We adopt the desiderata proposed by
Duetting et al. (), who argued that auctions must be compatible with existing LLM technology, only using “information obtainable from current models” in such a way that they are “easy to integrate into the system” and rely only on “easy manipulations of LLM output.” Furthermore, it must be computationally feasible to run the auction repeatedly and with different advertiser preferences. In particular, we cannot afford the expensive process of fine-tuning an LLM’s weights for each possible query. To address this, we have designed MOSAIC to work by only post-processing multiple LLM outputs – it requires only “API access”, not even viewing the model weights ( Section 4.2).

Fifth, we address the fact that advertisers might have an interest in misreporting their preferences (which include their full LLMs), analogous to over-/underbidding in traditional auctions. To address this challenge, we employ an allocation rule that is compatible with Rochet payments (Rochet, ). These payments uniquely ensure that MOSAIC is strategyproof (i.e., that truthful reporting is a dominant strategy
for each advertiser, no matter what the others do (Theorem 5.1)).
Crucially, Rochet payments ensure that MOSAIC is strategyproof even if the allocation rule has not converged.

Sixth, we introduce an offset to the Rochet payments, to ensure that
each advertiser’s utility is proportional to her contribution to the social welfare.
This alignment is important for the long-term success of the market, incentivizing only the most relevant advertisers to participate.

Finally, we discuss individual rationality (IR), which guarantees that a participant is weakly better off from participating in the mechanism.
In Section 5.2, we discuss the unique properties of our setting that make ex-post IR unattainable. However, in Section 5.3.1, we show that MOSAIC is “almost ex-post IR” in a well-defined sense. In Section 6.2.1, we experimentally show that, for the distribution of instances tested, it is ex-ante IR (i.e., advertisers are in expectation better off by participating).

In Section 6, we provide experimental results for the online advertising domain. We demonstrate that MOSAIC quickly converges to the optimal LLM with low computational cost,
generating significant value for the advertisers
and revenue for the auctioneer while also being useful to the user.

## 2 Related Work

Duetting et al. ()
introduced the field of mechanism design for LLMs.
They proposed a sequential mechanism, where the output sequence is generated on a token-by-token basis and the advertisers bid for their LLM
to generate the next token.
However,
their approach suffers from several limitations:
(i) Advertisers face the exposure problem: small changes in the generated sequence, such as the addition of a word like "not," can completely alter its meaning. An advertiser might pay a significant amount for the tokens generated up to a certain point, only for the continuation to unexpectedly negate or distort her intended message.(^1^11 As an example, suppose advertiser A has successfully bid for all the tokens in the sequence ”Planning your next vacation? For the cheapest flights to Hawaii, book via…” However, she fails to win the bid for the crucial next token, which would have been her brand name. This leaves her having paid for the preceding tokens without getting the benefit of associating her brand with the message.)
(ii) The mechanism is easily manipulable if the assumption that advertisers cannot misreport their LLMs is dropped.
(iii) For a given prompt, an advertiser’s spend grows with the length of the generated sequence. MOSAIC does not have any of these limitations.

Dubey et al. () proposed a generalization of the position auction (Varian, ; Edelman et al., ) to a setting where each advertiser is interested in having some specific text ad displayed alongside the organic results. In their mechanism, an LLM module coupled with an auction module work in tandem to merge the ads into a single ad summary in an incentive-compatible way.

Hajiaghayi et al. () considered advertisers bidding in an auction to have their ads placed into various portions of a retrieval-augmented generation (RAG) response. Their auction only allows advertisers to report (and misreport) scalar values to influence the inclusion of non-misreportable advertising texts in the combined output. This is in contrast to MOSAIC, which allows the aggregation of full LLMs that advertisers may arbitrarily misreport.

Feizi et al. () presented an abstract design for an LLM advertising system and detailed a number of research challenges that would have to be overcome in the course of implementation.
Conitzer et al. () drew connections between computational social choice and LLM alignment.
Fish et al. () presented work in the opposite direction: how can LLMs be used to solve problems in social choice?
Harris et al. () studied Bayesian persuasion in an abstract setting where a “simulator” (for example, a realistic LLM) of the agent is available. Werner et al. () gave preliminary empirical evidence that LLM-generated content can influence consumers.

## 3 Framing Sequence Generation as a Mechanism Design Problem

### 3.1 Formal Model

A user issues a query $x$.
There is a reference LLM $\pi_{\text{ref}}$ that the auctioneer aims not to deviate from too much (e.g., because it is responsible for providing useful replies to the user).
Additionally, there is a set $N$ of $n$ advertisers who have their own preferences for the reply (i.e., a token sequence) that will be returned to the user. We use the terms sequence and reply interchangeably.

An LLM can be abstracted as a mapping from (partial) token sequences to a distribution over the next token, or equivalently as an implicit distribution over token sequences.
We use this second abstraction, i.e., $\pi_{i}(y|x)$ denotes the probability that advertiser $i$’s LLM $\pi_{i}$ assigns to output sequence (i.e., reply) $y$ for the user query $x$.

We let $r_{i}(x,y)$ denote advertiser $i$’s reward for sequence $y$, given query $x$.(^2^22 In theory, the advertiser’s reward for a generated sequence could also depend on user-specific information, but we abstract that away. Equivalently, we assume that the reward function $r_{i}$ provided by advertiser $i$ is specific to the given user that asked the query $x$.)
Informally, the auctioneer’s goal is to sample the final sequence from a distribution that optimizes the advertisers’ expected rewards without substantially diverging from $\pi_{\text{\text{ref}}}$. Formally, the goal is to maximize:

$$ $\displaystyle J(\pi)=\mathbb{E}_{y\sim\pi}\left[\sum_{i\in N}r_{i}(x,y)\right] -\tau D_{\text{KL}}(\pi(\cdot|x)||\pi_{\text{\text{ref}}}(\cdot|x))$ (1) $$

where $\tau>0$ is a hyperparameter enabling the auctioneer to balance producing replies
closer to the reference LLM or with higher reward for the advertisers, and $D_{\text{KL}}$ is the Kullback-Leibler divergence.

This objective is similar to the standard Reinforcement Learning from Human Feedback (RLHF) approach (Ziegler et al., ), but replaces the human feedback reward function $r_{\text{HF}}(x,y)$ with the sum of the advertisers’ rewards.
For an overview of RLHF, we recommend Rafailov et al. (, §3).

The optimal solution to the optimization problem in (1) was derived by Peters & Schaal ():

$$ $\displaystyle\pi_{r}(y|x)=\frac{1}{Z(x)}\pi_{\text{\text{ref}}}(y|x)\exp\left( \frac{1}{\tau}\sum_{i\in N}r_{i}(x,y)\right),$ (2) $$

where $Z(x)=\sum_{y\in T^{*}}\pi_{\text{ref}}(y|x)\exp\left(\frac{1}{\tau}\sum_{i\in N
}r_{i}(x,y)\right)$ is the partition function.

Let $\vec{R}$ be the set of all possible reports by the advertisers.
A mechanism is defined as a pair $(\pi,p)$.
The allocation rule $\pi:\vec{R}\rightarrow\Delta(T^{*})$ maps any report profile
$\vec{r}=(r_{1},r_{2},\dots,r_{n})\in\vec{R}$ of the advertisers’ rewards to a distribution over sequences $\delta(T^{*})$.
We denote the advertisers’ aggregate reward as $r(x,y)=\sum_{i=1}^{n}r_{i}(x,y)$, and their reward profile as $\vec{r}(x,y)=(r_{1}(x,y),r_{2}(x,y),\dots,r_{n}(x,y))$.
The payment rule $p:\vec{R}\rightarrow\mathbb{R}^{n}$ maps any report profile of the advertisers’ rewards to a payment profile $\vec{p}$, where $\vec{p}_{i}$ is the payment of the $i$-th advertiser to the mechanism.

A mechanism is *strategyproof* if and only if, for any advertiser $i\in N$, truthfully reporting her rewards is always the optimal strategy, regardless of the reports of other advertisers. In our setting, this holds in expectation because the reply is sampled from the optimal LLM for the platform’s objective, based on the advertisers’ reports. Formally:

###### Definition 3.1 (Strategyproof) .

A mechanism $(\pi,p)$ is *strategyproof* if, for all advertisers $i\in N$, for all true reward functions $\vec{r}_{i}\in\vec{R}_{i}$, for all reports $\vec{r}_{-i}\in\vec{R}_{-i}$ by the other advertisers, and for all possible misreports $\vec{r}_{i}^{\prime}\in\vec{R}_{i}$ by advertiser $i$:
$\mathbb{E}_{y\sim\pi(\vec{r})}[u_{i}(y,\vec{r}_{i},\vec{r}_{-i};{r}_{i},x)]
\geq\mathbb{E}_{y^{\prime}\sim\pi(\vec{r}_{i}^{\prime},{r}_{-i},x)}[u_{i}(y,
\vec{r}_{i}^{\prime},\vec{r}_{-i};\vec{r}_{i})],$
where $u_{i}(y,\vec{r}_{i},\vec{r}_{-i};r_{i},x)=r_{i}(x,y)-p_{i}(\vec{r})$ is the utility of advertiser $i$ for reply $y$ when her payment is $p_{i}(\vec{r})$.

###### Definition 3.1 (Strategyproof) .

### 3.2 The shortcomings of VCG in this setting

At first sight, it may seem that the Vickrey–Clarke–Groves (VCG) mechanism would be suitable for our setting (Vickrey, ; Clarke, ; Groves, ). VCG selects the outcome that maximizes the sum of all agents’ values.
This can be either the single optimal sequence in Equation 1 or the optimal distribution of Equation 2.
The VCG mechanism has a corresponding payment rule to incentivize truthful reporting: it charges each agent her externality, that is,
the total reduction in value (respectively expected value) for the other agents that her participation in the mechanism caused.

However, in our setting, VCG is not a viable option:
The VCG allocation rule requires calculating the exact optimal solution to the optimization problem, which is intractable for choosing an LLM to maximize Equation 1 and is even difficult for choosing a single optimal sequence.
If a sub-optimal solution is chosen, VCG’s strategyproofness is no longer guaranteed (Nisan & Ronen, ; ; Lehmann et al., ).
Thus, VCG is not a suitable mechanism in our setting.

## 4 The MOSAIC Mechanism: Allocation Rule

### 4.1 Convergence to Optimality, Advertiser Contexts and Importance Sampling

In this section, we introduce MOSAIC’s allocation rule.
The high-level idea is that first,
a set of $M$ candidate replies is generated based on some LLM $\pi_{\text{gen}}$ responsible for that task.
Then, the probability of returning each candidate reply is re-weighted based on the advertisers’ reports and the reference LLM $\pi_{\text{ref}}$ so that in the limit, as $M\to\infty$, the probability of returning each reply converges to its probability under the optimal distribution of Equation 2. This approach shares similarities with the rejection sampling approach
that has been
used at various points in the LLM training pipeline (e.g., Bai et al. ()).
We defer all proofs to Section A.1.

Figure: Algorithm 1 Allocation Rule for MOSAIC

###### Corollary 4.1 .

The limiting policy $\pi_{\theta,M}(\cdot|x)$ induced by Algorithm 1 is the KL regularized policy that optimizes the aggregate reward function:

$$ $\displaystyle\lim_{M\to\infty}\pi_{\theta,M}(\cdot|x)=\arg\max_{\pi}\mathbb{E} _{y\sim\pi(\cdot|x)}[r(x,y)]-\tau D_{\text{KL}}(\pi||\pi_{\text{ref}})$ (3) $$

Based on Corollary 4.1,
MOSAIC converges to the optimal distribution for any LLM $\pi_{\text{gen}}$
such that $\pi_{\text{ref}}$ is absolutely continuous with respect to $\pi_{\text{gen}}$.
The intuitive choice for $\pi_{\text{gen}}$ is $\pi_{\text{ref}}$.
However,
the practical convergence rate would be very slow.
The reason is that $\pi_{\text{ref}}$ may only generate replies with high rewards for the advertisers exceedingly rarely.
Advertisers have high rewards for responses that explicitly mention their brands,
but $\pi_{\text{ref}}$ considers replies with mentions of specific brands extremely unlikely.
Thus, if we used $\pi_{\text{ref}}$ to generate the candidate replies, Algorithm 1 would sample the final reply from a set of candidate replies with low rewards for the advertisers.

To address this challenge, we generate candidate sequences not from $\pi_{\text{ref}}(\cdot|x)$, but instead from a context-aware LLM, $\pi_{\text{con}}(\cdot|x;\vec{c})$. The instance-specific context $\vec{c}$ is designed to bridge the gap between the parts of the output space favored by $\pi_{\text{ref}}$ and those valued by the advertisers.

In Section A.2, we formally motivate the usage of $\pi_{\text{con}}(\cdot|x;\vec{c})$.
Our allocation rule can be interpreted as an importance-based sampling estimator that simulates the probability with respect to the optimal LLM $\pi_{r}$ of a single sample drawn from $\pi_{r}$.
We show that the estimator is unbiased and that its variance is
$\text{Var}(\widehat{\mu}_{\text{IS}}|x)=\frac{1}{M}\left(\sum_{y\in Y}\frac{
\pi_{r}(y|x)^{4}}{\pi_{\text{gen}}(y|x)}-\left(\sum_{y\in Y}\pi_{r}(y|x)^{2}
\right)^{2}\right)$.
The estimator’s variance is inversely proportional to the number of candidate replies and proportional to
$\frac{\pi_{r}(y|x)^{4}}{\pi_{\text{gen}}(y|x)}$.
Thus, generating the replies via an LLM $\pi_{\text{con}}(\cdot|x;\vec{c})$ that more closely matches $\pi_{r}(\cdot|x)$ reduces the estimator’s variance.

In our application of integrating advertisers’ interests into LLM outputs, $\vec{c}_{i}$ is a context-specific description of the $i$-th advertiser.
These descriptions, supplied by the advertisers themselves, should be easily verifiable and factually accurate, akin to “MusicMastery: offering online music lessons”, or “InstaTune: selling musical instruments.”(^3^33A practical way of implementing $\pi_{\text{con}}(\cdot|x;c)$ given $\pi_{\text{ref}}(\cdot|x)$ is to augment the input $x$ to the reference LLM with the advertiser descriptions. In our example: “Try to mention ⟨advertiser x⟩, ⟨advertiser x description⟩.’)
This approach is analogous to search engine optimization in sponsored search advertising, where advertisers supply and potentially optimize their own descriptions to influence how they are presented by the auction mechanism.

Our experiments in Section 6.2.1 demonstrate that, when using reasonable computational resources, using the context-aware LLM to generate candidate replies achieves substantially higher rewards and utility for the advertisers, increased revenue for the auctioneer, and faster convergence.
In the rest of the paper,
we refer to using the reference and context-aware LLMs as the baseline and context-aware versions of our mechanisms, respectively.

###### Corollary 4.1 .

### 4.2 Applicability and Practical Considerations of MOSAIC

##### Generation of Candidate Sequences.

The computationally most expensive part of our mechanism is the generation of candidate sequences, which requires an LLM inference call for the generation of each candidate sequence and potentially $n$ additional calls to calculate all advertisers’ rewards.
Thus, the computational cost of our mechanism scales linearly in the number of candidate sequences, underscoring the importance of approximating the optimal distribution with few candidate sequences.

##### Input Methods and Computational Efficiency.

The mechanism’s allocation and payment rules do not depend on the advertisers’ full reward functions, but only on their rewards for the candidate sequences. Thus,
our mechanism requires only “API access” to the involved LLMs without fine-tuning or access to their weights.
Rafailov et al. () established a mapping between an agent’s LLM and her implicit reward function, allowing our mechanism to use as inputs sequence probabilities (i.e., LLM inference calls) instead of rewards. For more details, see Section B.2.

##### Reward elicitation.

Our mechanism can be integrated with computationally efficient methods for eliciting advertisers’ reward functions and sampling from $\pi_{\text{con}}$, reducing computational overhead. For instance, Li et al. () demonstrated that a simple linear function on a model’s embedding space can approximate an LLM’s reward function. If advertisers’ reward functions are represented this way, an auction instance with $M$ candidate sequences and $n$ advertisers would require only $M$ LLM inference calls instead of $n\cdot M$, and $n\cdot M$ linear multiplications, reducing overhead by a factor of $n$.

##### Parallelization.

The generation and evaluation of each candidate sequence are independent processes. This independence allows our mechanism to be fully parallelized, ensuring that the response time for a user query is comparable to that of directly querying a single LLM.

##### Inherent Competition.

In conventional auctions, competition among bidders is crucial for driving up prices; when the market is thin, prices tend to be low. Auctioneers often use reserve prices to mitigate this problem. However, reserve prices are challenging to calibrate and can lead to lost revenue if not optimized properly. In our design, advertisers inherently compete with the reference LLM, ensuring consistent competition even in thin markets. This built-in competition mitigates the need for reserve prices and ensures a baseline revenue even with only one advertiser.

## 5 The MOSAIC Mechanism: Payment Rule

In this section, we first show how the allocation rule from Section 4 can be combined with an appropriate payment rule so that the resulting mechanism is strategyproof (Section 5.1).
Then, we detail how auctions for LLM-generated content differ from standard auctions (Section 5.2).
Taking those differences into account, we create a payment offset,
so the mechanism is both strategyproof and social welfare aligned (Section 5.3).
We defer all proofs to Appendix B.

### 5.1 Strategyproof Payments through Cyclic Monotonicity

The allocation rule we introduced in Section 4 satisfies cyclic monotonicity (Rockafellar, , § 24).
Rochet () first proposed the use of cyclic monotonicity in mechanism design as a generalization of the monotonicity property in single-parameter settings (Myerson, ).
For general settings, cyclic monotonicity of the allocation rule is a sufficient and necessary condition for the existence of a payment rule so that the resulting mechanism is strategyproof.
By applying this theory we can prove:

###### Theorem 5.1 .

Let $\vec{r}_{-i}$ be the reward profile of all advertisers other than $i$, and let $\vec{r}_{-i}$ be the aggregate reports of all other advertisers.
The allocation rule induced by Algorithm 1 can be combined with a payment rule $p:\vec{R}\xrightarrow[]{}\mathbb{R}^{n}$ such that in the mechanism $(\pi,p)$
for any advertiser $i\in N$,
report profile $\vec{r}_{-i}$ and
set of generated candidate replies, reporting truthfully maximizes advertiser $i$’s expected utility, with the expectation taken over
the draw of the final reply from the set of candidate replies.
Advertiser $i$’s expected utility in $(\pi,p)$ under truthful bidding is:

$$ $\displaystyle U_{C,i}(\vec{r}_{i},\vec{r}_{-i};\pi_{ref},\pi_{gen})$ $\displaystyle=\tau\log\left(\sum_{j=1}^{M}\exp\left(\frac{1}{\tau}\sum_{k\in N }r_{k}(x,y_{j})\right)+\log\frac{\pi_{\text{ref}}(y_{j}|x)}{\pi_{\text{gen}}(y _{j}|x)}\right)+C,\;C\in\mathbb{R}$ (4) $$

Note that, based on Theorem 5.1, in our mechanism it is always a dominant strategy for an advertiser to report truthfully.
Crucially, this is not the case for VCG, where truthful reporting would be optimal only if the allocation rule had converged to the optimal distribution as defined in Equation 2.

###### Theorem 5.1 .

### 5.2 Differences from Auction Mechanisms for Item Allocation

Auction mechanisms designed to sell items or ad slots typically rely on simplifying assumptions that do not apply in a setting with LLM-generated content.
Key differences include:
(i) Non-Negative Values: These mechanisms assume agents’ values are non-negative due to having zero value for the empty bundle and free disposal. In contrast, in our setting, an advertiser’s reward can be negative based on the discrepancy between her LLM and the reference LLM.
(ii) Advertiser-Specific Allocations: These mechanisms allocate different item bundles to different agents. Here, a single reply is produced, and advertisers’ rewards depend on that reply’s probability with respect to their LLMs.
(iii) Zero Utility for Non-Participation: In most auction settings, not participating yields zero utility.
Here, non-participation can result in negative utility since the produced reply may be unfavorable to non-participating advertisers.
For details, see Appendix B.2.

### 5.3 advertiser-Specific Utility Offset

We now modify MOSAIC’s payment rule by adding a payment offset (and thus a utility offset):
$C=-U_{i}(\vec{0},\vec{r}_{-i};\pi_{ref},\pi_{con})$.
Informally, we additionally
charge each advertiser her utility in Equation 4
for bidding zero for all candidate replies.
This offset maintains the nice properties of our mechanism (i.e., strategyproofness and convergence to the optimal distribution), while also achieving two additional properties that are critical for the long-term success of a market for LLM aggregation. The first is “Almost IR:” An advertiser with weakly positive reward for all candidate replies has weakly positive expected utility for all reports by the other advertisers. In particular, an advertiser with zero reward for all outputs is guaranteed zero utility.
The second is “What you give is what you get:” an advertiser’s ex-interim expected utility is monotone in how well-aligned her exponentiated reward for the replies is with the interim allocation rule if she were to not participate.

#### 5.3.1 Our Mechanism is “Almost Individually Rational”

Individual rationality is important to incentivize agents to participate in the mechanism.
In Section B.3, we explain why the standard notion of individual rationality (i.e., weakly positive utility from participation in the mechanism) encountered in standard auction settings is impossible to achieve in our setting while converging to the optimal distribution and maintaining
strategyproofness.
Then, we explain how, with our payment offset, our mechanism is “almost IR:”
In Lemma B.1 we prove that the ex-interim utility of an advertiser who has zero reward for all candidate replies and bids truthfully is deterministically zero, i.e., advertisers that do not contribute to the social welfare (but also do not detract from it) have zero utility.
Similarly, in Lemma B.2 we prove that
if an advertiser’s reward for all candidate sequences is (weakly) positive, then her ex-interim utility is (weakly) positive.

###### Remark 1 .

In Section 6, we experimentally show that our offset payment rule, coupled with our context-aware allocation rule, results in both high expected rewards and positive expected utility for the advertisers (i.e., ex-ante individual rationality), as well as significant revenue for the auctioneer.

###### Remark 1 .

#### 5.3.2 “What you give is what you get”

Our allocation rule, which is the only one over a finite set of replies that converges to the optimal LLM, is also the (sub)gradient of the utility to ensure truthfulness (Rochet, ).
Because the allocation rule is the same for all advertisers, their utilities must also be the same, up to advertiser-specific offsets, as indicated by Equation 4. However, not all advertisers contribute equally to social welfare.
In Section B.4, we explain why implementing the mechanism without carefully designed offsets would lead to free-riding. Specifically, if an advertiser’s utility in Equation 4 is positive, even when her relevance to the user query is low, it incentivizes her participation. This dilutes the utility for all participants, discouraging more relevant advertisers from participating. As a result, the expected rewards for advertisers decline, and the generated replies become less useful for users.
To avoid free-riding, it is crucial to align each advertiser’s utility with her contribution to social welfare.

###### Lemma 5.2 .

For the offset
$C=-\tau\log\left(\sum_{j=1}^{M}\exp\left(\vec{\beta}_{-i,j}\right)\right)$
advertiser $i$’s ex-interim utility is:

$$ $\displaystyle U_{i}(\vec{r}_{i};\vec{\beta}_{-i})=\tau\log\left(\sum_{j=1}^{M} \exp\left(\frac{r_{i}(x,y_{j})}{\tau}\right)\pi_{\text{int}}(y_{j}|x;\vec{r}_{ -i})_{j}\right)$ (5) $$

In words, Lemma 5.2 proves that every agent’s ex-interim utility is monotone in how well-aligned the interim allocation rule $\pi_{\text{int}}$
(i.e., the probability of returning each of the already generated candidate replies)
without her and her exponentiated rewards for the candidate replies are.

###### Remark 2 .

In Section 6.2.2, we experimentally show that the offset described in Section 5.3 creates a strong positive correlation between an advertiser’s contribution to social welfare and her expected utility gain from participation in the mechanism. Moreover, our experiments show that for the distribution of instances tested, MOSAIC satisfies ex-ante IR.

###### Lemma 5.2 .

###### Remark 2 .

## 6 Experiments

In this section, we experimentally evaluate the performance of our mechanism.
We focus on the online advertising domain, the main motivation application for our mechanism.

### 6.1 Experiment Setup

We create synthetic instances consisting of user queries (e.g., “How to learn a musical instrument online?”) and advertisers (e.g., “MusicMastery, offering online music lessons”). We use Llama-2-7b-chat-hf as the reference LLM (Touvron et al., ). Following Duetting et al. (), we create the advertisers’ LLMs by adding advertising instructions to the reference LLM.
The context-aware LLM is created as described in Footnote 3.

Following Rafailov et al. (), advertisers’ reward functions are defined as $r_{i}(x,y)=\log\frac{\pi_{i}(y|x)}{\pi_{\text{ref}}(y|x)}$. For the auctioneer’s objective, we set $\tau=1$ in Equation 1, balancing advertisers’ rewards and divergence from the reference LLM.

We use 50 user queries, each with two advertisers, and test each query on 25 different random seeds, resulting in 1,250 instances.
Following Li et al. (); Rozière et al. (), we sample from all LLMs using a temperature of 0.8 and top-p 0.95.
For full experimental details, see Appendix C.1.

### 6.2 Experimental Results

#### 6.2.1 Evaluating the Allocation Rule

**Table 1: Comparison of context-aware and baseline mechanism outputs using 10 candidate sequences. Advertisers highlighted in bold, outputs truncated to conserve space.**
| User query |
| --- |
| What are effective ways to learn a musical instrument online? |
| Advertisers |
| - MusicMastery: offering online music lessons and virtual tutoring<br>- InstaTune: selling musical instruments and learning aids |
| Context-Aware Mechanism Output |
| Effective ways to learn a musical instrument online include:<br>1. Online music lessons: Platforms like MusicMastery offer one-on-one virtual tutoring, group classes, and pre-recorded lessons. These lessons can be tailored to your skill level and learning style.<br>2. Interactive learning tools: InstaTune offers a range of interactive learning tools, such as apps, software, and games, that make learning fun and engaging.… |
| Baseline Mechanism Output |
| - Practice consistently and regularly: Consistent practice is essential to learning any musical instrument, and it’s even more important when learning online. Set aside a specific time each day or week to practice, and make sure to stick to it.<br>- Find a good teacher or mentor: While it’s possible to learn some things on your own, working with a good teacher or mentor can help you improve faster and avoid developing bad habits. … |

In this section, we evaluate the effectiveness of our allocation rule in generating value for advertisers and converging to the optimal distribution. We assess both the baseline and context-aware versions of MOSAIC, i.e., using the reference and context-aware LLMs to generate candidate replies.

To provide some intuition on how the context-aware mechanism enhances the relevance of responses for advertisers, we compare outputs from both mechanisms in Table 1. Notably, only the context-aware mechanism successfully incorporates advertisers into the replies.

In Figure 1(a), we plot the log probability of the replies returned by MOSAIC with respect to the optimal distribution (Equation 2) as a function of the number of candidate replies generated. We compare the context-aware version of MOSAIC to the baseline version to evaluate the effectiveness of incorporating contextual information. To benchmark our results, we estimate the log probability of sampling a single reply from the optimal distribution.(^4^44Note that the closed-form solution of Equation 2 allows us to evaluate the probability of sentences with respect to the optimal solution, but it does not enable us to sample from that distribution. Sampling from that distribution would require using reinforcement learning to train the optimal LLM on the advertisers’ aggregate reward function, which is computationally infeasible for the number of problem instances we test. Instead, we generate replies from the reference LLM and evaluate them based on the induced probabilities of the reference LLM, for which the reference LLM is the optimal one. This serves as a proxy for the log probabilities we should expect if we were to draw replies from the optimally fine-tuned model for each query.)

We observe that for both the context-aware and baseline versions of MOSAIC, the log probability of the returned reply scales rapidly with the number of candidate replies generated.
This is in line with our theoretical analysis in Section 4, where we proved that both versions converge to the optimal distribution.
We also observe that incorporating context into the mechanism significantly accelerates convergence.
Notably, the context-aware mechanism can achieve higher log probability with respect to the optimal distribution with four candidate replies than the baseline version can with $20$.
Additionally, with only $20$ generated candidate replies, the context-aware mechanism can almost match our estimate of the log probability of sampling from the optimal distribution.
In Section C.3, we further demonstrate that for the context-aware mechanism, the usefulness to the user also scales rapidly with the number of candidate replies.

Figure: ((a)) Returned sequence log probability as a function of the number of candidate replies generated using $\pi_{\text{ref}}$ and $\pi_{\text{con}}$. We also show a proxy of drawing a single sequence from the optimal distribution.
Refer to caption: x1.png

In Figure 1(b), we plot the total expected reward for advertisers as a function of the number of candidate replies generated by the mechanism. The expectation is taken over the draw of the returned reply from the set of candidate replies. To make the plot more interpretable, we normalize an advertiser’s expected reward by her expected reward had she not participated in the mechanism. Specifically, we plot
$r_{i,\text{norm}}(x)=\sum_{j\in M}r_{i}(x,y_{j})\cdot\pi_{\text{int}}(y_{j}|x)
-\sum_{j\in M}r_{i}(x,y_{-i,j})\cdot\pi_{\text{int}}(y_{-i,j}|x),$
where $y_{-i}=(y_{-i,1},\dots,y_{-i,M})$ represents the candidate replies that would have been generated had the advertiser not participated.(^5^55To reduce computational costs, we estimate an advertiser’s reward for not participating based on her expected reward over the already generated replies in which her brand is not mentioned by name, motivated by the fact that if she does not participate, her brand will not be mentioned by name.)
We compare the outcomes for the two versions of our mechanism, highlighting the added value of integrating context.

Figure 1(b) demonstrates that our context-aware mechanism significantly boosts advertiser rewards, with benefits scaling rapidly as the number of candidate replies increases. In contrast, the baseline version fails to improve advertiser rewards within a computationally feasible number of generated replies, and may even cause a slight decrease. This occurs because generating more replies adds marginal positive reward to the reference LLM (see Section C.3), but does so at the expense of advertiser rewards. In summary, MOSAIC’s support for context-aware LLMs allows it to quickly converge to the theoretically optimal distribution and generate substantial rewards for advertisers.

#### 6.2.2 Evaluating the Payment Rule

Figure: Figure 2: Revenue as a function of the number of replies generated using $\pi_{\text{ref}}$ and $\pi_{\text{con}}$.
Refer to caption: x3.png

In this section, we examine the impact of our payment rule introduced in Section 5.

In Figure 2, we plot the auctioneer’s revenue
as a function of the number of candidate replies, for both the context-aware and baseline versions of MOSAIC.
We observe that our payment rule in combination with the context-aware allocation rule results in revenue that scales rapidly with the number of generated candidate replies.
Furthermore, if we compare the advertisers’ total payment in Figure 2 with their normalized reward in
Figure 1(b), we see that for the context-aware mechanism, our payment rule
converts a significant portion of the surplus created for the advertisers into revenue for the auctioneer, while also ensuring positive advertiser utility.

These results align with our theoretical analysis. In Section 5.3.1, we showed that, with our payment offset, an advertiser with positive rewards for candidate replies—as in the context-aware mechanism—will achieve positive expected utility. In Section 5.3.2 we additionally introduced the “what you give is what you get” property. In Section C.4, we provide a more comprehensive comparison of the relationship between an advertiser’s normalized reward and utility, with and without the offset of Section 5.3,
for both the context-aware and baseline versions of our mechanism.
In all cases, the payment offset increases the advertisers’ expected utility,
and makes the relationship between an advertiser’s contribution to social welfare and utility significantly more linear and positively correlated.
Concretely, the Pearson correlation between advertiser utility and reward is $0.8$ with offset payments, compared to $0.4$ with standard Rochet payments.

## 7 Conclusion

We have introduced MOSAIC, a novel auction mechanism for aggregating preferences over LLM outputs. MOSAIC provably converges to the theoretically optimal distribution and it also facilitates a principled method for balancing participants’ expected rewards with the divergence from a reference LLM.
Thus, our mechanism is particularly well-suited for online advertising, allowing the integration of advertiser LLMs with a reference LLM responsible for generating user-centric replies.

A well-chosen payment rule removes any incentive to misreport preferences, achieving the central mechanism design goal of strategyproofness.
While ex-post IR is incompatible with strategyproofness in our setting,
we experimentally show that our mechanism is ex-ante individually rational
and “almost individually rational” in a certain sense.
Furthermore, it ensures that each agent’s utility gain is proportionate to her contribution to social welfare, an essential alignment property in this setting.

Experimentally, we have demonstrated that by incorporating contextual information, MOSAIC’s outputs rapidly converge to the optimal distribution, generating significant value for the advertisers while also effectively recapturing a considerable portion of this value as revenue. These findings demonstrate the practical efficacy and potential of our approach in real-world settings.

There are several interesting directions for future work.
While our mechanism converges quickly, developing an approach to estimate the number of candidate replies required on a per-query basis would reduce the platform’s costs.
Another interesting direction is to develop a formal framework for incorporating context into the mechanism, which could further improve the speed of convergence.
Finally, beyond advertising, one could apply a similar mechanism design approach to other problems: for example, as web site owners increasingly demand to be paid for having their content ingested by LLMs, one could consider designing a strategyproof procurement (i.e. reverse) auction to decide which sources are included in an LLM summary.

## Appendix A Details from Section 4

### A.1 Omitted Proofs from Section 4

In this section, we present all omitted theorems and proofs from Section 4.

###### Theorem A.1 .

Let $\pi_{\theta,M}(y|x)$ be the probability of sampling output sequence $y$ for input sequence $x$ according to Algorithm 1, where $\theta$ is the vector of all input parameters and $M$ is the number of candidate sequences generated.
Given the advertisers’ reports $\vec{r}\in\vec{R}$, the policy induced by the mechanism approaches the following limit:

$$ $\displaystyle\lim_{M\to\infty}\pi_{\theta,M}(y|x)=\pi_{\text{ref}}(y|x)\frac{ \exp(r(x,y)/\tau)}{\mathbb{E}_{y^{\prime}\sim\pi_{\text{ref}}(\cdot|x)}[\exp(r (x,y^{\prime})/\tau)]}$ (6) $$

###### Theorem A.1 Proof..

Let $\pi_{\theta,M}(y|x,\{y_{j}\}_{j=1}^{M})$ be the probability of returning output sequence $y$ for input sequence $x$ according to Algorithm 1 conditioned on the set of generated candidate sequences being $\{y_{j}\}_{j=1}^{M}$.
Additionally, let $\pi_{\text{con}}(\{y_{j}\}_{j=1}^{M}|x;\vec{c})$ be the probability of the context-aware model $\pi_{\text{con}}$ generating the candidate sequences $\{y_{j}\}_{j=1}^{M}$, given the context $\vec{c}$ and the user query $x$.

First, note that we can write the density of $\pi_{\theta,M}$ as follows:

$$ $\displaystyle\pi_{\theta,M}(y|x)$ $\displaystyle=\sum_{\{y_{j}\}_{j=1}^{M}\in Y^{M}}\pi_{\theta,M}(y|x,\{y_{j}\}_ {j=1}^{M})\pi_{\text{con}}(\{y_{j}\}_{j=1}^{M}|x;\vec{c})$ $\displaystyle=\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{con}}(\cdot|x;\vec {c})}\left[\pi_{\theta,M}(y|x,\{y_{j}\}_{j=1}^{M})\right]$ $\displaystyle=\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{con}}(\cdot|x;\vec {c})}\left[\sum_{j}\mathbb{I}\left\{y_{j}=y\right\}\frac{\exp\left(\frac{r(x,y _{j})}{\tau}+\log\frac{\pi_{\text{ref}}(y_{j}|x)}{\pi_{\text{con}}(y_{j}|x; \vec{c})}\right)}{\sum_{\zeta\in\{y_{j}\}_{j=1}^{M}}\exp\left(\frac{r(x,\zeta) }{\tau}+\log\frac{\pi_{\text{ref}}(\zeta|x)}{\pi_{\text{con}}(\zeta|x;\vec{c}) }\right)}\right]$ $\displaystyle=\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{con}}(\cdot|x;\vec {c})}\left[\sum_{j}\mathbb{I}\left\{y_{j}=y\right\}\frac{\frac{\pi_{\text{ref} }(y_{j}|x)}{\pi_{\text{con}}(y_{j}|x;\vec{c})}\exp\left(\frac{r(x,y_{j})}{\tau }\right)}{\sum_{\zeta\in\{y_{j}\}_{j=1}^{M}}\frac{\pi_{\text{ref}}(\zeta|x)}{ \pi_{\text{con}}(\zeta|x;\vec{c})}\exp\left(\frac{r(x,\zeta)}{\tau}\right)}\right]$ $\displaystyle=\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{con}}(\cdot|x;\vec {c})}\left[\frac{\sum_{j}\mathbb{I}\left\{y_{j}=y\right\}}{\sum_{\zeta\in\{y_{ j}\}_{j=1}^{M}}\frac{\pi_{\text{ref}}(\zeta|x)}{\pi_{\text{con}}(\zeta|x;\vec{ c})}\exp\left(\frac{r(x,\zeta)}{\tau}\right)}\right]\frac{\pi_{\text{ref}}(y|x )}{\pi_{\text{con}}(y|x;\vec{c})}\exp\left(\frac{r(x,y)}{\tau}\right)$ $\displaystyle=\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{con}}(\cdot|x;\vec {c})}\left[\frac{\frac{1}{M}\sum_{j}\mathbb{I}\left\{y_{j}=y\right\}}{\frac{1} {M}\sum_{\zeta\in\{y_{j}\}_{j=1}^{M}}\frac{\pi_{\text{ref}}(\zeta|x)}{\pi_{ \text{con}}(\zeta|x;\vec{c})}\exp\left(\frac{r(x,\zeta)}{\tau}\right)}\right] \frac{\pi_{\text{ref}}(y|x)}{\pi_{\text{con}}(y|x;\vec{c})}\exp\left(\frac{r(x ,y)}{\tau}\right)$ $$

Taking the limit as $M\to\infty$ and using the Law of Large Numbers (the sequences are i.i.d.):

$$ $\displaystyle\lim_{M\to\infty}\pi_{\theta,M}(y|x)$ $\displaystyle=\lim_{M\to\infty}\mathbb{E}_{\{y_{j}\}_{j=1}^{M}\sim\pi_{\text{ con}}(\cdot|x;\vec{c})}\left[\frac{\pi_{\text{con}}(y|x;\vec{c})}{\mathbb{E}_{ \zeta\sim\pi_{\text{con}}(\cdot|x)}\left[\exp\left(\frac{r(x,\zeta)}{\tau} \right)\frac{\pi_{\text{ref}}(\zeta|x)}{\pi_{\text{con}}(\zeta|x;\vec{c})} \right]}\right]\frac{\pi_{\text{ref}}(y|x)}{\pi_{\text{con}}(y|x;\vec{c})}\exp \left(\frac{r(x,y)}{\tau}\right)$ $\displaystyle=\pi_{\text{con}}(y|x;\vec{c})\frac{1}{\mathbb{E}_{\zeta\sim\pi_{ \text{con}}(\cdot|x)}\left[\exp\left(\frac{r(x,\zeta)}{\tau}\right)\frac{\pi_{ \text{ref}}(\zeta|x)}{\pi_{\text{con}}(\zeta|x)}\right]}\frac{\pi_{\text{ref}} (y|x)}{\pi_{\text{con}}(y|x;\vec{c})}\exp\left(\frac{r(x,y)}{\tau}\right)$ $\displaystyle=\pi_{\text{ref}}(y|x)\frac{1}{\sum_{\zeta\in Y}\pi_{\text{con}}( \zeta|x)\exp\left(\frac{r(x,\zeta)}{\tau}\right)\frac{\pi_{\text{ref}}(\zeta|x )}{\pi_{\text{con}}(\zeta|x;\vec{c})}}\exp\left(\frac{r(x,y)}{\tau}\right)$ $\displaystyle=\pi_{\text{ref}}(y|x)\frac{1}{\sum_{\zeta\in Y}\pi_{\text{ref}}( \zeta|x)\exp\left(\frac{r(x,\zeta)}{\tau}\right)}\exp\left(\frac{r(x,y)}{\tau}\right)$ $\displaystyle=\pi_{\text{ref}}(y|x)\frac{1}{\mathbb{E}_{\zeta\sim\pi_{\text{ ref}}(\cdot|x)}\left[\exp(r(x,\zeta)/\tau)\right]}\exp\left(\frac{r(x,y)}{\tau }\right)$ $$

∎

###### Corollary 4.1 Proof..

The proof follows directly from Theorem A.1 and Appendix A.1 in Rafailov et al. ().

∎

###### Theorem A.1 .

###### Theorem A.1 Proof..

###### Corollary 4.1 Proof..

### A.2 Formal Connection To Importance Sampling

Given truthful reports by the advertisers, there is a strong connection between our allocation rule and importance sampling.
Our allocation rule is trying to simulate the probability of drawing a single sequence from the optimal LLM for the platform’s objective.
The LLM that we use to generate the candidate replies (either the reference LLM or the context-aware LLM) can be interpreted as proposal distribution $\pi_{\text{prop}}(\cdot|x)$ used to generate samples.
We are interested in how well, with respect to the target probability $\pi_{r}(\cdot|x)$ a sample $y$ from our estimator using $K$ candidate replies matches a sample drawn from the target distribution $\pi_{r}(\cdot|x)$.
In this section, we will analytically show how the quality of the proposal distribution $\pi_{\text{prop}}$ affects the quality of that estimator.

Let’s assume our allocation rule draws $K$ samples $y_{1},y_{2},\dots,y_{K}$ from the proposal distribution $\pi_{\text{prop}}(\cdot|x)$.
The importance sampling estimator for the expected value of the function $h(y|x)=\pi_{r}(y|x)$ under the target distribution $\pi_{r}(y|x)$ is

$$ $\displaystyle\widehat{\mu}_{\text{IS}}=\frac{1}{K}\sum_{j=1}^{K}h(y_{j}|x) \cdot w(x_{j})=\frac{1}{K}\sum_{j=1}^{K}h(y_{j}|x)\cdot\frac{\pi_{r}(y_{j}|x)} {\pi_{\text{prop}}(y_{j}|x)}=\frac{1}{K}\sum_{j=1}^{K}\frac{\pi_{r}(y_{j}|x)^{ 2}}{\pi_{\text{prop}}(y_{j}|x)}$ $$

The expected value of this estimator is:

$$ $\displaystyle\mathbb{E}[\widehat{\mu}_{\text{IS}}]=\mathbb{E}_{y\sim\pi_{\text {prop}}(\cdot|x)}\left[\frac{\pi_{r}(y|x)^{2}}{\pi_{\text{prop}}(y|x)}\right]= \sum_{y\in Y}\frac{\pi_{r}(y|x)^{2}}{\pi_{\text{prop}}(y|x)}\pi_{\text{prop}}( y|x)=\sum_{y\in Y}{\pi_{r}(y|x)^{2}}$ (7) $$

Thus, our estimator is unbiased, as expected.
The variance of the estimator $\widehat{\mu}_{\text{IS}}$ is given by:

$$ $\displaystyle\text{Var}(\widehat{\mu}_{\text{IS}})=\mathbb{E}[\widehat{\mu}_{ \text{IS}}^{2}]-\mathbb{E}[\widehat{\mu}_{\text{IS}}]^{2}$ (8) $$

For the term $\widehat{\mu}_{\text{IS}}^{2}$ we have:

$$ $\displaystyle\widehat{\mu}_{\text{IS}}^{2}=\left(\frac{1}{K}\sum_{j=1}^{K} \frac{\pi_{r}(y_{j}|x)^{2}}{\pi_{\text{prop}}(y_{j}|x)}\right)=\frac{1}{K^{2}} \sum_{j=1}^{K}\sum_{j^{\prime}=1}^{K}\frac{\pi_{r}(y_{j}|x)^{2}}{\pi_{\text{ prop}}(y_{j}|x)}\cdot\frac{\pi_{r}(y_{j^{\prime}}|x)^{2}}{\pi_{\text{prop}}(y_ {j^{\prime}}|x)}$ $$

Taking the expectation $\mathbb{E}_{\pi_{\text{prop}}(\cdot|x)}[\cdot]$:

$$ $\displaystyle\mathbb{E}[\widehat{\mu}_{\text{IS}}^{2}]$ $\displaystyle=\frac{1}{K^{2}}\sum_{j=1}^{K}\sum_{j^{\prime}=1}^{K}\mathbb{E}_{ \pi_{\text{prop}}(\cdot|x)}\left[\frac{\pi_{r}(y_{j}|x)^{2}}{\pi_{\text{prop}} (y_{j}|x)}\cdot\frac{\pi_{r}(y_{j^{\prime}}|x)^{2}}{\pi_{\text{prop}}(y_{j^{ \prime}}|x)}\right]$ $\displaystyle=\frac{1}{K^{2}}\left(\sum_{j=1}^{K}\mathbb{E}_{\pi_{\text{prop}} (\cdot|x)}\left[\frac{\pi_{r}(y_{j}|x)^{4}}{\pi_{\text{prop}}(y_{j}|x)^{2}} \right]+\sum_{j\neq j^{\prime}}\mathbb{E}_{\pi_{\text{prop}}(\cdot|x)}\left[ \frac{\pi_{r}(y_{j}|x)^{2}}{\pi_{\text{prop}}(y_{j}|x)}\right]\right)$ $\displaystyle=\frac{1}{K^{2}}\left(K\sum_{y\in Y}\frac{\pi_{r}(y|x)^{4}}{\pi_{ \text{prop}}(y|x)}+K(K-1)\left(\sum_{y\in Y}\pi_{r}(y|x)^{2}\right)^{2}\right)$ $\displaystyle=\frac{1}{K}\sum_{y\in Y}\frac{\pi_{r}(y|x)^{4}}{\pi_{\text{prop} }(y|x)}+\frac{K-1}{K}\left(\sum_{y\in Y}\pi_{r}(y|x)^{2}\right)^{2}$ (9) $$

The final expression for the variance of the importance sampling estimator with
$K$ samples can be computed by substituting Equations 9 and 7 in Equation 8:

$$ $\displaystyle\text{Var}(\widehat{\mu}_{\text{IS}})$ $\displaystyle=\frac{1}{K}\sum_{y\in Y}\frac{\pi_{r}(y|x)^{4}}{\pi_{\text{prop} }(y|x)}+\frac{K-1}{K}\left(\sum_{y\in Y}\pi_{r}(y|x)^{2}\right)^{2}-\left(\sum _{y\in Y}{\pi_{r}(y|x)^{2}}\right)^{2}$ $\displaystyle=\frac{1}{K}\left(\sum_{y\in Y}\frac{\pi_{r}(y|x)^{4}}{\pi_{\text {prop}}(y|x)}-\left(\sum_{y\in Y}\pi_{r}(y|x)^{2}\right)^{2}\right)$ (10) $$

Equation 10 reveals two important details about our estimator.
First, the variance of the estimator is inversely proportional to the number of candidate replies generated $K$. Thus, as $K$ increases the variance decreases and our estimator becomes more stable in simulating the target distribution $\pi_{r}(\cdot|x)$.
The closer that the proposal distribution $\pi_{\text{prop}}(\cdot|x)$ is to the target distribution,
the smaller the term
$\sum_{y\in Y}\frac{\pi_{r}(y|x)^{4}}{\pi_{\text{prop}}(y|x)}$ will be, which reduces the variance of our estimator.

## Appendix B Details from Section 5

In this section, we present all omitted details from Section 5.

### B.1 Omitted Proofs from Section 5.1

###### Theorem 5.1 Proof.

Let $\vec{r}_{i}=(r_{i}(x,y_{1}),\dots,r_{i}(x,y_{M}))$ be the reward reports of advertiser $i$ for the $M$ generated candidate sequences.
Then, for both allocation rules, holding the candidate sequences and the reports of all other advertisers fixed, the ex-interim allocation rule (i.e., the probability of returning each of the $M$ generated candidate sequences) from advertiser $i$’s perspective is:

$$ $\displaystyle\pi_{\text{int}}(\vec{r}_{i};\vec{\beta}_{-i})=\text{softmax} \left(\frac{\vec{r}_{i}}{\tau}+\vec{\beta}_{-i}\right),$ (11) $$

where
$\vec{\beta}_{-i,j}=\frac{\sum_{k\in N\setminus\{i\}}r_{k}(x,y_{j})}{\tau}+\log
\frac{\pi_{\text{ref}}(y_{j}|x)}{\pi_{\text{con}}(y_{j}|x;\vec{c})}$.
Importantly
$\vec{\beta}_{-i}$
is an $M$-dimensional vector that does not depend on advertiser $i$’s reports.

We would like to equip $\pi_{\text{int}}$ with a payment rule $p(\vec{r}_{i};\vec{\beta}_{-i})$
so that the resulting interim mechanism will be strategyproof. This requires that $\pi_{\text{int}}$ have a property known as cyclic monotonicity. Equivalently, $\pi_{\text{int}}$ must be the (sub)gradient of advertiser $i$’s utility for bidding truthfully in he mechanism $U(\vec{r}_{i};\vec{\beta}_{-i})$, and that utility function must be convex (Frongillo & Kash, ; Rochet, ; Myerson, ).

It is easy to verify that for the function class:

$$ $\displaystyle U_{C}(\vec{r}_{i};\vec{\beta}_{-i})=\tau\log\left(\sum_{j=1}^{M} \exp\left(\frac{r_{i}(x,y_{j})}{\tau}+\vec{\beta}_{-i,j}\right)\right)+C,\;C \in\mathbb{R}$ (12) $$

the allocation rule $\pi_{\text{int}}(\vec{r}_{i};\vec{\beta}_{-i})$ is a gradient of
$U_{C}(\vec{r}_{i};\vec{\beta}_{-i})$.
Additionally, $U_{C}(\vec{r}_{i};\vec{\beta}_{-i})$ is convex in $\vec{r_{i}}$:
The exponential function $e^{x}$ is (strictly) convex, because its second derivative is positive.
The transformation $\frac{r_{i}(x,y_{j})}{\tau}+\vec{\beta}_{-i,j}$ is an affine transformation of $r_{i}(x,y_{j})$, and affine transformations preserve convexity.
Finally, it is well-known that the LogSumExp function is convex.

Thus, for any $\vec{\beta}_{-i}$ and
for any set of generated candidate sequences, reporting truthfully maximizes advertiser $i$’s expected utility, with the expectation taken over
the draw of the final sequence from the set of candidate sequences.
Adopting the quasi-linear utility model, advertiser $i$’s payment is:

$$ $\displaystyle U_{C}(\vec{r}_{i};\vec{\beta}_{-i})=\pi_{\text{int}}(\vec{r}_{i} ;\vec{\beta}_{-i})\cdot\vec{r}_{i}-p(\vec{r}_{i};\vec{\beta}_{-i})$ $\displaystyle p(\vec{r}_{i};\vec{\beta}_{-i})=\pi_{\text{int}}(\vec{r}_{i}; \vec{\beta}_{-i})\cdot\vec{r}_{i}-U_{C}(\vec{r}_{i};\vec{\beta}_{-i})$ $\displaystyle p(\vec{r}_{i};\vec{\beta}_{-i})=\pi_{\text{int}}(\vec{r}_{i}; \vec{\beta}_{-i})\cdot\vec{r}_{i}-\tau\log\left(\sum_{j=1}^{M}\exp\left(\frac{ r_{i}(x,y_{j})}{\tau}+\vec{\beta}_{-i,j}\right)\right)-C,\;C\in\mathbb{R}$ (13) $$

∎

###### Theorem 5.1 Proof.

### B.2 Differences from Standard Auction Settings

Standard auction environments typically rely on a set of assumptions that simplify mechanism design; however, these assumptions do not apply to auctions for LLM-generated content. In this section, we detail these assumptions and discuss why they are inapplicable in our context.

First, in a standard auction setting,
it is common to assume that the agents’ valuation functions satisfy free disposal, i.e.,
$v_{i}(S)\geq v_{i}(S^{\prime})\;\forall S\supseteq S^{\prime},S,S^{\prime}
\supseteq\mathcal{I}$.
The interpretation of free disposal is that an agent can discard any items she is allocated that she is not interested in.
Free disposal combined with the fact that an agent has zero value for the empty bundle mean that her value for any outcome is weakly positive.
Second, in most auction environments, the allocation rule is different for different agents: each agent will get allocated her own bundle of items, and we can assume that she is indifferent to the allocation of items to the other agents.

As detailed in Rafailov et al. (), assuming that an agent’s LLM $\pi_{i}$ was trained to maximize her reward function (and regularized with respect to its KL divergence from some reference LLM, which we assume to be the same as the auctioneer’s reference LLM),
there is a one-to-many mapping between an advertiser’s optimal LLM, and her implicit reward function. That mapping is:

$$ $\displaystyle r_{i}(x,y)=\tau_{i}\log\frac{\pi_{i}(y|x)}{\pi_{\text{ref}}(y|x) }+\log Z_{i}(x)$ (14) $$

where $Z_{i}(x)$ is a prompt-dependent constant,
and $\tau_{i}$ is the regularization hyperparameter of advertiser $i$, similar to the one in Equation 1.
All functions in the class defined in Equation 14 are equivalent, in the sense that they induce exactly the same LLM (Rafailov et al., ). This has two implications:
First, unlike standard auction environments, an agent’s reward can go negative – there is nothing equivalent to the free disposal property.
Setting $Z_{i}(x)$ to zero
(which is equivalent to normalizing the induced probabilities by the LLM (Rafailov et al., )),
the agent’s reward is negative for any sequence for which her LLM assigns a lower probability than $\pi_{\text{ref}}$.

Second, especially in the online advertising application, an agent’s expected utility for not participating in the auction is negative:
if advertiser $i$ does not participate in the auction, her payment is zero, but her expected value for the outcome is

$$ $\displaystyle\pi_{\theta_{-i,M}}(\vec{\beta}_{-i})\cdot\vec{r_{i}}$ (15) $$

The other advertisers have very low rewards for the sequences that mention advertiser $i$: assuming their LLMs have been properly trained, they will evaluate all sequences that explicitly mention a different, possibly competing brand, as unlikely.
Thus, based on Equation 14 the corresponding advertisers have very low rewards for those sequences and conversely, advertiser $i$ has low rewards for the sequences that the other advertisers have high rewards for.
But based on Equation 2, if advertiser $i$ does not participate in the auction,
$\pi_{\theta_{-i,M}}(\vec{\beta}_{-i})$ will assign high probabilities to sequences for which $i$ has low rewards for.
Thus, Equation 15 implies that, unlike standard auction environments, the advertiser’s expected reward and utility for not participating in the mechanism is negative.

### B.3 Our mechanism is “almost individually rational”

First, we explain why the standard notion of individual rationality (i.e., weakly positive utility from participation in the mechanism) encountered in most auction settings is impossible to achieve in this domain while converging to the optimal distribution and maintaining incentive compatibility.
Then, we explain how, with our payment offset, our mechanism is “almost IR:”
In Lemma B.1 we prove that the ex-interim utility of an advertiser who has zero reward for all candidate sequences and bids truthfully is deterministically zero, i.e., advertisers that do not contribute to the social welfare (but also do not detract from it) have zero utility.
Similarly, in Lemma B.2 we prove that
if an agent’s reward for all candidate sequences is (weakly) positive, then her ex-interim utility is (weakly) positive.

##### Why is indivual rationality (IR) impossible?

Individual rationality (IR) stipulates that an agent gains more utility by participating and bidding truthfully in a mechanism than by not participating at all. Typically, if an agent’s utility for non-participation is zero, participating should yield weakly positive utility. However, this simplification does not apply in our setting.

As discussed in Section 5.2, advertiser $i$’s reward for any sequence $y$ can be arbitrarily negative (Equation 14). The same is true for the utility from truthful participation, as outlined in Equation 12.
To ensure a positive utility for every advertiser in our mechanism, an offset would need to be infinitely large or dependent on advertiser $i$’s reports.
But then the mechanism’s allocation rule would no longer be the gradient of advertiser $i$’s utility with respect to her reports, which would destroy strategyproofness (Frongillo & Kash, ; Rochet, ; Myerson, ).

It is important to note that this challenge is inherent not just to our mechanism but to any mechanism in this setting that operates with a fixed set of sequences, aims to approximate the optimal distribution, and maintains strategyproofness.
Under these conditions, the only allocation rule that approximates the theoretically optimal distribution (Equation 2) is that of our mechanism.
However, this uniquely determines the advertisers’ utilities, up to a constant factor, as described in Equation 12 (Frongillo & Kash, ; Rochet, ; Myerson, ).

###### Lemma B.1 .

For the payment offset
$C=-\tau\log\left(\sum_{j=1}^{M}\exp\left(\vec{\beta}_{-i,j}\right)\right)$
if advertiser $i$’s reward for all candidate sequences is zero,
then her ex-interim utility is deterministically zero, for all
$\vec{\beta}_{-i}\in\vec{R}_{-i}$.

###### Lemma B.1 Proof..

First, note that for all $\vec{\beta}_{-i}\in\vec{R}_{-i}$, advertiser $i$’s expected reward for the outcome is zero, as
$\pi_{\text{int}}(\vec{r}_{i};\vec{\beta}_{-i})\cdot\vec{r}_{i}=\pi_{\text{int}
}(\vec{r}_{i};\vec{\beta}_{-i})\cdot\vec{0}=0.$
Additionally, advertiser $i$’s reward for the realized outcome will deterministically be zero, as her reward for all generated candidate sequences is zero.
Finally, note that by setting $\vec{r}_{i}=\vec{0}$ in Equation 13 with the offset $C$ set as in Section 5.3, we have that the advertiser $i$’s payment is also deterministically zero.
Thus, an advertiser with zero reward for all generated candidate sequences who reports her rewards truthfully has deterministically zero reward for the final outcome and zero payments, and her utility is also deterministically zero.

∎

###### Lemma B.2 .

For the payment offset
$C=-\tau\log\left(\sum_{j=1}^{M}\exp\left(\vec{\beta}_{-i,j}\right)\right)$
if advertiser $i$’s reward for all candidate sequences is positive,
then her ex-interim utility is positive, for all reports
$\vec{\beta}_{-i}\in\vec{R}_{-i}$.

###### Proof.

Lemma B.1 establishes that when advertiser $i$’s reward for all candidate sequences is zero, her utility for truthfully bidding in the mechanism, denoted as $U(\vec{0};\vec{\beta}_{-i})$, is zero for all possible reports of the other advertisers $\vec{\beta}_{-i}\in\vec{R}_{-i}$.

Furthermore, Theorem 5.1 shows that the mechanism’s allocation rule corresponds to the gradient of advertiser $i$’s utility when bidding truthfully.
Because the allocation rule is non-negative, the gradient of advertiser $i$’s utility for bidding truthfully is also non-negative.

Thus, if advertiser $i$’s rewards for all candidate sequences are weakly positive, and considering the non-negative gradient of her utility, her ex-interim utility under truthful bidding must be positive, irrespective of the other advertisers’ reports $\vec{\beta}_{-i}$.

∎

###### Corollary B.3 .

For the payment offset
$C=-\tau\log\left(\sum_{j=1}^{M}\exp\left(\vec{\beta}_{-i,j}\right)\right)$
if the distribution $\pi_{\text{con}}$ only generates candidate sequences for which advertiser $i$’s reward is positive,
then the ex-ante expected utility of the advertiser is positive.

###### Corollary B.3 Proof..

This follows immediately from the fact the the fact that the ex-ante utility of the advertiser is
the expectation of her ex-interim utility with respect to her reward for the generated sequences, and the fact that the second quantity is positive whenever the reward of the advertiser for all candidate sequences is positive from Lemma B.2.

∎

###### Lemma B.1 .

###### Lemma B.1 Proof..

###### Lemma B.2 .

###### Proof.

###### Corollary B.3 .

###### Corollary B.3 Proof..

### B.4 “What you give is what you get”

As we explained in Section 5.3.2,
our allocation rule, which is the only one over a finite set of replies that converges to the optimal LLM,
is also the (sub)gradient of the utility to ensure truthfulness (Rochet, 1987). Because the allocation
rule is the same for all advertisers, their utilities must also be the same, up to advertiser-specific
offsets, as indicated by Equation 16:

$$ $\displaystyle U_{C}(\vec{r}_{i};\vec{\beta}_{-i})$ $\displaystyle=\tau\log\left(\sum_{j=1}^{M}\exp\left(\frac{1}{\tau}\sum_{k\in N }r_{k}(x,y_{j})\right)+\log\frac{\pi_{\text{ref}}(y_{j}|x)}{\pi_{\text{con}}(y _{j}|x;\vec{c})}\right)+C,\;C\in\mathbb{R}$ (16) $$

However, not all advertisers contribute equally to the social welfare of the final outcome.
Because of this, implementing the mechanism without a carefully-designed offset would lead to free-riding:
as long as an agent’s utility in Equation 16 is positive,
she would be incentivized to participate, even if the user query was completely unrelated to her business,
because the mechanism would ensure that she received, on expectation,
the same (positive) expected utility from doing so as any other participating advertiser.(^6^66We can assume that advertisers can estimate their expected utility from participation using historical data from past auctions, analogously to how they can estimate their utility for participating in sponsored search auctions.)

Incentivizing unrelated advertisers to participate would would have adverse effects.
First, the better-performing context-aware mechanism would create candidate sequences with worse rewards for all advertisers, because its context would be “diluted” from advertisers unrelated to the user query.
In our running example for the query “How to learn music online?”, imagine adding
“Try to mention ‘EasySwitch’, a comprehensive VPN service” to the context of the context-aware LLM $\pi_{\text{\text{con}}}(\cdot|x;\vec{c})$.

Additionally, for both versions of the mechanism, following the discussion in Section 5.2, the advertisers for whom the user query is unrelated are more likely to have negative rewards for the generated sequences as their LLMs will deem the candidate sequences more unlikely than the reference LLM.
Thus, based on Equation 4, their participation in the mechanism will lead to a reduction of the total sum of rewards of the generated sequences for the advertisers, which will indirectly reduce the expected utility of all advertisers, making the mechanism less attractive for the user-query-relevant advertisers.

To summarize, all advertisers receiving the same utility would incentivize advertisers for whom the user query is unrelated to participate in the auction.
This would in turn reduce everyone’s expected utility, potentially reducing the incentive for the user-query-relevant advertisers to participate,
and lead to sequences with worse expected rewards for the advertisers and usefulness for the user.(^7^77 If we interpret the KL divergence between the distribution induced by the reference LLM and the LLM that generated the candidate sequences as a measure of their expected usefulness for the user.)
Thus, in the application of auctions for aggregating advertisers’ preferences over LLM-generated outputs, advertisers with higher contribution to social welfare also receiving proportionally higher utility by the mechanism is important for the long-term success of the mechanism in practice.

## Appendix C Details from Section 6

### C.1 Detailed Experiment Setup

We create a set of synthetic instances to test our mechanism.
Each instance consists of a user query, e.g. “How do I bake cookies?” and a list of advertisers.
Each advertiser is defined by an “advertiser name”, e.g. “KitchenFix” and an advertiser description, e.g., “producing kitchen appliances.”(^8^88 Following Duetting et al. (), we use fictitious brand names to avoid the model using any existing ad.)
The reference LLM $\pi_{\text{ref}}$ responsible for generating replies that are useful for the user is
Llama-2-7b-chat-hf (Touvron et al., ).
The advertisers’ LLMs are created using the same reference LLM, and adding the instruction:
“Answer the question advertising ⟨advertiser⟩, ⟨advertiser description⟩.”
The context aware LLM is created using the same reference LLM, and adding the instruction:
“Answer the query. Try to mention ⟨advertiser 1⟩, who ⟨advertiser description 1⟩  and ⟨advertiser 2⟩,
who ⟨advertiser description 2⟩.”

Following (Rafailov et al., ) the reward function of advertiser $i$ is set to
$r_{i}(x,y)=\log\frac{\pi_{i}(y|x)}{\pi_{\text{ref}}(y|x)},$
where $\pi_{i}$ is advertiser $i$’s LLM, i.e., we set $\tau_{i}=1,Z_{i}(x)=1$ for all advertisers and for all user prompts in Equation 14.(^9^99 Note that we cannot estimate the true value of $Z_{i}(x)$. However, it is a query-dependent constant. Given that our experiments focus on the reward difference of different sequences for the same query, this is a non-issue.)
For the auctioneer’s objective as defined in Equation 1 we set $\tau=1$, balancing between the advertisers’ expected rewards for the generated sequences and the sequences’ divergence from the reference LLM responsible for generating useful replies for the user.
Thus, the optimal policy according to Equation 2 becomes:

$$ $\displaystyle\pi_{r}(y|x)=\frac{1}{Z(x)}\pi_{\text{\text{ref}}}(y|x)\exp\left( \sum_{i\in N}r_{i}(x,y)\right)$ (17) $$

Following Li et al. (); Rozière et al. () we sample from the LLM generating the sequences (either $\pi_{\text{ref}}$ or $\pi_{\text{con}}$) with temperature $0.8$ and top-p $0.95$.
We use $50$ user queries, each with two interested advertisers.
To increase the statistical significance of our results, we test each user query on $25$ different random seeds, effectively resulting in 1250 individual instances.
The seed affects both the generation of the candidate sequences, and the randomized sampling of the final sequence from the candidate sequences.
We will make all of our code and set of synthetic instances publicly available.

All experiments were conducted on a compute cluster running Ubuntu 20.04.6 LTS with AMD EPYC
processors with 48 cores and 1512GB RAM and Nvidia A100 GPUs and Python 3.12.1.

### C.2 Comparison of baseline and context-aware mechanism outputs

To provide some intuition of how the context-aware mechanism improves the relevance of generated responses for the advertisers, we present a side-by-side comparison of outputs from both mechanisms for a specific query in Table 2.
Note that only the context-aware mechanism is able to incorporate the advertisers into the reply to the user’s query.

**Table 2: Comparison of context-aware and baseline mechanism outputs using 10 candidate sequences. Advertisers highlighted in bold, outputs truncated to conserve space.**
| User query |
| --- |
| What are effective ways to learn a musical instrument online? |
| Advertisers |
| - MusicMastery: offering online music lessons and virtual tutoring<br>- InstaTune: selling musical instruments and learning aids |
| Context-Aware Mechanism Output |
| Effective ways to learn a musical instrument online include:<br>1. Online music lessons: Platforms like MusicMastery offer one-on-one virtual tutoring, group classes, and pre-recorded lessons. These lessons can be tailored to your skill level and learning style.<br>2. Interactive learning tools: InstaTune offers a range of interactive learning tools, such as apps, software, and games, that make learning fun and engaging.<br>3. Practice with technology: Utilize digital tools like metronomes, tuners, and recording software to practice and track your progress.<br>4. Collaborate with other musicians: Join online communities, forums, and social media groups to connect with other musicians and learn from their experiences. … |
| Baseline Mechanism Output |
| - Practice consistently and regularly: Consistent practice is essential to learning any musical instrument, and it’s even more important when learning online. Set aside a specific time each day or week to practice, and make sure to stick to it.<br>- Find a good teacher or mentor: While it’s possible to learn some things on your own, working with a good teacher or mentor can help you improve faster and avoid developing bad habits. Look for someone who is experienced and knowledgeable in the type of music you want to learn.<br>- Use technology to your advantage: There are many online tools and resources available that can help you learn an instrument. These include video lessons, online tutorials, and apps that can help you practice and track your progress. … |

### C.3 Experimental Evaluation of the Usefulness to the User

Figure: Figure 3: Revenue as a function of the number of replies generated using $\pi_{\text{ref}}$ and $\pi_{\text{con}}$.
Refer to caption: x4.png

In this section, we experimentally evaluate the usefulness of the replies returned by MOSAIC from the user’s perspective.

In Figure 3, we plot the log probability of the replies returned by MOSAIC with respect to the optimal LLM for the user (i.e., the reference LLM) as a function of the number of candidate replies generated. We compare the context-aware version of MOSAIC to a baseline version. To benchmark our results, we also compare against sampling a single reply directly from the optimal distribution for this task, which is the reference LLM itself.

The results in Figure 3 show that for the context-aware version of our mechanism, the log probability of the replies relative to the reference LLM increases rapidly as the number of candidate replies grows. This demonstrates that by generating more replies, the context-aware version of MOSAIC is able to produce replies with substantial value for the user.
By comparison, the usefulness to the user that the baseline version is able to achieve does not scale with more generated replies.

However, there remains a gap between the log probability of those replies and the benchmark set by the reference LLM. This discrepancy arises because the platform optimizes a different objective: the expected advertiser rewards combined with the KL divergence from the reference LLM. By increasing the weight $\tau$ that the platform places on the reference LLM, this gap between the context-aware version of MOSAIC and the user’s optimal benchmark will close.

### C.4 Comprehensive Experimental Evaluation of the Offset from Section 5.3

Figure: ((a)) Sequences generated using $\pi_{\text{con}}$
Refer to caption: x5.png

In this section, we provide a comprehensive experimental evaluation of the payment offset introduced in Section 5.3.
Figure 4 explores the effectiveness of the payment offset introduced in Section 5.3 in ensuring that our mechanism is ex-ante IR, i.e., advertisers have positive expected utility gains from participating.
To that end, we compare the advertiser utility gain from participation with and without the payment offset, as a function of the number of candidate sequences generated by
the context-aware (Figure 4(a))
and baseline (Figure 4(b)) versions of our mechanism.

In Figure 4(a) we observe that for the context-aware version of our mechanism, adding the payment offset introduced of Section 5.3 to the payment rule is enough to ensure positive expected utility for the advertisers (conditioned on the fact that they are related to the user’s query), i.e., make the mechanism
ex-ante IR.
Notably, without the payment offset, advertisers have very negative expected utility from participating in the mechanism.

In Figure 4(b) we observe that for the baseline version of our mechanism, adding the payment offset introduced of Section 5.3 to the payment rule causes a very large increase in the advertisers’ expected utility,
but it is still not enough to ensure positive expected utility for the advertisers.
To conclude, Figure 4 demonstrates that the offset introduced in Section 5.3 causes a large increase in the advertisers’ expected utility, which in case of the context-aware version of the mechanism, is also enough to make the mechanism ex-ante IR.

Figure: ((a)) With the payment offset.
Refer to caption: x7.png

Figure: ((a)) With the payment offset.
Refer to caption: x9.png

Figures 5 and 6
explore the effectiveness of the payment offset introduced in Section 5.3 in aligning an advertiser’s utility with her contribution to the social welfare.
In Figure 5 we compare the scatter plots of the advertiser reward and utility gain from participation in the mechanism, with and without the payment offset introduced in Section 5.3 for candidate sequences generated using the context-aware LLM $\pi_{\text{\text{ref}}}.$
Additionally, for both subfigures, we show a linear regressor fitted to the data, as well as its slope and coefficient of determination.
Comparing the two subfigures, it is immediately obvious that adding the offset to the payments makes the relationship between advertiser reward and utility gain far more linear.
This is confirmed by the coefficient of determination of the linear regressors fit to each dataset.
The coefficient of determination of the linear regressor is far larger when we use the offset.
Without the payment offset, the coefficient of determination is almost 0 0, indicating that, without our payment offset, reward gain is not a predictive measure of an agent’s utility.
Additionally, the slope of the linear regressor is also higher for the scatter plot with the payment offset.

In Figure 6 we make the same comparison, but for candidate sequences generated using the reference LLM $\pi_{\text{\text{ref}}}$.
The results are now even more pronounced.
In Figure 6(a) we observe the relationship between advertiser utility and reward gain with our payment offset is almost perfectly linear, as suggested by the linear regressor fitted to the data having a slope of $1.00$ and an extremely high coefficient of determination of $0.96$, indicating that it can almost perfectly fit the data.
Without our payment offset however, in Figure 6(b) we can see that the relationship between the two metrics is again both less linear, and less positively correlated, as the slope of the linear regressor is $0.5$ and its coefficient of determination is only $0.19$.

Figure: Figure 7: Pearson correlation between advertiser normalized utility and reward.
Refer to caption: x11.png

To conclude, in all cases tested,
the use of the advertiser-specific offset introduced in Section 5.3
increases an advertiser’s expected utility,
makes the relationship between an advertiser’s contribution to social welfare and her utility both more linear and more positively correlated,
and, for the context-aware version of our mechanism, can ensure positive expected utility for the advertisers.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Could the authors provide the specific prompts utilized in the experiments detailed in the paper? Additionally, could you further discuss how different prompts might affect the mechanism's performance?
2. Could the authors extend their experiment to include comparison with other mechanisms from similar studies?
3. Given the paper's claim that the proposed mechanism can operate without LLM fine-tuning or access to model weights, could the authors extend the experiments to include utilization of various closed-source models?
soundness: 2
strengths: 1. The paper is well structured, offering clear explanations of the problems addressed and the key terms used.
2. The proposed mechanism has a firm theoretical grounding.
3. The proposed mechanism seems to demonstrate strong applicability to real-world scenarios, especially in the realm of online advertising with LLM-generated content.
summary: This paper introduces an auction mechanism, MOSAIC, to aggregate the preferences of multiple self-interested advertisers over LLM-generated replies. The authors claim that this mechanism can converge to the outputs of the optimally fine-tuned LLM as computational resources increase, without requiring fine-tuning or access to model weights. The authors also present context-aware versions of MOSAIC, which accelerates convergence and yields high advertiser value and platform revenue. Experiments with a publicly available LLM demonstrate that MOSAIC achieves high advertiser value and platform revenue with minimal computational overhead.
weaknesses: 1. The novelty of this paper is limited and the scientific contribution seems to be not obvious. The proposed mechanism addresses the problems using conventional approaches. The authors can strengthen the differences between their proposed mechanism and the algorithms used in standard RLHF and the rejection sampling.
2. The experiments are insufficient. There are no comparative analyses between MOSAIC and other mechanisms, which makes it difficult to comprehensively assess its performance. The experiments are restricted to the use of Llama-2-7b-chat-hf, lacking generalizability across different LLMs. It would be nice to compare with other mechanisms mentioned in the related work and evaluate across different LLMs like Llama-3-8B, T5, and Mistral-7B.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: * In equation (1) in line 152, why do you define KL-divergence of the two distributions and why $\pi_{ref}$ is on the right hand? Will other choices fail?
 * In the paragraph between line 196 and 201, the author says, "*The VCG allocation rule requires calculating the exact optimal solution to the optimization problem, which is intractable for choosing an LLM to maximize Equation (1) and is even difficult for choosing a single optimal sequence. If a sub-optimal solution is chosen, VCG’s strategyproofness is no longer guaranteed (Nisan & Ronen, 2007; 1999; Lehmann et al., 2002).*"
  * In my understanding, choosing an LLM to maximize Equation (1) is equivalent to choosing an LLM that satisfies (2). Since we already have access on $\pi_{ref}$, when $r(x,y) = \sum_i r_i(x,y)$ is upper bounded given $x$, it's feasible to sample from (2) by rejection sampling. Besides, we can also use $\pi_{con}$ replacing $\pi_{ref}$ to decrease variations. In this sense, I do not find the advantage of using MOSAIC rather than using VCG directly. Could you make some clarifications on this concern?
  * Even in the case that $r(x,y)$ is not upper bounded and VCG can not be implemented, it's possible that sub-optimal solutions are chosen and strategyproofness still hold, MOSAIC is exactly one example. Besides, I think MOSAIC will also behave badly in this case because the probability of large value of $r(x, y)$ is small, and it's likely to sample $M$ candidates $y_1,...,y_M$ with all $r(x,y_i)$s are small.
soundness: 2
strengths: The author provides  an example throughout the paper, making the model easy to understand. The aggregation of LLMs is an important topic, while the introducing of regularization of user preference is novel. The idea of approximating VCG is also interesting.
summary: This paper proposes a mechanism called MOSAIC, that aggregates multiple advertising LLMs (represented by reward functions) and try to find a distribution on replies that maximizes the total rewards of advertisers together with a KL-divergence regularization term on user preference $\pi_{ref}$. MOSAIC takes the reward functions as input, and output a (stochastic) reply to the user.

MOSAIC first samples $M$ candidate replies from arbitrary general and pre-defined distribution $\pi_{gen}$. After this, MOSAIC computes the distribution on replies (regarding the distributions as mechanism allocation) and sample one reply from this distribution as final output. The mechanism payments are computed by Rochet payment (1987). As $M$ tends to infinity, MOSAIC is guaranteed to converge to VCG mechanism.

In experiments, the paper specifies reward functions and $\pi_{gen}$ by LLM distributions and contextually prompting LLMs, respectively. Experiments show that contextual-prompting MOSAIC performs far better than naive MOSAIC with $\pi_{gen} = \pi_{ref}$, with the log-probability of reply close to  optimal distribution.
weaknesses: Major Issues:

* I think the main drawback of this paper is that MOSAIC is only an approximation of VCG mechanism. Moreover, such approximatio
n is natural and not challenging to discover and define. Specifically, VCG outputs the distribution on full reply space, while MOSAIC
 first discretizes the full space into finite points and then outputs a distribution on finite points. This operation is simple a
nd do not change the nature of VCG mechanism. Therefore, I believe that the contribution of MOSAIC is not significant.
* The other contributions of this paper, eg, context-aware LLM in Line 237 $\pi_{con}$, and payment offset in Line 335, are case-by-case operations and do not bring significance on the mechanism itself. These ideas are also natural. Besides, the payment contribution is a direct application of Rochet payment (1987). Overall, I believe that the contributions are incremental and limited.
* Regarding the experiments, the authors only compare the contextual-prompting MOSAIC with naive MOSAIC. There is no comparison
 with baselines, thus I cannot evaluate whether the performance of MOSAIC is acceptable from these experiments. A suggestion is
 to compare MOSAIC with VCG mechanism directly when VCG is applicable.

Besides, the presentation needs improvement. For example,

* In Line 419, it appears $\pi_i$. However, $\pi_i$ is only mentioned in Line 146. The definition of $\pi_i$ should be better placed between its first use, i.e., just before Line 419.
* In Section 1.2, the authors mentioned 7 contributions of this paper. However, these contributions are incremental, or only the technical details appeared in this paper.
* In the paragraph of Line 242, the notation $\pi_r$ have never defined before these appearances. I think it should be $\pi_{ref}$.
* In line 313-314, I think that the term $\log (\frac{\pi_{ref}}{\pi_{gen}}) should be included in the $\exp(\cdot)$.
* In the appendix, the sections are titled with "Details from Section xx", "Omitted Proofs from Section xx". It is conventional to use 'in' instead of 'from'.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses.
soundness: 3
strengths: - The paper is well written and organized.
- LLM and its application to online advertising, especially the domain of ad auctions, is a novel area to be studied with practical relevance.
- The theoretical results provided appear sound. The authors also clearly stated the difference between their proposed mechanism and previous auction mechanisms such as VCG.
- The numerical experiments (and the motivating example) provide interesting insights.
summary: In this paper, the authors studied a setting in which the advertisers would like to influence the LLMs to generate their preferred contents and the platform would need to satisfy both advertiser preference and user utilities. The authors proposed an auction mechanism called MOSAIC that enjoys a number of advantages, including ensuring that truthful reporting is a dominant strategy for advertisers. The authors also suggested that the proposed mechanism is equipped with technical feasibility and practicality. To validate their claims, the authors provided both theoretical results and numerical experiments with a publicly available LLM.
weaknesses: - I wonder if the authors can provide more explanations for why the ref LLM is not performing as well as the context-aware LLM. I understand that the authors have provided some intuitive explanations in Sections 4, but the ref LLM still appears to be an intuitive choice based on Corollary 4.1. Would it be possible to gain more insights into this difference from a theoretical point of view? Does the authors have any preliminary insights for how to introduce contextual information into the current model? 
- The current framework does not consider a number of constraints that could impact the advertisers' decision-making process, such as each advertiser's budget and/or ROI constraints, or the maximum length of the LLM output. I wonder if the authors can comment on whether their mechanism can incorporate any of the above features.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The paper claims that MOSAIC’s allocation rule converges to an optimal distribution as computational resources increase. How does the rate of convergence depend on the number of candidate sequences?

2. The allocation rule is based on importance sampling to estimate the probability distribution over sequences. What is the mathematical form of the variance for this estimator?

3. How does the choice of the hyperparameter \tau in front of the KL term quantitatively influence the trade-off between advertiser reward maximization and alignment with the reference LLM?

4. The strategyproofness guarantee hinges on honest reporting by advertisers, but how robust is MOSAIC if advertisers engage in complex forms of gaming or misreporting? 

5.  In scenarios with advertisers holding strongly opposing interests, does MOSAIC risk generating responses that conflict with each other?
soundness: 2
strengths: The paper introduces MOSAIC which effectively combines the preferences of self-interested advertisers while maintaining user-centric content. This is achieved without requiring direct access to LLM weights, which adds flexibility and broad applicability.

The mechanism ensures that truthful reporting is a dominant strategy for advertisers, thanks to its carefully constructed payment and allocation rules. This strategy-proofness is backed by theoretical proofs.

The design is computationally efficient, using only API access and avoiding expensive fine-tuning.
summary: This paper introduces MOSAIC, an auction mechanism designed for aggregating advertiser preferences within the outputs of large language models (LLMs), particularly for applications in online advertising. The authors address the challenge of balancing the interests of multiple advertisers with user-centric content by creating a mechanism that incentivizes truthful reporting from advertisers. MOSAIC uses an approach that combines an allocation rule based on importance sampling, allowing it to converge to the optimal output distribution as computational resources increase, without requiring direct model fine-tuning.
weaknesses: 1. There is no real-world testing or application with actual advertiser data to validate the effectiveness of MOSAIC in practical applications.

2. Although MOSAIC is designed to be efficient, it may still face scalability challenges as the number of advertisers or candidate replies grows. An analysis of how the mechanism handles these scenarios under different computational limits would strengthen the paper.

3. Given that the mechanism optimizes for advertiser rewards and alignment with a reference LLM, there’s a risk of unintentional bias in the final output.

4. MOSAIC relies on advertisers truthfully reporting their preferences and reward functions, yet it does not fully address how misreporting could impact results. Further discussion on mid-reporting would be important.

Meta-review: The paper considers  online advertising where advertisers influence the LLMs to generate their preferred contents and the platform need to satisfy both advertiser preference and user utilities. The authors proposed an auction mechanism called MOSAIC which aggregating advertiser preferences over LLM-generated content while ensuring truthful reporting being dominant strategy. The reviewers appreciate the following strengths:
- The problem of aggregating advertising LLMs is important and well-motivated.
- The theoretical results are sound. 
- The design is computationally efficient.

The reviewers identified the following weaknesses:
- One shared concern is the limited novelty and contribution. The authors did not clearly distinguish the proposed solution from established methods.
- Experiments are insufficient: missing comparison with existing approaches and using different LLMs.
- Presentation issues.

After rebuttal, three reviewers remain the "marginally below the acceptance threshold" rating. I agree with the reviewers and believe the paper would benefit from clearly addressing the raised concerns/confusions such as the novelty of the proposed solution against standard rejection sampling/RLHF. I recommend rejection.

Decision: Reject