Ad Auctions for LLMs via Retrieval Augmented Generation
Authors: MohammadTaghi Hajiaghayi
Sebastien Lahaie
Keivan Rezaei
Suho Shin
Venue: NeurIPS 2024 poster (2024)
Keywords: Large Language Model
Online Advertising
Auction Design
Primary area: other

Abstract: In the field of computational advertising, the integration of ads into the outputs of large language models (LLMs) presents an opportunity to support these services without compromising content integrity. This paper introduces novel auction mechanisms for ad allocation and pricing within the textual outputs of LLMs, leveraging retrieval-augmented generation (RAG). We propose a \emph{segment auction} where an ad is probabilistically retrieved for each discourse segment (paragraph, section, or entire output) according to its bid and relevance, following the RAG framework, and priced according to competing bids. We show that our auction maximizes logarithmic social welfare, a new notion of welfare that balances allocation efficiency and fairness, and we characterize the associated incentive-compatible pricing rule. These results are extended to multi-ad allocation per segment. An empirical evaluation validates the feasibility and effectiveness of our approach over several ad auction scenarios, and exhibits inherent tradeoffs in metrics as we allow the LLM more flexibility to allocate ads.

Ad Auctions for LLMs via Retrieval Augmented Generation
MohammadTaggh Hajiaghayi University of Maryland hajiagha @ umd.edu
Sébastien Lahaie Google Research slahaie google.com
Keivan Rezaei University of Maryland krezaei @ @umd.edu
Suho Shin University of Maryland suhoshin udu.edu
Abstract
the field of computational advertising, the integration of ads into the outputs of large language models (LLMMs) presents opportunity support these ser- vices without compromising content integrity. This paper introduces novel auction mechanisms for ad allocation and pricing within the textual outputs of LLMs, leveraging surrivall-augeette generation (RAG). We propose segment auction where ad probabilistically retrieved for each discourse segment (paragraph, section, or entire output) according to its bid and relevance, following the RAG framework, and priced according competing bids. We show that our auction max- imizes logarithmic social welfare, new notion of welfare that balances allocation efficiency and fairness, and we characterize the associated grrentive-compatible pricing rule. These results are extended to multi-ad allocation per segment. An empirical evaluation validates the feasibility and effectiveness of our approach over several ad auction scenarios, and exhibits inherent tradeoffs in metrics as we allow the L.M more flexibility allocate ads.
Introduction
Large language models (LLMs) [4, 1, 39] have recently gained widespread attention, serving various functions including question answering, content generation, translation, and code completion [31, 13, 44, 24]. The emergence of AI-driven assistant models like ChatGPT, Gemini, and Claude has influenced how individuals interact with these technologies, as they increasingly use them to streamline and enhance their work.
While LLMS provide a fresh way to engage with information, the most advanced models are costly operate [27]. To date, online advertising has been one of the most successful business models of the digital economy. Ads support a wide variety of online content and services, ranging from search engines, online publishers, video content and more. However, LLM services today predominantly follow subscription model [32]. A natural question to ask in this context whether advertising could support LLMs to alleviate serving costs and charges users, and what format advertising on LLMs might take.
In this paper, we develop auctions that allocate online ads within the output of LLMs using the framework of retrieval augmented generation (RAG) [23]. RAG is one of the most popular techniques to integrate factual information into the output of LLMs. When query is submitted by user, RAG first retrieves the top-k most relevant documents for the query from a database, and then conditions on these documents generate the LLM's output, significantly enhancing the reliability of the generated
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Advertisers
AUCTION(b.o) 4)
Generation
bids
winner
b (D1.02...,. Dn) q (91, 9n)
Vilore
Query: some bocks cén To K3l Mockingsed?
BeokdHaven
ExpressoEdge
ColaBubdie
relevance
Context
MasieStream
ads
Seyrea
LLM
Retriever Pg
Spyres:
Query: Can you suggest some books similar Kill Mockingbird'
Output
Time Muckingloed"" ready iremersive [Segment MasaMaart offers snacks your reading marations. (Begment Eriaanc your reading convenience with Volore's latest tablecs amartosacches, dasigned effortiess transition batween digitll and sterary explontioo
[Bagment explore "The
of high-queiity
Figure 1: Segment auction architecture for LLMs via RAG.
content [14]. The RAG framework naturally lends itself to ad allocation, by retrieving relevant ads from a database rather than documents. The ads can then be incorporated into the output of the LLM via a variety of methods, most directly via prompt engineering.
In the auction design literature, a typical approach is to start with a desirable social choice function, and derive an allocation rule that maximizes this function [34]. Here, we take the RAG allocation as given, and investigate which social choice function it corresponds to and what associated pricing rules give good incentive properties. In particular, we are interested in pricing rules that are individually rational, such that there is always an incentive to participate, and ideally incentive compatible, such that advertisers are motivated to report their true willingness to pay for their ad to be shown [15, 35,21] 21].
Our Contributions. We introduce the concept of a segment auction, in which ads are allocated for each discourse segment, which could be sentence, paragraph. or the entire LLM output. The architecture of a segment auction is depicted in Figure 1. Given a user query to the LLM, relevant ads together with bids are retrieved from database. The retriever forwards the bids to the auction, along with click probabilities (aligned with retrieval probabilities). The auction implements a randomized allocation rule based on these inputs, following the RAG framework, and the LLM bases its output on the winning ad. The auction can be run repeatedly for each segment, or it can compute several winners for multiple segments at once.
We first consider the case where a single ad is allocated per segment, and later study the generalization to multiple ads per segment. For single-ad allocation per segment, we show that the RaG-based allocation rule is optimal with respect to a new notion of logarithmic social welfare (LSW), a type of welfare function that balances economic efficiency and fairness. This balance highly desirable for LLM outputs, which need to be satisfactory to users while potentially generating ad revenue. We show how the randomized RAG allocation rule can be obtained as a randomization over deterministic truthful auctions, which directly leads to truthful implementation of RAG allocation. We confirm that the expected payment under this scheme matches the pricing rule that obtains from Myerson's lemma [28]. For the general setting of multi-ad allocation per segment, we again provide an auction obtained as a randomization over deterministic truthful auctions. The main device for single- and multi-ad allocation is to perturb the bids with random additive offsets, drawing on ideas from discrete choice methods [41].
We validate the feasibility and effectiveness of our approach via experiments using publicly-availate LLM APIs. We compare single- and multi-allocation segment auctions against each other, and against two naive baselines that do not consider relevance scores, or do not use the LLM to integrate ads (simply appending them the output instead). Our key finding is that whereas repeated single-ad segment auctions generate higher revenue, a multi-al allti-allocation auction leads to higher output quality, as measured by the cosine similarity between embeddings of the output omitting ads, and the output conditioned on ads. We corroborate these results with a qualitative analysis of outputs from single- and multi-allocation segment auctions. We conclude by discussing remaining practical challenges in implementing segment auctions.

---

Related Work. The question of using auctions to influence LLM output has been examined by few very recent papers, Feizi et al. [12] present a high-level framework for LLM- advertising and discuss key requirements such as privacy, latency, and reliability. Duetting et al. [10] propose token auction to aggregate the outputs of several distinct L.M,s, weighted by bids. The motivation that the LLMs can be provided by different competing advertisers. Under this approach every single token is the result of an auction to choose the source LLM, whereas in our work advertisers bid more traditionally to be placed in some segments of the output (e.g., the first paragraph).
Soumalias et al. [37] provide an auction framework for agents (e.g,, advertisers) to steer LLM output according to their preferences, which can be represented by their own LLM or directly via a reward function. Their approach closely linked reinforcement learning with human feedback (RLHF), rather than RAG. Candidate outputs are generated by conditioning on context from each advertiser, and one of these outputs is sampled according to aggregate reward across agents. Our approach does not necessarily require generating output candidates for each ad, although this can increase allocative efficiency, as we diseuss. Along similar lines, Sun et al. [38] investigate how to design mechanisms that incentivize truthful reporting of preferences when fine-tuning LLMs to cater to multiple user groups.
Dubey et al. [9] introduce a factorized framework for LLM ad auctions where an auction module allocates prominence (representing relative importance) to each ad based on their bids and predicted chick-through rates. Although prominence could in practice map to ad selection probabilities under RAG, their paper focuses on the concrete application of generating ad summaries within the LLM output. The auction module's prominence allocation serves as guide to control the output of the LLM module, ensuring that ads with higher prominence receive longer mentions and more user attention. The framework is designed to be incentive compatible and to maximize social welfare by ensuring high-quality summaries and efficient allocation of ad space.
Since the introduction of RAG by Lewis et al. [23]. the technique has gained widespread interest in academia and industry. The retrieval component is crucial for our work, with key sub-components including the embedding model for efficient document similarity search [7, 36, 45] and query optimization to incorporate contextual information [47, 8]. For more details on RAG, see the recent survey by Gao et al. [14] or tutorial by Asai et al. [3].
2 Preliminaries
We now formally define the model behind LLM auctions for ad allocation via RAG. Consider a set of ads indexed by [n] = (1. n.., where each ad i is provided by an advertiser. (We will refer to the ad and advertiser interchangeably for simplicity.) We often write a; to denote the i-th ad for clarity. Each advertiser a, has a private valuation v; for its ad to be clicked. Each advertiser, possibly strategically, submits a bid b, to be shown in the output in the LLM and to maximize its own payoff, which will be defined shortly. We write z to denote user query (a prompt), y to denote the output generated from the LLM,, and (é:))) to denote the sub-sequence of y from i-th token to j-th token. We use boldface to denote a vector, e.g., b = (b), by...., b,) is the vector of bids.
When user enters query into the LLM, auction mechanism selects an ad a, to advertise, and generates an output yi that includes a mention of ad a; along with a hyperlink. By design, once the ad a; to advertise is decided, the generation of y; is independent of the auction and bids b.
Retrieval augmented generation. To build some intuition on how an L.LM auction would operate under the RAG framework, we first recap how the original formulation of RAG proceeds given set of documents [23]. Given a query x, suppose there exists a set of documents {œ1, (21, ø2, zn } that can be used to inform the output of the LLM. Under RAG, the output follows the generative model:
P(y|z)
Σ (P,,
Pr((esl)) 21).
(1)
where the summation is over the top-k documents with highest (z) retrieved via a technique like maximum inner-product search [19, 18). The vj and here refer to the parameters of the retrieval and generator components, either of which can be fine-tuned for overall RAG performance. In
practice, RAG is often implemented simply by including information from the selected document 2 into the prompt for generating y. The model in (1) refers to variant called RAG-sequence:
3

---

single document is selected probabilistically, and is then used to inform the entire output sequence. Lewis al. [23] also introduce variant called RAG-token, where separate document is selected and considered for each token generation. The flexibility of RAG to consider different contextual inputs at separate stages of output generation is one of the features that make it particularly suitable for integrating ads. We emphasize that document retrieval in (1) is randomized; RAG does not just deterministically retrieve the highest-scoring document. This probabilistic integration helps the model to leverage information from multiple sources and enhances the robustness and accuracy of the generated responses.
Auction design. To define an auction under the RAG framework, we must specify ad selection probabilities given submitted bids, along with prices for ads that are selected. We assume that RAG provides baseline ad selection probabilities Pa (a,l2) given a query z; these are the probabilities that should hold if all ads bid equally, so that there is no reason to prefer any ad based on the bids, We make the following important assumption that the retrieval component is calibrated to the expected clicks an ad a, would receive under query x, i.e., its click-through rate (ctr,).'
Assumption 2.1 (Calibrated Retriever). Let C2 be the binary event that ad is clicked. We assume that ctr; == [[C]|a]] = Ey. from the query x augmented with the ad aq.
y: E[Ca yil P(us (z) x (ay(a) =: qi where yi is the output generated
For ad retrieval purposes, the system could allocate according to E(C, yo] after observing the output y/ generated by conditioning each ad i. Our model accommodates such generalization at the cost of additional query complexity; we elaborate on this in Appendix A and B. However, from the perspective of advertiser, all strategizing happens before the output is generated, taking randomness in ad retrieval and output generation into account.
The quantity 9; can be seen as an indirect measure of the relevance of to query Throughout we assume that advertisers are charged per-click. However, in mechanism design it is more standard to work with expected prices per-impression." 2 The per-click price p; and per-impression price pt for ad i are related by i = ctr, Pt. by Assumption (2.1). Given this assumption, we emphasize that our auction would not directly require information the ctr,, but only requires the retrieved relevance q, to run the entire mechanism and generate the output, due to inherent normalization in the auction allocation rule. We will elaborate on this shortly.
An auction defines an allocation rule x(b), where x; (b) is the selection probability of ad under the given bids (which implicitly also depends on the baseline selection probabilities). Note that under RAG, the allocation rule is naturally randomized. The auction also defines payment rule pbb). where p:(b) is the expected per-impression payment of ad i. Given ad i's private value-per-click Vs its ex-ante utility (namely, its expected utility before selection and clicks are realized) is x q: (1,a,; (b))). We write (b). An auction is comminant-strateg incentive-compatibl (DSIC) if is optimal for ad a; to report its true value to the auction, holding the other bids fixed: u, (1, b) 2 (b,,, b-:) for all possible bids b; and competing bids b_i. An auction individually
defined as (b( ctr, U,2, (b) - f. (b) = ctr, (b; p:b))
per-click utility as u, (b(b) = v,a,(b)
rational if no advertiser is worse off by participating in the auction: (1, b_ 2 0 for all b
3 Single allocation segment auction
Following the RAG framework, we introduce a segment auction to retrieve and allocate ads during the LLM's process of output generation. A discourse segment is an abstraction of a series of tokens that will be the minimal unit of generation for the LLM auction. For example, the segment could be single token, sentence, paragraph, or even an entire document. The segment size can be enforced at a low-level by truncating tokens; otherwise, prompt engineering can be quite effective at limiting LLM output to specific number of sentences or paragraphs [12, 40].
'The retrieval component can he calibrated using number of standard methods, such Platt scaling or Bayesian binning [33, 29j. We also refer to [25] and [16] for descriptions of actual systems at Google and Microsoft using calibration via isotonic regression.
rate estimation
In advertising terms, "impression" refers the instance when an advertisement is viewed once by user. or displayed once on a webpage.
'With a slight abuse of notation, we use without any subscript to refer to the user query, whereas x or 2; denotes the allocation probabilities, following conventions in RAG and auction theory.

---

Single allocation segment auction
Collect q and b.
2. Draw (umbel(0, 1) for each i E [ni] independently.
Compute the score 8, q.b.e"!
4. Select the winner w argmaxie|j]
Find the second highest e [ 8i.
Find the smallest for such sw 2 st, which = qobee f
7. Charge z ad per click.
Figure 2: Single allocation segment auction
We first focus on the scenario in which a single ad is incorporated into each segment; we consider the generalization multiple ads per segment in Section 3.2. Let T be the number of segments. Formally, interested in generating the I-th segment ( given the series of previous segments y(I=t-1), In generating each segment ytt), we have opportunity incorporate one of k ads into the output. The RAG generative model as follows.
[x)
II Σ SE(T)
Pala, y( (b) (o( xr, (1:-1) a.).
The probability Py (a, (1:tt=1, bids. We will focus on the following adjusted probability based on linear aggregation [10]:
1;; b) is adjustment of (a,1z,
[2, y (1:-11) according the advertisers'
(c)
b. qi
[EjEm)
q (0)
Note that if all the bids are the same, this reduces to the baseline RAG output model.
We further impose following assumption asserting that each segment is rich enough to capture click-through rate by itself, and importantly, the advertiser's utility is additive over each segment.
Assumption 3.1 (Rich Segment). Let c! be the binary event that ad aj is clicked in the f-th
segment. We assume that Assumption 2.1 holds segment-wise, that ctr (t) E(C(") (ar, (1] x (a jr, (1) =: q; (4) for each / E [7]. We also assume that utility decomposes additively across segments: u; Σ Every ui
(1) (b).
Due to this assumption, one can observe that (3) is equivalent to b, ctr." /(E)e(m) by ctr." ( Thus, suffices to only deal with the calibrated relevance instead of the actual thick-through rates here.
Our segment auction is presented formally in Figure 2. The key idea is to first perturb each agent's s score (i.e., hid-per-impression q:h:) using independent Gumbel random variables, and then run standard recond-price auction. The bid perturbation ensures that bidders win following adjusted probabilities (3), egg., see Lemma H.1. This kind of perturbation is known as the Gumbel max-trick, and is also a familiar idea in discrete choice methods in econometrics [17, 41]. After the segment
auction determines the allocation and payment, the LLM outputs (*) according to the generative model (2).*
3.1 Theoretical analysis
We now provide a theoretical analysis of the segment auction. In the mechanism design literature, the auctioneer is typically interested (I) incentie--omppatiliiyy.. that truth telling is dominant strategy, (2) individual rationality, so that no participant is ever worse off by by participating in the
"We focus on the segment auction with replacement, where the same ad can be selected multiple times across different segments. We also implement the segment auction without replacement in Section 4.

---

auction. We mainly consider the following independent segment auction such that the relevance is independent from the previous segments, i.e., for every E [T]:
4 x (a.
(4)
(t) = 800) qs. where 8(4) is segment-wiss factor that can A slightly more general model would be qi
capture a user's decreasing propensity to click as the ad is shown in later segments in the output. Our results extend in a straightforward fashion to monotonically decreasing segment factors, so we omit them for simplicity.
Our first result is that for the class of independent segment auctions, segment auction maximizes a new notion of logarithmic social welfare assuming truthful bidding, and further satisfies desired properties. All the proofs can be found in Appendix H.
Theorem 3.2. Given query the segment auction is DSIC, IR, Pareto-efficient and has the maximal logarithmic social welfare (henceforth LSW) among independent segment auctions, where LSW is defined by"
LSW
II LSW TE(T]
II ( (0)0 (E
Recall that we write T; to denote a component of the allocation vector and x to denote the user query (see footnote 3). We remark that even though LSW is defined over qi, replacing it with ctr, induces the same optimization problem due to the calibrated relevance assumptions.
Intuitivelyy if the mechanism sets 2; (1) O for some E [n], then LSW(") becomes zero, implying that the mechanism should guarantee some positive probability of selection to every ad for every segment. Note that this is indeed a logarithmic analogue of the social welfare since log(LSSW(t) =
Eieloj oags log x. (t) Investigating further properties of the proposed notion of logarithmic social welfare remains as interesting open question.
Theorem 3.3. The segment auction is a randomization over truthful auctions. For the t-th segment, its per-click payment rule takes the form
W-i In
q:bb
+ w-i
G.b,
(5)
9i
W-i
W-$
q:bs
where w-; = rule (5), up to an additive constant.
Eszz 95hر- Any truthful auction for RAG allocation rule (3) has per-click payment
The segment auction is truthful, as it is randomization over truthful second-price auctions [26]. The fact that payment (5) is unique up to an additive constant follows from Myerson's lemma [28].
3.2 Multi-allocation segment auction
So far, we have focused on the setting in which the auction mechanism only advertises a single ad per segment. This approach, however, might be wasteful if the segment is long enough to adapt multiple ads, or if there are several ads that can be advertised naturally without compromising the segment's quality. In this section, we propose multi-allocation segment auction that allocates multiple ads in single segment. The main question here is how one can design the allocation and payment function obtain mechanism that exhibits several desired properties. To this end, formally consider the auction procedure for the t-th segment. Assuming that we are interested in selecting k ads for each segment, it proceeds depicted in Figure 3. Given that the mechanism selects the set of winners A E A₁ where A₁ = (A C [n]] IA| = k}. we delegate the role of generating the output yA* entirely to the LLM. For instance, we provide single document that concatenates the descriptions of the ads in A and query the LLM to generate the output conditioned on such document.
The following theorem characterizes the allocation function for the multi-allocation segment auction.
'This is analogous to position effects in search advertising auctions [11, 43J.
'This differs slightly from the well-knows Nash social welfare can be viewed a version of weighted Nash social welfare with a certain structure. Since weighted Nash social welfare satisfies several fairness notions such as weighted proportional faimess and competitive equilibrium from equal income (CEEI), LSW also guarantees versions of these fairness criteria. Detailed discussion provided in Appendix D.

---

Multi-allocation segment auction
Collect q and b.
2. Draw (0, 1) for each i E [ni] independently.
Compute the score 8, = q.bre"!
4. Sort the bidders that 8o(1) 80(2) 2 ... Se(n) for some permutation over [ri].
Select winners = [o(()...... [k))))))))k)
6. For each winner (1) for E [.), find the smallest hid such that (c(s) 2 (a()+-1); which is
(ot++=)) (90))))))/0 (6(6)
7. Charge 2; to each winner o(i) per click.
Figure 3: Multi-allocation segment auction.
Theorem 3.4. Let S [n]] S.S. For each S E Ak, the probability that the of ads S is selected as the winners is
Σjer Exesur qob.
P(S wins)
(-1)))
TES
Indeed, this strictly generalizes the single allocation segment auction since taking S = {i), we get
(P(E) wins) = (-1)1(91+1 Σje(} 9iby Ejesumi 9yby EjeN
q,b,
which is the standard selection probability for the single-ad setting.
In fact, the described multi-allocation segment auction be deemed special case of more general combinatorial segment auction (see Appendix E). Briefly speaking, in the combinatorial segment auction, we consider each set A E A₁, as single entity to retrieve RAG, and we assign a set-wise relevance metric to obtain the allocation probability of each set, which is further decomposed by the individual relevance 9A, of each ad A.? One advantage of the combinatorial segment auction is that the individual relevance QA,i given the set A can be more naturally connected with the advertiser utility, making it easier calibrate with the actual click tick-tthrough rate. However, this comes at the cost of larger computational complexity and query complexity with respect to the relevance and the LLM module, and requires to compute individual relevance as well as the set-wise relevance.
4 Experiments
validate our theoretical findings and provide insights on operating segment auctions in practice via numerical simulations. After determining the winning advertiser, we provide the ad to the LLM context and ask the model to generate an additional segment incorporating the ad, while continuing from the previous segments and advertising the selected ad. More details the LLM and prompts used are in Appendix F.
Setup. We consider segment auctions where each segment is a single sentence, and the entire document consists of three segments. There are five types of auctions: (1) segment auction with replacement, allowing repeated selection the same ads across segments, (2) segment auction without replacement, requiring different ads for each segment, (3) Naive I, which uses the same allocation and payment functions as the segment auction with replacement but concatenates selected ads' texts the end of the output, without using the LLM to integrate them into the output, (4) Naive II, similar to single allocation segment auctions but disregarding relevance (see Pseudocode in Appendix F.2, Figure 5), and (5) multi-ale allocation auction, which treats the three sentences as one longer segment, allocating three ads to the entire output at once.
multi-allocation
"We further characterize the VCG payment that makes the combinatorial segment auction DSIC, IR, and formally prove that further maximizes combinatorial version of the LSW. Details can be found in Appendix E.

---

Relevance measure. To compute the relevance measure, we use model from the sentence- werennceetrasfooooo ormers library. 8 This model maps input sentences or paragraphs into an embed- ding space where semantically similar texts have higher cosine similarity, while unrelated texts have lower cosine similarity.
Scenarios. We consider three experimental scenarios, each involving a set of advertisers and their corresponding bids. However, due space limitations we defer the analysis of two scenarios the Appendix. We run each scenario 500 times (trials) and calculate the average of the metrics, which will be defined shortly. Throughout the experiments, the query is fixed to: "Can you suggest some books similar to Too Kill Mockingbird??".
Auction outcomes. We calculate the following outcome metrics for evaluation:
Revenue -IEE(T) Eie(n) P.
Social welfare == ElERn Σie[nl U:G; (0)
Relevance = Exerry Eiein 9i x2.
(1) (1)
Minimum social welfare == min.e[m] Σ ūzs5 where üi denotes the allocative utility I;
Eieryy Pig. (#) (t) of agent i in trial j.
Quality of output. To capture the genuine quality of the generated output, inspired by Feizi al. [12]. we measure the embedding similarity between the original outputs in which no ads are advertised but rather purely generated from the LLM, and the modified output corresponding to each mechanism. This similarity computed using cosine similarity and normalized to lie in [0, 1].
4.1 Results
Auction outcomes. The scenario we consider is shown on the left of Table and includes four ads with wide range of final allocation probabilities. Note that we do not include the results for Naive I here since its auction metries are necessarily identical to the segment auction with replacement. As seen the right of Table 1, social welfare varies significantly between mechanisms. The segment auction with replacement has the highest social welfare, followed by the one without replacement, due to large differences in allocative efficiency (4:4) among advertisers. The segment auction without replacement still outperforms Naive II in terms of social welfare. However, the multi-allocation segment auction tends to have the lowest revenue as it charges lower payments to winners.
Advertiser
Bid
%
Mechanism
Soc. Wel.
Revenue
Relevance
Min. Soc. Wel.
Velora
0.36
0.22
Seg repl.
.600 (1.0001)
.371 (1 0000000
.688 (1.0082)
.185
BookHaven
0.87
0.54
Seg w/o repl.
.521 (#-0025)
.333 (t 0000)
.565 (=.0021)
.294
MussMart
0.31
0.13
Naive
.508 (4.0085)
.379 0005)
.552 (1.0076)
.329
EspressoEdge
0.26
0.11
Multi alloc
.52 (0.00
.238 0061)
.569 (2.0016)
.298
Table 1:
Experiment setup (left), and the corresponding auction outcomes (right). Note that all metrics are normalized by dividing them by their maximum possible value.
Notably, the relevance of the segment auction with replacement far exceeds that without replacement, unlike the uniform scenario. This is due to the ad 'Bookhaven' with very large relevance (0.87). Naive II and the segment auction without replacement have similar overall relevance, likely because the number of ads (4) is small compared to the total number of slots (one for each of 3 segments). For minimum social welfare, the ordering is opposite to social welfare due to differences in allocation probabilities. Segment auction with replacement selects 'Bookhaven' repeatedly, while without replacement, different ads are chosen for different slots. Naive II has slightly larger minimum social welfare than the segment auction without replacement due to more uniform selection procedure
'nttss//hugginggace.c cwrsentence-transfornneee transformers/mmulti- -ai-iiaa-----M-GGG- "We here use qi instead of the exact click- -hrrugh rate, Given the calibrated relevance assumption, all the mechanisms' social welfare would be equivalently scaled, so all the discussions carry over with the exact throuhh rate.
8

---

induced by similar bids in Table 1. Similar tendencies are observed in the other two scenarios, detailed in Appendix G.1.
Output quality. To further verify the effect of incorporating the set of ads in the context of the entire output, implement the multi-allocation segment auction. For fair comparison, in this auction, we define the segment to be the entire three sentences, and allocate k = 3 ads within it.
Mechanism
1st seg
2nd seg
3rd seg
& ==1
k: == 2
A: 3
Seg w/ repl.
.746 (1. 0040)
5566 (4.0040)
.588 (#. (039)
.746 (1. 0040)
.715 (d.0039)
.700 (4.0036)
Seg w/o repl.
.752 (+-0040)
.602 (+.0045)
.576 (+.0)33)
.752 (+-004))
.716 (+30035)
.702 (+.0034)
Naive I
.743 (+4))
.555 (#.0033)
.551 (=.0035)
.743 (# (013))
.740 (#.0044)
.671 (#.0032)
Naive II
.745 (+.0048)
.600 (#.0040)
.584 (#.0047)
.745 (+.0088)
.712 (#.0045)
.698 (+.0040)
Multi-alloc
.715 (+.0030)
Table 2: The 2-4th columns represent the similarity of the individual segment to the original output, and the 5-7th columns represent the similarity of the first l segments to the original output.
Interestingly, we indeed observe that the eventual output quality of the multi-allocation segment auction is the highest among every mechanism. This implies that if one gives flexibility of deciding which part to incorporate ads among the entire document, the LLM would do much better job articulating the advertised output without compromising the output quality. In Appendix G.I, we observe that this phenomenon amplified with more advertisers, demonstrating the superiority of the multi-allocation segment auction in terms of output quality.
Qualitative analysis of single vs. multi-allocation. We provide qualitative comparison of the output quality between the single and multi-allocation segment auctions with 11 advertisers in Figure 4. In the aulti-alloocttion segment auction, interestingly, we observe that ad is not always advertised in each sentence. Indeed, both 'MassMart' and "EspressoEdge" are advertised in the second sentence
coherent manner (teal text), while the first sentence is devoted to fully addressing the user's 's query. In addition, the third sentence (teal text) is constructed in a cohesive way from the previous sentence.
This verifies our conjecture that the multi-allocation segment auction constructs more coherent output, as the LLM can optimize over the entire document to incorporate the selected ads. The LLM can decide a coherent ordering of ads within the document, unlike the single allocation segment auction, which forces one ad into each segment. For example, in the first segment of the single allocation auction, advertising "BrainChips' is less cohesive (red text), while the second segment is more fluent (teal text), and the third segment becomes irrelevant (red text) again. Further qualitative analyses are provided in Appendix G.2.
Single allocation:
exploration moral ethical questions "The Help" by Kathryn Stockett equally compelling, providing rich narratives driven hy the kind of complex social issues that users BrainChips technology tackle every day quest innovative solutions understanding, (Segment 2) Reflect on these intricate tales of humanity and justiee with good book in hand, and perhaps your next reading adventure can kick off with delightfull shopping trip to MassMart, where you can explore their extensive range of high-toch electronies and more, enhancing reading experience with unbeatable value and convenience. (Segment 3) After securing your new reads, unwind with visit Espressoodgge, where the rich, meticulously crafted beverages otler the perfect accompanimett to dive into your literary journey. reinforcing truly immersive experience with each
(Segment 1) you appreciate
Mockinghird, you might
Multi-allocation:
If you enjoyed the profound themes of racial justice and moral growth "To Kill a Mockingbird, then I suggest checking out "The Help" by Kathryn Stockett and "Go Set Watchman" by Harper Loc, which explores similar veins social ethical dilemmas. While you're 'r picking up these intriguing reads MusMart, where quahiquality products unbeatable prices, perhaps consider enhancing your reading experience with a comforting cup of coffee from Espressobige,, renowned for its exquisite blends perfect for literary afternoons. And for those who prefer digital reading, make sure your devices are powered by BrainC processors, ensuring smooth, efficient reading experience that keeps you immersed the world of justice and personal integrity.
Figure 4: Outputs of single and multi-allocation segment auctions.

---

5 Conclusions
This paper considered the question of integrating ads into the output of LLMs, to offset serving costs and user subscription charges. Our approach is based on the popular RAG framework for incorporating factual information into LLM-ggnerated content [23]. We introduced the concept of a segment auction where an auction is run to integrate single or multiple ads into each output segment (e.g., sentence, paragraph). We showed that our segment auction designs implement the RAG allocation rule while charging incentive compatible prices, We also showed that the single-ad segment auction maximizes logarithmic social welfare, which balances efficiency and faimesss in the allocation. In our experimental evaluation, our key finding was that whereas repeated single-ad segment auctions have higher revenue, less-frequent multi-ad auctions lead to higher quality output, for the same number of ads. This uncovers an inherent trade-off between revenue and quality for operators of segment auctions.
We see several avenues for follow-up work. We note that while our work takes the perspective of charging ads appear in LLM output, one could also take the reverse perspective where information sources need to be compensated for providing unique, factual information under the RAG framework. In that case reverse auction would be run obtain high-quality information at minimum cost. We expect the main design ideas presented here to carry through, though important practical details (e.g.. per-impression vs. per-click pricing) would change. Another question the integration of reserve prices, which can serve to both increase revenue and maintain output quality standards. Finally, based on our findings on the relative quality of single- vs. multi-ad segment auction output, it would be worthwhile to investigate more sophisticated approaches to RAG segment auctions like joint fine-tuning of the retriever and generator components.
6 Acknowledgements
This work is partially supported by DARPA QuICC, NSF AF:Small #2218678, NSF AF:Small #21 14269, Army- Research Laboratory (ARL) #W911NF2410052, and MURI on Algorithms, Leam- ing and Game Theory.
References
[1] Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. Palm 2 technical report. arXiv preprint arXiv:2305. 10403, 2023.
[2] Kenneth Joseph Arrow, Michael D Intriligator, Werner Hildenbrand, and Hugo Sonnenschein. Handbook of mathematical economics, volume 1. North-Hollann Amsterdam, 1981.
[3] Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. Retrieval baasee language models and applications. In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume 6: Tutorial Abstracts), pages 41-46, 2023.
[4] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33: 1877-1919,,,, 2020.
[5] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 1 (9966):061-1100) 201
[6] loannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions Economics and Computation ( (TEAC), 7(3):1-32, 2019.
[7] Zhuyun Dai, Vincent Y Zhao, Ji Ma. Yi Luan, Jianmo Ni, Jing Lu, Anton Bakalov, Kelvin Guu, Keith B Hall, and Ming- Wei Chang. Promptagator: Few-shot dense retrieval from 8 examples. arXiv preprint arXiv:2209.11755. 2022.
[8] Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of-verificatioo reduces hallucination in large language models. arXiv preprint arXiv: 11495, 2023.
10

---

[9] Kumar Avinava Dubey, Zhe Feng, Rahul Kidambi, Aranyak Mehta, and Di Wang. Auctions with Ilm summaries. arXiv preprint arXiv:2404.08122 2024.
[10] Paul Duetting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, and Song Zuo. Mechanism design for large language models. arXiv preprint arXiv:2310. 10826, 2023.
[11] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(11:242 2007.
[12] Soheil Feizi, MahammadTaghi Hajiaghayi, Keivan Rezaci, and Suho Shin. Online advertise- ments with Ilms: Opportunities and challenges. arXiv preprint arXhv:2311.7661, 2023.
[13] Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. Incoder: A generative model for code infilling and synthesis. arXiv preprint arXiv:2244.0599) 2022.
[14] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval-auge -uumente- generation for large language models: A survey. arXiv preprint w:Xx::2312.10999) 2023.
[15] Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society, pages 587-601, 1973.
[16] Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising microsoft's s bing search engine. Omnipress, 2010.
[17] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 16Xiv: 1./////1111144 2016.
[18] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scake similarity search with gpus. IEEE Transactions Big Data, 7(3):535-547, 2019.
[19] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.0-400 200000000000 2020.
[20] Frank Kelly. Charging and rate control for elastic traffic. European transactions on Telecommu- nications, 8(1):33-37, 1997.
[21] Jerry S Kelly. Arrow impossibility theorems. Academic Press, 2014.
[22] Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. IEEE, 2010.
[23] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Retrieval-augmented generation for knowledge-inteniive nlp tasks. Advances in Neural Information Processing Systems, 33:9459-9474, 2020.
[24] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. arXiv preprint 304.052304.08485, 2023.
[25] H Brendan McMahan, Gary Holt, David Sculley, Michael Young. Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222-1230, 2013.
[26] Aranyak Mehta and Vijay V Vazirani. Randomized truthful auctions of digital goods are randomizations over truthful auctions. In Proceedings of the 5th ACM conference on Electronic commerce, pages 120-124, 2004.

---

[27] Shervin Minaee, Tomas Mikolov, Narjes Nikzad, Meysam Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: A survey. arXiv preprint arXiv:2402.00 26966 2024.
[28] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 73, 1981.
[29] Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelligence, volume 29, 2015.
[30] John F Nash et al. The bargaining problem. Econometrica, 18(2):155-162, 1950.
[31] Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingho Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. arXiv preprint arXiv:2203. 13474, 2022.
[32] OpenAL. ChatGPT Pricing. https://openal: wtt.coocccccccc.cc chatspt/priccnn. 2024.
[33] John Platt al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances large margin classifiers, 10(3):61-74, 1999.
[34] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78 86, 2010.
[35] Mark Allen Satterthwaite. Strategy-prowd proofness and arrow's conditions: Existence and correspon- dence theorems for voting procedures and social welfare functions. Journal of economic theory, 1072)1187-217, 1975.
[36] Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. Replug: Retrieval-augmented black-box language models. arXiv preprint arXiv:2301. 226522 2023.
[37] Ermis Soumalias, Michael J Curry, and Sven Seuken. Truthful aggregation of Iims with an application to online advertising. arXiv preprint arXi::2405.0590 2024.
[38] Haoran Sun, Yurong Chen, Siwei Wang, Wei Chen, and Xiaotie Deng. Mechanism design for Ilm fine-tuning with multiple reward models. arXiv preprint wrx.v:2405.162777 2024.
[39] Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint arXiv::201 220.00299 2022.
[40] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne I Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.1397) 2023.
[41] Kenneth E Train. Discrete choice methods with simulation. Cambridge university press, 2009.
[42] Hal R Varian. Equity, envy, and efficiency. 1973.
[43]
Hal R Varian. Position auctions. international Journal of industrial Organization, 25(6):
1 1163-1178, 2007.
[44] Ben Wang and Aran Komatsuzaki. Gpt-j-6b: A 6 billion parameter autoregressive language model, 2021.
[45] Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. Improving text embeddings with large language models. arXiv preprini arXiv:2401.00.33 2023.
[46] Sichao Yang and Bruce Hajek. Veg-kelly mechanisms for allocation of divisible goods: Adapt- ing veg mechanisms to one-dimensional signals. IEEE Journal on Selected Areas in Communi- cations, 25 2007.
[47] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv: 2022.
12

---

A Ex-post relevance
Recall that each allocation probability o depends the RAG probability (a,(asar), and assume that the average CTR is proportional this quantity. Note further that this is obtained from retriever component which typically uses the relevance between two documents to compute the similarity. Alternativlly, one may consider incorporating the output into the context to derive the ex-post relevance, (a, Uk. ((), where y; the generated output when a; is selected." We denote the previous notion of relevance which marginalizes over the output by ex-ante relevance. There can be several ways to compare such relevance, e.g., concatenating the query and the output Yi and computes its merged document's relevance to the ad document, This approach, however, comes the cost of the additional computation complexity because one needs precompute every possible y; for i E [ni] to obtain the ex- ex-post relevance. This will further be discussed shortly in the complexity paragraph.
Further, similar to Assumption 2.1, we may assume that our retrieval component to measure the ex-post relevance is calibrated to the ex-post CTR.
Assumption A.1. Let C2 be the binary event that ad i is clicked. We assume that o = E|C(") [z. Vis
y (1=-11)] 101 x (a; Vi, gi, (1)-
Then, assuming that the ex- ex-post relevance is calibrated to the ex- ex-post CTR, the segment auction with ex-post relevance ensures that allocation function always achieve better objective function.
Proposition A.2. Given a query x and for any objective function f AT the optimal allocation with ex-post relevance achieves better (or equivalent) optimum than the allocation with ex-ante relevance.
Proof. To see why this holds, let (()) be the optimal allocation vector for the segment auction with ex-ante relevance for i-th segment. Notice that with ex-post relevance, we can optimize the allocation vector (()) An given the precomputed output (yi)sejn), i.e., x(t)
(y),.... Vx.) Here, however, we can restrict x(1) (y1...., yn) = xx9) i.e. uniformly the same over the output, and let (f) = (*)), Then, the resulting allocation becomes exactly equivalent to the optimal allocation for the ex-ante relevance. Therefore, marginalizing over the output would yield the same value of the objective function, implying that segment auction with ex-post relevance can at least achieve such quantity.
B Complexity of mechanisms
One another important aspect of the segment auction is to display the finalized output as fast as possible not deteriorate user experience. We here formally characterize the computational complexity required to run each mechanism from the user experience perspective. To simplify the statements, restrict our focus to the single allocation setting, however, similar argument carries over to the multi-allocation setting. Overall, to start generating 1-th segment, the segment auction
requires to retrieve relevance measures g for every i [n], decides the winner of the auction and corresponding payment. Note, however, that the payment does not need to be calculated immediately, so will only consider the computational/query complexity that will be required until the L.M starts generating the output. For instance, one can store the data occurred during the segment auction and compute the payment in an asynchronous manner by looking up the historical data.
To quantify the overall latency of each mechanism, we define the notions of query complexity to each modules we have defined. First, the LLM query complexity denotes how many times the segment auction required to call the LLM oracle which gives an output of desired length given a query. Next, the relevance query complexity denotes the number of times the segment auction calls the relevance oracle that computes the relevance between two given text documents. The relevance oracle here
WWWe here focus on the single-allocation setting for the ease of exposition, but the same argument carries over to the aalti-allocation setting.
We remark that this impossible [9]. since output is endogenous to the mechanism in their setup so that the mechanism computes the prominence each ad in the output. On the other hand, since the generation of output is fully governed by LLM to optimize the output, our mechanism can retrieve the output as parameters well.
13

---

can be deemed as an abstraction of the retrieval component in the RAG framework. Typically. it is expected that the LLM query would be much more expensive than relevance query, which will be again much expensive than the bitwise operation dealt in the standard time complexity.
The complexity of an auction will be characterized by query complexities each oracle as well as time complexity required throughout the computation of the mechanism.
Theorem B.1. The single-allocation segment auction with ex-ante relevance has L.M query com- plexity of ((),, relevance query complexity of O(n), and time complexity of O(n) to generate each segment.
Proof. To exccute the mechanism, first needs to compute the relevance measure q; for each i E [n], which requires n calls of relevance oracle. After then, we need to sample the random (t) b,e which requires (n)) noise, and compute the largest and the second-largest perturbed bid qi time complexity. Then, the output can be generated by single query to LLM. This completes the proof.
On the other hand, the following theorem explicitly shows that dealing with ex- ex-post relevance requires more LLM query complexity.
Theorem B.2. The dingle-allocatin segment auction with ex-ante relevance has LLM query com- plexity of (n),, relevance query complexity of (n)), and time complexity of O(n) to generate each segment.
Proof. The only difference is that, to compute the relevance (9) for each E [nl], it requires the computation of y; in advance, which requires (nn) LLM query complexity. Note here that after the winner of the auction is selected, there is no need of further calling the LLM oracle since all the outputs are already generated.
C Beyond the independent segment auction
In Section 3, we restrict our attention the case in which the relevance measure does not depend on the previous segments generated, but only on the query. We here generalize this limitation by introducing general segment auction. In the general segment auction, we allow the relevance to be a function of the previous segments, which implies that for * t' E [T]. it might be the
case that qi (t) + q; (t'), Importantly, each q; is in fact a function of all the previous segments (1a--1) and decision variables (i1, (,,,...,4-,) therein. That is, the relevance should be indexed (f1.(h...... 1), Thus, allocation (i,, 22,..,,,,, (T) that maximizes the logarithmic NSW should solve the following optimization problem.
by q:
Σ
(t) v.l. (0.(0smmmttt)) log x T3
max
(x(1)
DEA)
(E(T) kE(M)
Note here that once (1(1) determined, the subsequent segment i, will be sampled according to the proper probability distribution, which then affects the quantity of (f).(6......)))) Since each of (1)-(6.....ft)))) can have arbitrary value, solving the optimization problem above requires (i) exhaustive search over the space [n]] to obtain the quantities q; (1).(51......))) for every / E [T] and every (fI...., E [m] and (ii) optimization over each probability simplex x() for t [T]] given the exponentially many parameters. Overall, this is computationally infeasible in practice, particularly given the limited latency in the online advertisement system.
Instead, our segment auction can be deemed as greedy algorithm that approximates the globally optimal allocation rule. Indeed, given the previous tokens, the segment auction chooses the next token maximize the logarithmic social welfare up to the subsequent round. This is straightforward to see since the logarithmic social welfare is decomposable over each token and our segment auction chooses token with respect to the probability that maximizes the single round logarithmic social welfare for the next round.
Proposition C.I. Given query x and previous segments y (1:--1), the segment auction chooses the next token that maximizes LSW up the next token.
14

---

D Further notion of fairness and its connection to LSW
We here explain several standard fairness concepts widely used in the literature, and how they are relevant to LSW. Given agents, let X C 22 be the space of feasible allocation, X E X be an allocation and w R2 be corresponding weights. Such weight may represent entitlement of an agent that is exogenous from the allocation rule. For example. in a network bandwidth allocation scenario, user with higher weight might represent eritical application that requires more guaranteed resources, and in economic planning. different sectors (e.g.. healthcare, education) might be assigned different weights based on their societal importance, influencing the distribution of resources. Suppose that each agent i E [r]] has valuation function v X + Rg0.
The standard notion of Nash social welfare is defined as the following [30].
Definition D.1 (Nash social welfare). The weighted Nash social welfare is defined as [kę]a] ((u+(>;))) m)) Exe(m) ws If w; = for i E [n], then is simply called the Nash social welfare.
Nash social welfare recently receive tons of attraction from the computer science as well as economics literature [6], since it well balances the trade-off between the efficiency and faimess.
The following notion of proportional fairness is broadly studied in the resource allocation literature, in particular from the network utility maximization perspective [20, 22, 46]
Definition D.2 (Weighted proportional fairness). The allocation x E X satisfies weighted propor- tional fairness if for any other allocation y E X, it satisfies
Σ KE|D
1/4 24 wi
O.
Z4
If w. = w for E [n]], then this is simply called the proportional fairness.
In essence, if we want to increase a certain coordinate i's allocated resource by 6, then it comes at the cost of decreasing some other agent j's resource by ō (or summing over others), and proportional fairness precisely implies that the overall change of proportional utility s/2; - 5/2, is always nonpositive.
Finally, these notions have close connection to the following competitive equilibrium from equal incomes [42, 2, 5].
Definition D.3 (CEEI). Consider agents and (divisible) goods. Each good j [m]] has supply of s.. Each agent has a budget of w; unit of currency. Let pj be the price of good j. Let u, (x,) be the utility functoin of agent i for the bundle x; (Ia1, T.2...., Zim) where Zij represents the quantities of each good j allocated to agent i, A competitive equilibrium a set of prices p and allocation x such that (i) each agent maximizes their utility, i.e., 2; argmax,, uz(y) subject Σjejm) PyUli S 1, and (ii) the market clears, i.e.. Eietol Tig = s, for j [m]]
These concepts are independently discovered by several different communities including economics as the solution of the bargaining problem [30] and the concept of competitive equilibrium [42], and also as the solution network scheduling problem [20]. It was a folklore knowledge for decades that all these notions induce the same allocation vector for divisible goods.
Theorem D.4. Given weights w, an allocation x E that maximizes the weighted NSW satisfies weighted proportional fairness, and coincides with the competitive equilibrium given the weighted budget.
Interestingly, our notion of logarithmic social welfare can be deemed as a version of the weighted NSW in which go;; is the weight w,, and the utility is only about the allocation Te since LSW = Πeε[. 2 The main difference is that the actual utility decomposed into two parts of allocation (xx;) and the per-allocation utility (gey),, and further the monetary transfer not considered at all. Therefore, one might interpret LSW as measure that captures the balance between the allocational efficiency and fairness given that each advertiser has an entitlement of qeu; Its further connections to proportional faimess and CEEI can be analogously argued per Theorem D.4,
15

---

E Combinatorial segment auction
We here present a combinatorial generalization of the multi-allocatiio segment auction presented in Section 3.2. Let A 2/x) be the power set over [n], and Ar {A E A |A| k}. In the RAG-sequence model [23] as written in (1), the term (,,(2) (v) 24) corresponds to conditioning the output y on each single document 24. 12 Recall that As is the collection of set of ads whose cardinality k. To advertise ads within single segment, we introduce the following equation similar to (2) using combinatorial variant of R RAG-sequence model.
Ply |c, (1t 11)-
Σ Po(zAlz, O1t (b) x, 2, y AEAL
(6)
where 2 a document that represents the ads included A.
To construct our intuition towards the auction, first assume that the bids are uniformly the same. Then, our each probability in the RAG equation should boil down to (2 la, (1) Here, similar to Assumption 2.1, we can deem this probability as an indirect measure of the relevance of the set of ads to the query x. However, we cannot exactly relate the average CTR of individual ad i with Pa (ZA|Z; y (1)t11)), since 2 only accounts for the set-wise property but not how much individual ad i is relevant to the query context.
Alternatively, we can decompose the probability (2,(2A |x, y (1) by summation over the promi- nence of each ad E A that contributes to the overall relevance of i.e.
Po Po(zalz,y (1:-11)) = Σ Pa(zile, ( (1:t-1), 22))) (1:t 11)
xm(m
where Σie(s) Pa pa(=ijo,g((t))))) = The parameter denotes the model that computes the promi- nence of each and overall relevance A, which is different from the previous retriever's parameter n) since it will be calculated in a different manner. Note here that we specify the relevance of the set A to be retrieved from a different model with é not 77, since if we simply append or summarize a set of ad documents and measure the relevance, there could be some biases due to positional effects. This implies one may need to implement an individual module to capture the overall relevance. For instance, one can use heuristic of Qл
Σie li + 3 ΣiæjeA rel(a;; aj) for a proper choice of weights 2 O and B 2 O. We also emphasize that our mechanism does not control the prominence but is given by the LLM in a exogenous manner, so one only needs to implement a proper relevance/prominence computation module that is well-calibrated with the CTR.
Then, can impose the following assumption analogous to Assumption 2.1.
Assumption E.1. In a f-th segment, let c((.) be the binary event that ad is clicked in t-th segment if it is advertised with the set of ads A. We assume that
(t) A
E E|C( A. (1:-11)]=
(t) U/A ddyd
po 2A)P, (EAlZ, (21--1)).
Correspondingly, we can define the linear aggregation function as follows.
EIEs LA.b
2/4² Po(zall, (12 (12-))bb)))))) b)= EBEAL EiEB BB.b,
If all the bids are the same, this reduces to the baseline RAG equation (6) such that
Po (rAaal,, (2:t-1)) EiE Polz,k (1:t-1), (1lt-1),=)),,((( (2ll,, (1:-11)), (( which is proportional to EieA QA,i-
Finally, given the number of winners k the combinatorial segment auction for f-th segment can rigorously defined as follows.
NNot that even though we compute the normalized probability by summing over i E [n]] this is not about conditioning the output on multiple ads, but rather conditioning the output on each single ad, and selecting the output by marginalizing every possible choice of the single ads.
16

---

Collect b and a0) AEAA)A
Draw εΛ Gumbel(0,)) for each E Ak-
Compute 8A Σiea 4 cEa.
Pick A" argmax AEA: SA.
For each E A
Find (' argmax AE Ar SA- Charge each i A the following VCG price per click:
Σ
(4) (neslye
/ /lad
(A((1) -
JEA
We further assume analogue of Assumption 3.1 stating that the advertiser's utility is additive over each segment, ie., per-impression utility u, Exerry u. E "i -p:
Unlike the single allocation setting, ad i's utility is positive whenever a set that includes is selected. Thus, we define the following variant of the weighted NSW.
Definition F.2. The combinatorial logarithmic social welfare (CLSW) is defined as follows.
(1)
CLSW = II II
A
<E(M) AEAANE
The following theorem states that the presented multi-allocation segment exhibits several nice properties, proof of which can be found Appendix H.
Theorem E.3. Given a query and number of slots k. the combinatorial segment auction is DSIC, IR, Pareto efficient and has the maximal CLSW among independent segment auctions.
We further show that it exhibits the following complexity measures.
Proposition E.4. Combinatorial segment auction hasLLM query complexity of O(),, relevance query complexity of Oke""), and time complexity of Onn²).
Proof. The proof directly follows from fact that first needs to compute the set-wise segment for every A and correspondingly the individual relevance for each set, which requires (2) x A query to the relevance measure. Then, computing the perturbed score and selecting the winner requires the computational complexity of (nn)). The LLM generation can be done by single call once the mechanism finishes.
One issue of the combinatorial segment auction is that it does not always induce nonnegative payment, unlike the standard VCG payment. In the VCG payment, the payment is always guaranteed to be nonnegative due to the monotonicity of the social welfare. To this more formally, let W be the optimal social welfare with optimal set A", and let Vi, be i's utility contributed for i E A*, Let W-; be the optimal social welfare when the agent i is excluded from the society. Then, VCG charges the externality to each i E A", i.e., = W ; because computing W-; includes the choice of A {i}. Thus, W is always larger or equivalent to EjALJEA Vy-
Σj Vj. Here, p; is guaranteed to be nonnegative
In the combinatorial segment auction, however, choice over the i-excluded optimal social welfare W-, does not subsume the choice of A'' ) {i} since we restrict our choice to be within the set with cardinality k. Hence, there might be chance that p; is often negative. Indeed, letting B A \ {i}. qB.j for j E B is significantly smaller 9A* for E A", then might happen that the social welfare of B with cardinality & 1 is much smaller than that of A" with i added. In this case, since adding to the increases the participant's 's utilities, reasonable to compensate the agent with negative payment.
One way to prevent such a phenomenon to simply round up the negative payment to zero once occurs. On the other hand, our perturbation based implementation of the segment auction enforces
17

---

that the random noise is multiplied as exponent do e This often incur a large gap between the first and the second highest score in the segment auction, inducing a higher chance of resulting negative payment. To prevent this, one may consider truncate the Gumbel distribution to be drawn from, or controlling the temperature parameter in the discrete choice model [41], both of which comes at the cost of having a slightly different allocation function.
F LLM, prompts, and further experimental details
We use publicly-availabie API access of GPT4 as our LLM in our experiments. this Section, we first provide the set of prompts used to generate output in our experiments. Then in F.I we discuss our communication protocol with GPT4 API, and F.2, we provide more details on experimental setup, including Naive II mechanism and ads used in experiments.
We use the following prompts to generate output:
Single-allocation segment auction. We start with init init_query query and continue the conversation with the model with rest_ pes_y..ry. Note that ad refers the advertiser context document describing its products or services.
prompt = "Can you suggest some books similar to \"To Kill Mockingbird "?"
= frrt
{prompt}> \n please respond to this question for only one
sentence while also advertise (advertiser) with this context >>
(ad}
Make sure to connect the answer and the advertisement very naturally, not something like appending the ads after just answering the question.
Focus answering the question, there shouldn't 't be too much advertisment in the output.
Make sure that response should be sentence.
rest_query = f!!!
You must continue your answer to my original query. Your previous response was (previous_output)
And you now should advertise (advertiser), but without hurting the coherency of the entire document. Here s some contexts about (advertiser)
(ad)
Make sure that there is one new sentence. Write the entire document, which merges your previous response and paragraph.
Multi-allocation auction. We mainly did out experiments with three ads, but this template could be further generalized for more/fewer number of ads.
prompt = "Can you suggest some books similar to \Too Kill Mockingbirdy "?"
query f 1 (prompt)<n An please respond to this question for only three sentence while
(1) advertise (advertisers [o]] with this context >>
{ads [O]]
We remark that our prompt engineering might not be optimal, so better/different prompt engineering might result in better outputs.
18

---

(2) advertise (advertisers(1]) with this context {ads [1]}
(3) advertise [2] with this context >> (ads [2]}
Make sure to connect the answer and the advertisement very naturally, not something like appending the ads after just answering the question. Focus on answering the question,
there shouldn't be too much advertisment in the output. Make sure to advertise all three brands and ensure that the response is three sentences.
F.1 Configuration of prompt the LLM
Here we provide our protocol of communication with GPT4 model. messages refers the history of chat between the model and us (client).
response client aeaiet.chatt... cowpletion.......ooooooooooco..c compeetiios.createe create(
model = "gpt-4-turbo",
logprobs = False, temperature 1,
max_ max_tokens 300, measages-messages,
F22 Further experimental details
The following is a detailed pseudocode of Naive II mechanism.
Naive II mechanism
1. Collect q and b.
2. Draw &, ~ Gumbel(0, 1) for each i [n]] independently.
3. Compute the score s; b
4. Select the winner 1" = argmax, $t-
5. Find the second highest argmax 84-
6. Find the smallest bid for 1 such that 8;- 82, which is -bveev /efe.
7. Charge z to i" per click.
Figure 5: Naive II mechanism
The following are one-sentence description of the ad listed in Table 5, followed by the ad document which is actually used the prompt to incorporate each ad in the output generation process. Fach ad is a mocked version of real-wor world company named by LLM (guess what?), and all the relevant texts are generated by LLM as well.
Velora: tech company that designs and sells premium, seamlessly integrated smart devices and services for sophisticated and efficient lifestyle.
19

---

Discover the future of technology with Velora, the brand that redefines innovation and el- egance. Velora designs and sells a premium range of smartphones, tablets, laptops, and smartwatches, all crafted to seamlessly integrate into your lifestyle. Our products are engi- neered with user- sver-friendly interfaces, stunning designs, and cutting-edge technology to keep you connected and productive. Velora's ecosystem offers unparalleled synchronization across devices, ensuring smooth and efficient experience whether you re at work, school, or on the go. With Velora Pay, you can enjoy secure and convenient payment services, while our robust cloud service keeps your data safe and accessible anytime, anywhere. Elevate your tech experience with Velora, where sophistication meets simplicity and advanced functionality.
2. BookHaven: An online bookstore offering selection of seamless shopping experience and reliable delivery.
books across all genres with
Introducing BookHaven, your ultimate online bookstore where the world of literature is just click away. At BookHaven, offer extensive collection of books spanning every genre and interest, from timeless classics and gripping thrillers to insightful non-fiction and enchanting children's 's stories. Our friendly platform ensures a seamless shopping experience, with personalized recommendations and unbeatable prices. Whether you't re a voracious reader or just looking for your next great read, BookHaven dedicated delivering literary treasures right to your doorstep with fast, reliable shipping and passle-free return policy. Discover the joy of reading with BookHaven, where every book finds perfect reader. Dive into world of endless possibilities and let your next adventure begin at BookHaven!
3. Mass.art: A membership-basee retail store offering premium bulk products at unbeatable prices with a focus on customer satisfaction and community support.
Experience the joy shopping at MassMart, where quality meets value in a dynamic retail environment tailored for your satisfaction. At MassMart, members enjoy exclusive access vast selection of premium, bilk-sized products, from fresh groceries to high-tech electronics, customer happiness, sustainability,
all at unbeatably low prices. With commitment and community support, MassMart isn't just a shopping destination it's part of your community. Dive into world of savings and discover why millions choose MassMar their trusted shopping partner. Join us today and see the difference MassMart can make your shopping experience, where every visit is more than just shopping it's an adventure!
4. EspressoEdge: A premium coffee shop offering high-quality, handcrafted beverages made from the finest Arabica beans, providing luxurious coffee experience for all.
Experience the warmth and delight of EspressoEdge, where every sip offers an invitation to a world of exquisite flavors and aromas. Renowned globally for its high-quality, handcrafted beverages, EspressoEdge is committed to sourcing the finest Arabica beans, expertly blending them into a variety of rich espressos, frothy cappuccinos, and creamy lattes. Each visit to an EspressoEdge store is more than just coffee run iin-it's an opportunity to savor moment of luxury amid the hustle of daily life. Whether you seek the comfort of a familiar classic or the thrill of new seasonal specialty, EspressoFdge welcomes all to gather, connect, and enjoy cup perfectly tailored to your taste. Step into your local EspressoEdge today and join us in celebrating the art of coffee.
5. SocialHub: A leading social media platform that connects over two billion users through personalized news feeds, interactive groups, and tools for sharing life's moments and promoting businesses.
20

---

Discover the power of connection with SocialHub, the world's leading social media platform. With over two billion active users, SocialHub is your gateway to staying in touch with friends and family, discovering new communities, and sharing your life's 's moments. Our innovative features, from personalized news feeds to interactive groups, make it easy to engage with what matters most to you. Whether you're re promoting your business, staying updated the latest news, or simply keeping up with loved ones, SocialHub the ultimate tool to enhance your digital experience. Join today and be part of a global network where connections come to life!
6. ColaBubbles: The world's favorite soft drink, known for its unique flavor blend and effer- vescent bubbles that have been delighting people for over a century.
Experience the refreshing taste of ColaBubbles, the world's favorite soft drink. With its unique blend of flavors and effervescent bubbles, ColaBubbles has been bringing joy to people of all ages for over a century. Whether you re enjoying moment of relaxation, celebrating with friends, or on the go, ColaBubbles is the perfect companion quench your thirst and uplift your spirits. Our commitment to quality and tradition ensures every sip is delightful as the first. Indulge the classic taste of ColaBubbles and make every moment special. Taste the feeling!
7. FizzyPop: An iconic soft drink celebrated for its crisp. refreshinn flavor and vibrant effer- vescence, perfect for those who live life boldly and seek excitement in every moment.
Unleash the bold taste of FizzyPop, the iconic soft drink that invigorates and refreshes like no other. Known for its crisp, refreshing flavor and vibrant effervescence, TizzyPop is the perfect choice for those who dare to live life to the fullest. Whether you rr at party, watching a game, or simply taking a break. FizzyPop brings burst of excitement any occasion. With a heritage of quality and commitment to innovation, every sip of FizzyPop delivers an unmatched experience. Embrace the bold, and make every moment extraordinary with the unmistakable taste of FizzyPop.
8. SkyTech: The world's leading aerospace company, designing and manufacturing advanced commercial airplanes, defense systems, and space technologies to ensure safe and efficient global connectivity and exploration.
Explore the skies with Sky'Tech, the world's leading aerospace company renowned for its innovation, quality, and reliability. SkyTech designs, manufactures, and services commercial airplanes, defense systems, and space technologies, making global connectivity and explo- ration possible. Whether you're re traveling for business or leisure, SkyTTechs is state-of -att--ff-the-att aircraft ensure safe, comfortable, and efficient journey. With legacy of pioneering advance- ments and a commitment to excellence, SkyTech continues to shape the future of aviation. Choose SkyTech and experience the pinnacle of aerospace engineering and performance. Fly with confidence, fly with Sky SkyTech.
9. AeroDynamics: The global leader in aerospace innovation, designing and manufacturing advanced commercial aircraft that provide unparalleled comfort, efficiency, and reliability for superior flying experience.
21

---

Experience the future of aviation with AeroDynamies, the global leader in acrospace innova- tion and excellence. AcroDynamics designs and manufactures the world's most advanced commercial aircraft, providing unparalleled comfort, efficiency, and reliability. From cutting- edge technology to sustainable solutions, AeroDynamics is dedicated to shaping the future of air travel. Whether you embarking long-haul journey short domestic flight, AeroDynamics ensures a superior flying experience with spacious cabins, innovative features, and top-notch safety standards. Trust AeroDynamies for seamless and enjoyable journey every time. Fly smarter, fly with AeroDynamics.
10. MusicStream: The ultimate destination for streaming millions of songs with personalized recommendations and offline listening capabilities, offering seamless music experience anytime, anywhere.
Immerse yourself in the world of music with MusicStream, the ultimate destination for streaming your favorite tunes anytime, anywhere. With a vast library of millions of songs, playlists curated just for you, and personalized recommendations, MusicStream puts the power of music discovery in your hands. Whether you're 're in the mood for chart-topping hits, underground gems, soothing melodies, MusicStream has something for everyone. Plus, with offline listening capabilities and seamless integration across devices, you can take your music with you wherever you go. Join the millions of music lovers worldwide and unlock endless possibilities with MtsicStream. Discover, stream, and experience the joy of music like never before.
11. BrainChips: The global leader in semiconductor technology, providing cutting-edge proces- sors that power wide range of devices with industry-leading performance, reliability, and security for professionals, gamers, and more.
Experience the cutting-edge innovation of BrainChips, the global leader in semiconductor technology. BrainChips' groundbreaking processors power the devices that fuel our modern world, from laptops and desktops to servers and cloud computing systems. With a legacy pushing the boundaries of technology, BrainChips continues to deliver industry-leading performance, reliability, and security. Whether you re professional tackling complex tasks or gamer seeking immersive experiences, BrainChips processors provide the power and efficiency you need. Trust BrainChips deliver the performance you demand and the reliability you can count on. Join the millions who rely on BrainChips technology and unlock possibilities for productivity, creativity, and entertainment.
G Further experimental results
We here provide further experimental results that could not discussed in the main paper. For the auction outcomes, Scenario denotes the setup presented in Section 4.
G.1 Further results on the auction outcomes with different scenarios
Advertiser
Bid
Mechanism
Soc. Wel.
Revenue
Relevance
Min. Soe. Wel.
Velora
0.36
0.22
Seg w/ repl.
.888 (1.0022)
.47 (L.0071)
.527 (L.0077)
.430
BookHaven
0.87
0.26
Seg w/o repl.
.896 0013)
.377 (t. c0.0000
.521 (240040)
.490
MassMart
0.28
Naive
.897 (2.0023)
.378
(t: tt.0
.418 (000)
.287
EspressoEdge
0.26
0.24
Multi alloc
(+-0013)
.255 0000)
.516 (=.0012)
.515
Table 3: Setup of Scenario 2 representing an almost uniform allocative vector (left), and the corre- sponding auction outcomes (right).
Scenario 2: Almost uniform allocation vector. In this scenario, the allocation probabilities are
almost the same across the four ads. The bids b, computed relevance q, and the allocation probability
22

---

x as well as the auction outcomes are presented in Table 3. Since all the advertisers induce almost the same allocative social welfare q,,; one can verify that the overall social welfare does not significantly differ across the mechanisms in this case.
Since Naive II only accounts for the bids regardless of the relevance, observe that the revenue is indeed the highest among three auctions. However, the overall relevance of the Naive II mechanism much lower than both the segment auctions, which implies that the user experiment might be much worse than the segment auctions. For the minimum social welfare, Naive II exhibits significantly smaller quantity which is due the nonuniform bids across the ads in Table
Mechanism
Soc. Wel.
Revenue
Relevance
Min. Soc. Wel.
Seg w/ repl.
0.898 (20.0022)
0.347 (d000077)
0.527
(00))7
0.439
Seg w/o repl.
0.896 (10.0013)
0.317 (et00006))
0,521 (0400)
0.490
Naive II
0.897 (#0.0023)
0.378 (#00 (00.0669
0.418 (=0. 0053)
0.287
Multi alloc
0.892 (1:0.0033)
0.255 (#000058)
0.516 (=0.0042)
0.515
Table 4: Auction outcomes for Scenario
Scenario 3: More number of ads. Here consider 11 different advertisers as follows.
Book Haven
Mass Mart
Espresso Edge
Social Hub
Cola Bubbles
Fizzy Pop
Sky Tech
Acro Dynamics
Music Stream
Brain Chips
Adv
Velora
Bids
4:
0.36
0.87
0.31
0.26
0.21 0.053
0.38 0.095
0.28 0.070
0.33 0.082
0.34 0.084
2;
0.088
0.215
0.076
0.064
0.088
0.082
Table 5: Bids and relevance of the advertisers for Scenario
Briefly speaking, an ad ('BookHaven') has relatively large allocation probability of 0.21 than any others, while all the others have similar allocation probability of around 0.08. We mainly observe similar tendency discussed so far in the first two Scenarios.
Mechanism
Soc. Wel.
Revenue
Relevance
Min. Soc. Wel.
Seg w/ repl.
0.507 (10.0068)
0.482 (#0.0070)
0.507 (=0.0068)
0.039
Seg w/o repl.
0.489 (10.0048)
0.481 (+0.0074)
0.489 (=0.0048)
0.034
Naive
0.423 (=000049)
0.495 (#0.0071)
0.423 (=0.0049)
0.052
Multi-alloc
0.491 (=0.0049)
0.453 (#0.0073)
0.491 (=0.0049)
0.042
Table 6: Auction outcomes for Scenario
For the quality of the output, we again observe a similar tendency, however, the gap between the multi and single allocation segment auction amplifies.
Mechanism
k
k = 3
Seg w/ repl.
0.733 (= (=.005)
0.701 (4.005)
0.686 (1..004)
Seg w/o repl.
0.745 (+.005)
0.711 (+.004)
0.697 ( 004) 0.738 (1. (04)
Multi-alloc
Table 7: Similarity of output to the original output in Scenario 3.
23

---

G.2 Further qualitative analysis
We here provide some qualitative analyses on the generated outputs from different mechanisms pre- sented in Section 4. Relevant information about each ad can be found in the subsequent Appendix F.2. The following are examples of the original response with three sentences without any ad allocated.
If you enjoyed "To Kill Mockingbird," consider reading "The Help" by Kathryn Stockett, which explores racial issues in 1960s Mississippi through the eyes three women. Another excellent choice is "A Tree Grows in Brooklyn" by Betty Smith, poignant coming- of-age story set in early 20th century Brooklyn. For a powerful narrative on racism and social justice, "The Secret Life of Bees" by Sue Monk Kidd is highly recommended, set in South Carolina during the 1960s civil rights movement.
Example 1.
Example 2. If you liked "To Kill a Mockingbird," you might enjoy "The Help" by Kathryn Stockett, which delves into racial tensions in 1960s Mississippi. "A Tree Grows in Brooklyn" story in early 20th-century Brooklyn. Another
by Betty Smith offers touching coming-of great choice is "The Secret Life of Bees" by Sue Monk Kidd, 1960s South Carolina, exploring themes of racism and redemption.
Example 3. For those who appreciated "To Kill Mockingbird," "Thh Help" by Kathryn Stockett is a compelling choice, examining racial issues in 1960s Mississippi. "A Tree Grows in Brooklyn" by Betty Smith is another excellent option, featuring heartfelt coming-of-age story in early 20th-century Brooklyn. Additionally, "The Secret Life of Bees" by Sue Monk Kidd, set in 1960s South Carolina, explores themes of racism and personal growth.
With or without replacement. In the setting of Scenario 2, the following is an output of the segment auction with replacement. Note that explicitly specify the segment number for readability, although was not directly specified in the LLM output.
(Segment 1) At BookHaven, where every book finds its perfect reader, you'll '1l discover amaz- ing works similar to "To Kill Mockingbird," such as Harper Lee's "Go Set a Watchman," Carson McCullers' "The Heart is Lonely Hunter," and William Faulkner's "Intruder in the Dust," all ready to be explored and delivered right to your doorstep. (Segment 2) Dive into BookHaven, your ultimate online bookstore, to enjoy a user-friendly shopping experience with personalized recommendations and unbeatable prices, ensuring that every literary adven- ture is just click away. (Segment 3) Plus, with commitment to fast, reliable shipping and a hassle-free free return policy, your next great read is guaranteed to arrive swiftly at your door.
In this random incidence of the segment auction with replacement, the same ad 'BookHaven' is repeatedly selected for all the segments. Notably, in the last segment LLM does not explicitly mention 'BookHaven', while keep talking about the benefits of 'BookHaven' actually (teal texts). From the user experience perspective, this would be better than keep mentioning an url to ad for each segment, since the user may think the LLM is trying to advertise more but not to answer the query. We find this be potential advantage of allowing repeated selection of the same ad in the segment auction.
On the other hand, one might notice that the second segment is not coherently continued from the first segment's 's context (red texts). One might require a better prompt engineering, or allowing repetition might not be good option for coherency, since it essentially requires several segments to repeatedly mention the same ad. This might be even more critical if the same ads are selected in a non-consecutive manner. One remedy might be to restrict the repeated selection to be allowable only it is going to be consecutively selected in the neighboring segments.
The following is an output of the segment auction without replacement.
24

---

(Segment 1) If you appreciated the profound narratives and moral questions explored in "To Kill a Mockingbird." " you might enjoy "The Help" by Kathryn Stockett or "A Time to Kill" by John Grisham, both of which blend compelling storytelling with social issues, much like Velora blends sophistication and functionality in their cutting-edge devices. (Segment 2) Just these books provide backdrop reflect societal issues story, visiting an EspressoEdge store can be your perfect escape to reflect and unwind with a meticulously crafted coffee, enhancing your experience of luxury and quality in every sip. (Segment 3) After indulging in coffee and social reflections, why not continue exploring similar profound narratives by visiting BookHaven, where vast selection of literature awaits to complement your tastes and spark further thought, all conveniently available with just click.
compelling
Interestingly, even though the LLM is forced to advertise different ad in each segment, we find that the resulting output is very coherent, in partieular from how it begins the new sentence from the previous sentence's s context (teal texts). Generally, however, when it allocates a less relevant ad like 'Velora', one may see that is not very fluently advertised (red texts).
Multi versus single allocation.
Figure is another pair of outputs for multi and single allocation segment auction.
Multi-allocation:
If you treasured "To Kill Mockingbird," you might enjoy exploring similar themes of justice and morality in books like "The Help" by Kathryn Stockett or "A Time to Kill" by John Grisham, both of which you can easily find BookHaven, where classic stories and modern narratives converge for readers like you. Between readings, you can dive into discussions with other book lovers share your favorite quotes using SocialHub, transforming your reading experience into lively conversations and digital connections. Plus, imagine reading these great books Velora's 's latest tablet, which offers not only elegant design but also the cutting-edge technology to enhance your reading with features like blue light reduction for your comfort during long reading hours.
Single allocation:
(Segmentl) If you appreciated the complex social themes and engaging narrative of "To Kill Mockingbird." you might enjoy "The Secret Life of Bees" by Sue Monk Kidd, which explores similar questions of justice and identity in setting that, much like Velora's seamlessly integrated technology, deeply connects and resonates with its environment. (Segment2) To easily find this book and many others that stir powerful discussions and thoughts, check out BookHaven the ultimate online bookstore for a seamless shopping experience and personalized recommendations that ensure you find your perfect read, just Velora ensures your tech experience is just right for your lifestyle. (Segment3) Furthermore, to discuss the impactful themes and characters found in both books, join global conversations on SocialHub, where you can connect with other literature enthusiasts and engage in meaningful discussions, bringing your reading experience into vibrant community where every voice matters.
Figure 6: Outputs of multi and single allocation segment auction.
Again, we observe that the multi-allocation segment auction is superior in its quality from our (subjective) judgement. All the selected ads are very smoothly expanded throughout the response (teal texts). In the single allocation segment auction, however, the first segment includes 'Velora' in an awkward manner (red texts). Interestingly, the second segment in the single allocation segment auction once more mentions 'Velora" (red texts), even though only 'BookHaven' is selected in that segment. We believe this because L.LM tries to more naturally generate the second segment given the first segment, which in turn worsens its quality paradoxically.
25

---

Longer segments. Finally, we conduct an analogous experiment with longer segments (paragraph) using the single ad segment auction withour replacement. The following is an output of the segment auction without replacement.
(Segment 1) If you appreciated the thematic depth and moral introspection of "To Kill Mockingbird." " you might enjoy exploring similar narratives like "The Help" by Kathryn Stockett or A Time to Kill" by John Grisham. Find these titles easily Bovenaven, your ultimate online bookstore. With an extensive collection and personalized recommendations, BookHaven ensures a seamless shopping experience. Dive into world of endless possibilities with BaokHaven, where every book finds its perfect reader.
(Segment 2) Additionally, consider delving into classics such as "Cry, the Beloved Country" by Alan Paton, which, like Harper Lee's 's masterpiece, offers profound insights into social justice and empathy. Pair your reading experience with a visit to EspressoEdge, where each sip of their high-quality. handcrafted beverages provides a moment of luxury. Savor rich espressos or creamy lattes while you immerse yourself in timeless literature Edpr (Segment 3) For contemporary twist, you might also enjoy "Small Great Things" by Jodi Picoult, a novel that tackles race and prejudice in modern society. Enhance your reading experience with Velora's 's range of tablets and e-readers, which offer crisp displays and user- friendly interfaces. Velora's ' smart devices ensure your favorite books are always accessible, whether you'te re at home or on the go. Elevate your tech experience with Velora.
Although not directly comparable with the previous result the entire document itself gets longer, we find that the LLM keeps answering the original user's ' query in the beginning of each paragraph, and then try advertising the corresponding product more in a smooth manner (teal texts), whereas one might argue that there are some redundant texts advertising too much about the product (red texts), which might backfire for the marketing purpose.
H Proofs
H.1 Proof of Theorem 3.2
Proof. We first prove that the allocation vector induced by the segment auction is equivalent to (2). To this end, we use the following well known result from discrete choice model.
Lemma H.1 (Chapter 3. [41]). For each i E [n]. let 8; 2 0 be the score, and let & be the perturbed score with i...d. random noise E; drawn from Gumbel(O, 1), i.c., 3, =s Eg. Then, the probability that 3, has the largest value among i E [n] is / 8z)-
Using the lemma above, it is straightforward to see that each ad i is selected with probability q.b./ (EjE(n) 9.b,).
Now we show that such allocation vector maximizes the logarithmic social welfare, assuming the truthful bids, i.e., b v. Due the independence, it suffices to show that the logarithmic social welfare for fixed segment is maximized by our allocation rule. We take an inverse approach of finding the allocation that maximizes the LSW. That is, we are interested in x that maximizes
NSW() = II
9.
x
<E(m)
such that Eie(n) Ti- and x; > 0 for any i E [n). Set up the Lagrange function L as follows.
T(x, A) = II hh
X(11 Σ z.).
iE[n]
By taking the partial derivative with respect to x, for E [n] and A, we obtain system of equations aL
= q:b,
x
| + x = 0, Vi [n]
dz,
kE(N)
aL.
- Σ
I4 = 0.
0x
26

---

To solve for x, we first obtain
q.b. II
2 2:b
/x;
sc/n]
for some constant C for any i [n]. This yields proportional relationship of
q:b:
2;
for some constant e for any i E [n]. Plugging into Lie(n) Zi = 1, we get the desired allocation.
Finally, given any random noise (st) we will show that the resulting realization of our segment auction is DSIC and IR. To prove IR, first consider the winner i", Its per-click utility is given by
gg di- qi- C
Uy- = 0/-
0,
for second highest bidder index j since argmaaXe[m| b.b Since = 0 for every other j. clear that IR holds. DSIC also naturally follows from the fact that the second price auction is DSIC, and the segment auction can be viewed explicitly prove this fact given the random noise, for the winner i", is obvious that there exists no incentive to deviate due to the second price payment. Consider + i", i.e., qi-bi. gzbye55 14 Originally j realizes per-elick utility of " = O. Suppose j increases its bid so that 8/ satisfies u,ble 2 9:- e Then, j per-click utility will be
randomization over the second price auction. To more
qi- ti-be-
(u3) S
<0< Uj.
Thus, j's utility only decreases, and this concludes that the segment auction is DSIC for any random noise. Note that the same argument holds for per-impression utility. Finally, the Pareto-efficiency directly follows from the fact that the allocation is maximal.
H.2 Proof of Theorem 3.3
Proof. To characterize the expected per-click payment formula, we use the lemma by [28].
p. b) = 1%²
bi
d qi2 Eje(n ggbs
dz.
dz
Write w-; w- -=E byby- Computing the integral above, obtain
9iz
p;(q,b)
= dz
dz
W- +
4iz
w w-s/9
dz
(w i g 2)²
W w-i2/u0 dz
(w-s/0m qi + 2)
W w-i/
+ In & + w-// 1.a
qi
+ w-s/9:
W
w_i
+ Iu(bs + w-i///) - In(w-s/9))
(8)
W- + qibi
In( 41bb + w-))
q:b4
(9)
qi
w_i
W- + qobs
0
(10)
NNte that we can ignore the tie- nre-breaking case since Gumbel distribution is continuous, thereby g.bee can be deemed sample from continuous distribution for each
[r.].
27

---

where the last inequality follows from the fact (n)))+++/++) 2 0. Individual rationality in expectation follows from the fact that each realized instance of segment auction is individual rational, however, to see this explicitly, observe that for each E [n]. per-elick utility satisfies
q,b;
W-1 In( gib; + (w-i)
q: w- + qbb.
u.(q. b) = b1 w-; + q:b;
w-
q:b;
bi + w0 w-bb;
2 b, W-; + 9:b;
W-; + qibs
= b, b, =
where in the first inequality In(11 + +1) 2 for -.
H.3 Proof of Theorem E.3
Proof. We first prove that our allocation maximizes the CLSW. A similar Lagrangian-based argument implies that our allocation function maximizes the following over x = (ε that belongs to (+) dimensional probability simplex.
JEAL argmax Σ
(00 LA log
(11)
=EA (x) AEAx
argmax Σ #EA (2) AEAu
Σ
log
(12)
NiEA
argmax
Σ
TA.t log xA
(4)
(13)
#EA (:) vE[n]
LAEARNEA
Equivalently, this can be written as
II <E|N] MEAAEEA
II
I )
(14)
which implies that our allocation maximizes CLSW. DSIC, IR, and Pareto efficiency follow from similar argument with Theorem 3.2, i.e., from the fact that payment function VCG payment of charging the externality, which is equivalent to the Myerson payment the single-dimensional
setting.
H.4 Proof of Theorem 3.3
Proof.
To characterize the expected per-click payment formula, we use the lemma by [28].
p.(q.b) b) = ph: -fm==
qiz Eje(n
dz.
dz
gzb;
We skip the elementary level algebraic manipulation.
28

---

Write w-; EjE(n/Eo Jz... Computing the integral above, we obtain
p.
dz
0
dz
W-i + 9i2
w w-1/9:
dz
(w-i// i/g: + +z²²
W-22//q dz
Jo
(w / 9: 2)²
w-
w-s/q:
+ In + w w=-1/1))) 1.=
qi
+ w-i/q
w-
w-i
+ In(b; + w-///:) (n(w=//a)
(15)
qi
W-i qibi
W-i
q:b; + Whis
q:
In
(16)
qi
w-i
w + q:b.)
2 0
(17)
where the last inequality follows from the fact (n(x)++++++))))> +1/2 0. Individual rationality in expectation follows from the fact that each realized instance of segment auction is individual rational, however, to this explicitly, observe that for each E [n). per-click utility satisfies
q:b;
w-i In( q:b;
+ + --i)-
q:
(. b) = b;
w- ; 9:b;
w-i
w-t + q:b.
q:b;
w wibbi
2 by w-; q:b;
b: +
w-i + 9:bs
= b, b, = 0
where in the first inequality use In(1 (1 + t) 2 -t fort -.
H.S Proof of Theorem 3.4
For ease of exposition, we slightly redefine some notations. Let N be the set of agents and n be the number of agents. We overwrite b, log(q:b:) and therefore perturbation can be written as b, + E; instead of q=bçe e ~ (0mbel(O, 1) to yield the final perturbed bid B; by + 6;. We take the top & ads according to perturbed bids, where 1 < & S Recall that the pdf and edf of a Gumbel 1) distribution
clog(a.))) eFi That is, each agent places bid b,, which is perturbed by
f(e) = e e F()) e
We want to evaluate the probability that the set of agents S N wins, where |S] k. First evaluate the cdf and pdf for the minimum perturbed bid among S.
Pmin B, 2 u) FES
II [ F(u 6:))
Σ (-1)
F(u -bg)
TCS
jET
= Σ
11) exp
expp
- - l -
TCS
JET
Pmmi B, u) = Σ
(-1) exp
- - -
FES
TES
JET
l6 skip the elementary level algebraic manipulation.
29

