Truthful Aggregation of LLMs with an Application to Online Advertising
Authors: Ermis Soumalias
Michael Curry
Sven Seuken
Venue: NeurIPS 2025 poster ()
Keywords: Market Design
LLMs
Large Language Models
Auctions
Economics and Computation
LLM Aggregation
Online Advertising Auctions
Preference Aggregation
Primary area: theory
TL;DR: We create an ad auction mechanism for LLM-generated content that ensures truthful advertiser behavior, aligns utility with social welfare, and provably converges to optimal LLM outputs.

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, 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. Via experiments with publicly available LLMs, we show that MOSAIC leads to high advertiser value and platform revenue with low computational costs. 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.

Truthful Aggregation of LLMs with an Application to Online Advertising
Ermis Soumalias University of Zurich ETH AI Center ermis@ifi. uzh.ch
Michael J. Curry University of Illinois Chicago mj cejceciccccm edu
Sven Seuken University of Zurich ETH AI Center
seuken@ifi. .uw.iiiiii.......... ch
Abstract
The next frontier of online advertising revenue generation from LLM- L.M-generated content. We consider setting where advertisers aim to influence the responses an LLM, 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 each advertiser with their contribution 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 resourees increase. Additionally, it can incorporate contextual information about advertisers, which significantly improves social welfare. Via experiments with publicly available LLMs, we show that MOSAIC leads to high advertiser value and platform revenue with low computational costs. While our mechanism can be applied in any setting with monetary transfers, making it veneral-purposs solution for truthfully aggregating the preferences of self- interested agents over LLM-generated replies.
motivating application is online advertising,
Introduction
Large language models (LLMM) are becoming ubiquitous: as coding assistants, chat interfaces, and even alternatives search engines [Bommasani al., 2022]. 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 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, the main source of revenue for large tech companies such as Google, Meta, and X. For example, in 2023, Meta's ss advertising revenue of 132 billion USD constituted workhorse mechanism to determine the placement and prices of commercial content [ [Varian, 2007, Edelman et al., 2007]. LLM providers have begun integrating instant checkout capabilities into their services [OpenAI, 2025), and they are also exploring how to incorporate ads into LLM LLM-generated content [Criddle, 2024]. Thus, new auction mechanisms needed for this emerging setting.
than 97% of its total revenue [Meta, 2024). Ad auctions the
We present a new auction mechanism for this problem, which we call MOSAIC (Mechanism for Optimally Sampling and Aggregating LLM Outputs with Incentive Compatibilltyy. The advertisers are paying, not for some particular item or bundle, but rather to influence the output generated by an LLM in direction closer to their own preferences. Although MOSAIC could be of interest whenever one has to aggregate the preferences of multiple self-interested agents over LIMM behavior (as long as
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

it is reasonable to charge 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
We consider a situation where a user queries an LLM with a specific question. We assume the following: (i) There is reference I.IM that can produce useful replies to the user's query, and (ii) there are advertisers who want to influence the reply to the user. In our model, each advertiser is represented via her fine-tune LLMs in the Reinforcement Learning from Human Feedback pipeline [Azar et al., 2023]. For this reason, we refer to an advertiser's value for a reply as her reward. The auctioneer's s task is, given the user's 's query and the advertisers' preferences, to produce a reply that is useful for the user while also generating high rewards for the advertisers.
LLM directly with reward function, similar the function used to
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 replics. 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 (c.g.. Ziegler et al. [2020]), 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 LLM mechanism design literature that both provably converges to the optimal distribution (Corol- lary 4.1) and converges efficiently in practice (Section 6). Third, MOSAIC can incorporate contextual information, similar to how sponsored search auctions utilize advertiser descriptions, accelerating convergence and increasing value for advertisers and revenue for the auctioneer (Section 6.2).
Fourth, we address technical feasibility and practicality. We adopt the desiderata proposed by Dütting et al. [2024], who argued that auctions must be compatible with existing LLM technology, only using "information obtainable from current models" in a way that is "easy to integrate into the system" and relying 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 design MOSAIC to work by only post-processing multiple LLM outputs: 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 LLMs), analogous to peer//under-bidding in traditional auctions. To address this challenge, we employ an allocation rule compatible with Rochet payments [Rochet, 1987]. These uniquely ensure that MOSAIC is strategyproof, i.e., that truthful reporting is dominant strategy for each advertiser, no matter what the others do (Theorem 5.1). Crucially, Rochet payments ensure that MOSAIC remains strategyproof even if the mechanism has not fully converged to the optimal LLM.
Sixth, introduce offset the Rochet payments ensure that each advertiser's utility is proportional to her contribution to social welfare. This alignment is crucial for the long-term success of the market, incentivizes the participation of only the most relevant advertisers.
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 well-defined sense. In Section 6.2, experimentally show that, MOSAIC 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 L.M 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
In their pioneering work, Dütting et al. [2024] introduced the field of mechanism design for LLMs, proposing sequential mechanism where the output sequence is generated token by token, and advertisers bid for their LLM to produce the next token. This work laid the foundation for future work in this area. However, several challenges hinder the adoption of their approach the real world: (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 certain point, only for the continuation to unexpectedly negate or distort her intended message. (ii) The mechanism is easily manipulable if the assumption that advertisers cannot misreport their LLMs is dropped. (iii) For given prompt, an advertiser's 's spend grows with the length of the generated sequence. MOSAIC addresses all of the above challenges.
Dubey et al. [2024] proposed generalization of the position auction [Varian, 2007, Edelman et al., 2007] to a setting where each advertiser is interested in having some specific text ad displayed alongside the organic results. In their mechanism, an L.M module coupled with an auction module work in tandem to merge the ads into a single ad summary an incentive-compatible way.
Hajiaghayi et al. [2024] 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 in contrast to MOSAIC, which allows the aggregation of full LLMs that advertisers may arbitrarily misreport.
In work that appeared after the initial version of this paper, Bergemann et al. [2024] study mechanism design problem where agents have both private types and signals, one motivation of which is to model generalization of our problem. For further discussion of related work, see Appendix A.
3 Framing Sequence Generation as a Mechanism Design Problem
3.1 Formal Model
A user issues query There is a reference LLM Tee that the auctioneer aims not to deviate from too much (e.g., because is responsible for providing useful replies to the user). Additionally, there is set N of n advertisers who have their own preferences for the reply (i.e., token sequence) that will be returned to the user. We use the terms sequence and reply interchangeably.
We let r (2, y) denote advertiser i's reward for reply y. given query x.2 Informally, the auctioneer's s goal is to sample the final reply from distribution that optimizes the advertisers' expected rewards without substantially diverging from Nee. This is motivated by traditional online ad auctions, where the implicit goal is to maximize advertiser value subject to ensuring a chosen level of usefulness to the user (e.g.. the balance between allocating search slots to ads and native content). In the context of an LLM environment, the analogous notion of "usefulness to the user" is represented by the closeness of the final distribution to Wee- Formally, the goal is to choose maximize:
E Byna
Σ re v) LiN
where - > 0 is a hyperparameter enabling the auctioneer to balance producing replies closer to the reference LLM or with higher reward for the advertisers, and DKL is the Kullback-Leibler divergence.
This objective is analogous to the standard Reinforcement Learning from Human Feedback (RLHF) approach [Ziegler et al., 2020], but replaces the human feedback reward function with the advertisers' aggregate reward rxx, y) = ΣiEN ra rx( y). For an overview of RLHF, see Rafailov et al. [2023, $3).
As an example, suppose advertiser A wins the bids for all the tokens in the sequence "Planning your next vacation? For the cheapest flights book via..." However, she loses the bid for the crucial next token, her brand name. She thus pays for the preceding tokens without benefiting from associating her brand with the message. IIn theory. an advertiser's 's reward for generated reply could also depend on user-specific information, but we abstract that away. Equivalently, assume that the advertisers provide user-specific reward functions.
3

---

The optimal solution ग. to the optimization problem in (1) was derived by Peters and Schaal [2007]:
(y|z)) 2(x)
T T exp
Σ rr(2z, n((o,v)) w)
(2)
IEN
where =(x)=E = Eyer- [e((y>>) exp (+ EiEN (x B)) is the partition function.
The performance goal we seek to maximize is log ( + EieN Te( y); as it aggregates the interests of both the user and all the advertisers, we refer to it as the social welfare of y.
Let R be the set of all possible reports by the advertisers. A mechanism is defined as a pair (TT, p). The allocation rule π Rt + (T* + )(T*)) maps any report profile F == (f1, (2,-/2,.-- ,., fnn) E of the advertisers' rewards to an L.M My, which turn is a mapping from a user query x to a distribution over token sequences 8(T*). We denote the LLM that the allocation rule induces for reports f as Tp, and the optimal LLM for those reports (i.e., the maximizer of Equation (1)) as TT.. The payment rule p: Rt - RR maps any report profile f to a payment profile p(f), where (f) is the payment of the i-th advertiser. We aim for strategyproof mechanisms, meaning that no advertiser has an incentive to misreport her preferences:
Definition 3.1 (Strategyproof), A mechanism p) is strategyproof if. for any advertiser E N, true reward function ri, reported reward function function is reported reward functions P- by the other advertisers and prompt x: (o (ra( y) - fr): 2 Ry-ssos-o(ia (T(( y) - pe(fi, where re(x,,) v) f=(,,, is the utility of advertiser i for reply y when her payment is p: f-)).
3.2 The shortcomings of VCG in this setting
At first sight, it may seem that the Wikrey-Clarkk
(VCG) mechanism would be suitable for our setting [Vickrey, 1961, Clarke, 1971, Groves, 1973]. VCG selects the outcome that maximizes the sum of all agents' values. This can be either single optimal sequence for Equation (1) or the optimal distribution of Equation (2). The VCG mechanism has corresponding payment rule to incentivize truthful reporting: charges each agent her externality, 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 viable option: VCG requires calculating the exact optimal solu- tion to the optimization problem, which is intractable for choosing an L.M to maximize Equation (1) and is even difficult for choosing a single optimal sequence. If a sub-optimal solution is chosen, VCG's prrofesysroofness is no longer guaranteed [Nisan and Ronen, 2007, 1999, Lehmann et al., 2002]. We provide an intuitive example illustrating this failure for two advertisers in Appendix B.
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 as follows: first, set of M candidate replies is generated based on an LLM Tgen- Then, the probability of returning each candidate as MM + co, the return probability of each reply converges to that under the optimal distribution of Equation (2). This approach resembles importance sampling techniques that have been used in various LLM training pipelines (e.g., Xie et al. [2023]). All proofs are deferred to Appendix B.
re-weighted based on the advertisers' reports and the reference LLM Tret so that
Corollary 4.1. For any reported reward functions E and any LLM gen such that Kne absolutely continuous with respect to geens the MOSAIC policy Nr.M (-1x), from Algorithm 1, using M candidate replies, converges to an optimal solution for the platform's 's objective (Equation (1)) as M + 0o. Formally, limu oo0 Tr,a0 (-1x:) (-1x) E arg max [r)=(-) w)] -7 Drx ( (T())
Based on Corollary 4.1, MOSAIC converges to the optimal distribution for any LLM π Tgen- provided that गeर is absolutely continuous with respect to Tgen- While Tga Tee is an intuitive choice, would result in impractically slow convergence rates. The reason is that advertisers have high rewards for responses that explicitly mention their brands, but nhe considers replies with mentions of specific brands extremely unlikely. Consequently, generating candidate replies directly from कee leads Algorithm I to sample from set of low-reward candidates, hindering performance.

---

Algorithm 1: Allocation Rule for MOSAIC
Input:
User prompt I, reference L.MM Reef LLM used for candidate reply generation Tggnn advertiser reward functions (ri) number of candidate replies to generate M, reference LLM weight r
Output: Reply y drawn according to the optimal distribution as defined in Equation (1) for the
aggregate reward function r(x, y) = > (z.
Sample Vj ~ Tgan (-)2,, S M
Calculate r(z, Uů) = Di=1 rr( 3o) 1 M
3 return y ~ softmax
r(z.9))
log
rla.ve)
+ log Barly (x) gige (2
181
To address this challenge, we generate candidate sequences from [-er(- but instead from a context-aware LLM, Toon (oo((-);;c) c). The instance-specific context e is designed to bridge the gap between the parts of the output space favored by गet and those valued by the advertisers.
We formalize this intuition in Appendix B.3, connecting MOSAIC's allocation rule to an importance- based sampling estimator for x and proving the following lemma:
Lemma 4.2. For any LLM Tgen such that Te is absolutely continuous with re- spect to genn the variance of TrM((1x) as an estimator of (1)=;())) is (yl2) (gn(((
M E Eger
Applying Chebyshev's inequality the variance of Lemma 4.2, MOSAIC converges to π. a rate (yla))
of VM (Lemma B.3).² However, this convergence also depends Taa [y]
=)) Thus, generating
replies via an LLM closer to म. reduces the estimator's variance and improves convergence speed.
In our application of integrating advertisers' interests into LLM outputs, 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 "InstaTTune: selling musical instruments." "4 This approach analogous to search engine optimization in sponsored search advertising, where advertisers supply and potentially optimize their own descriptions influence how they are presented by the auction mechanism.
Our experiments in Section 6.2 demonstrate that 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 the baseline and context-aware aware versions of our mechanism, respectively.
4.2 Practical Considerations
Input Methods and Black-Box Access to Advertiser LLMs. MOSAIC's allocation and payment rules do not depend on the advertisers' full reward functions, but only on their rewards for the candidate replies. Thus, MOSAIC requires only "API access" to the involved LLMs without fine- tuning or access to their weights. Rafailov et al. [2023] established a mapping between an agent's LLM and her implicit reward function, allowing MOSAIC to use as inputs reply probabilities (i.e., LLM inference calls) instead of rewards. For more details, see Appendix C.2.
Static Setting and Incentive Implications. The number M of candidate replies considered by MOSAIC is predetermined. Each advertiser observes all M candidate replies before submitting her reports, resulting in static rather than a dynamic setting (e.g., as in Dütting et al. [2024]), where advertisers interact sequentially with evolving information, significantly complicating incentive considerations. Theorem 5.1 ensures that truthful reporting is dominant strategy for each advertiser.
'In Appendix B.4 we establish a more general result, showing that for any sequence y. its estimated probability converges to the corresponding probability under n² a rate 1/ I/M
'A practical way of implementing Tean (=o[(-1;; e) given (=e(-1())) (z) is to augment the input to the reference LLM with the advertiser descriptions. In our example: "Try mention (advertiser x). (advertiser x description)."
5

---

Complexity. Generating a single candidate reply of length L tokens requires L forward passes through Wgens as tokens are generated sequentially an autoregressive manner. Evaluating each reply processes the entire sequence in a single forward pass (and is compatible with efficient evaluation methods, e.g. Li al. [2024]). For M candidate replies and n advertisers, MOSAIC requires (L n 1) total forward passes. In contrast, Dütting et al. [2024] require I.-n forward passes, as all n advertiser LLMs participate in generating each token. Section shows that MOSAIC achieves convergence with M- 20 candidate replies, reducing computational cost for large
Compatibility with Efficient Methods and Practical Costs. MOSAIC relies solely on LLM forward passes, the core operation modern architectures are optimized for, enabling it to take full advantage of existing optimizations for efficient generation. As a result, MOSAIC converges to the optimal distribution with compute costs equivalent to just five LLM queries (Appendix D.8).
Parallelization and Eser-Pereeived Latency. The generation and evaluation of each candidate sequence are independent processes, allowing MOSAIC to be fully parallelized. In fully parallelized setting, the response time for a user query is comparable to directly querying a single LLM.
Inherent Competition. Unlike conventional auctions, MOSAIC ensures high baseline revenue even in low-competition environments, as advertisers always compete against Tel- Traditional auctions rely reserve prices boost revenue, but slight miscalibration above critical threshold result in zero revenue. In contrast, MOSAIC uses a single tunable parameter, т, and its revenue varies smoothly and differentiably with (see the proof of Theorem 5.1). As result, revenue optimization in MOSAIC is significantly more robust to parameter tuning.
An " "Autobidder" Perspective the Mechanism. In practice, advertiser might not have the know-how to produce an LLM reflecting their preferences. In conventional online ad auctions, two existing practices are used solve a similar problem: platforms offer tools to help advertisers improve ad quality, and they provide autobidders to help advertisers bid. The largest online advertising platforms have the capacity to host and finetune L.Ms,, so they already have the infrastructure offer an "LLM autobidder." Concretely, they could train an LLM for an advertiser, reflecting the advertiser's s interests, and they could also provide inference. Even under this "autobidder" implementation, all properties of our mechanism are preserved.
5 The MOSAIC Mechanism: Payment Rule
In this section, 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 ALM--generate content differ from standard auctions (Section 5.2). Taking those differences into account, we create a payment offset, so that MOSAIC is both strategyproof and social welfare-aligned (Section 5.3). We defer all proofs to Appendix C.
5.1 Strategyproofness through Cyclic Monotonicity
The allocation rule of Algorithm 1 satisfies cyclic monotonicity [Rockafellar, 1970, $ 24). Rochet [1987] first proposed the use of cyclic monotonicity in mechanism design as a generalization of monotonicity in pagle-parameter settings [Myerson, 1981]. For general settings, cyclic monotonicity of the allocation rule is a sufficient and necessary condition for us to prove:
Theorem 5.1. The allocation rule of Algorithm I can be combined with puyment rule such that for any advertiser E N and set of candidate replies {y, } reporting truthfully a dominant strategy. Advertiser i's expected utility (up constant of integration C') under truthful reporting is:
Fr(r,,f-::TT ) = C¹ + rlg 1==
exp
+ +log TTee (e)
Note that, based on Theorem 5.1, in MOSAIC 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 (Example l).

---

5.2 Differences from Standard Auction Seftings
Auction mechanisms designed to sell items or ad slots typically rely on simplifying assumptions that do not apply in a setting with -LMe-eenrrtted 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) Severtiser-Specciee
Allocations: These mechanisms allocate different item bundles to different agents. Here, a single reply is produced (iii) Zero Utility for Von-Participation
In most auction settings, not participating yields zero utility, Here, non-participation can result negative utility since the produced reply may be unfavorable to non-participating advertisers. For details, see Appendix C.2.
5.3 Advertiser-speeific Utility Offset
We now modify MOSAIC's payment rule by adding payment offset (and thus utility offiset): -= -0, Fref, Teon): ). Informally, we additionally charge each advertiser her utility in Theorem 5.1 her reward for all candidate replies was zero. This offset maintains the key properties of our mechanism (i.e., straegyyrroffeee and convergence 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. The second is "What you give is what you get:" an advertiser's 's 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 "Almost Individually Rational"
Individual rationality is important to incentivize agents to participate in the mechanism. In Ap- pendix C.3, we explain how the unique properties of our setting, namely lack of free disposal and common outcome for all agents, make the standard notion of individual rationality (i.e., weakly positive utility from participation) unobtainable while converging to the optimal distribution and maintaining strategyproofness. Then, we explain how, our payment offset achieves "almost IR:" In Lemma C. we prove that the expected utility of an advertiser who has zero reward for all candidate replies and bids truthfully is zero, i.c., advertisers that do not contribute to the social welfare (but also do not detract from it) have zero utility. Similarly, in Lemma C.2 we prove that an advertiser's reward for all candidate sequences is (weakly) positive, then her expected utility is (weakly) positive.
Remark 1. In Section we experimentally show that our offset payment rule, coupled with our context-aware allocation rule, results in both high expected rewards and positive utility for the advertisers (i.e., ex-ante individual rationality), as well as significant revenue for the auctioneer.
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 ensure truthfulness [Rochet, 1987]. Because the allocation rule is the same for all advertisers, their utilities must also be the same, up to advertiser-specinn offsets, indicated by Theorem 5.1. However, not all advertisers contribute equally social welfare. In Appendix C.4, we explain why implementing the mechanism without carefully designed offsets would lead to free-riding, Specifically, an advertiser's 's expected utility 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, crucial to align each advertiser's utility with her contribution social welfare.
Lemma 5.2. For the offset C - (0, Tref; Teon) advertiser i's expected utility under truthful reporting is Fr( Tref; Teon) T log E/ exp (r(l.15)) TT_I (y5 | (x))
M
'While we focus on the most general model that includes negative rewards. MOSAIC maintains all its desir- able properties discussed in Sections 4 and under the assumption that all advertiser rewards nonnegative.
7

---

User query
What are effective ways musical instrument online?
Advertisers
MusicMastery: offering online music lessons and virtual tutoring
InstaTune: selling musical instruments and learning aids
Context-Aware Mechanism Output
Effective ways to learn musical instrument online include:
1. Online music lessons: Platforms like MusicMastery ofler one-on-one virtual lntoring, group classes, and pre-recorded lessons, These lessons can be tailoredd your skill level and learning style.
2. Interactive learning tools: Insta Tume offers a range of interactive learning tools, such as apps, software, and games, that make learning fun engaging....
Baseline Mechanism Output
Practize consistenlly and regularly; Consistent practice is essential to learning any musical insirumeni, and it's even more imgortant when learning online. aside speciffic time day or week practice, and Find good teacher mentor: While it's possible to learn some things your own, working with good teacher mentor can help improve faster and avoid developing bad habits.
Figure I: Comparison of context-aware and baseline mechanism outputs using 10 candidate replics.
In words, Lemma 5.2 shows that each advertiser's 's expected utility is monotone in how well aligned her exponentiated reward function is with MOSAIC's induced LLM क. (i.e., the optimal LLM for the reports P_, that would have been obtained had advertiser i not participated).
Remark 2. In Section 6.2, we experimentally show that the offset of Section 5.3 induces a strong positive correlation between advertiser's 's contribution social welfare and her expected utility gain from participating. Moreover, for the tested distribution of instances, MOSAIC satisfies ex-ante IR.
6 Experiments
In this section, we evaluate MOSAIC's performance on its flagship application of online advertising.
6.1 Experiment Setup
We create synthetic instances, each comprising a user query (e.g.. "How to learn a musical instrument online?"") and two advertisers (e.g.. "MusicMastery, offering online music lessons")) This matches the setup of Dütting et al. [2024] while highlighting MOSAIC'S performance and revenue, even in low competition scenarios. We use 1lmma2-7b-chat- [TTourron et al., 2023] as the base architecture for all LLMs. In Appendices D.6 and D.10 we extend our analysis to settings with more advertisers and alternative architectures, observing similarly strong results. See Appendix D for details.
(Ho..."How
6.2 Experimental Results
In this section, we evaluate MOSAIC's overall effectiveness, assessing both its allocation and payment rules. We first focus on how well the allocation rule generates value for advertisers and converges to the optimal distribution, comparing the baseline and context-aware versions. Figure illustrates how the context-aware mechanism enhances response relevance for advertisers. Notably, only the context-aware mechanism successfully incorporates advertisers into the replies.
In Figure 2a, we plot the log probability of the replies returned by MOSAIC with respect to the optimal distribution (Equation (2)) against the number M of candidate replies generated. We compare the context-aware version of MOSAIC to the bascline version to evaluate the effectiveness of incorporating contextual information. Note that baseline MOSAIC is the strongest applicable benchmark, as it is the only other tractable mechanism for this problem in the literature that converges to the optimal distribution (for a detailed discussion, please see Appendix D.2).
To assess MOSAIC's convergence, we estimate the log probability of sampling a single reply from the optimal distribution. 6 We observe that for both the context-aware and baseline versions of
'The closed-fone 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, which would require using RL to train the optimal LLM on the advertisers' aggregate reward function, which is computationally infeasible for
8

---

18)
Rad Using Mevl
Using Werd
Novunue 24
Ro Palooiiyy
Using Soef
Uning Tut 5d]
Single sample fuafjt
Candidate
1 18 a II
1 TRRD D. Candidati
(a) Returned reply log probability function of the number can- didate replies generated using Tiat and Weon- We also show proxy of drawing a single sequence from the optimal distribution.
(b) Total advertiser normalized ward as function of the number candidate replies generated us-
(c) Revenue function of the number of replies generated using That and Reon.
ing Riet and Teon-
Reply log probability, total advertiser normalized reward, and revenue as a function of the number of candidate replies generated using Tee and coo Averages over 1250 runs with 95% Cls.
Figure 2:
MOSAIC, the log probability of the returned reply scales rapidly with the number of candidate replies. This aligns with our analysis in Section 4, where we proved that both versions converge to the optimal distribution. We also observe that incorporating context significantly accelerates convergence. Notably, the context-aware version of MOSAIC achieves higher log probability with respect to the optimal distribution with four candidate replies than the baseline version with 20. Additionally, with only 20 candidate replies, the context-aware mechanism can almost match our estimate of the log probability of sampling from the optimal distribution. In Appendix D.4, we further demonstrate that the usefulness to the user also scales rapidly with the number of candidate replies.
In Figure 2b, we plot the total expected reward for advertisers against the number of candidate replies generated, with the expectation over the distribution of the returned reply from the set of candidate replies. To make the plot more interpretable, we normalize each advertiser's expected reward by her expected reward had she not participated. Specifically, we plot nim (a: = =EjEM r. ri yj) ( [z) - EJEM re(2,yys.5) -r_ (y-1.) |z), where y-4 are the candidate replies that would have been generated if advertiser i had not participated, and Tr_, MOSAIC's allocation rule in that case.? We compare MOSAIC's two versions, highlighting the value of incorporating context.
Figure 2b demonstrates that our context-aware mechanism significantly boosts advertiser rewards, with benefits scaling rapidly with the number of candidate replies. contrast, the baseline version fails to improve advertiser rewards and may even cause slight decrease: generating more replies adds marginal positive reward to the reference LLM (see Appendix D.4), but does so the expense of advertisers. In summary, MOSAIC's support for context-aware LLMMs allows it to quickly converge to the optimal distribution and generate substantial rewards for advertisers. In an ablation study (Appendix D.7), we demonstrate that MOSAIC maintains strong performance across all key metrics even under significantly reduced contextual input.
In Appendix D.8 we provide a detailed experimental evaluation of MOSAIC's compute requirements, showing how requires the compute cost of just five LLM queries to converge, and discuss how can be fully parallelized so that the user-percess seer-pereiived latency is the same as single LLM query.
Next, we examine the impact of our payment rule from Section 5. In Figure 2c, we plot the auctioneer's revenue for both the context-aware and baseline versions MOSAIC. Our payment rule in combination with the context-aware allocation rule yields revenue that scales rapidly with the number of candidate replies. Moreover, comparing the advertisers' total payment with their normalized reward in Figure 2b, see that for the context-aware mechanism, our payment rule converts much of the advertisers' surplus into revenue, while also ensuring positive advertiser utility,
These results align with our theoretical analysis. In Section 5.3.1, we showed that an advertiser with positive rewards for candidate replies- as in the context-aware mechanism achieves positive expected utility, and in Section 5.3.2 introduced the "what you give is what you get" property. In
the number of problem instances we test. Instead, we generate replies from कer and evaluate them based on the induced probabilities of Teds for which गie is the optimal L.M.. This serves proxy for the log prohabilities draw replies from the optimally fine-tuned model for each query.
we should expect if
"To 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.

---

Appendix D.5 we show that, for both versions of our mechanism, the payment offset increases the advertisers' expected utiliiy,, and makes the relationship between an advertiser's contribution to social welfare and utility significantly more linear and positively correlated. Concretely, our offset increases the Pearson correlation between advertiser utility and reward from 0.4 to 0.8.
Discussion
The motivation for our paper is one particularly common way in which users interact with LLMs: using them as search tools with a single query. This use of LLMs is a close cousin to ordinary search, and most of the existing considerations for sponsored search also apply. For example, the platform would need to vet participating advertisers as well as the content they want to generate, and the platform would also need to visually distinguish ddtertiser-inffueecee
parts of the response.
We have made several design choices in our problem setting. While these are completely standard in mechanism design, and we think they also make sense in the application we envision, they still represent limitation in the scope of our work. Below, we discuss those design choices in more depth, and take the opportunity to consider broader impacts and possible directions for future work.
The first such design choice the platform's 's objective in Equation (1). This objective corresponds to a "utilitarian" concept of social welfare. This is the most common objective in mechanism design, and indeed, all large online ad platforms maximize for this objective. However, a platform might reasonably focus on other objectives, for example, revenue or egalitarian faimess. As long closed-form solution for the platform's 's objective can be derived and the corresponding allocation rule satisfies eyclic monotonicity, our mechanism is also applicable for that objective.
second design choice is focus on single-query, static mechanism design setting. Handling multi-query LLM interactions involving lengthy conversations would include a much larger range of usage patterns. Determining where and how advertising could be appropriate (c.g., in product searches) and where it might be inappropriate (c.g., in emotionally challenging conversations) would require careful consideration. Additionally, this would involve dynamic mechanism design. In Section 2, we explain some limitations of the specific dynamic mechanism proposed by Dütting al. [2024] for this problem. However, mechanism and not unique to that paper, overcoming them is an important direction for future work.
large extent, these issues are inherent to any dynamic
Finally, we have made the design choice of equating the usefulness of a reply the user with the likelihood of that reply given by the reference LLM,, and we have equated an advertiser's value for a reply with the induced reward of that reply by their LLM. Regarding the first choice, we argue that it is reasonable to assume that the platform wants its results to be as high-quality as possible. The second choice corresponds to the standard assumption in mechanism design that participants know their type for any possible outcome. But in practice, it may not be realistic for advertisers to train their L.Ms and run inference on potentially private user data. Section 4.2, we have discussed an autobidder perspective on the mechanism that addresses both of these challenges.
8 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 principled method for balancing participants' expected rewards with the divergence from a reference LLM. Thus, mechanism is particularly well-suited for online advertising, allowing the integration of advertiser LLMs with a reference LLM responsible for generating user-centric replics.
Our payment rule removes any incentive to misreport preferences, achieving the central mechanism design goal of prrategys While ex-post IR is incompatible with ptrategysroofness 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 participant's 's utility gain is proportionate to her contribution to social welfare, 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 realistic settings.
10

---

Acknowledgments
language models, 2022. URL We would like thank various anonymous reviewers for their thoughtful comments and suggestions. We are also thankful for the feedback we received from participants at the following events: the 2025 NBER Market Design Working Group Fall Meeting, the Foundation Models and Game Theory workshop at 2C,24, the Harvard EconCS seminar, the UChicago CS department seminar, the Frontiers of Online Advertising Workshop at EC'24, and the 2024 Rising Stars in Market Design workshop. This paper is part of a project that has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (Grant agreement No. 805542).
References
Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A general theoretical paradigm to understand learning from human preferences. arXiv preprint arXiv:2310. 12036, 2023.
Martino Banchio, Aranyak Mehta, and Andres Perlroth. Ads in Conversations,, page 350. Association for Computing Machinery, New York, NY, USA, 2025. ISBN 9798400719431. URL https: //doi. ///oi..org/ii 10. 1144/ 3742545..
Dirk Bergemann, Marek Bojko, Paul Dütting, Renato Paes Leme. Haifeng Xu, and Song Zuo. Data-Driven Mechanism Design: Jointly Eliciting Preferences and Information, December 2024.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel F. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose F. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang. On the opportunities and risks of foundation models. arXiv preprint 20Xiv:2008.077 2022.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang. Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. Scaling petps://arriis org/
11416.
Edward Clarke. Multipart pricing of public goods. Public Choice, 11(1):17-33, 1971.
Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H. Holliday, Bob M. Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, Emanuel Tewolde, and William S. Zwicker. Social choice for ai alignment: Dealing with diverse human feedback. arXiv preprint arXiv:2404. 102711, 2024.
Cristina Criddle. Perplexity talks with top brands on ads model as it challenges Google, Financial Times, September 2024.

---

Kumar Avinava Dubey, Zhe Feng, Rahul Kidambi, Aranyak Mehta, and Di Wang. Auctions with 1lm summaries. arXiv preprint 2rX1:22404008126, 2024.
Paul Dütting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, and Song Zuo. Mechanism de- sign for large language models. In Proceedings of the ACM Web Conference 2024, wwW '24. page 144-155, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400701719.
Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the gener- alized recond-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242-22) 259. March 2007.
Soheil Feizi, MohammadTaghi Hajiaghayi, Keivan Rezaci, and Suho Shin. Online advertisements with Ilms: Opportunities and challenges. arXiv preprint arXiv:2311.0760) 2024.
Sara Fish, Paul Gölz, David C. Parkes, Ariel D. Procaceia, Gili Rusak, Itai Shapira, and Manuel Wüthrich. Generative social choice. arXiv preprint arXiv:2309.01291, 2023.
Rafael M. Frongillo and lan A. Kash. General truthfulness characterizations via convex analysis. Games and Economic Behavior, 130:636-662. 2021.
Theodore Groves. Incentives in teams. Econometrica, 41(4))617-63) 1973.
MohammadTaghi Hajiaghayi, Sébastien Lahaie, Keivan Rezaei, and Suho Shin. Ad Auctions for LLMs via Retrieval Augmented Generation, June 2024.
Keegan Harris, Nicole Immorlica, Brendan Lucier, and Aleksandrs Slivkins. Algorithmic persuasion through simulation. arXiv preprint arXiv:2311.18133 2024.
Daniel Lehmann, Liadan Ita Oéallaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM
2002.
Kenneth Li, Samy Jelassi, Hugh Zhang, Sham Kakade, Martin Wattenberg, and David Brandfonbrener. Q-probe A lightweight approach to reward maximization for language models. arXiv preprint 2rXiv:2402.146888 2024.
Meta. Meta reports fourth quarter and full year 2023 results, initiates quarterly dividend, 2024. URL https: http///vveeetrrreee fb. com/ womm/nvestorr-ie news/ wwwss-eeeeeeeeeeeeeeeeeeeeeeeeee
-eaaaRReprrs--ooooe -ourr--uuuttrtrr-reererrr Quarter-and-Frnt and-Full- Cod-Full-Yoenn Y020-123------------ Results- Initiates Sewrlltts--uaaaerl---Da (uarierly-Dividendd/ default. aspx. Meta Investor Relations, accessed: 2024-01-31.
Roger B Myerson. Optimal Auction Design. Mathematics of Operations Research, 6(1), February 1981.
N. Nisan and A. Ronen. Computationally Feasible VCG Mechanisms. Journal of Artificial Intelli- gence Research, 29:19-47, May 2007. ISSN 1076-9757.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129-140, 1999.
OpenAl. "buy it in chatgpt: Instant checkout and the agentic commerce protocol". https:// https://openai com/ com/index/buy-tie it- in- chatgpt/, September 2025. Accessed: 20-5-10-18.
Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighte regression for operational space control. In Proceedings of the 24th International Conference Machine Learning, ICML '07, page 745-750, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595937933.
Rafacl Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2305.1888 2023.
Jean-Charles Rochet. necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16(2):191-200, 1987.
12

---

Ralph Tyrell Rockafellar Convex Analysis. 9781400873173.
Princeton University Press, Princeton, 1970. ISBN
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafioni, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12990 12950, 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurall, David Esiobu, Jude Fermandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Hal R. Varian, Position auctions. International Journal of Industrial Organization, 25(6): 16000116631118 December 2007.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8-37, 1961.
Tobias Werner, Ivan Soraperra, Emilio Calvano, David C. Parkes, and Iyad Rahwan. Experimental Evidence That Conversational Artificial Intelligence Can Steer Consumer Behavior Without Detection, September 2024.
Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy Liang. Data selection for language models via importance resampling. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint Xiv: / 08593, 2020.
13

---

A Further related work
Feizi al. [2024] presented an abstract design for an LLM advertising system and detailed number of research challenges that would have to be overcome in the course of implementation. Conitzer et al. [2024] drew connections between computational social choice and LLM alignment. Fish al. [2023] presented work in the opposite direction: how can LLMs be used to solve problems in social choice? Harris et al. [2024] studied Bayesian persuasion an abstract setting where "simulator" (for example, realistic LLM) of the agent is available. Werner et al. [2024] gave preliminary empirical evidence that LLM--generate content can influence consumers. Banchio al. [2025] discuss running auctions where the allocative decision involves placing ads in multi-turn conversation after up-front bidding.
In work that appeared after the initial version of this paper, Bergemann et al. [2024] considers a setting where bidders have both private types reflecting their preferences and private signals reflecting information about world state (for example, user interests). When applied to LLM auctions, they identify their setting as generalization of ours, where the signals known the advertisers may actually improve the output for the user, and where deviations from the reference LLM may be measured by arbitrary distance functions. They analyze conditions under which welfare maximizing mechanism can be implemented truthfully (eliciting both types and signals) in posterior equilibrium, but do not consider practical implementations of their mechanism.
B Details from Section 4
In this section, we present all omitted theorems and proofs from Section 4.
B.1 An Example Where VCG Not Strategyproof in This Setting
In Example 1, we present simple example illustrating that the VCG mechanism is not strategyproof when the allocation rule cannot fully converge to the optimal LLM based on the advertisers' reports.
Example 1. Suppose there
advertisers, A and B, and five possible replies:
two replies that mention both advertisers.
one reply that mentions only A.
one reply that mentions only B. and one reply that mentions neither advertiser.
The advertisers' rewards for each reply are shown in Table 1:
Outcome
TA
TB
[A, B
0.9
0.9
{A, B)
0.4
0.4
{A}
1.0
0.0
{B}
0.0
0.5
0
0.0
0.0
Table 1: Advertiser rewards for different replies.
Assume that t O, so that the optimal L.M would deterministically select {A, B),, maximizing total advertiser reward. However, suppose that the allocation rule cannot converge to this reply-for instance, because RLHF is used to train the aggregate LLM गिद and the process noisy. Instead, when aiming {A, B, the resulting LLM a produces {A, B B),.
Under truthful reports, advertiser A's utility would be
UA = T (, B)2) + + (Tr))rr(((AAA B)2) - TB (B(BB)) = 0.4.
AAlternatively, one could interpret this setup as a setting where the mechanism cannot converge to replies mentioning both advertisers, perhaps due to optimization difficulties, but can converge to replies mentioning only advertiser.
14

---

However, if advertiser A misreports by declaring ((([ABB)) = 0.0. the mechanism would instead converge to an LLM that always returns {A). that case, A utility would be
U -A((A)) +rB((A)) (B) 0.5.
Thus, advertiser A would be incentivized to misreport her preferences. illustrating how VCG payments cannot ensure strategyproofness when the allocation chosen may be suboptimal.
B.2 Proving that MOSAIC converges to the target distribution in the limit
Theorem B.1. Let (ylm) be the probability of sampling output sequence for input sequence according Algorithm/ 1, where M is the number of candidate sequences generated and f e R is the advertisers' reported reward functions. For any LLM gen such that Tef is absolutely contimuous with respect to genn the policy induced by MOSAIC approaches the following limit:
exp(f(x,, v)/((
lim (f)a))) Tro(U(o>) M-000
(1s) (2)////))))))))
Theorem B.1 Proof. Let (Blz, (3, } be the probability of returning output sequence y for input sequence according to Algorithm conditioned on the set of generated candidate sequences being {uj M Additionally, let Wem((1) } c) be the probability of the context-aware model Toon generating the candidate sequences {y, 3=1 given the context and the user query
First, note that we can write the density R. as follows:
Σ
TR. (yke 1 (1
t0s) ErM
(u {us -
exp f(a.u1) + llog Tarl [xx)
( 1r Te ( (1330)
Σ I v)
Ece exp
((z,C)) + log
Tarl ( (x))
Rum (c) 20:))
[x)
exp ((amwss))
-B -
I I(1 = v)
Tone (on) (x:c)
Ecelus
TatlC at) Tenn((lore) exp ((2.5)
E, 11 =b
Tea
f((, v)
-Eig, 1i Mann N (-1200)
exp
[er(((=)) Σ EcE(U, Rom (00(51123))
exp F(a.()
Teom (y) xx; c)
M E, I[ = y}
[Te(((1)))
f(2x y)
= EEg 1as Roan (-12z0)
exp
Roma 22:0 exp F(a.))
Tnd ((12)
Tooa (y) x
M Ece )
15

---

Taking the limit as M + oo and using the Law of Large Numbers (the sequences are i.i.d.::
Teoo (3) Jz; c)
[rer(y)
(f(x, v)
lim (v)M(y))))= lim
E (os) m
cxp
M-+00
M -0000
E (e-wrall-1s))
exp
f(ar.()
Tran (5/75)
(Cr(()
Tecaa (2/12
1
Teat Free((111 (3)zz) (r)
f(x,, 31
Toon [oon(y)2; c)
exp
B (e
exp
((x,()
Mmr(C(ar) (x)) (cco((la))
Tooon (1) (z)
(( v)
=
exp
Ecer Tacal (coa((|2) exp
exp
f(am(()
(er((
Moo ([12;))
((rr, y)
= =
exp
Ecer TTe((( exp
f(a.5)
T
f(zz, y)
E (g
(xp(f((;()/r)
exp
Corollary 4.1 Proof. The proof follows directly from Theorem B.1 and Appendix A.I in Rafailov et al. [2023].
B.3 Formal Connection To Importance Sampling
Given truthful reports by the advertisers, there is strong connection between our allocation rule and importance sampling. The optimal LLM for the platform's objective गे can be interpreted as the target distribution that our allocation rule is trying to simulate. The aim of our allocation rule to return reply as similar possible a reply drawn from the optimal LLM ग.. This can be interpreted drawing reply from ur and then evaluating it with respect to the same function, i.e., our allocation rule is trying to estimate Eyy-a= (-[x) | (y/z)]. The L.MM Tgen that we use to generate the candidate replies (either the reference L.M or the context-aware LLM) can be interpreted as the proposal distribution ppropp1|2) used to generate samples. We are interested in how well, with respect to the target probability TH (-1x), sample y from our estimator using M candidate replies matches sample drawn from the target distribution x (-Iz). In this section, we will analytically show how the quality of the proposal distribution Trop gen affects the quality of that estimator.
First, in Lemma B.2 we establish the variance of our estimator:
Lemma B.2. For any LLM gen such that Rief is absolutely continuous with respect to Tge the variance of the policy Nr.M (-1z) as an estimator for (11))( is
(ylx)
Var(fus) = M
Σ [=]])))) PEY
gen (y/(o))
WEY
Proof. Let M1, V2. ... VM be the M generated candidate replies drawn from the proposal distribution (rropp/2z) Conditioned on those candidate replies, the importance sampling estimator for the expected value of the function x, (y|z) under the target distribution n, (y|z) is
1 Ais
(1,(æ)
w(x;)
M
Ø=1
M
म. (3/ (x) Tprp (M (z)
n, (y, (z)
M
グ=1
1
M
(リ)
M
prop (Uy xx)
16

---

Taking expectation over the generated candidate replies y1.
Mar
M
म. (5اع 3z)
E
[
B y1 ... MM pop
M
TT prop Us (x)
m
x. 8 |x:)2
Ry pmp
M
Tprpp 3/ (x)
Th (v/ (xz)
Topo (3/2x)
T. (1)32)
Trop (3/zz
prup (1/ (x)
yEY
n. (u/z)²
(5)
MEY
Thus, our estimator is unbiased, expected. The variance of the estimator jus is given by:
Var(Aus) E[pis]
E[Ais|
(6)
For the term pis we have:
M
ক. (#, )x prop و xx)
M
j=1
M
M
म. (3, x2)
x, ( (x)2 Trrop Ugr (x:
M
Tprop (Wا (x)
Taking the expectation E Exppp(
m)]
M
(yg(o)) /x)
n, (Mgr /1:)2 poop (Uyy (x:
P
E Exppep (-10)
M
Tprop (3/ (x)
j=1 ;'=1
M
T. (Mj (x)
x (3 )xz
E Toop (112)
+ Σ
E
M
Trrpp Ug (x)
Trrop y (x)
3#8
(y(x)
M
+ 1(M -1
Σ
कH (urla))
M
prop (v)x)
DEY
VEY
2
(
M
Σ WEY
2))
M
Trop y x))
M
The final expression for the variance of the importance sampling estimator with M samples can be computed by substituting Equations (5) and (7) in Equation (6):
2
()(x)*
M- -
Var(fis)
Σ NEY
M
Tprop (2)1((2)
M
BEY
veY
1
()(1))
Σ
क, (ulo))
(8)
M
DEY Trrop z))
WEY
17

---

Lemma B.2 reveals two important details about our estimator. First, the variance of the estimator inversely proportional to the number of candidate replies generated M. Thus, M increases the variance decreases and our estimator becomes more stable in simulating the target distribution T (-1x). Second, the closer that the proposal distribution ppp (-|z) the target distribution, the smaller the term EBEy
(ylaa) will be, which reduces the variance of our estimator.
Fiapp (1/22)
Lemma B.3 establishes how a smaller variance leads to faster convergence:
Lemma B.3. Let Pune (-(x)) (, x)], and jus be the importance sampling estimator as Eyer (-(p"))" candidate replies. Then, for any LLM Tgen such Tppp(yla))
Lemma B.2 using M =
that The absolutely continuous with respect Tigen we have that lips -uruel < E with probability at least - 5.
Proof. Let jus the importance-weighheed estimator whose variance is given by Lemma B.2
Var(fu)) =
( 2)
y 2) z)))
M
Prop (y x))
FEY
BEY
We have already shown in Lemma B.2 that the estimator is unbiased. By Chebyshev's inequality, for any
O,
Var(ūus)
TH x
Pr| Lis Muree
El
Σ
M.
prop x))
DEY
DEY
where Minee (ynoxt(-1a)) TT (y x)] Eper कH (v)ar)
Setting Pi(lins Mineel
8 and solving for M yields:
)
2
M E
(リ x²
Σ WEY
7 C= 10)3
Σ (1 | x)
Tprop (3)
2))
5E2
Trup (y) x))
WeY
WEY
Based on Lemma B.3, our allocation rule converges to the quantity is is trying to approximate at rate VM.
B.4 Bounding the Total Variation Distance
In Appendix B.2 we proved that MOSAIC converges in the limit to the theoretically optimal distribu- tion for the platform's 's objective. Then, Appendix B.3 we showed how MOSAIC's allocation rule relates to importance sampling, and what that implies for the similarity of MOS AIC's output to that of the optimal distribution म. Now we will also show that MOSAIC's probability estimates for any possible sequence converge to that of गद at a rate of VM
Theorem B.4. Let y be the domain consisting of all sequences in a finite token vocabulary of length up to L. Hence [)] < co. Assume O I w(y) & for all E ), where
w(y) = 7 (x)
Tprop (y x))
Consider M i.i.d. draws y1..... VM Tpmpl (: x) and define the self-normalized importance- sampled distribution induced by Algorithm 1:
M
Σ w(ys) 1l4; = y}
# #r (y)
1=1
w w(y))
== 1
18

---

Then, for any 0 and 8 0, if o (C in( in((:)) with probability at least 1-6 (over the random draws), the Total Variation distance between at (: x)) and mz (: x)) satisfies drv(AM; m²)= S..
Proof. First, we will show that for any M E N, MOSAIC is an unbiased estimator of ....
For each fixed V define x == w(y)) 1(U; y to be random variable that equals w the j - 1/ draw from the proposal distribution is y. Intuitively, this weighted indicator for whether the j-th draw is equal y.
For any V, the expected value of this indicator, with the expectation taken over the draw of Y prop
E E[x]00] = Σ *EY
w(2) 1f2 = = Tprup (2) = w(y) Tprpp (V) (T)
Thus, Qm((u)) 1/ شラ Xj (v)
is unbiased estimator of ( x))
Similarly, (2) 1 Σド= (1ú)) is an unbiased estimator of (since E[w(y;)] 1) (assuming that n, is the optimal policy, i.c. normalized LLM so that the probabilities sum to one).
M
The self- normalized distribution can be written as
(m((())
( x))
())
Hoeffding's inequality for bounded random variables tells us that for any e' > 0:
2M E2
(r() 7, x)]
2 e - 2exp
C
For each y E V/ we have the same deviation event, so by union bound over all y E Y:
2M C = 2(21 exp
2.
Praacy: (1m((1)) +3 x))
Σ DEV
2exp
S
61
C
Thus, using M 0 ( In( ) candidate replies, with probability at least 81 over the draw of those replies, we have simultaneously for all V. (Qvr(())) <;(v xx) < e'. By similar argument, applying Hoeffding's inequality to Q ()"), which is an unbiased estimator of
2M c²
P2( - 2 e| s 2 exp(
C
Hence, with high probability 82. Q2r())) is also within te of 1. A union bound over both events
(all y E y plus Qsi ()")) yields final event Eyg with probability (81 + 52) on which:
(mv( E (x) - e', (x) + +el, Qx())) E [1 - E', + + VyEv.
On this good event Ege, for each y E V::
(m(( Qu ())
Tテ (y(xr - TF (1(1a)) + g
#u (vla)
E
1tE
Recall the total variation (TV) distance between two discrete distributions and Q on y is
drv Q)
EIP()- Q())
2
DEy
19

---

We aim to show that on the event E (which holds with probability at least 1 1- (61 + 62)). the quantity
vEy
most O(s)).
On Eg,, we have, for each y V.
(tr(t)))
T (v|æ)
(yla)
1 1
Thus:
TT (y)2z)
(y
E'
* (1(o)
(9)
1 e'
1 e
1 5
28
2s
(10)
1 +
1-8
Thus, conditioned on the good event Egr, we have (fx - [T) = O(e)) by a Taylor expansion for small s'.
Therefore, on the event E"
drv(AM, m;)
Σ 1;)]
-(21)))((11)))))))
NEY
yEY
Setting 5' M
to achieve the target error concludes the proof.
20

---

C Details from Section
In this section, we present all omitted details from Section 5.
C.1 Omitted Proofs from Section 5.1
Theorem 5./ Proof. Let F. = (.)...... fr (M)) be the reward reports of advertiser i for the M generated candidate sequences. Then, for MOSAIC's allocation rule, holding the candidate sequences and the reports of all other advertisers fixed, the probability of returning each of the M candidate sequences function of i's reports is:
T(E B_:) softmax
+ ( B.:)
(11)
where B-i.j EnEMy (x(m)))))
log (ar()) (aa (mpp)) Importantly B_ is an M-dimensional vector that does not depend advertiser i's reports.
We would like to equip x(; (-:) with a payment rule p(:; so that the resulting mechanism (r(,,B.i,,p's:
will be strategyproof. This requires that B-;) have property known as cyclic monotonicity. Equivalently, x(-,8-i) must be the (sub)gradient of advertiser i's utility for bidding truthfully in the mechanism U (r,;;3__) (.:;;,.;... :), and that utility function must be convex [Frongillo and Kash, 2021, Rochet, 1987, Myerson, 1981].
is easy to verify that for the function class:
M Σ exp
Ti(1, + B ) + CC, CER (12)
Uc(r:B-i)) = - log
the allocation rule (r;;;BB;)) a gradient of (r:::BB)) Additionally, (r; B-.) is convex in T; the exponential function e is (strictly) convex, because its second derivative is positive. The transformation rx(a,,)) + B_s.j is an affine transformation of (2, yj), and affine transformations preserve convexity. Finally, it is well-known that the LogSumExp function is convex.
Thus, for any B_, and for any 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 of candidate sequences. Adopting the quasi- -ineer utility model, advertiser i's payment is:
Uc(re 0-;) ((r;; B_:) p(r;; B-s) p_r;:B,)) = ITr; B) T; - -Uc(r;
M
ri(3, Uz). + 3 - C, CER
B-a) = ((raBB)) T - T log
exp
(13)
21

---

C.2 Differences from Standard Auction Settings
Standard auction environments typically rely on set of assumptions that simplify mechanism design; however, these assumptions do not apply to auctions for ALM-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., (5()) 2 (S") AS S", S' 2 I. The interpretation of free disposal 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 al. [2023], assuming that an agent's LLM IT, trained to maximize her reward function (and regularized with respect to its KL divergence from some reference LLM, which we assume be the same as the auctioneer's reference LLM)), there is a one-to-many mapping between an advertiser's 's optimal LLM, and her implicit reward function. That mapping is:
Ty y) = Tú log (1(()z)
(y) + log (()x)
(14)
where (x( is a prompt-deppendnt constant, and T; is the regularization hyperparameter of advertiser 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., 2023]. This has two implications: First, unlike standard auction environments, an agent's 's reward can go negative there is nothing equivalent to the free disposal property. Setting Z<(x:) to zero (which is equivalent to normalizing the induced probabilities by the LLM [Rafailov al., 2023)), the agent's reward is negative for any sequence for which her LLM assigns a lower probability than Tee--
Second, especially in the online advertising application, an agent's expected utility for not participat- ing the auction is negative: if advertiser i does not participate in the auction, her payment zero, but her expected value for the outcome is
π (0.) - - - T(B.)) -r,
(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 different, possibly competing brand, as unlikely. Thus, based on Equation (14) the corresponding advertisers have very low rewards for those sequences and conversely, advertiser 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, x >00; 9i)) 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 the mechanism is negative.
22

---

C.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 C.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 C.2 we prove that if an agent's 's reward for all candidate sequences is (weakly) positive, then her ex-interim utility is (weakly) positive.
Why is individual 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 all. Typically, if agent's 's utility for con-atticcipation 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 's allocation rule would no longer be the gradient of advertiser i's utility with respect her reports, which would destroy strategyproofness [Frongillo and Kash, 2021, Rochet, 1987, Myerson, 1981].
It is important 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 constant factor, described in Equation (12) [Frongillo and Kash, 2021, Rochet, 1987, Myerson, 1981].
Lemma C.I. For the payment offset C = -T log (Σj exp (B-1)) if aavvertiser i's reward for all candidate sequences is zero, then her ex-interim utility is deterministically zero, for all B_ E R.
Lemma C.I Proof. First, note that for all B_: R..,. advertiser i's expected reward for the outcome is zero, as (Ty; (3:) = π (1r;33,)) -0 -0 0. Additionally, advertiser i's reward for the realized outcome will deterministically be zero, her reward for all generated candidate sequences is zero Finally, note that by setting rÜ O 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 also deterministically zero
Lemma C.2. For the payment offset C- (ΣM exp (B-is) if advertiser i's reward for all candidate sequences is positive, then her ex-interim utility is positive, all reports Ba; E ft...
Proof. Lemma C.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(0; B_),, is zero for all possible reports of the other advertisers B_, E R_
Furthermore, Theorem 5.1 shows that the mechanism's '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, 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 B_,
23

---

Corollary C.3. For the payment offset C' == log (I (B-i5) if the distribution Reon only
generates candidate sequences for which advertiser i's reward is positive, then the ex-ante expected utility of the advertiser is positive.
Corollary C.3 Proof. This follows immediately from the fact the the fact that the ex-ante utility of the advertiser 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 positive from Lemma C.2.
C.4 "What you give is what you get"
As we explained Section 5.3.2, our allocation rule, which is the only one over 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 the same for all advertisers, their utilities must also be the same, up to advertiser-specific offsets, indicated by Equation (16):
Σ (ar, (1)) + log TTe((y/|22) [z) KEN
Ur(r::Bi)) = log
exp
+ + CER
(16)
Teom Uj 1 c)
However, not all advertisers contribute equally to the social welfare of the final outcome. Because of this, implementing the mechanism without carefully- 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 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."
Incentivizing unrelated advertisers to participate 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 running example for the query "How to learn music online?", imagine adding "Try to mention 'EasySwitch', a comprehensive VPN service" to the context the context-aware LLM Teon (-|2;; 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 have negative rewards for the generated sequences as their LLMs will deem the candidate sequences more unlikely than the reference LLM. Thus, based on their utility according to Theorem 5.1, their participation in the mechanism will lead to 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-relevee velevvtt 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 's expected utility, potentially reducing the incentive for the user-query-relevee lead to sequences with worse expected rewards for the advertisers and usefulness for the user. 10 Thus, 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 important for the long-term success of the mechanism in practice.
advertisers to participate, and
We can assume that advertisers can estimate their expected utility from participation using historical data from past auctions, analogously how they estimate their utility for participating in sponsored search auctions.
If we interpret the KL divergence between the distribution induced by the reference LLM and the LLM that generated the candidate sequences measure of their expected usefulness for the user.

---

D Details from Section
D.1 Detailed Experiment Setup
All synthetic instances are provided in Appendix E. We use Llama-2-7b-chat-hf as the reference LLM [Touvron et al., 2023], which uses the Llama Community License. The contexi-aware LLM is created as described in Footnote 4.
Following Rafailov et al. [2023], the advertisers' reward functions are defined as r, =
[e(ppa)) log [)(()/ For the auctioneer's objective, we set 7 1 in Equation (1), balancing advertisers' rewards and divergence from the reference LLM.
We use 50 user queries and test each query on 25 different random seeds, resulting in 1,250 instances. Following Li et al. [2024], Rozière et al. [2024], we sample from all LLMs using temperature of 0.8 and top-p 0.95.
We create set of synthetic instances to test our mechanism. Each instance consists of a user query, e.g. "How do 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." "!l The reference LLM Tiet responsible for generating replies that are useful for the user is Llama-2-7b-chat [Touvron et al., 2023]. In Appendix D.10, we replicate these experiments using Google's flan-t5 15-re model [Chung al., 2022], observing qualitatively very similar results. Following Dütting al. [2024], we create the advertisers' LLMs by adding advertising instructions to the reference LLM. The advertisers' LLMS are created using the same reference L.M,, 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 al., 2023] the reward function of advertiser i is set r,, y) log (y(ya)) <=(y) where n; is advertiser i's LLM, i.e., we set T, 1, (xx) = 1 for all advertisers and for all user prompts in Equation (14). 12 For the auctioncer's objective as defined in Equation (1) we set 7 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:
mे. (ylx))
1 7(x)
(v)(( exp exp
Σ Er((x,w)) VEN
(17)
Following Li et al. [2024], Rozière al. [2024] sample from the LLM generating the sequences (either Tet or Teon) 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 1.11
D.2 Choice of baselines
There are no other mechanisms in the literature for aggregating multiple LLMs to compare against. The only other mechanism that aggregates multiple LLMS is Dütting et al. [2024], which is not strategy-proof and does not converge to the platform's 's objective. The only other potential comparison is VCG, which, as explained in Section 3.2. is not applicable since it does not align with the platform's 's objective. Hence, the best baseline for comparison is naive MOSAIC, which we consider
Following Dütting et al. [2024]. we use fictitious brand names to avoid the model using any existing ad. 12 Nooe that we cannot estimate the true value of Z. However, it is guery-dependent constant. Given that experiments focus the reward difference of different sequences for the same query, this is non-issue.
25

---

strong benchmark given that it provably converges to the platform's 's optimal distribution based on Corollary 4.1.
D.3 Comparison of baseline and context-aware mechanism outputs
To provide some intuition how the context-aware mechanism improves the relevance of generated present side-by dide-by-side comparison of outputs from both mechanisms
responses for the advertisers, 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.
User query
What are effective ways learn musical instrument online?
Advertisers
MusicMastery:
offering online music lessons and virtual tutoring
InstaTune: selling musical instruments and learning aids
Context-Aware Mechanism Output
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. These lessons can be tailored to your skill level and learning style.
Insta offers a range of interactive learning tools, such as apps, software, and games, that make learning fun and engaging.
Interactive learning tools:
3. Practice with technology: Utilize digital tools like metronomes, tuners, and recording software practice and track your progress.
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 essential to learning any musical instrument, and it's even more important when learning online. Set aside specific time each day or week to practice, and make sure to stick to it.
Find good teacher or mentor: While it's possible learn some things on your own, working with good teacher or mentor can help you improve faster and avoid developing bad habits. Look for someone who experienced and knowledgeable in the type of music you want learn. 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.
Table 2: Comparison of context-aware and baseline mechanism outputs using 10 candidate sequences. Advertisers highlighted bold, outputs truncated to conserve space.
D.4 Experimental Evaluation of the Usefulness to the User
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 replics returned by MOSAIC with respect to the optimal LLM for the user (i.c., the reference LLM) function of the number of candidate replies generated. We compare the context-aware version of MOSAIC to baseline version. To benchmark our results, we also compare against sampling 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 bascline version is able to achieve does not scale with more generated replies.
26

---

Reply Log Probability wet
-140
-100
Using Ray
Using Rell (K)
-200
Single sample Rad (x]
Replies
Figure 3: Reply log probability with respect to the reference LLM as function of the number of replies generated using Tief and Teon-
However, there remains 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 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.
D.5 Comprehensive Experimental Evaluation of the Offset from Section 5.3
Without Offset
26
Adbertiierr
-40
+20
Offict Without Offset
17
12 3T
Candidate Sequences Generated
Candidate Sequencee Generated
(a) Sequences generated using Teom
(b) Sequences generated using Tref
Figure 4: Comparison of total advertiser utility gain from participation with, and without the payment offset, as a function of the number of candidate sequences generated using Tref and Tean- Averaged 1250 runs including 95% Cls.
In this section, provide comprehensive experimental evaluation of the payment offset introduced in Section 5.3. Figure explores the effectiveness of the payment offset introduced 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 function of the number of candidate sequences generated by the context-aware (Figure 4a) and baseline (Figure 4b) versions our mechanism.
In Figure 4a 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 4b we observe that the baseline version of our mechanism, adding the payment offset introduced of Section 5.3 to the payment rule causes very large increase in the advertisers' expected utility, but it is still not enough ensure positive expected utility for the advertisers. To conclude, Figure 4 demonstrates that the offset introduced in Section 5.3 causes large increase in
27

---

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.
e' 0.61
R² 0.12
Stope 0.52
Slope 0.40
Advartiorr utiley
Advertseer
Advertiser o Reward
Advertiser Rewaard
(a) With the payment offset.
(b) Without the payment offset.
Figure 5: Comparative scatter plots of advertiser reward and utility gain from participation, with and
without the payment offset of Section 5.3 for candidate sequences generated by the context-aware LLM genn We additionally show linear regressor fit that data, its slope and its 1²a
Slope
Slope
Advertioar Utiltt
Advertizer N2
-12
-30
Advertiser o Reward
Advertiser Reward
(a) With the payment offset.
(b) Without the payment offset.
Figure 6: Comparative scatter plots of advertiser reward and utility gain from participation, with and without the payment offset of Section 5.3 for candidate sequences generated by the reference Teef- We additionally show linear regressor fit that data, its slope and its R
Figures and 6 explore the effectiveness of the payment offset introduced Section 5.3 aligning an advertiser's '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-awan LLM Tief- 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 the linear regressor is far larger when we use the offset. Without the payment offset, the coefficient of determination is almost 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 we make the same comparison, but for candidate sequences generated using the reference pronounced. In Figure 6a we observe the relationship
LLM Tie-- The results 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 slope of 1.00 and an extremely high coefficient of determination of 0.96, indicating that can almost perfectly fit the data. Without our payment offset however, in Figure 6b 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.
see that the relationship between the two metrics is
To conclude, all cases tested, the use of the advertiser-speecficc offset introduced in Section 5.3 increases advertiser's expected utility, makes the relationship between advertiser's contribution
28

---

Pearson Corre Irtelatton Coefficient
With Offset
Without Offset
0.8
0.6
0.4
0.2
10 12 13 15 16
19 20
Candidate Replies Generated
Figure 7: Pearson correlation between advertiser normalized utility and reward.
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.
D.6 Experiments in Settings with Many Advertisers
In this section, we test MOSAIC's performance in settings with n and n = 10 advertisers, compared to the results of Section where the number of advertisers same balance between advertisers and the usefulness to the user as in the experiments of the main paper, set n/2.." We use the same 50 queries, but each query has five and ten advertisers, and test each query on 20 different random seeds, resulting in 1000 instances.
set to 2. To maintain the
In Figures 8a to 8j, we present the log probability of the returned reply with respect to the optimal LLM for the platform's 's objective म. and the reference LLM mes, the total advertiser value and reward gain from participating in MOSAIC and the platform's 's revenue. All plots are with respect to the number of candidate replies (i.e., L.M queries) that MOSAIC used. We compare MOSAIC's baseline and context-aware versions.
First, in Figures 8a and 8b we observe that the context-aware version of MOSAIC quickly converges to the platform's 's objective. By comparison, MOSAIC's naive version fails to do so. It is noteworthy that for very low numbers of candidate replies, the naive version of the mechanism performs better than the context-aware version. That is because in these experiments, more weight is placed towards reference LLM, as we have set a higher t value. However, the superior convergence rate of context-aware version of the mechanism recovers that difference very quickly. At the same time, Figures and 8d show that the context-aware version of the mechanism produces sequences that closely match the distribution of the reference I.M,, thus maintaining the usefulness to the user.
Finally, the context-aware version of MOSAIC is able to generate significant value (Figures and 8f) and utility (Figures 8g and 8h) for the advertisers, while also recapturing a significant portion as revenue for the platform (Figures 8i and 8j).
Taken together, similar to our results the main paper, we have shown that even with a large number of advertisers, MOSAIC quickly converges to the theoretically optimal distribution, generating significant value and utility for the advertisers and revenue for the platform, while also maintaining its usefulness the
Note that in the main experiments of Section 6 we had 2 and
29

---

100
-10
-120
Rebabbllty
-240
Repty Lop Probability
--30
+200
-200
1:00
203
Using Ran Arl Using Ro
Using Ruo
marl
Single sample fund (8) n Genersted
-275
Single Rp
Candidate
Candidate Repiles Ganerated
(a) Log probability w.r.t for 5 advertisers.
(b) Log probability w.r.. mp for 10 advertisers.
Probability Roe
Reply Log Probubilitty Net the
+278
-20
-27
Using Rond (K] Using (rt
Using (14)
Using
-200
Single sample (k
Single sample - And
Candidate Replics Generated
Candidate Replies Generated
(c) Log probability w.r.t. Tre for 5 advertisers.
(d) Log probability w.r.t Tha for 10 advertisers.
Using Ranl-X)
Using (a.u-jj)
Total Advortisa Reward Gah..
Using nei-kr]
Using nallke
Advertiser
13 Candidate Replies Generated
10 13 37 Candidate Replies Generated
(c) Advertiser value gain for 5 advertisers.
(f) Advertiser value gain for 10 advertisers.
Total Advertisur Ubiltty Cain
Using Rwi[-k]]
Total Advertiive Unility Cain
Using Rudllkd
15 nl Candidate Replies Generated
Candidate Replies Generated
(g) Advertiser utility gain for advertisers.
(h) Advertiser utility gain for 10 advertisers.
Using Raml-10) F-X Using Sui--X]
Using Rese Using mu((k))
Revamu
Revemuee
Candidate Replics Generated
Candidate Replies Generated
(i) Revenue for advertisers.
(i) Revenue for 10 advertisers.
Figure 8: Comparison of results for 5 advertisery(left and 10 advertisers (right). Each row corre- sponds to specific metric: log probability with respect to the optimal LLM π; the reference LLM Tref, advertiser value and utility gain, and revenue. Shown are averages over 1000 instances including 95% Cls.

---

D.7
Comprehensive Experimental Evaluation of Context
Strong
Strong
Weak
20
Weak
Total Advertser Reward
Weaker
Weaker
Context
No Context
20
Revenuu
30
Candidate Replies Generated
Candidate
(a) Total Advertiser Reward Gain
(b) Revenue
Total Advertber Utilty Gain
Strong
Weak
Reference LLM Log Probabiliyy
Weaker
No Context
2-
Strong
Weak
Weakee
No Context
Using (op(+1))
6 2
10 12 15
2.8 12 24
Candidate Reglies Generated
Candidate Replies Generated
(c) Total Advertiser Utility Gain
(d) Reference LLM log probability
Figure Total advertiser normalized reward, revenue, total advertiser utility gain and reference LLM log probability as functions of the number of candidate replies generated for various levels of context. Averages over 700 runs with 95% Cls.
In this section, we experimentally evaluate MOSAIC's performance under varying levels of context c. Specifically, we test four levels of context:
Strong: the context-aware LLM T-on(- (z:c) c) has access to both the advertisers' names and their descriptions;
Weak: T- x; c) has access only the advertisers' names;
Weaker: <- (- x;; c) is given neither names descriptions, and is simply instructed to "try to promote related brands";
No context: corresponds to omitting context entirely.
Using "strong" context corresponds to the context-aware version of MOSAIC evaluated in Section while "no context" corresponds to the baseline version.
For each level of context, replicate the experiments from Section 6 using the same of test instances. To reduce computational costs, we evaluate only 700 instances for the strong, weak, and weaker context levels. For the context setting, reuse the results from the 1250 instances reported in Section 6.
In Figure 9, plot, for each context level, the total advertiser normalized reward and utility gain from participation, log probability the reply under the optimal LLM (Equation (2)), and the platform's revenue, all functions of the number of candidate replies generated.
In Figure 9a, we observe that for all context levels except "no context," the total advertiser reward increases rapidly with the number of generated replies. Comparing these results with the total advertiser utility gain Figure 9c reveals an interesting insight: even under the weak context setting, where the context-aware LLM is provided only with advertiser brand names, MOSAIC generates substantial utility for advertisers, which also scales quickly with the number of candidate replies. Notably, the utility gains under strong and weak contexts using twenty candidate replies nearly
31

---

identical. As the level of context increases beyond the weak setting, the additional social welfare generated by MOSAIC is largely recaptured as revenue for the platform, as shown in Figure 9b.
Finally, in Figure 9d, we observe that as the level of context increases, the reference L.M log probability is initially lower for small numbers of candidate replies but quickly matches across all context levels (except no context) as the number of candidates increases. This shows that MOSAIC'S allocation rule (Algorithm 1) is powerful enough that the gains in advertiser value and platform revenue enabled by richer context do not come at the expense of user utility.
To conclude, MOSAIC delivers substantial advertiser utility and platform revenue with minimal contextual information. As the level of context increases, both advertiser value and platform revenue grow significantly, without compromising the usefulness of responses to the user.
D.8 Compute Experiments
In this section, we experimentally evaluate MOSAIC's computational requirements. Using the setup described in Section 6.1, we measure the total wall time required by MOSAIC on single A100 GPU, focusing on the number of candidate replies generated for evaluation. This total time includes:
1. Generating candidate replies using the context-aware LLM.
2. Evaluating these replies with the advertisers' LLMs implemented as discussed in Section 1.
3. Calculating the Rochet payments, as detailed in Section 5. In practice the time to calculate payments is negligible (under 10 milliseconds), and need not increase user-perceived latency because they can be calculated after showing outputs to the user.
Figure 10 presents the total time taken by MOSAIC, which includes both the generation and evaluation of candidate replies. These components are further broken down in Figures 11 and 12, respectively.
As previously demonstrated in Section 6 and Appendix D.6, MOSAIC converges to the optimal distribution using only 20 candidate replies, regardless of the number of advertisers. In Figure 11, observe that generating 10 and 20 candidate replies seconds, respectively. This represents 2.5- and 5-fold increase over the 12.0 seconds required to generate single reply from the same LLM, i.c., the latency perceived by the user when directly querying the LLM.
single A 100 GPU takes 30.5 and 60.5
To reduce user- user-perceived latency, MOSAIC can parallelize candidate generation across multiple GPUs. For example, distributing the generation of 20 replies across two GPUs (each generating 10 replies) reduces the total time to 30.5 seconds, assuming efficient evaluation techniques outlined in Section 4.2. This approach results in MOSAIC requiring approximately times the compute time of generating single reply converge, but with a perceived latency the user of only 2.5 times that of directly querying an LLM (of the same architecture and similar size). Although our experiments were run on a single GPU, note that MOSAIC can always be parallelized further that the user-perceived latency is the same as directly querying a single LLM, as explained in Section 4.2.
180
120
1O3
15
8
Candidoce Reil es Genenite
Figure 10: MOSAIC total wall time (seconds) as a function of the number of candidate replies generated using Reon- Shown are averages over 50 instances including 95% Cls.
32

---

Centration secorvto
dace Rept Generated
Figure 11: MOSAIC generation time as a function of the number of candidate replies generated using Toon Shown are averages over 50 instances including 95% Cls.
Townustion
Candiduse Real is Genorated
Figure 12: MOSAIC evaluation time as a function of the number of candidate replies. Shown are averages over 50 instances including 95 % Cls.
33

---

Fraction Advertises Menúoned
0.0
0.8
6.
85
10 13 Candidate Replies Generated
Figure 13: Fraction of advertisers mentioned in the output reply as a function of the number of candidate replies. Shown are averages over 1250 runs including 95% Cls.
D.9 Conflicts between advertisers
The output of MOSAIC is single text response to the user. In trying to reflect the interests of multiple advertisers, there is a risk of single response being incoherent, just mentioning as many advertisers possible without being good promotion for any of them. However, the platform's 's objective. which takes into account both advertiser utility and usefulness for the user, should account for this: if advertisers are happy to be pross-promoted those outcomes should be more likely, but incoherent advertisements or those that simultaneously promote competitors should be less likely.
In Figure 13 we show the fraction of advertisers mentioned by the context-aware version of MOSAIC as a function of the candidate number of replies used. We observe that initially, the fraction of advertisers mentioned is very high, but drops significantly once the mechanism has converged. The reason is precisely the fact that mentioning more advertisers in this case would cause either significant drop in advertiser utility, drop in the usefulness of the reply to the user. By placing more weight towards the advertisers (i.c., decreasing the value of T in Equation (I)), the platform can increase the number of advertisers shown when the mechanism has converged.
34

---

Using Mone (k0
Using monl Hk] Using Rui()k)
Total Advertiser Reward Sain
120
Using Hbil-10
1:50
Total Adverticar Uniliy
20
5 11 12 Candidate Replies Generated
5
Candidate Replies Generated
(a) Advertiser value gain.
(b) Advertiser utility gain.
Figure 14: Advertiser gains function of the number of candidate replies generated using nee and Toon for the flan-t5-large model. Shown are averages over 1250 instances including 95% Cls.
Using Fand Using Rha (K]
Reply Probabiiity
-1000
Revenus
60
-1500
-2000
20
Using Rowl [K]
Using nu(+)))
Single sample (
Candidate Replies Generated
Candidate Replies Generated
(a) Revenue.
(b) Reply log probability w.r.t the reference LLM.
Figure 15: Revenue and reply log probability as a function of the number of candidate replies generated using Teer and Teon for the flan-t5-large model. Shown averages 1250 instances including 95% Cls.
D.10 Testing with additional language models
In this section, we test MOSAIC's performance using Google's flan-t5-large model [Chung et al., 2022], which uses the Apache 2.0 License.
We repeat exactly the same procedure as detailed in Section 6.1, but using flan-r5-large as the basis for both gen the advertisers' LLMs, and the reference LLM. We the same 50 user queries, each with two advertisers, and test each query on 10 different random seeds, resulting in 500 instances.
In Figure 14a Figure 15b, present the total advertiser value gain, reward gain from participating in MOSAIC, platform revenue, and the usefulness of the returned reply to users as functions of the number of candidate replies generated.
Consistent with the main paper's 's results using Llama-2 2-7bhchht-hhf [Touvron al., 2023], the context- aware version of MOSAIC demonstrates significant value and utility generation for advertisers and successfully captures a substantial portion as platform revenue. In contrast, though, the naive version of MOSAIC fails to generate value utility for advertisers, resulting in negligible revenue for the platform. Similar to the results the main paper, despite both mechanisms converging the platform's objective, shown in Corollary 4.1, their performance for computationally tractable number generated replies diverges.
limit to
Similar to the findings in the main paper, the naive version retains the reference LLM's usefulness to the user (which optimal for the task), while the context-aware version prioritizes the platform's ''s objective, leading to lower user usefulness. Overall, our results using flan-t5- agree closely with those obtained using -lama-2-7bbl 2-7-chat--- demonstrating consistency across models. The main difference is that the context-aware mechanism is even more important when using flan--5-large.
35

---

E
Expanded text of prompts
Table 3: Table of user prompts with corresponding advertisers and their descriptions. Only the first two advertisers are shown for each query; the full prompts are available in the code supplement.
User Query
I Learning to play the guitar.
Advertisers
Sttummaster: selling guitars, tuners, and learning materials for beginners
Chordifyy offering online guitar lessons and interactive practice tools
User Query 2
Best skin routine for dry skin.
Advertisers
HydraSkin: providing moisturizers and serums for dry skin GlowEssentials: selling natural and organic skin care products
User Query 3
Improving productivity while working from home.
Advertisers
MakeeeMakers: offering ergonomic furniture and home office setups FocusApp: providing productivity apps and time management tools
User Query 4
Starting a small online business.
Advertisers
LaumLaunch:: offering e-commerce platform solutions and web design services
MarketMover: providing digital marketing services and SEO optimization
User Query 5
Healthy meal planning budget.
Advertisers
BudgetBites: selling affordable meal kits and recipe books
NutriSaver: offering discounts on healthy groceries and food delivery services
User Query 6
Mastering digital photography.
Advertisers
PixelPro: selling cameras, lenses, and photography accessories
EditCraft: offering photo editing software and online tutorials
User Query 7
Effective ways to reduce household energy use.
Advertisers
EcoSave: offering energy merry--fficcient home appliances and lighting solutions InsulaTech: providing home insulation and energy audit services
User Query 8
Finding the perfect hiking trails. Advertisers
-inailFinder: offering mobile app with detailed maps and trail reviews - GearUp: selling outdoor gear and apparel for hiking enthusiasts
User Query 9
Building a personal brand on social media.
Advertisers
-BrandBuilder: offering personal branding courses and social media strategy consultations VisualizeMe: providing graphic design services for social media content
User Query 10
Learning new language effectively.
Advertisers
LingoLeap: offering online language learning courses and tutoring
36

---

SpeakEasy: providing language learning apps with speech recognition technology
User Query 11
Staying fit without a gym.
Advertisers
HomeFit: selling home workout equipment and fitness accessories
Movelt: offering online fitness classes and personal training sessions
User Query 12
Eco-friendly travel options.
Advertisers
GreenPath: offering eco-friendly travel packages and sustainable tourism experiences
EcoStaa: providing listings for green hotels and accommodations
User Query 13
Mastering the of cooking steak. Advertisers
GriilMaater:: selling premium grills and barbecue accessories
SteaaPerfecctio: offering online cooking classes focused on meat preparation
User Query 14
Creating a successful YouTube channel.
Advertisers
VidGrowth: offering video production courses and YouTube growth strategies ChannelDesign: providing custom YuuTube channel art and video thumbnails
User Query 15
Decorating your home on a budget.
Advertisers
DeccoDDells selling affordable home decor and furniture
StyleSavvy: offering interior design consultations and budget-friendly decorating tips
User Query 16
Managing stress and anxiety.
Advertisers
-CalmSpace: offering mindfulness apps and stress reduction tools
WWllnnss Wave: providing online therapy sessions and mental health resources
User Query 17
How can I make my home more energy efficient?
Advertisers
EcoWise: offering smart home energy solutions and solar panels
GreenInsulate: providing eco-friendly insulation materials and installation services
User Query 18
What are the best strategies for investing in the stock market? Advertisers
InvestSmart: offering investment advice and financial planning services StockGenius: providing an Al-powered stock market analysis tool
User Query 19
How can I improve my mental health?
Advertisers
MindBalance: offering mental health apps and mindfulness courses Serenity providing online counseling and therapy sessions
User Query 20
Where can find organic and sustainable clothing?
Advertisers
FeooWear: selling sustainable and organic elothing options StreenThreadse offering eco-friendly fabrics and fair-trade fashion
User Query 21
How do start a vegetable garden in my backyard? Advertisers
37

---

GardenGuru: selling gardening tools, seeds, and starter kits
PlantPerfect: offering online gardening courses and personalized garden planning
User Query 22
What are the best tools for remote team collaboration?
Advertisers
Tyn:mSnn: offering collaboration software and project management tools
ConneetSSute: providing video conferencing solutions and team communication platforms
User Query 23
How can learn to cook healthy meals quickly?
Advertisers
-QuickChef: offering quick and healthy cooking classes online
NutriFast: selling kitchen gadgets and appliances for healthy cooking
User Query 24
What are the best ways to save for retirement? Advertisers
FutureFund: offering retirement planning and investment services
PensionPlus: providing personalized financial advice for retirement savings
User Query
How can I decorate my apartment on minimalist budger?
Advertisers
-innimalSpace: selling minimalist furniture and decor
Designn: offering interior design consultation for minimalist living spaces
User Query 26
What are the best practices for data security in small businesses? Advertisers
SecurelT: offering cybersecurity solutions for small businesses DataGuard: providing data protection services and training
User Query 27
How can I reduce my carbon footprint with daily habits?
Advertisers
EcoHaaits: offering products and tips for sustainable living
GreenStep: providing carbon offset subscriptions and eco-friendly lifestyle goods
User Query 28
What are effective ways to learn musical instrument online?
Advertisers
MussiMasttrr:: offering online music lessons and virtual tutoring
InstaTuun: selling musical instruments and learning aids
User Query 29
How can I keep my pets healthy and happy? Advertisers
PetWell: offering pet health insurance and wellness products HappyPaws: selling organic pet food and eco-friendly toys
User Query 30
What's the best way to start learning coding from scratch? Advertisers
CodeBegin: offering coding bootcamps and online tutorials for beginners DevPath: providing interactive coding courses and learning platforms
User Query 31
How to find affordable eco-friendly travel destinations?
Advertisers
"GreenTraveles offering eco-friendly travel guides and affordable green vacation packages Adiiisss providing reviews and bookings for sustainable travel options
User Query 32
What are the best ways to improve indoor air quality?
38

---

Advertisers
AirPure: selling air purifiers and natural air freshening solutions
BreatheFasy: offering indoor plant subscriptions and ventilation solutions
User Query 33
How to make my own natural beauty products?
Advertisers
NatureGlow: offering DIY beauty product kits and organic ingredients
EcoBeauty: selling guides and supplies for creating homemade natural cosmetics
User Query 34
What are the best techniques for effective online teaching?
Advertisers
EduTech: offering online teaching tools and educational technology solutions
TeachMaster: providing courses on online pedagogy and digital classroom management
User Query 35
How create a successful podcast from home?
Advertisers
-PoCCastffy: offering podcast creation courses and audio equipment
Wave selling podcast editing software and hosting services
User Query 36
What are the most effective ways to market a small business locally? Advertisers
LLoclBoost:: offering local SEO services and marketing strategies for small businesses
MarketTown: providing targeted advertising solutions and local business networking opportunities
User Query 37
How can I optimize my home office for productivity?
Advertisers
WorkZen: offering ergonomic office furniture and productivity tools
SpaceCraft: providing home office design services and organization solutions
User Query 38
What are the best platforms for freelance writers to find work?
Advertisers
-WiieFFreel:: offering job board and resources for freelance writers -ContentConnect: providing a platform to connect writers with businesses
User Query 39
How to get started with meditation and mindfulness?
Advertisers
MindffulStart: offering guided meditation apps and mindfulness training -ZenSpace: selling meditation cushions and mindfulness journals
User Query 40
Where can find unique handmade gifts?
Advertisers
-CraftCorner: selling handmade gifts and artisan crafts
MakerMarret: offering marketplace for unique handmade items from local artists
User Query
How can I improve my credit score quickly?
Advertisers
CreditBoost: offering credit monitoring services and financial advice
ScoreSurge: providing tools and tips for improving your credit score
User Query 42
What are the best apps for tracking fitness and nutrition?
Advertisers
FitTrack: offering comprehensive fitness and nutrition tracking apps
-utriiSnn: selling personalized nutrition plans and diet tracking tools
User Query 43
39

---

How to plan an environmentally friendly wedding? Advertisers
GreenBride:: offering eco- fo-friiedly wedding planning services and supplies
FcoWed: providing sustainable wedding attire and decor
User Query 44
What are the safest ways to travel during pandemic? Advertisers
SafeJourny:: offering travel safety kits and pandemic travel advice Trave:: providing information on safe destinations and travel insurance
User Query 45
How can learn DIY home repairs and improvements? Advertisers
Yoursef: offering online courses and tutorials for home repair -DIHHome: selling DIY home improvement tools and kits
User Query 46
What are the best resources for starting a plant-based diet? Advertisers
PlantEats: offering guides and meal plans for starting plant-based diet DeggieVibe: selling plant- based cookbooks and kitchen gadgets
User Query 47
Tips for running marathon.
Advertisers
- ReanaattGear: specializing in perfrmerfore running shoes
- Hyddrauull: offering electrolyte drinks and energy bars for athletes
User Query 48
Best practices for organic gardening.
Advertisers
GreenThhmb Solutions: providing organic fertilizers and pest control products
- EeooGrow: selling heirloom seeds and sustainable gardening tools
User Query 49
How to improve home WiFi?
Advertisers
SignalBoost: which offers advanced WiFi routers and extenders NetWizard: providing network optimization services and support
User Query 50
Ways to save travel.
Advertisers
BudggetJorneys: specializing in affordable travel packages and deals
StayLocal: offering discounts on boutique hotels and unique accommodations
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction make theoretical claims, which we prove, and describe the experiments ran.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We clearly state the (quite weak) assumptions required for our key mecha- nism design properties to hold in Section and Section 5. We describe the scope of the experiments (multiple language models, ablation on aspects of the mechanism, etc.) in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All proofs (e.g., of strategyproofness, convergence rates, etc. in Sections 4 and 5) have their assumptions clearly stated and discussed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All relevant prompts, the list of fictitious advertisers, and hyperparameters required for running the experiments are included.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
42

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
Our generated data and code are included in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
onPolicy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. wtwpps.ccppulll//ppp wwcpublic/geteeececccccccceeeeee meliiccggudes////e ProdeSubmissiooPoon
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: As in question all relevant hyperparameters included. We also clearly describe how we estimated performance metrics to compare performance under different conditions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We report 95% CIs (over experiment runs) around our key performance metrics (revenue, advertiser welfare gain, etc.) in Section 6 and in all relevant appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We describe the compute nodes used in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : htt///eerrpp..// cct
Answer: [Yes]
Justification: There are human subjects or sensitive data. The primary contribution of our paper is mechanism design theory well proof of concept experiments. Negative social impacts of our work are unlikely. See also checklist item 10.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Our paper is primarily fundamental research, consisting of theoretical results and proof of concept experiments, so there no direct societal impact. Our experiments (Section 6) do consider shifts in welfare between advertisers, the user, and the platform.
44

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We don't train any models nor does any of our released code have high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: For the open-source LLMs in our experiments, creators are credited, the terms of use are respected, and the licenses named (Appendix D).
Guidelines:
The answer NA means that the paper does
existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
45

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We don't it release any new assets other than the code and synthetic data required reproduce the experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We don't 't have any human subjects experiments.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: We don't have any human subjects experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
46

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: The entire paper, especially the experiments section, describes our usage of LLMs, and we mention them even in the title.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https:/ anttps//neurrps. http:////errrpsscccoooeeeeeeeeee /ct///oeeeeencce/225//////////// for what should or should not be described.
47


Reviews:
[{"review_id": "uqwlpLei8u", "reviewer": "Reviewer_vqqH", "summary": "This paper introduces a truthful mechanism MOSAIC for advertising with LLMs. The authors assume that each advertiser provides an LLM or reward model as the ad creation and wants to affect the auctioneer’s LLM output towards the advertiser’s benefit. This paper provides a practical mechanism to balance the advertisers’ utilities and user’s satisfaction. The mechanism includes an allocation rule that only requires API access to the advertisers’ models and approximately maximizes the social welfare, and a payment rule that incentivizes truthful reward reporting. The authors conducted experiments on real LLMs, demonstrating the effectiveness of MOSAIC.", "questions": "When the advertiser evaluates its preference of the query-answer pair, the user query is meant to be sent to the advertiser’s model. This can potentially cause privacy issues, especially in the “API access” scenario.\nHow about the cost of serving the advertisers’ models? The cost could be too high to be ignored in the mechanism especially for the cutting-edge LLMs.", "limitations": "please refer above", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\nTo the best of my knowledge, this work proposed one of the first practical mechanisms for LLM advertising, showing the potential to fill the gap between theory and practice. The mechanism is concise and theoretical analysis is solid.\nWeaknesses\nConsidering that the authors claim this is a practical mechanism, the experiment setup is not sufficient, leading to less convincing results. For example, the authors did not discuss the optimal M choice when various numbers of advertisers participated in. I suggest the authors provide more experimental results in various settings, including different kinds of advertiser’s model (reward model or LLMs), various ad topics and more advertisers.\nThe paper assumes advertisers can accurately encode their preferences via LLMs or reward functions, which may not be feasible for all advertisers, especially smaller or non-technical ones.\nSome of the notations are not clear. For example, what is the exact definition of $\\pi_{\\hat{r}_{-i}}$ in Lemma 5.2 (Line 287)?.\nThe paper does not deeply engage with ethical implications of allowing advertisers to influence LLM outputs, such as manipulation, bias amplification, or impacts on user trust. There is also little discussion of fairness, such as whether small advertisers get fair exposure compared to large ones with higher rewards.", "was_revised": true, "final_justification": "I have read the rebuttal and discussions with authors, and maintain my current rating.", "rebuttal": "We thank the reviewer for their positive comments about the relevance of our application and their positive remarks about our mechanism. We worked hard to make a mechanism without needless complexity, yet which works well and has the right theoretical properties.\n\n## Response to questions:\n\n### “The authors did not discuss the optimal M choice when various numbers of advertisers participated”\n\nIn appendix D.6 we provide results with a varying number of advertisers and show that, for all numbers of advertisers tested, MOSAIC's performance across all metrics of interest increases monotonically with M. At the same time, the marginal benefit of increasing M is decreasing, as supported by our theoretical analysis. The optimal M  to use would be the one where the marginal cost of generating an additional reply becomes greater than the marginal benefit to the platform  (see appendix D.8 for a detailed analysis of the marginal cost of increasing M). Of course, that depends on the business weights placed by the platform on the various metrics of interest. \nNote that this trade-off is not unique to advertising with LLMs; in classic online ad auctions, large platforms have to trade off the predictive power of the models they use to evaluate the quality of ads shown to the user with the computational costs of those same models.\n\n\n### Further experimental results (different reward models, various numbers of advertisers,  different ad topics):\n\nWe provide extensive additional experimental results throughout the appendix:\n\nReward models: In Appendix D.10, we evaluate multiple LLM architectures (corresponding to different reward models) and observe consistently strong performance. That said, identifying which reward models best reflect advertiser preferences remains an important direction for future work.\n\nNumber of advertisers: In Appendix D.6, we provide extensive experimental results varying the number of advertisers, and observe that MOSAIC exhibits similarly strong performance for all tested setups.\n\nQuery diversity: Our experiments use over 50 user queries spanning diverse topics and advertiser types including music lessons, skincare routines, household utility providers, and mental health advice. For a complete list of prompts and participating advertisers please see Appendix E. \n\n\n\n### On the feasibility of  advertisers accurately encoding their preferences via LLMs and on potential privacy issues on the “API access” scenario:\n\nThank you for raising these very reasonable concerns. To address the first point: An advertiser indeed has higher utility in our mechanism if they can produce LLMs that better reflect their interests. This is generally the case in truthful mechanism design: a participant’s utility is maximized when they perfectly report their value function, which is why for our theoretical analysis we adopt the typical mechanism design assumption that truthful reporting is possible.\n\nOf course, from a practical perspective, a real advertiser might not have the know-how to produce an LLM reflecting their advertising preferences. This is closely related to two interlocking issues in conventional online ad auctions: (1) the conversions that an advertiser will experience also depend on the quality of the ad, not just the position where it is shown, and (2) advertisers may not know how to bid appropriately in the auction. Ad platforms offer various solutions to help advertisers improve their ads, and autobidders to help them bid successfully, an approach that could also be adopted for our mechanism.\n\nSeveral of the largest online advertising platforms also have the capacity to host and finetune LLMs, so they already have the infrastructure to offer an “LLM autobidder”, where they would help an advertiser train an LLM to reflect their interests, and also provide inference. Offering such a feature would be consistent with longstanding practice in traditional ad auctions. And, if all LLMs are hosted by the platform, it would solve the issue of user privacy.\n\nWe note that the platform-hosted setup described here is simply an alternate framing of the same mechanism. All theoretical guarantees discussed in the paper are preserved. We will add a short discussion of this alternate perspective on the mechanism to the final version of the paper.\n\n\n### “How about the cost of serving the advertisers’ models? The cost could be too high to be ignored in the mechanism especially for the cutting-edge LLMs.”\n\nThere is a cost in extra inference passes that would need to be offset by the revenue brought in by the auction. In Appendix D.8, we provide detailed computational results, showing that the compute cost of generating 10 or 20 candidate replies (sufficient to converge to the optimal distribution for all number of advertisers tested) is less than 2.5 and 5 times the compute cost of generating a single reply. At the same time, in Section 4.2, we detail how MOSAIC is fully compatible with efficient methods for query generation and evaluation, which means that it benefits from any advancements in this research area. Finally, in practice, we don’t think that a high-parameter model that also uses a ton of reasoning tokens (for example) would be required to accurately capture advertiser preferences.\n\nIt is also worth noting that online ad platforms incur per-query inference costs to serve ads. For instance, in sponsored search auctions, the platform estimates the expected value of showing a specific ad in a specific position by performing inference to predict the likelihood of a user conversion. This is conceptually similar to evaluating advertiser-specific models in our setting. In that sense, MOSAIC’s inference requirements are compatible with existing infrastructure and practices.\n\n\n### \"What is the exact definition of $\\pi_{\\hat{r}_{-i}}$?\"\n\n$\\pi_{\\hat{r}_{-i}}$ is the theoretically optimal LLM for  the reported reward profile of all advertisers other than $i$. We will clarify this in the final version of the paper. \n\n\n### Alternative objectives such as fairness for smaller advertisers:\n\nThe most common objective in mechanism design, and by extension in ad auctions, is social welfare. Creating a similar mechanism for a different objective, e.g. egalitarian social welfare or a similar concept, would be valuable follow-up work, and in other mechanisms design settings such mechanisms have followed welfare-maximizing solutions. But we believe that solving the mechanism design problem for social welfare is the key first step.\n\n### On the ethical implications and impact on user trust of allowing advertisers to influence LLM outputs:\n\nWe’ve made the key assumption that, in the absence of advertisers, the platform’s and user’s interests are aligned: that is, the reference LLM has been successfully trained to maximize usefulness to the user. This mirrors common assumptions in settings like sponsored search or social media feeds, where the native (non-ad) content is assumed to optimize user utility.\n\nIn practice, of course, this alignment may be imperfect. To what extent do trained LLMs reflect user interests? Do users trust them? Should they? These are deep and important questions, but they are orthogonal to our paper, relating to human psychology and perception, and arise even in advertising-free settings. We view them as well outside the scope of our work.\n\nRather than address such questions incompletely, we adopt the standard assumption in both theoretical and applied mechanism design: namely, that true user and advertiser preferences can be accurately conveyed to the mechanism.\n\nFinally, it's worth noting that these concerns are not unique to LLM-based advertising. In any platform that incorporates ads, whether search engines or social media, the presence of advertisers influences what users see. Ensuring the integrity of this ecosystem requires vetting advertiser content, a responsibility of the platform. But this vetting process is orthogonal to the question we study: how to best represent vetted advertisers within a mechanism that balances revenue for the platform, value for the advertisers, and utility for the user. \n\nWe will add a brief discussion to the paper highlighting the need for more research in this direction."}, {"review_id": "ElXdedFl46", "reviewer": "Reviewer_riQC", "summary": "This paper studies a model where multiple LLMs need to truthfully aggregate preferences, with respect to a reference LLM. The authors noted that online advertising is the most natural application setting of this model, so discussion of this paper is centered around advertising.\n\nUnder the authors' model, each advertiser has her own LLM, and the advertisers aim to influence the reference LLM (provided by the search engine to give good answers to users maximizing user experience). The authors noted a relationship between the studied model and Reinforcement Learning from Human Feedback. The core technique is described in Equation 2, which basically uses RLHF techniques. To summarize it in English, we can use the refernece LLM to generate samples, and then apply importance sampling techniques to create samples that maximize Equation 1, which considers the advertisers' preference.", "questions": "Could you please comment on whether free riding is an issue, as a result of providing context using the method in footnote 4.", "limitations": "Yes, in the paper checklist, the authors emphasized that this is theoretical research.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Overall, the paper's proposal of the new LLM advertising framework is, for the most part, practically sound. The algorithm is elegant. The authors showed that the allocation rule is monotonic so strategy-proof payments can be derived and different versions of IR conditions are discussed in the paper. Even though LLM advertising's main goal should be revenue in my opinion, but welfare maximizing is also a reasonable objective. Section 4.2 discusses practical considerations, which in my opinion adds a lot of strength to the paper. The proposed framework is easy to implement, unlike the earlier token-based auction, which in its current form cannot be used in practise. For example, the proposed framework uses 20 LLM forward passes and the welfare is already quite good, as shown in experiments, and the token-based auction would require a lot more to generate any long paragraph.\n\nThe downside of this paper is \"context-aware\" part. In practise, if we need to provide context like footnote 4 -- \"try to mention advertiser x, advertiser x description\", then I think it creates a free-rider situation. It will be a problem if the objective is revenue maximizing. If we need to provide context like this, then I think there is a good chance that an advertiser gets free advertisement. What I mean is that an advertiser can bid 0 and there is still chance of having the ads shown if the context is provided this way in practise. This is difficult to fix. As the authors noted, we kind of must provide the context in practise, because the beautiful theoretical result in Equation 1 and 2 cannot be used directly without the context.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my concern on free-riding.", "rebuttal": "We appreciate the reviewer’s positive comments about the elegance and practicality of our algorithm. Designing a mechanism that is practical and simple to implement, yet has nice theoretical properties, was a central goal in working on this paper.\n\n## Response to questions:\n\n### \"I think there is a potential issue of free-riding.\"\n\nThank you for pointing to the potential issue of free-riding, which was indeed a major challenge we had to address. \nIn Section 5.2 and Appendix C.2, we explain in detail why free-riding can be much more pronounced in LLM-based advertising compared to traditional online advertising. In Appendix C.4, we additionally explain why free-riding will lead to market unravelling for any mechanism in this setting. \n\nTo mitigate this potential issue, in Section 5.3, we introduce a carefully-designed offset to the Rochet payments, ensuring that MOSAIC remains truthful, while satisfying a property we call \"what you give is what you get:\"with this offset in place, advertisers' utilities are proportional to their contributions to MOSAIC's welfare. Thus, advertisers who have very low values also have very low utility, which effectively mitigates the concern regarding “free-riding.” \n\nFinally, in Appendix D.5, we provide strong computational experiments, showing that, in all cases tested, this advertiser-specific offset increases an advertiser's expected utility, makes the relationship between an advertiser's contribution to social welfare and her utility both more linear and positively correlated, and also makes  our mechanism ex-ante IR."}, {"review_id": "gXL5fv3qPO", "reviewer": "Reviewer_SNPf", "summary": "This paper introduces MOSAIC, a novel auction mechanism designed for the truthful aggregation of multiple advertisers' preferences concerning Large Language Model (LLM) outputs. The mechanism addresses the challenge of enabling advertisers to influence LLM-generated content while simultaneously allowing the platform to optimize advertiser utility without compromising user satisfaction. MOSAIC offers several key advantages: it incentivizes truthful preference reporting, provably and efficiently converges to the optimal LLM output without requiring fine-tuning or direct manipulation of model weights, and effectively integrates contextual information to enhance performance. Experimental evaluations underscore MOSAIC's effectiveness, demonstrating strong advertiser value, robust platform revenue, and notable computational efficiency.", "questions": "1. How robust is the MOSAIC mechanism in scenarios where advertiser preferences significantly diverge from the user preferences encapsulated by the reference LLM?\n\n2. What implications arise for MOSAIC's performance or theoretical guarantees if the contextual policy ($\\pi_{con}$) is substantially different from the optimal policy ($\\pi_{opt}$)? In the current experiments, the observed difference between $\\pi_{con}$ and $\\pi_{opt}$ appears relatively small.\n\n3. Do the authors believe that the current allocation rule presented is the unique solution for this problem setting?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n1. This paper investigates an interesting and highly practical problem with strong motivation, particularly relevant for online advertising scenarios.\n\n2. The authors provide thorough explanations for each of their results and conduct detailed comparisons with prior work across various properties, significantly improving the paper's clarity and ease of comprehension.\n\n3. The proposed mechanism is straightforward to implement, and the experimental section offers valuable insights into how the size of the candidate set ($M$) influences other critical variables.\n\n### Weaknesses:\n\nMy primary concern lies with the relative technical strength of the paper. The main theoretical result, Theorem 5.1, appears derivable by simply validating the cyclic monotonicity of the allocation rule, which in turn directly implies the payment rule. While other theoretical results pertain solely to computational aspects.\n\nRegarding the experimental section, the comparison between the Context-Aware Mechanism Output and Baseline Mechanism Output in Figure 1 is arguably meaningless. Without incorporating advertiser-specific information, it is unreasonable to expect the LLM to generate content relevant to them.", "was_revised": true, "final_justification": "I have read the authors' rebuttal, and I would like to maintain my original assessment. Specifically, I believe this paper addresses a significant problem in online advertising, and the solution can be efficiently implemented. Meanwhile, the contribution of the theoretical results remains incremental to me. **Therefore, I stand by my initial score of weakly accept.** I respect the final decision of the AC and the perspectives of the other reviewers.", "rebuttal": "We thank the reviewer for acknowledging the relevance of our problem and the thoroughness of our analysis and experiments. We also especially appreciate the remark on how straightforward our mechanism is to implement: this was a primary design goal.\n\n## Responses to questions:\n\n### \"Robustness to cases where the reference LLM diverges significantly from the advertiser’s preferences\"\n\nFrom a theoretical perspective, MOSAIC remains truthful in all such cases. As far as payments go, if the result strongly favors the advertisers, compared to the reference LLM, they will have to pay a lot; if the result strongly favors the user, the advertisers will not pay too much . This intuition is formalized in Lemma 5.2, where we prove that an advertiser’s expected utility is proportional to how well-aligned her preferences are with the theoretically optimal LLM for the platform’s objective in the marginal economy where she does not participate in the mechanism. Put differently, the more an advertiser “moves” the output distribution, the higher her payments, and the lower her utility.\n\n### “What implications arise for MOSAIC's performance or theoretical guarantees if the contextual policy $\\pi_{con}$ is substantially different from the optimal policy $\\pi_{opt}$? In the current experiments, the observed difference between πcon and πopt  appears relatively small.”\n\nIn Lemma 4.2, we prove that, under very reasonable assumptions (absolute continuity),  any contextual policy will converge to the optimal policy. At the same time, in Lemma B.3, we show that the convergence rate is at least 1 / \\sqrt{M}. However, the convergence also depends on the distance between the optimal and the contextual policy, meaning that, the further apart that the two policies are,  the more samples are required. \n\nWe disagree that  in the current experiments, the difference between the two distributions is small: note that the y-axis of  figure 2 (a) is in log scale. Nevertheless, in appendix D.7, we perform an extensive ablation experiment on MOSAIC’s performance for various levels of context, and show that MOSAIC maintains very strong performance even under much weaker contextual policies. \n\nHowever, both the advertiser’s utility, and the platform’s revenue are monotonically increasing with better contextual policies. Thus, all participants in the system are incentive-aligned to provide useful context to the platform. In our eyes, this is similar to online advertising, where advertisers are incentivized to design better ads to increase their CTR and therefore their utility. \n\n\n### Do the authors believe that the current allocation rule presented is the unique solution for this problem setting?\n\nWhen working on this paper, we explored many alternative approaches before settling on this design. One decision we made is that our mechanism should be static: all “options” for the advertisers are decided in advance, the advertisers report their preferences, and a final decision is taken by the mechanism. This is in contrast to a dynamic mechanism, where there are intermediate points for the advertisers to report their preferences, and then this affects the mechanism’s downstream actions. In section 2, we explain some limitations behind the dynamic mechanism for this problem proposed  by Dütting et al., 2024 [1]. To a large extent, these issues are inherent to any dynamic mechanism and not unique to that paper.\n\nWe also decided that, given the advertising application we envision, any fine-tuning of weights would be impractical and computationally costly. Given this constraint, in order to change the output distribution, one has to choose some LLM sampling scheme.\n\nConsidering only static and sampling-based mechanisms leaves us in a relatively small part of the design space. An approach based on importance sampling is the most natural and straightforward way to solve the problem while ensuring cyclic monotonicity. It is also pleasantly simple and works well in practice.\n\nWith that being said, this does not exclude the design of sampling rules tailored to this problem.  There are many methods for guided LLM sampling appearing all the time. Some may be well-suited to conversion into an even better truthful static mechanism, in the same spirit as our paper. And there may be ways to overcome the challenges of designing dynamic incentive compatible mechanisms. This is an interesting area of future work. We will add a discussion to this end to the final version of the paper. \n\n\n### \"My primary concern lies with the relative technical strength of the paper. The main theoretical result, Theorem 5.1, appears derivable by simply validating the cyclic monotonicity of the allocation rule, which in turn directly implies the payment rule.\"\n\nWe believe that our answer above also sheds light on your concern regarding technical strength. Cyclic monotonicity is the necessary and sufficient condition for strategyproofness, and (up to a constant) pins down truthful payments, so showing that any mechanism is strategyproof will involve nothing more or less than establishing cyclic monotonicity.  \n We see our contribution not as a highly technical proof of this property, but as designing a very simple and practical mechanism that has many nice properties including strategyproofness. While some of the other allocation rules we explored might have resulted in a more interesting proof, they were also much worse in terms of computational efficiency and practicality.\n\nWith that being said, as we alluded to before, Rochet’s result identifies our payments only up to a constant. In Appendices C.3 and C.4,  we detail how naively setting that constant to zero would be detrimental to the long-term success of a mechanism for this setting, as it could lead to free-riding, while at the same time, the mechanism would not be individually rational. Then, in Section 5.3, we design an advertiser-specific payment offset that, while maintaining strategy-proofness, completely alleviates those issues. In Lemmata C.1 and C.2, we prove that MOSAIC is “almost IR”, which we explain  is the strongest notion of IR one could hope for in this setting. Additionally, in Lemma 5.2, we prove that this offset aligns each advertiser’s utility with her contribution to social welfare. Finally, in Section 6 and Appendix D, we experimentally  show how effective this offset is in mitigating these potential issues. We believe that identifying and mitigating these issues is a further important technical contribution.\n\n### Meaningfulness of figure 1:\n\nThe goal of Figure 1 was to clearly establish  that the context is important for reasonable practical performance (we also emphasize this in the experiments). This fact is the reason we need to design a mechanism that still works with samples from any \\pi_con, not just \\pi_ref, which is a key aspect of our paper.\n\n\n### References \n[1] Paul Dütting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, and Song Zuo. Mechanism Design for Large Language Models. In Proceedings of the ACM Web Conference 2024 (WWW ’24), pp. 144–155. ACM, 2024."}, {"review_id": "2HKMrMAZpx", "reviewer": "Reviewer_g2Ts", "summary": "This paper study the scenario where LLM are applied to ad auctions and they propose a mechanism that converges to optimal distribution. They conduct experiments of MOSAIC in real settings. Their payment rule ensures that there is no incentive for a participant to misreport their preference, according to the theory analysis.", "questions": "How in real world that this model makes sense, i.e., the auctioneers pay to influence the output of LLM.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n(1) Applying LLM to ad auctions is an emerging field and has own its significance in real application and requires further research. This paper provides one way of doing so.\n\n(2) The results provided in this paper are comprehensive, in the sense of with both theory analysis and empirical results.", "was_revised": true, "final_justification": "I have read the authors’ response defending their model. Though it is a solid empirical work, the conclusion appears to be that there is currently no mature application scenario for paying to influence an LLM’s output. I maintain my original score of acceptance.", "rebuttal": "We thank the reviewer for their positive comments about the significance of our application and thoroughness of the analysis.\n\nWe assume that the main question is whether or not allowing *advertisers* to pay to steer LLM responses could have any real-world application. Currently, many LLM platforms are experimenting with advertising, although as far as we know, none allow advertisers to bid on generated content, yet. Also, one of the leading AI companies is also a leading ad auction company (Google). And in other settings (e.g., newsfeeds), running complex auctions to mix user content with ads is already standard. So we see this as the natural next step.\n\nWe think our approach makes the most sense for \"LLM search summaries\" (e.g. Perplexity, Google AI search, etc.) where a user makes a single fact-based query and receives a reply, and where traditional search already uses an ad-driven model."}]

Author rebuttal:

Meta-review: The paper studies the problem of designing LLM-based truthful auctions, where a user queries an LLM whose answer is the result of an auction among different “advertisers” who would like to sway the outcome in their favor, whereas the platform wants to generate the best answer for the user, while ensuring high reward for the advertisers. The authors make connections with RLHF and design an allocation rule and a payment strategy to ensure a strategy proof mechanism, while maximizing social welfare. The paper reports a series of theoretical guarantees as well as a practical implementation and tests using mid-scale LLMs in a synthetic advertising scenario.

Based on the reviewers and rebuttal, there is general consensus towards accepting the paper. The main concerns raised by the reviewers relate to some of the setting and theoretical assumptions (e.g., assuming advertisers have a properly trained LLMs for their preferences) and the empirical validation (e.g., number of advertisers). The authors already addressed some of these concerns in the appendix and in the rebuttal, but there are definitely some remaining aspects that are not fully covered such as ethical considerations, a broader fairness analysis, or privacy issues. While I believe these are very valid concerns, the novelty of the contribution, its technical soundness and preliminary evidence of effectiveness outweighs these concerns and make the paper a very solid “first” step in this new very significant problem. In order to reinforce even further this aspect, I strongly encourage to further expand the conclusion section by discussing all the limitations of the current setting/approach and the most promising open research directions.
Decision: Accept (poster)