  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
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.