---

Taking the derivative:
P(min B; - u)
Σ TCS
E-1)
1
exp
Σed
IES
JET
JEZ
The cdf for the maximum perturbed bid among S is as follows.
P(max B, S u) = II
F(u (() b,)
iE9
.ES
Σeeh ci-
exp
iES
Continuing, the probability that S C N wins is as follows.
000
F(S wins)
P(max
Bi S u)
P(min B; u) du
iES
IES
exp
Σ biuu
Σ
(-1)
exp
exp
--Eeh
cli-u
Σ
e
du
iES
TCS
JET
JET
Σ
(-1)
exp
Σ bi-
Σ c
du
TCS
iEŠUT
JET
Σ(-))
Σ
exp
-
Σ b
e
du
-00
TCS
FET
iESUT
We now do the change of variable = -u dl = - du. As u - -x0, + 00, and as -> oo,
I + O. Continuing:
PPS wins)
(-1)121+1
Σ b
exp
-t Σ
(-dt)
TCS
JET
NESUT
Σ
1971+
Σ
bj
exp
b
dl
TCS
JET
iEŠUT
(-1 (-1 EiE eli)
100
Σ
(1)177++1
Σ
exp
ΣIESUT ele
TCS
JET
Σ
(11)17++
Σ ) JET
0
Eiesur
1
TCS
Ejer e Eiesur
Σ TCS
(-1)17++1
eb
To summarize, the probability that a set SCS N of size S k S wins is:
P(S wins) = (11) Σjer eby
Eiesur chi'
TCS
Plugging back b, log(()b)) yields the desired allocation probability.
30

---

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: Abstract and the introduction only includes proven theorems and validated experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 or
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 are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Model, main result, experiments, and appenix discussions on the limitations.
Guidelines:
The answer NA means that the paper has no 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 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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
Section 3 and appendix includes it.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details are written and code will be also attached.
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 be 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 is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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 clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification: Github repo will be available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Seeiiiccgiieee/CCooo
wwwpoimmsssoooooiioooooooooooooo onnolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurIPS code and data submission guidelines (https:
/ //iips.cooo wttpccccppppcpeeeececccccccccctc http:////giieeeeeeeeuuubiiiiiiia /Codeeeooiissseeeeee wwtpaubmmsssoonni sswonnoll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as 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: Appendix presents all the details. 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We reported the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
33

---

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 enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or 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
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments with standard computation resource, without GPU, 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, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics https: : //wuurrrrs....// cc hc/pppllitt/thhhccuuddeee...
didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is briefly discussed in the introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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 considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
34

---

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 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 correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe 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: It does not involve such risk.
Guidelines:
The answer NA means that the paper poses no 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: All the references are made.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi sepprsswithood thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
35

---

Answer:
[NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part 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 as details about compensation (if any)?
Answer: [NA]
Justification:
It does not involve crowdsourcing experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: It does not involve crowdsourcing experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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 expect authors to adhere 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.
36


Reviews:
[{"review_id": "fOZITIopcy", "reviewer": "Reviewer_zmfd", "summary": "The work studies ad auctions integrated in LLM output powered by retrieval-augmented generation. The authors propose an ad auction (so-called segment auction) where an ad is put in retriever with some probability. An efficiency-fairness balance is maximized (through logarithmic social welfare). An extension to multi-ad setup is proposed. Evaluation of the framework has been done through synthetic experiments.", "questions": "-\tIt is not very clear why does LSW has been selected for optimization? Is it chosen after segment auction invention? Or you purposely searched for auction that optimize LSW?\n\n-\tDoes segment auction maximize SW? What is the auction design for SW optimality?", "limitations": "the authors adequately addressed the limitations", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "-\tHighly important novel topic for research (due to restructuring of web search market and LLM/RAG-based search system deployment around the world)\n\n-\tBoth theoretical guarantees and empirical evaluation", "weaknesses": "-\tUnclear selection of optimization function (see questions)\n\n-\tIt would be nice to have real-life evaluation as the topic is highly relevant for production search engines", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first appreciate the reviewer for insightful comments.\n\n> About unclear selection of optimization function\n\nThe reviewer is correct that it is chosen after the allocation function of segment auction is determined. We remark that our selection of optimization functions stems from the probabilistic retrieval nature of the RAG framework. RAG framework suggests retrieving each document proportional to the probability $p_\\eta(a_i | x)$. Thus, we restrict our mechanism to have the same allocation function so that the overall architecture exactly resembles the RAG framework but with ad documents. In hindsight, we observe that such an allocation function maximizes LSW, which has never been studied in the literature to the best of our knowledge. We firmly believe that LSW may play a crucial role as an objective function in ad auctions for LLMs in further works, and also we found that it achieves a balance between fairness and efficiency in a similar vein with the Nash social welfare.\n\n> Does segment auction maximize SW? What is the auction design for SW optimality?\n\nIn fact, an (single-allocation) auction that maximizes SW will be any auction that selects an ad with the highest value of $q_i \\cdot b_i$, e.g., second-price auction or first-price auction. As per the revenue-equivalence theorem by Myerson’82, all these auctions would induce the same revenue, whereas our segment auction intentionally deviate from such SW-maximizing allocation function to be consistent with the probabilistic retrieval of RAG, i.e., in order to improve the overall quality of LLM outputs themselves.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WKZnFMXbft", "reviewer": "Reviewer_VuMT", "summary": "In this paper, the authors integrate the auction mechanism into RAG LLMs for computational advertising. They propose a novel segment auction method where an auction is run to integrate single or multiple ads into each segment output of LLMs. Experiments on several auction scenarios are conducted to verify the effectiveness and feasibility of the proposed framework.", "questions": "Refer to detailed comments.", "limitations": "Refer to detailed comments.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe research problem of this paper is interesting. This paper combines the popular RAG LLM framework with traditional auction mechanisms, exploring the prospects of integrating computational advertising with LLMs.\n2.\tThis paper is well-structured with a clear and coherent logic.", "weaknesses": "1.\tThe technical novelty of the proposed method seems limited.\n2.\tThe experimental evaluation should include more baseline methods.\n3.\tThe evaluation method is not comprehensive enough.\n\nDetailed Comments:\n1.\tThe proposed method lacks innovation. While combining computational advertising with LLMs is an interesting direction, this paper merely provides a simplistic integration of auction mechanisms and RAG, lacking innovation in its overall approach. \n2.\tIn the evaluation of the proposed method, this paper only compares two naive baselines (without relevance score / without an LLM), lacking comparison with other existing auction methods. The comparison should be made within the same RAG framework, between the proposed auction mechanism and other existing auction mechanisms, to demonstrate that the proposed mechanism is most compatible with RAG LLM.\n3.\tThe effectiveness of the whole proposed framework is not well verified. First, simply comparing the cosine similarity of embeddings between the output text and the original text without ads may not sufficiently indicate the text quality. On one hand, comprehensive metrics like perplexity could be incorporated. On the other hand, the quality of the advertising content in the text has not been considered. Second, there is a lack of overall results that can demonstrate how well this method achieves the tradeoff between advertising effectiveness, output quality, allocating efficiency, and fairness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for detailed review. We hope that our rebuttal can address your concerns.\nNote that our framework consists of several components, each of which could be further researched to improve real-world deployment. Our focus was on proposing the framework, analyzing it theoretically, and evaluating it with simple yet efficient methods.\n\n> The technical novelty of the proposed method seems limited.\n\nWe kindly ask the reviewer to see our general response in “Novelty of the paper”\n\n> The experimental evaluation should include more baseline methods.\n\nOur framework on ad auctions LLM is indeed the first study to explore ad auction framework within the LLM’s textual output, so we compare our mechanisms with simple mechanisms that one might naively think of. There are simultaneous works by Aranyak and Soumalias, however, we remark that these works do not explicitly compare their mechanisms with one another due to the lack of existing/standard benchmarks, but also only considers a naive version of auctions, e.g., greedy append of ad documents similar to our naive mechanism. We kindly ask the reviewer to let us know if the reviewer has any specific auction to compare in mind.\n\n> First, simply comparing the cosine similarity of embeddings between the output text and the original text without ads may not sufficiently indicate the text quality.\n\nMeasuring text quality while including advertisements is a challenging research question that requires further exploration by the NLP community. Traditional metrics like ROUGE may be unsuitable due to ads in the output and the absence of ground truth. While our framework's validation employed semantic similarity as a proxy for quality, qualitative analysis suggests our framework generally produces high-quality outputs. We acknowledge that this aspect could open a promising research area.\n\n> On one hand, comprehensive metrics like perplexity could be incorporated.\n\nThank you for your valuable suggestion. We found that comparing perplexity is indeed useful and conducted experiments using the LLaMA3 8B model. We measured perplexity (given the query) for outputs in scenario 1 (100 samples per mechanism). Perplexity was low for original outputs but increased significantly when ads were included. Auction mechanisms that allow replacements showed slightly lower perplexity due to ad replication, which reduces model surprise. Other baselines performed competitively in terms of perplexity. \n\n| mechanism                        | perplexity |\n|----------------------------------|------------|\n| original                         | 4.93  |\n| single-alloc w replacement    | 12.66 |\n| multi-alloc greedy               | 14.69 |\n| single-alloc w/o replacement | 14.44 |\n\nNote that while perplexity is a useful measure, it doesn't fully capture how well the model responds to the query or the overall output quality. This limitation highlights an interesting problem that requires further research to develop better metrics for evaluating response relevance and quality.\n\n\n> On the other hand, the quality of the advertising content in the text has not been considered. \n\nThanks to the reviewer for pointing this out, It indeed raises an interesting and fundamental research question for the general RAG framework: how effectively does the model utilize retrieved documents? There has been extensive study to evaluate RAG output given its retrieved documents. We believe that this problem requires further analysis in ad domain specifically.\n\nIn our framework, we assumed for simplicity that when an ad is selected, the LLM can effectively integrate it into the output. Qualitative results support this assumption, demonstrating that the model properly blends ads into the generated output.\n\n\n\n> Second, there is a lack of overall results that can demonstrate how well this method achieves the tradeoff between advertising effectiveness, output quality, allocating efficiency, and fairness.\n\nWe note that qualitative results show that our proposed approach is feasible and recent LLMs like GPT4 are useful for this framework. We used simple but efficient proxies for measuring ads relevance and output quality that compares different baselines and show that output quality of our mechanism is pretty reasonable. A bit more formally, advertising effectiveness and allocating efficiency can be captured via social welfare, output quality can be captured via relevance, and fairness can be captured via minimum social welfare as stated in L#260~265.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U6uoP426zj", "reviewer": "Reviewer_xTCf", "summary": "This paper studies an interesting and timely application of ad auctions for LLMs via retrieval augmented generation. They propose a segment auction that takes the bid and relevance as the input and outputs the price by a randomized second price auction. This auction maximizes the logarithmic social welfare that is proposed in this paper.", "questions": "In the paper, does the auction repeat for $T$ times, where one for each segment?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The combination of RAG and Ad Auction is pretty interesting and novel. \n- The presentation of the figures is clear and informative. \n- This paper has empirical experiments.", "weaknesses": "- The underlying assumption of this paper, i.e., [line 188-189] the relevance is independent of the previous segment is too strong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s valuable comments.\n\n> Independent assumption\n\nWe in fact extend our independent segment auction to a more general segment auction with history dependent relevance measure in Appendix C. We will make sure to add a pointer to this part in the main body of the paper. In the dependent segment auction, our notion of relevance depends on the previous tokens. In this case, since the relevance measure that determines the value of the objective function LSW might arbitrarily depend on the previous tokens, from the computational perspective, it requires the extension of every possible token sequence to exactly optimize the objective function without no assumption. Interestingly, we show that  our segment auction can be viewed as a local greedy algorithm that approximates the globally optimal allocation rule. More precisely, our segment auction chooses next tokens to maximize LSW given that previous tokens are fixed.\n\n\n> Question on the repetition\n\nThe reviewer is correct - our segment auction repeatedly runs to determine the output for each segment, where there are flexibilities in determining what to choose as a segment. Also our multi-ad segment auction further allows flexibility in determining how many ads to allocate within a segment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wXmJDU00CZ", "reviewer": "Reviewer_2L4f", "summary": "The paper considers the integration of ads into large language model (LLM) generation, as well as the design of a mechanism for ad allocation and pricing that comes with this integration. The paper introduces the notion of a \"segment auction\", where the output discourse is break down into various segments. Following the retrieval augmented generation (RAG) framework, the auction selects winner for each segment considering the bids and relevance, and provide the winning ad to the LLM as part of the prompt to generate segment with the ad incorporated. The paper provides theoretical analysis on the desirable properties of the segment auction, as well as empirical analysis in a synthetic setting.", "questions": "- How will the relevance measure $q_i$ be obtained if the mechanism is put into practice, and will there be ways of ensuring accuracy and calibration?\n- The qualitative empirical results right now (e.g. Figure 4) shows that the generated output stops providing useful information to the user once the ad starts appearing in the generated text in the first sentence, and all subsequent generations are just rhetorical transitions to another ad. Is this effect prevalent? Are there additional qualitative or quantitative results showing the effects of ad on subsequent segments and potential solutions to preserve an informative output?\n- Current pricing uses the VCG mechanism for incentive compatibility. In ad auctions GSP and first price auctions are frequently used. Can these alternative pricing schemes can be easily implemented under the current scheme?", "limitations": "The authors mentions the inherent trade-off between revenue and quality that's evident from the empirical observations. Different from traditional ad auctions, under LLM when the generation of later texts depends on prior generations, integrating additional ad leave open potential room for attack and injecting biased information through the type of the ad itself. The authors can provide a more detailed exposition of the potential social impact of such mechanism.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- The paper does a good job connecting the ideas to theoretical concepts, and provides solid theoretical analysis\n- The paper is well-motivated, tackling a novel problem that has great practical implications", "weaknesses": "- The paper uses strong assumptions on the retrieval component being calibrated to the click through rate, which forms the basis of most theoretical results provided. In the experiment section, the relevance measure are instead estimated by a model from the sentence-transformers library, which leaves a gap between theoretical guarantees and empirical approaches. \n- Under the general segment auction exposited in Appendix C, where each relevance measure is additionally dependent on all previous segments and allocations, the assumption of calibrated relevance seem even harder to achieve. Without this assumption and its associated theoretical properties, the paper presents only incremental technical contribution since running a second price auction and incorporating the winner of the auction into the LLM prompt lacks technical novelty.\n- The experiments section in the paper is not compelling enough. \n    - The five types of auctions considered in the Experiment section, which varies in whether replacement or relevance measure is used, are not well-motivated and appear disconnected from the earlier theoretical section, which focus on only the segment auction with replacement. The authors do not provide a compelling reasoning for considering this five variants, and the result analysis does not provide a strong case or intuition for which should be chosen (see line 273-287) - the writing and analysis for these parts could be improved.\n   - Both the numbers in output quality and the qualitative example provided in Figure 4 suggests that the addition of ads in the generation quite notably impairs the quality of the generated content. Particularly worrisome is the fact that in both the single allocation and multi allocation example (as well as in the examples in Appendix G.2), as soon as the paragraph starts pivoting to the ads *in the first sentence*, it never goes back in providing *any* additional useful information to answering the original question *\"Can you suggests books similar to `to kill a mocking bird'\"*. This seems to empirically suggests that the presence of ads in the earlier segment may impair the quality of content generated in the following segments.\n  - The experiments assume that each segment is one sentence in the experiments and add an ad to each segment. This is arguably too extreme for it to be deployed and a more realistic setting might be to integrate only a few ads to an entire page of results, which will suggests that the segment be longer than a single sentence. Additional experimental results should demonstrate that the proposed mechanism work as well under a longer segment.\n- When the number and categories of the advertisers are not diverse enough, augmenting an irrelevant ad appears to come with a significant cost to the quality of the output. The bid system also introduces the potential problem of misleading and corrupting the accuracy of the response, which is a new problem not faced by traditional ad auctions. This should be either empirically evaluated or discussed in more detail (see more in Limitations part).\n- Typo in line 140 - both the per-click and per-impression price are denoted using the same symbol.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for thoughtful and detailed comments.\n\n> The paper uses strong assumptions on the retrieval component\n\nWe agree that implementing a performant, calibrated retrieval component is a challenging engineering task in practice. However, it is well studied in the literature. We refer to McMahan et al. [1] and Graepel et al. [2] for descriptions of actual click-through rate estimation systems at Google and Microsoft. Both papers have sections on calibration using isotonic regression. We will cite these works and add some more discussion of calibration to the paper based on the reviewer’s comments.\n\nFor our experimental evaluation, we view retrieval and calibration as modular components, where various implementations could be used in practice. Our evaluation uses embedding similarity as a measure of similarity because RAG commonly uses vector embeddings for retrieval. Vector embeddings capture semantic information and enable efficient similarity search, but as mentioned above, other options are possible. As we did not conduct the real-world experiment with an implemented system, our experiments are bound to use a proxy measure. We also kindly refer to simultaneous work by Dubey et al. [3] that pose the same assumption on the calibrated relevance (in their words, prominence).\n\n1. McMahan et al.: Ad Click Prediction: a View from the Trenches, KDD’13\n2. Graepel et al.: Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search\nAdvertising in Microsoft’s Bing Search Engine, ICML‘10\n3. Dubey et al.: Auctions with LLM Summaries, Dubey, Feng, Kidambi, Mehta, Wang, KDD’24\n\n> Under the general segment auction exposited in Appendix C\n\nModern click-through rate estimation and retrieval systems take many contextual features to make their predictions. We refer again to papers [1, 2] cited above. In our application, prior generated output would be included as contextual features. We agree this is important and nontrivial to handle in practice, but again view this aspect as orthogonal/modular to the question of auction design tackled in our paper.\n\n\n> The five types of auctions considered in the Experiment section\n\nThank you for raising this point. In our camera-ready draft, we will elaborate on our choice of baselines and how our results highlight trade-offs between mechanisms in terms of output quality, revenue, and social welfare. Here’s a brief intuition. We refer to L#242-250 regarding different baselines and L#271-287 for interpreting the results.\n\nIn summary: (1) Naive II generates the highest revenue but results in the lowest relevance and social welfare, potentially incorporating unrelated ads and diminishing user experience; (2) Segment auctions with replacement achieve the best social welfare and relevance but lead to lower minimum social welfare; (3) Multi-allocation produces competitive results with segment auctions without replacement but sacrifices revenue.\n\nTables 2 and 7 evaluate LLM output under different mechanisms. We measure relevance to the original output (without ads). Multi-allocation mechanisms generally produce better outputs, as longer segments with more ads lead to more coherent results. Single-allocation auctions with shorter segments result in lower quality. Naive I and II lead to the lowest quality due to the inclusion of irrelevant ads. Segment auctions without replacement show marginal improvement over those allowing replacement.\n\nThese results highlight the trade-offs between different criteria, guiding the auctioneer to select the appropriate mechanism or a combination based on their requirements.\n\n\n> Figure 4 suggests that the addition of ads impairs..\n\nWe kindly refer the reviewer to global rebuttal. As seen in the attached pdf, in 3rd paragraph in the first sample and in particular 2nd paragraph in the second sample, the output still answers the query. These can further be improved with more prompt engineering.\n\n> Augmenting an irrelevant ad appears to come with a significant cost to the quality of the output\n\nLike standard search auctions, target ads can be prefiltered to exclude irrelevant ones. Most ad platforms use prefiltering to reduce computational load and maintain user satisfaction. Therefore, we assume all ads are relevant in L#31.\n\n> Privacy / reliability issue\n\nWe agree that integrating ads without privacy or robustness issues is crucial. However, our main focus is to introduce the RAG integration into the LLM ad system, validate its feasibility, and derive theoretical and empirical evidence. Our paper doesn’t address every practical issue. Similar perspectives are taken by Duetting et al., Dubey et al., and Soumalias et al. For broader technical concerns like privacy and reliability in LLM ad systems, refer to Feizi et al.'s survey paper.\n\n1. Dubey et al.: Auctions with LLM Summaries, KDD’24\n2. Duetting et al.: Mechanism Design for Large Language Model, WWW’24\n3. Soumalias et al.: Truthful Aggregation of LLMs with an Application to Online Advertising\n4. Feizi et al: Online Advertisements with LLMs: Opportunities and Challenges\n\n\n> How will the relevance measure be obtained if the mechanism is put into practice?\n\nWe refer to the cited papers on CTR prediction for calibration. While we use vector similarity as a proof of concept, more research is needed on designing effective metrics to measure relevance between queries and ads. \n\n> The qualitative results show that the generated output stops providing useful information.\n\nPlease see our response above.\n\n> Can these alternative pricing schemes can be easily implemented?\n\nAs can be seen from our randomized segment auction, any pricing scheme can be implemented from our idea - randomly perturb $q_i \\cdot b_i$, and apply any mechanism as desired. For instance, perturbing the bids and then run GSP (Figure 3) does not induce incentive-compatible mechanism as VCG does, however, this would be a reasonable analogue of the GSP auction widely adopted in the sponsored search auction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their constructive feedback. In this section, we address the concerns regarding design choices and engineering components in our proposed framework, along with a recap over our main contributions, and further results for multi-ad segment auction.

------

### Segments and Prompt Engineering

+ choice of segments: the segment size is intentionally set and is not constrained by our mechanism or theoretical results. It's determined based on our understanding of the large language model's (LLM) ability to incorporate ads within each segment's output, in order to focus on delivering our main takeaway. In the paper, we used smaller segments to produce shorter, more efficient outputs and provide clearer qualitative results. The success of the LLM with shorter segments suggests that our approach will also work for longer segments. We have included some qualitative examples for **longer segments (e.g., paragraphs) in the PDF file**.

+ output quality: The quality of the outputs can be improved by refining the prompts given to the language model, ensuring better integration of ads within the output while effectively responding to users’ queries. Effective prompt engineering can lead to more coherent outputs that meet the needs of both advertisers and users.

While we appreciate the reviewers' insights on these choices, we emphasize that the main contribution of our paper is to propose and theoretically analyze this framework, alongside empirical evaluation. There is always room for improvement in each component by selecting better options.

------

### Novelty of the paper

We believe that the main technical novelty lies in applying the RAG framework into the ad auction for LLM and revealing its several properties. 

+ First, our main mechanism considers a completely different approach than the standard mechanism design literature since we consider the allocation function as given from the RAG’s probabilistic retrieval nature. Then, given the allocation function as fixed, we aim to discover which objective such an allocation function tries to achieve, which turns out to be the logarithmic social welfare we defined. We firmly believe this approach could be a stepping stone to explore the intersection of RAG and mechanism design.

+ In addition, our perturbation technique inspired by discrete choice methods is indeed a novel component to implement any such randomized allocation rule in a simplistic manner. For instance, if one wants to naively implement a linearly proportional allocation rule, the straightforward approach would be to simply randomize the allocation function and sample from the corresponding function. In this approach, however, the payment function is not easy to obtain. One may apply Myerson’s lemma to obtain the expected payment given the randomized allocation function, however, this only guarantees incentive-compatibility in an ex-ante manner. In stark contrast, our perturbation technique ensures that the segment auction is ex-post incentive-compatible if the mechanism given the perturbed bids is incentive-compatible. Even more interestingly, in our framework, one can apply arbitrary pricing schemes given by any auction literature, e.g., generalized second price auction (GSP), even though it is not incentive-compatible. The approach is again to apply random perturbations to the bids, and then use the GSP pricing rule with the resulting fixed bids. Note that this is not possible without perturbation technique, e.g., it is not straightforward to answer what is the analogue of GSP when the allocation function needs to be randomized.
We remark that there has been no work to consider the idea of RAG + LLM ad auction and investigate the underlying theoretical / empirical nature of the corresponding framework in detail.

+ Finally, we evaluated various segment auction mechanisms and other ad auction baselines within the RAG framework. Our analysis provides insights into auction outcomes, such as social welfare and revenue, in some realistic scenarios, providing practical guidance for implementing this framework in real-world use cases.

------

### Further result on the multi-ad segment auction

We actually have obtained the allocation function of the GSP analogue under the RAG framework. Precisely, for the multi-ad segment auction presented in Figure 3, we observe that the allocation probability can be computed as follows:
$$ P(S \text{ wins }) = \sum_{T \subseteq S} (-1)^{|T|+1} \frac{\sum_{j \in T} q_jb_j}{\sum_{i \in \bar{S}\cup T}q_ib_i},$$
which strictly generalizes the single allocation segment auction by taking $S$ to be a set including $i$. We will add a brief remark on this result in the camera-ready.

Meta-review: While there was a general consensus in the reviews that this paper is providing a plausible initial approach to an important emerging domain, the discussion focused on two aspects.  First, given the experimental results is the approach promising enough.  Second, is the market design sufficiently novel and interesting.

The general consensus is that the experiment results are relatively weak.  The authors stressed in their response that these results are not the main focus of the paper, and I and some others agree that in an early paper like this it isn't essential for the experimental results to be state of the art or even really practical.

This makes the second question more important, and after the discussion there remained at least some disagreement.  My own option, shared with some of the reviewers, is that even if the design doesn't have much technical novelty in terms of introducing major new building blocks or analysis techniques, it does combine existing techniques in a novel way to create a design that is able to achieve desirable properties in a novel and interesting setting. (Arguably, the limited technical novelty is even a benefit in terms of being able to explain the way the market works to participants.)
Decision: Accept (poster)