Paper deep dive
Diffusion-Based Auctions for Multi-Winner Banner Ads
Lilian Sun, Henry Huang, Fucheng Warren Zhu, Giannis Daras, Constantinos Daskalakis
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/14/2026, 9:58:41 AM
Summary
This paper proposes a novel framework for banner ad auctions that leverages diffusion models to allow multiple bidders to co-win a single ad opportunity. Unlike traditional single-winner auctions, this mechanism aggregates bidders' textual descriptions and bid strengths into a composite score that drives the reverse process of a diffusion model (specifically FLUX.1-schnell) to generate a welfare-maximizing image. The study evaluates the mechanism's efficiency, monotonicity, and approximate incentive compatibility (using Myerson lemma or VCG-style payments), demonstrating improvements over single-winner baselines while preserving image quality.
Entities (9)
Relation Signals (8)
Lilian Sun → affiliatedwith → Harvard University
confidence 99% · Lilian Sun Affiliation: Harvard
Constantinos Daskalakis → affiliatedwith → MIT
confidence 99% · Constantinos Daskalakis ... Affiliation: MIT
Giannis Daras → affiliatedwith → MIT
confidence 99% · Giannis Daras Affiliation: MIT
Diffusion-Based Auctions → appliesto → Banner Ad Auctions
confidence 98% · We propose a new framework for banner ad auctions
Diffusion-Based Auctions → uses → FLUX.1-schnell
confidence 95% · Specifically, for all our experiments we use FLUX.1-schnell.
Diffusion-Based Auctions → utilizestechnique → Classifier-Free Guidance
confidence 95% · Using ideas from classifier-free guidance Ho and Salimans (2021), we aggregate these bidder-specific conditional scores
Diffusion-Based Auctions → employspaymentrule → VCG Payment Rule
confidence 90% · As a heuristic alternative, we propose using prices inspired by the VCG payment rule.
Diffusion-Based Auctions → employspaymentrule → Myerson Lemma
confidence 90% · approximate incentive compatibility when combining our allocation rule with Myerson lemma-based or Clarke rule-based payments.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We propose a new framework for banner ad auctions, leveraging diffusion models to allow for multiple bidders to co-win a single banner ad opportunity, and in particular influence the ad shown on the banner depending on the strength of their bids, enabling a far richer outcome space compared to standard banner ad auctions, where there is a single winner who shows their ad. In our framework, the outcomes are images (what ad to show) and each bidder expresses their preferences over outcomes by declaring their value per unit of alignment between the image chosen by the mechanism and a textual description of their desired image. Our proposed mechanism combines the advertisers' bids and textual descriptions into a score that drives the reverse process of a diffusion model. This is used to sample a set of candidate images from which the welfare maximizing one is eventually chosen. Extensive experimentation evaluates our proposed mechanism around the following axes: (1) efficiency improvements of our allocation rule relative to the single-winner allocation rule; (2) monotonicity of our allocation rule; and (3) approximate incentive compatibility when combining our allocation rule with Myerson lemma-based or Clarke rule-based payments. Improvements along all these axes are shown with the number of Monte Carlo samples. Meanwhile, these benefits are attained while preserving the image quality.
Tags
Links
- Source: https://arxiv.org/abs/2610.14473v1
- Canonical: https://arxiv.org/abs/2610.14473v1
Trouble viewing inline? Open PDF directly →
Full Text
76,609 characters extracted from source content.
Expand or collapse full text
Diffusion Based Auctions for Multi-Winner Banner Ads Appeared in the proceedings of the 27th ACM Conference on Economics and Computation Lilian Sun Affiliation: Harvard Henry Huang Affiliation: Harvard Fucheng Warren Zhu Affiliation: Harvard Giannis Daras Affiliation: MIT Constantinos Daskalakis Note: Supported by a Simons Investigator Award, a Simons Collaboration on Algorithmic Fairness, ONR MURI grant N00014-25-1-2116 and ONR grant N00014-25-1-2296. Affiliation: MIT Abstract We propose a new framework for banner ad auctions, leveraging diffusion models to allow for multiple bidders to co-win a single banner ad opportunity, and in particular influence the ad shown on the banner depending on the strength of their bids, enabling a far richer outcome space compared to standard banner ad auctions, where there is a single winner who shows their ad. In our framework, the outcomes are images (what ad to show) and each bidder expresses their preferences over outcomes by declaring their value per unit of alignment between the image chosen by the mechanism and a textual description of their desired image. Our proposed mechanism combines the advertisers’ bids and textual descriptions into a score that drives the reverse process of a diffusion model. This is used to sample a set of candidate images from which the welfare maximizing one is eventually chosen. Extensive experimentation evaluates our proposed mechanism around the following axes: (1) efficiency improvements of our allocation rule relative to the single-winner allocation rule; (2) monotonicity of our allocation rule; and (3) approximate incentive compatibility when combining our allocation rule with Myerson lemma-based or Clarke rule-based payments. Improvements along all these axes are shown with the number of Monte Carlo samples. Meanwhile, these benefits are attained while preserving the image quality. Contents 1 Introduction 2 Related Work 3 Methodology 4 Results 5 Discussion 6 Conclusion References A Prompts B Generalized Score Composition C Linear Aggregation D Comprehensive Empirical Evaluation E Bid Combination Values 1 Introduction Online advertising auctions, including sponsored search and banner ad auctions, are a cornerstone of the digital economy. A fundamental limitation of these auctions, however, is that they make discrete allocations, in that every ad opportunity is allocated to a single advertiser. However, this might leave economic efficiency on the table. It stands to reason that augmenting the allocation space to allow multiple advertisers to co-win an advertising opportunity and co-influence the shown ad according to their combined preferences could substantially improve efficiency in many contexts. The challenge is that, in order to unlock this source of increased efficiency, the allocation rule of the mechanism needs to optimize over images to output one that is both natural and aggregates the advertisers’ preferences according to the strength of their bids. The goal of this paper is to investigate how to do this by combining methods from mechanism design and diffusion models. Taking a step back, our work belongs to a growing line of literature investigating the interface between mechanism design and generative AI. While monetization of generative AI is certainly one motivation for pursuing this line of research, our motivation is different. We want to explore whether generative AI can be leveraged to overcome the limitation of optimizing over a discrete set of candidate allocations, encountered in many mechanism design settings involving digital goods. When a generative model for this type of goods is available, the outcome of the auction can be taken to be much richer and the allocation of the auction can leverage the generative model to select from this richer set of alternatives. Consider banner ads, for example. In a standard banner ad auction, the allocation rule of the auction effectively selects one (or none) out of a finite set of banners corresponding to the different bidders, as there is at most one winner of the auction. Instead, we want to think of the outcome space as continuous, allowing all possible images to be placed on the banner! By allowing a larger set of outcomes, we can combine the preferences of multiple bidders in the chosen allocation, and increase the efficiency, or other economic property of the auction. Analogous opportunities arise for other data modalities. Consider, e.g., asking “What should I do in Boston?” to a Large Language Model (LLM). The LLM’s response could be: Boston is a great city for Italian food… Try <Italian Restaurant Ad 1> in the North End, then stop by <Local Shop Ad 2> for souvenirs. By allowing multiple bidders to influence the text generation process, we can allow multiple advertisers to win exposure from the answer to a single query. Indeed, recent works by Dütting et al. (2024); Hajiaghayi et al. (2024); Feizi et al. (2023); Dubey et al. (2024) make various different proposals for how to use mechanism design methods in auto-regressive generation to enable multiple advertisers to influence the sampled text according to their bid strength. Our goal in this paper is to study the visual domain and, in particular, to explore how diffusion models, as opposed to autoregressive ones, can be leveraged to enable mechanisms whose allocation space is the continuum of all possible images. To fix ideas, consider the banner ad auction example discussed earlier. We want to design an auction whose goal is to select what content to show on a banner, when there are several advertisers interested to show their advertising content on the banner, and we want to allow any possible content to appear on the banner (subject perhaps to certain ground rules that prevent offensive or otherwise undesirable content). To approach this question we need to model how different bidders express their preferences, how the allocation rule of the auction aggregates these preferences, and how the bidders are charged. Our approach and contributions are as follows: ∙ A novel auction design challenge: We introduce an auction design challenge where multiple bidders compete for the generation of an image. In our stylized model, each bidder i has a private scalar type mim_i and a public caption (prompt) cic_i. So the setting is single-dimensional. The bidder’s value for an image I that the auction can select is mi⋅α(I,ci)m_i·α(I,c_i), i.e. the alignment α(I,ci)∈[0,1]α(I,c_i)∈[0,1] between the image and their caption, multiplied by their private type. The alignment can be computed using a standard model that computes the alignment between images and captions, e.g. CLIP, and it is fixed by the auctioneer. The bidders are asked to report their value mim_i per unit of alignment according to this model. The allocation space of the auction are all possible images, of some fixed resolution. The goal of the auctioneer is to maximize welfare. Perhaps the auctioneer has some basic desiderata for the image, e.g. enforcing some content, avoiding certain outputs, etc. These are all summarized in a “system caption” c∅c_ and a dummy bidder is included in the computation of the welfare, whose value is m∅⋅α(I,c∅)m_ ·α(I,c_ ). Besides the system caption there is also an implicit desideratum that the image be “natural.” ∙ An allocation rule: We propose a scalable, diffusion model-based generative algorithm that can serve as the allocation rule of an auction in the afore-described setting. Through comprehensive empirical validation, we show that our algorithm generates images that are (i) visually appealing; (i) aggregate the bidders’ preferences according to their captions and the strengths of their bids; and in particular (i) attain higher welfare compared to the single-winner alternative where the highest bidder wins and an image is generated according to their caption. Figure 1 demonstrates (i) and (i), showing the outputs of our algorithm for three bidders of different captions and varying bids. In Section 4.3, we provide extensive experimental evidence for (i). (a) (0.33,0.33,0.33)(0.33,0.33,0.33) (b) (0.4,0.4,0.2)(0.4,0.4,0.2) (c) (0.6,0.3,0.1)(0.6,0.3,0.1) (d) (0.6,0.2,0.2)(0.6,0.2,0.2) (e) (1,0,0)(1,0,0) Sampled images for 33 agents with captions “Louis Vuitton bag”, “H&M storefront” and “Nike shoes” and (normalized) bids b1b_1, b2b_2 and b3b_3 respectively, for different choices of (b1,b2,b3)(b_1,b_2,b_3). Figure 1: Visual examples of our allocation rule. This scenario simulates an auction between three agents with captions “Louis Vuitton bag”, “H&M storefront” and “Nike shoes” bidding to influence the generation of an image with system caption “A person walking down a city street.” We denote by b1b_1, b2b_2 and b3b_3 the normalized bids of the agents, i.e. the relative strengths of their bids. From left to right, the images show the visual output as the bid distribution shifts from balanced, where all agents are equally represented, to scenarios with one or two dominant agents, and finally to a single strong bidder case. This fine-grained, bid-dependent control is achieved by our mechanism aggregating agent preferences directly within the diffusion model’s score function, creating a scalable auction for a continuous, visual outcome. Our allocation rule is designed as follows. We make use of a conditional diffusion model,11 1 Specifically, for all our experiments we use FLUX.1-schnell. sampling a distribution, p(x|c)p(x|c), over images x conditioning on captions c. For each bidder’s caption cic_i, this model provides us access to a conditional score function st(x|ci):=∇xlogpt(x|ci)s_t(x|c_i):= _x p_t(x|c_i), where t indexes diffusion time; in particular pt(x|c)=p(x|c)∗(0,σ2(t)I)p_t(x|c)=p(x|c) N(0,σ^2(t) I) for some increasing noise schedule σ2(t)σ^2(t), t∈[0,T]t∈[0,T]. Using ideas from classifier-free guidance Ho and Salimans (2021), we aggregate these bidder-specific conditional scores according to the relative strengths of their bids to obtain a composite score function, which we use to define a reverse diffusion process. We run this reverse diffusion process for a number of times, k, to sample multiple images, and output the image with the highest welfare. Our algorithm is scalable. Its generation time depends on the time taken to run the reverse diffusion process times the number of samples k that we draw. Meanwhile, the number of samples influence the final welfare, as shown by our experiments. So there is a trade-off between generation time and welfare. ∙ Payment rules: The well-studied empirical properties of classifier-free guidance Ho and Salimans (2021) suggest that, as bidder i increases their bid bib_i while the bids b−ib_-i of the other bidders remain fixed, the image sampled from the reverse diffusion process defined by our composite score is influenced more and more by bidder i’s caption cic_i. So the expected alignment α(x,ci)α(x,c_i) between the generated image, x, and bidder i’s caption should be approximately increasing in bidder i’s bid bib_i, everything else held constant. Suppose that it was indeed increasing; in Figure 4 we provide evidence that, at least approximately, this is the case. Then, because the alignment score lies in [0,1][0,1], and the bidder’s value is their private type times the alignment α(x,ci)α(x,c_i), we can straightforwardly adapt the payment rule from Myerson’s lemma to compute prices that make truthful reporting of types a dominant strategy. Figure 2 shows that this adaptation is straightforward. Figure 2: If the expected alignment between the generated image and bidder i’s caption were increasing in bidder i’s bid, we would be able to straightforwardly adapt the payment rule from Myerson’s lemma to compute prices that induce truthful reporting of types a dominant strategy. In practice, the expected alignment might only be approximately increasing in the bid, because the diffusion model and the alignment model might be misaligned (no pun intended) with each other. So, if we stick to the payment rule that is the area to the left of the curve, we will have approximate incentive compatibility. There are two additional issues we need to consider: (1) We only have sample access to α(x,ci)α(x,c_i) for a given set of bids and captions. This is not a big issue. We can apply Myerson’s lemma on a sampled curve (whose randomness is with respect to the randomness in running the diffusion process k times and for various bids by the bidder) and we would get the desired price, in expectation. (2) We do not have an analytical description of the expected curve or a sampled curve to apply Myerson’s lemma. So we will need to do numerical integration to estimate the price, which will introduce error in incentive compatibility. The errors resulting from the approximate monotonicity and the numerical integration should be small, as illustrated in Figure 8, and the latter is also controllable with computational effort. The main disadvantage of the afore-described approach is that it takes time to perform numerical integration, and this would make the price computation slow. As a heuristic alternative, we propose using prices inspired by the VCG payment rule. For each bidder i, we run our allocation rule without this bidder’s bid or caption to sample an image. We then charge this bidder the difference between the welfare of the other bidders under this image and under the image sampled with this bidder included. This is an approximation to the VCG allocation rule, which exactly optimizes over images. Instead, we optimize using Monte Carlo sampling. Due to this approximation, this will not be guaranteeing incentive compatibility. We perform extensive experimentation to evaluate how approximately truthful the resulting mechanism is. See Section 4.4. As shown in our experiments, the incentive to not be truthful decreases with the number k of Monte Carlo samples in the allocation rule, and is relatively controlled. The additional benefit of a VCG-style payment is that it is also robust to manipulation of captions, if we are in a setting where bidders can manipulate both their value per unit of alignment of the chosen image with their caption and their caption. ∙ Extensive empirical validation: As mentioned earlier, we perform extensive experimentation to evaluate the performance of our proposed allocation rule and mechanism. In particular, we experiment with a wide range of prompts capturing settings where the bidders have prompts that are non-competing (e.g. “Nike shoes” and “Gucci bag”) or competing (e.g. “Starbucks coffee” and “Dunkin coffee”). We consider settings where bidders’ bids are comparable in strength or there is variation in their strengths. We experiment with settings from two up to twenty bidders. Finally, we experiment with the number of Monte Carlo samples used in our allocation rule. We demonstrate through extensive multi-agent experiments on a diverse dataset that our mechanism achieves key economic properties: welfare improvement over single-winner baselines, approximate incentive compatibility, and bid monotonicity, all without degrading image quality. All in all, our work proposes a new challenge in mechanism design, and a productive combination of diffusion model and mechanism design methods to approach it, complete with extensive experimental evidence about the economic value of extending beyond single-winner mechanisms. We believe that we make an important first step to a very rich direction. 2 Related Work We review the most relevant strands of related literature, focusing on recent work at the interface of mechanism design and Large Language Models, and guiding diffusion models. 2.1 Mechanism Design and Generative AI Recent research has begun to explore the interface of mechanism design and Large Language Models, largely motivated by the monetization of LLMs. A central challenge is how to model and how to aggregate the preferences of agents over generated content. To this end, Dütting et al. (2024) introduce token auctions, wherein the bidders are competing at the token level, competing to influence the distribution of the next generated token. Others have focused on contextually relevant ad placement within LLM outputs using retrieval-augmented generation (Hajiaghayi et al., 2024); auctions for placement within ad summaries (Dubey et al., 2024); and auctions where the bidders are bidding for modifications to a neutrally generated text (Feizi et al., 2023). While these works have provided a starting point for studying mechanism design in generative applications involving text, they have left open the question of how to do so in generative applications involving other data modalities and other types of generative models, beyond LLMs. This is the challenge that we set out to study in this work, focusing on image generation and diffusion models. Moreover, our main motivation is to enhance the attainable welfare in auction settings, such as banner ad auctions, that are already widely used in practice, by enabling an increased allocation space, versus introducing advertising to generative models which is the motivation of some of the afore-described works. 2.2 Controllable Image Generation with Diffusion Models To realize a generative auction in the visual domain, we build upon the recent advances in diffusion models, which have achieved state-of-the-art results in synthesizing diverse, high-fidelity images (Ho et al., 2020; Song and Ermon, 2019; Rombach et al., 2022; Dhariwal and Nichol, 2021). These models learn how to generate data by learning how to reverse a gradual noising process, which allows them to progressively remove noise from a random sample until a clean image sample is produced (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song et al., 2021). Recent advances, such as Rectified Flow, have further improved generation speed and quality (Liu et al., 2023; Esser et al., 2024). An important feature of this technology for our purposes is its controllability. Generation can be steered toward desired attributes using guidance techniques. Classifier-free guidance (CFG) has become a prominent method, as it allows for strong conditional control without a separate classifier model (Ho and Salimans, 2021). Its effectiveness in high-fidelity caption-to-image synthesis has been well-demonstrated (Saharia et al., 2022; Nichol et al., 2022). Our work leverages this technical capability not just for creative control, but as a primitive upon which we build an allocation rule that integrates multiple agents’ preferences. 3 Methodology Recall that our goal in this paper is to propose an auction that takes as input the preferences of bidders over images and generates a single image that aggregates these preferences in a welfare-maximizing way. We will propose a model specifying how the agents may express their preferences over images to the auction, an algorithm that aggregates these preferences to sample an image with high social welfare (the allocation rule), and an algorithm computing the agents’ payments (the payment rule). Our goals from the proposed auction are (a) approximate monotonicity of the allocation rule; (b) approximate incentive compatibility of the auction; and (c) welfare-improvement compared to single-winner baselines, i.e. auctions that select the highest bidder as the winner and generate an image according to this bidder’s preferences. We start with some preliminaries from auction theory and diffusion models, before presenting our proposed design. 3.1 Preliminaries 3.1.1 Auctions and Social Welfare Our goal is to maximize social welfare. For a set of agents N and a chosen outcome I, which in our case is a natural image, the social welfare is W(I)=∑i∈Nvi(I),W(I)= _i∈ Nv_i(I), (1) where vi(I)v_i(I) is the value that agent i derives from image I. An auction takes as input some description of the viv_i’s and computes an outcome I as well as payments pii∈N\p_i\_i∈ N for all the bidders. The allocation rule of the auction computes I and the payment, or price, rule outputs the prices. If agents could communicate their viv_i’s exactly and we were able to optimize over natural images, we could use the Vickrey-Clarke-Groves (VCG) mechanism to optimize social welfare in a truthful fashion. Unfortunately, optimizing W(I)W(I) over I is highly non-trivial. One reason is that it is not mathematically easy to define what makes I a natural image. So it is unclear what is the space of feasible allocations. Another challenge is that it is not clear how bidders can specify their preferences over natural images. 3.1.2 Score-Based Diffusion and Guidance Denoising diffusion models (see references above) learn to sample a target distribution p(x)p(x) over images to which sample access is provided, by learning how to reverse a diffusion process that progressively adds noise to samples from p according to a noise schedule σ2(t)σ^2(t). This is often achieved by learning the score functions, st(x)=∇xlogpt(x)s_t(x)= _x p_t(x), of the distributions, pt(x):=p(x)∗(0,σ2(t)I)p_t(x):=p(x) N(0,σ^2(t) I), of noised samples. Knowledge of the scores suffices to run the reverse diffusion process, i.e. starting with a noisy sample and progressively improving it until a clean sample is obtained. There are variations to the theme related to whether the noising process is variance exploding (as we presented it) or variance preserving or has a different type of drift, and various other generalizations of this theme. When caption-image data is available, one targets a model that can do conditional generation, i.e. sample an image x conditioning on a caption c. To gain this capability, the approach is to learn the scores, st(x|c)=∇xlogpt(x|c)s_t(x|c)= _x p_t(x|c), of the noised conditionals, pt(x|c):=p(x|c)∗(0,σ2(t)I)p_t(x|c):=p(x|c) N(0,σ^2(t) I). Once the conditional scores are learned, they can be used directly to do conditional sampling by reversing the diffusion process starting with a sample from p(x|c)p(x|c), where c is the caption that we want to condition on. A key technique that has been found to improve the generated samples is Classifier-Free Guidance (CFG) (Ho and Salimans, 2021). CFG sharpens the generation by steering the unconditional score st(x|∅)s_t(x| ) towards the conditional score st(x|c)s_t(x|c). The guided score s^t s_t is typically taken to be: s^t(x|c)=(1−ω)st(x|∅)+ωst(x|c) s_t(x|c)=(1-ω)s_t(x| )+ω s_t(x|c) (2) where ω denotes the guidance scale. Increasing ω amplifies the conditioning signal. 3.2 Our Setting: Image Generation Auctions We now formalize the main components of our setting: 1. Allocation Space (ℐI): The goal of the auction is to output a natural image I∈ℐI , where ℐI is the space of all “natural images.” Part of the challenge here is that the set of natural images is not well-defined mathematically, and we only have proxies for accessing this set, e.g. by sampling a diffusion model trained to sample natural images. 2. Agents (N=1,…,nN=\1,…,n\): Each agent i wishes to influence the image output by the auction. 3. Agent Types: Each agent i has a public text prompt/caption cic_i describing their desired content and a private type mi∈ℝ≥0m_i _≥ 0 which is a scalar. In particular, the setting is single-dimensional.22 2 While this is the main setting we will study, it is well motivated to consider the multi-dimensional setting where the caption of the bidder is also private. We will briefly discuss this setting in this paper. 4. Agent Valuations: As a function of their public caption, cic_i, and private type, mim_i, bidder i’s valuation is vi(I)=mi⋅α(I,ci)v_i(I)=m_i·α(I,c_i), where α(I,ci)∈[0,1]α(I,c_i)∈[0,1] is how well image I aligns with caption cic_i according to some fixed model (announced to the bidders) that computes image-text alignment. We will be using the CLIP model throughout. In particular, a bidder’s private type expresses their value per unit of alignment between the image and their caption. 5. Agent Bids: Each bidder will communicate a bid bi∈ℝ≥0b_i _≥ 0 to the auction. 6. Base/System Prompt (c): A text prompt describing the base content of the image to be output, as well as guardrails protecting against offensive content. This could be empty. We could view the system prompt as an extra bidder with valuation v0(I)=m0⋅α(I,c)v_0(I)=m_0·α(I,c). In the context defined by the above ingredients, the goal of our mechanism is to implement an Allocation Rule that will generate a high-welfare image (Section 3.4) and a Payment Rule that will charge the agents in a way that induces good incentive properties (Section 3.5). We propose such rules in the next few sections. 3.3 A Prelude: the VCG auction A natural question to ask at this point is what it would mean to implement the Vickrey-Clarke-Groves mechanism. The allocation rule of this mechanism would be to choose an image as follows: I∗∈argmax∑i∈N∪0I∈ℐvi(I), I^*∈ _I _i∈ N∪\0\v_i(I), (3) using some tie-breaking rule, while the Clarke payment rule would charge bidder i as follows: pi=max∑j≠iI∈ℐvj(I)−∑j≠ivj(I∗). p_i= _I _j≠ iv_j(I)- _j≠ iv_j(I^*). (4) The challenge is that the maximization problems showing up in the allocation and price rules above are over ℐI, the set of “natural images.” Unfortunately, this set does not have a mathematical specification which is amenable to exact optimization. We will instead leverage diffusion models to access this set, and approximately optimize over it via sampling. In the next section, we discuss how to build effective samplers. 3.4 Our Allocation Rule: From Bids and Captions to High-Welfare Images via Score Composition Our allocation rule approximately optimizes welfare over natural images, by leveraging a diffusion model, and in particular a text-to-image diffusion model. At the heart of our approach lies a score composition technique, inspired by classifier-free guidance. Our score composition technique aggregates bidders’ bids and captions into a composite score that drives a reverse diffusion process, used to sample over high-welfare parts of ℐI. We first describe our score composition technique for two agents as it is simpler. Instead of combining conditional scores with the unconditional score (as is done in classifier-free guidance, see Eq. (2)), we perform a bid-weighted interpolation between two conditional scores: the conditional score with the concatenation of the bidders’ prompts and the conditional score under the highest bidder’s prompt. More precisely, suppose that our two agents submitted bids b1,b2b_1,b_2, where b1≥b2b_1≥ b_2 without loss of generality. We define bidder 11’s normalized bid b1(1)=b1b1+b2b_1^(1)= b_1b_1+b_2 and, from this, bidder 1’s weight w(1)=2b1(1)−1w^(1)=2b_1^(1)-1. We then define our composite score st(1,2)(x)s_t^(1,2)(x) as follows: st(1,2)(x)=(1−w(1))st(x|c,c1,2)+w(1)st(x|c,c1)s^(1,2)_t(x)=(1-w^(1))s_t(x|c,c_1,2)+w^(1)s_t(x|c,c_1) (5) where c,c1,2=c,c1,c2c,c_1,2=\c,c_1,c_2\ is the concatenated prompt of the two bidders (and the base prompt if any), and c,c1=c,c1c,c_1=\c,c_1\ is the concatenation of the base prompt and bidder 1’s prompt. When the bids are equal, we have b1(1)=0.5b_1^(1)=0.5 and w(1)=0w^(1)=0 so the composite score relies solely on the first term. When Agent 1 is fully dominant, i.e. b1(1)=1b_1^(1)=1, we have w(1)=1w^(1)=1, and the composite score collapses to the second term, i.e. the dominant agent’s score. We generalize the score composition technique to n agents recursively, with the full derivation in Appendix B. The score for n agents, whose bids are w.l.o.g. ordered as b1≥b2≥⋯≥bnb_1≥ b_2≥·s≥ b_n, is defined as: st(1:n)(x)=(1−w(1))s(x|c,c1:n)+w(1)st(1:n−1)(x)s^(1:n)_t(x)=(1-w^(1))\,s(x|c,c_1:n)+w^(1)\,s^(1:n-1)_t(x) (6) where st(1:n−1)(x)s^(1:n-1)_t(x) is the composite score for the n−1n-1 most dominant agents, and it is computed recursively. Given our composite score, we are ready to describe the allocation rule of our mechanism. We use the composite score to run a reverse diffusion process k times, generating k candidate images. We then output the image I I that maximizes the total welfare, as calculated using the agents’ submitted bids (which we hope will be close to their private types if we choose a good payment rule). Our allocation rule tries to approximate the VCG allocation rule in the previous section, leveraging our score composition approach to sample over high-welfare parts of ℐI, which is otherwise inaccessible from an optimization standpoint. Our score composition technique is empirically found to generate images that combine the agents’ prompts according to the strengths of their bids. So while we cannot optimize welfare exactly over images, our sampling method gives us a good Monte Carlo sampling approach to identify high-welfare images. For some illustrations of our allocation rule see Figures 1 and 3. We also test alternative score composition techniques, namely linearly combining the bidders’ scores according to the relative strengths of their bids. However, this leads to worse performance due to diffusion model sensitivity to conflicting gradients. Objects tend to overlay incoherently rather than creating a cohesive image. See Appendix C for some samples. This is to say that choosing a good composition method is crucial for our intended application. 3.5 Payment Rule Alternatives: Myerson Lemma-Based and Clarke Rule-Based We propose two alternatives for the payment rule of the mechanism, one based on Myerson’s lemma, and another based on Clarke’s payment rule. The former is closer to yielding incentive compatibility of the resulting mechanism but the latter is easier to compute. 3.5.1 Computing Prices Using Myerson’s Lemma. As discussed in the introduction, the empirical properties of diffusion guidance suggest that the allocation rule of the previous section should be approximately monotone, in that increasing one’s bid should result in an expected higher alignment of the sampled image with their caption. This is empirically verified in Section 4.2. This suggests a route towards identifying a payment rule that, combined with the allocation rule, would produce a mechanism with strong incentive compatibility properties, based on Myerson’s lemma Myerson (1981). Recall that this lemma establishes that, if the allocation rule xi(bi,b−i)x_i(b_i,b_-i) of some mechanism, is monotone non-decreasing in the agent’s bid, bib_i, while holding the bids, b−ib_-i, of the other bidders fixed, then there exists a unique payment rule (up to a constant shift) that combined with this allocation rule renders truthful bidding a dominant strategy in the resulting mechanism (see also Figure 2): pi(bi,b−i)=bi⋅xi(bi,b−i)−∫0bixi(z,b−i)z.p_i(b_i,b_-i)=b_i· x_i(b_i,b_-i)- _0^b_ix_i(z,b_-i)\,dz. (7) Under this payment rule, an agent with true value mim_i who bids truthfully (bi=mib_i=m_i) obtains utility ui(mi,mi)=mi⋅xi(mi,b−i)−pi(mi,b−i)u_i(m_i,m_i)=m_i· x_i(m_i,b_-i)-p_i(m_i,b_-i), and no alternative bid would yield them a strictly higher utility ui(mi,bi)=mi⋅xi(bi,b−i)−pi(bi,b−i)u_i(m_i,b_i)=m_i· x_i(b_i,b_-i)-p_i(b_i,b_-i). To apply this lemma to our setting, we substitute the expected alignment in place of xi(bi,b−i)x_i(b_i,b_-i) i.e. we take xi(bi,b−i):=[α(I,ci)|bi,ci,b−i,c−i]x_i(b_i,b_-i):=E [α(I,c_i)|b_i,c_i,b_-i,c_-i ], where the expectation is taken with respect to running the reverse diffusion process k times and choosing the welfare-maximizing image among the k samples. With this substitution in place, we notice that, in our setting, we can also write the expected value of a bidder whose private type is mim_i and who bids bib_i as mi⋅xi(bi,b−i)m_i· x_i(b_i,b_-i). So Myerson’s lemma implies that the price rule (7) would induce a truthful mechanism, if our allocation rule was indeed monotone non-decreasing. We experimentally evaluate the approximate monotonocity of the allocation rule in Section 4.2 and the approximate truthfulness induced by applying Myerson’s lemma for computing prices, in Section 4.4.1. As discussed in the Introduction, there are two additional issues we need to consider when computing prices: (1) Our allocation rule is randomized, and in particular we only have sample access to α(I,ci)α(I,c_i) for a given set of bids and captions. This is not a big issue. We can apply Myerson’s lemma on a sampled curve (whose randomness is with respect to the randomness in running the diffusion process) and for various bids by the bidder (holding the other bidders’ bids fixed) and we would get the desired price, in expectation, and therefore maintain the incentive properties ex ante. (2) We do not have an analytical description of the expected curve or a sampled curve to apply Myerson’s lemma. So we will need to do numerical integration to estimate the price, which introduces additional error in incentive compatibility. The errors resulting from the approximate monotonicity and the numerical integration should be small, as illustrated in Figure 8, and the latter is also controllable with computational effort (increasing the grid points). Everything considered, our experiments suggest that the resulting mechanism has promising incentive compatibility properties. The main disadvantage of the afore-described approach is that it takes time to perform numerical integration, and this makes the price computation slow. As a heuristic alternative, we propose using prices inspired by the Clarke payment rule, in the next section. 3.5.2 Computing Prices Using Clarke’s Payment Rule. To avoid the computational burden of computing prices based on Myerson’s lemma, as discussed in the previous section, we propose using a payment rule inspired by Clarke’s payment rule in the VCG mechanism. For each bidder i, we run our allocation rule without this bidder’s bid or caption to sample an image I^−i I_-i. We then charge this bidder the difference between the welfare of the other bidders under this image and under the image I I sampled with all bidders included, namely pi=(∑j≠ivj(I^−i))−(∑j≠ivj(I^)).p_i= ( _j≠ iv_j( I_-i) )- ( _j≠ iv_j( I) ). (8) This is an approximation to the Clarke payment rule (4), which optimizes (not via Monte Carlo sampling) over all natural images ℐI. Since there is approximation error in the Clarke payment computations, the payment rule will not be guaranteeing incentive compatibility. We perform extensive experimentation to evaluate how approximately truthful the resulting mechanism is in Section 4.4.2, and it shows reasonable performance, albeit it is worse than the performance of the Myerson lemma-based payment rule. The incentive to deviate from truthful bidding is found to decrease with the number k of Monte Carlo samples in the allocation rule. We finally note that, besides the computational efficiency of the Clarke rule-based payments, they offer another advantage, which is protection against the strategic manipulation of captions by the bidders, as they are not tied to the single-dimensional setting we study here, where the captions are public and only the value-per-unit-of-alignment is private information held by the bidders. While we didn’t conduct experiments to evaluate how strong the incentives for caption manipulations are, this is a promising direction for future work. 4 Results 4.1 Experimental Setup To comprehensively analyze our proposed mechanism, we evaluate properties of the allocation rule and the payment rule, across a diversity of prompts, bids, and the number of bidders, amounted to more than 80,00080,000 image generations over all. Each setting comprises a base prompt that captures an everyday scenario, ranging from natural backdrops to indoor spaces. These base prompts are paired with bidder prompts in various sectors such as technology, food, fashion, and automobiles, capturing a representative view of modern consumer categories. Table 1 displays example prompt configurations in two-agent scenarios. Table 1: Example prompt configurations across 2-Agent scenarios Base Prompt Agent 1 Prompt Agent 2 Prompt Two friends chatting over coffee at a cafe Starbucks mug Apple MacBook Air A hiker resting on a mountain trail North Face backpack Gatorade bottle A woman with a tray of food at a cafeteria McDonald’s fries Pepsi can A person walking down a city street Louis Vuitton handbag H&M storefront Friends gathered for a movie night at home Doritos chips Coca-Cola cans A car driving along a scenic coastal highway Tesla car ExxonMobil sign For example, the following prompts correspond to the generations from our allocation rule, shown in Figure 3, under different combinations of bids for two agents: (a) (0,1)(0,1) (b) (0.3,0.7)(0.3,0.7) (c) (0.5,0.5)(0.5,0.5) (d) (0.7,0.3)(0.7,0.3) (e) (1,0)(1,0) Figure 3: Allocation rule outputs for 2 agents, North Face and Gatorade, with bids (b1,b2)(b_1,b_2). ∙ Base: “A hiker resting on a mountain trail” ∙ Base + Agent 1: “A hiker resting on a mountain trail with North Face backpack” ∙ Base + Agent 2: “A hiker resting on a mountain trail with Gatorade bottle” ∙ Base + Joint: “A hiker resting on a mountain trail with North Face backpack and Gatorade bottle” In the next sections, we describe our findings from experimenting with our proposed allocation rule and mechanism across various settings, involving different prompts and bid combinations. We test the robustness of our findings by considering settings involving 22, 33, 55, 1010, and 2020 bidders. For example, Figure 1 displays example outputs of our allocation rule for 33 agents. Appendix A details the full prompt generation setup and Appendix E shows the distribution of bids that we sweep over. Our setup allows us to systematically vary agents’ bids under various prompts, allowing a range of score compositions. As per the definition of our allocation rule, for each combination of bids and prompts, we conduct Monte Carlo sampling, generating k images and output the welfare-maximizing one. All images are generated using the FLUX.1-schnell diffusion model with 5 inference steps and a guidance scale of 10. To compute welfare, we use CLIP (Radford et al., 2021). In particular, we compute the alignment αi=CLIP(I,ci) _i=CLIP(I,c_i) as the cosine similarity between the CLIP image embedding and text embedding, which lie in a shared embedding space. 4.2 Bid Monotonicity: Prompt Alignment Increases with Bid (a) Agent 1’s alignment with the output image as her bid is varied. (b) Agent 2’s alignment with the output image as her bid is varied. Figure 4: Alignment of the image output by the allocation rule with a particular bidder’s caption as they vary their bid from 00 to 11 in increments of 0.050.05, while keeping the opposing agent’s bid fixed at 0.30.3. For each bid combination and prompt configuration, k=5k=5 images are generated per trial across 55 trials; the welfare-maximizing image is selected within each trial, and CLIP alignment scores are averaged across the 55 trials and the two prompts. Shaded regions indicate standard deviation. An important property that we would like our allocation rule to have is bid monotonicity: agents who bid higher should receive higher allocation, meaning that the image selected by the allocation rule should have a higher expected alignment with their prompt as their bid increases. To study this, we consider two representative prompt combinations in the two-agent setting.33 3 Specifically, one setting uses “A woman with a tray of food at a cafeteria,” as base prompt, with “McDonald’s fries” and “Pepsi can,” as prompts for Agents 1 and 2. The other setting uses “A person walking down a city street,” as base prompt, and “Louis Vuitton handbag” and “H&M storefront,” as prompts for Agents 1 and 2. For each of these prompt configurations, we fix one of the two agent’s bid at b=0.3b=0.3 and vary the other agent’s bid over 0.00,0.05,0.10,…,1.00\0.00,0.05,0.10,…,1.00\. For each of the 21 bid combinations, we run our allocation rule using k=5k=5, i.e. we generate 55 images using our composite score and select the welfare-maximizing one. To obtain a better estimate of the expected alignment, we repeat 55 times, and compute the average CLIP alignment across the 55 repetitions. Figure 4 shows the curves plotting the average allocation to each agent as they increase their bid from 00 to 11, holding the other bidder’s bid fixed at 0.30.3. We show the average of Agent 1’s and Agent 2’s allocation, averaging across repetitions and the two prompt configurations. The shaded region represents the standard deviation across samples. Figure 8 (top plots) shows Agent 1’s allocation split between each of the prompt configurations. These curves are approximately monotone non-decreasing, consistent with our allocation rule satisfying approximate bid monotonicity. This is also visualized in Figures 1 and 3. 4.3 Efficiency: Improved Welfare Compared to Single-Winner Baseline (a) Average welfare improvement of up to 15.4% over single-winner baseline for 2 agents. (b) Average welfare improvement of up to 23.0% over single-winner baseline for 5 agents. Figure 5: Percent improvement of the welfare from our allocation rule over the single-winner baseline, averaged across all prompts in the two-agent and the five-agent settings respectively. We use k=20k=20 Monte Carlo samples in the allocation rule, for each prompt and bid combination. Unlike single-winner allocations, our allocation rule enables multiple agents to be represented simultaneously in the generated image. It is important to evaluate whether this compositional capability of our allocation rule leads to a higher total welfare. Single-Winner Baseline. We compare our allocation rule against a single-winner baseline that generates images considering a single agent’s prompt at a time. In this baseline, for a number of bidders n and parameter k in the allocation rule, for each combination of a base prompt and bidder prompts, n images are generated from our allocation rule, using the base prompt and a single agent’s prompt; in particular, for each agent, k images are generated using this agent’s prompt appended to the base prompt and the image that maximizes welfare for this agent is chosen. After n images are generated, one corresponding to each bidder’s prompt, the final output is the image that optimizes the overall welfare. This baseline serves as a direct comparison that lacks compositionality of agent preferences. Results. Our allocation rule consistently outperforms the single-winner allocation rule described above, across our experiments, varying the agent prompts and the number of agents. For the 22-agent setting, Figure 5(a) shows that our allocation rule improves the average welfare (averaged over all 200200 prompts we consider in the two-agent setting) by up to 15.415.4% over the baseline, which occurs when both agents’ normalized bids are equal to 0.50.5. In the 55-agent setting, Figure 5(b) shows that our allocation rule improves the average welfare (averaged over all 8585 prompts we consider in the five-agent setting) by up to 23.023.0% over the baseline, which occurs when all 5 agents’ normalized bids are equal to 0.20.2. Welfare improvements for up to 2020 agents are included in Appendix D.1. Figure 6: Welfare improvement is most significant when agents bid similar values. Individual prompts exhibit even larger improvements; e.g., we see up to 2121% welfare improvement in the two-agent setting and up to 36.036.0% welfare improvement in the 55-agent setting, for specific prompt and bid combinations. In Figure 6 we show results when the base prompt is “A car driving along a scenic coastal highway,” and the bidders’ prompts are “Tesla car” and “ExxonMobil sign.” In this plot we use k=50k=50 Monte Carlo samples in the allocation rule, and vary Agent 1’s bid from 0.0 to 1.0 in increments of 0.1 and Agent 2’s bid from 0.0 to 1.0 in increments of 0.25. The welfare improvement over the baseline is the highest when the agents bid similar values. This occurs because the bidders’ prompts are compatible and balanced bids activate the cooperative potential in our score composition. This allows the allocation rule to sample high-welfare outcomes that are inaccessible to the single-winner allocation rule, which is limited to using one agent’s prompt at a time. Finally, we conduct experiments varying the number k of Monte Carlo samples in the allocation rule, from k=1k=1 to k=20k=20 and for varying numbers of agents. For up to 10 agents, we see a rapid convergence of the welfare improvement over the single-winner baseline, with k=5k=5 samples achieving at least 90% of the welfare improvement attained with k=20k=20 samples. Figure 7 shows the average, across our 3-agent settings, welfare improvement as a function of k. Welfare improvement plateaus beyond k=5k=5, indicating that the benefits from Monte Carlo sampling saturate quickly. For 20 agents, k=15k=15 achieves a similar effect. Our detailed results are included in Appendix D.4. Figure 7: k=5k=5 Monte Carlo samples in the allocation rule attain more than 90% of the welfare improvement over the single-winner baseline attained with k=20k=20. For real-time advertising scenarios where latency matters, these plots suggest that the benefits from our allocation rule are realized for moderate values of k. 4.4 Incentive Compatibility We evaluate the incentive properties of our mechanism under the two payment rules we proposed. 4.4.1 Near Truth-Inducing Payments from Myerson’s Lemma The approximate bid monotonicity of the allocation rule suggests a path towards a payment rule that induces an approximately truthful mechanism, based on Myerson’s lemma Myerson (1981), as developed in Section 3.5.1. In this section, we experimentally evaluate the impact to incentive compatibility from the approximate monotonicity of the allocation rule and the numerical integration involved in computing Myerson payments. To estimate the ex ante regret of the agents for not reporting truthfully, we approximate the (ex ante) allocation of the auction, xi(bi,b−i):=[α(I,ci)|bi,ci,b−i,c−i]x_i(b_i,b_-i):=E [α(I,c_i)|b_i,c_i,b_-i,c_-i ], by replacing E with the empirical average over 55 trials. Using the approximate allocation rule x^i x_i, we compute approximate Myerson payments p^i p_i, by applying the trapezoidal rule on Eq. (7) (with xix_i replaced by x^i x_i). From approximate allocations and prices, we compute approximate utilities u^i(mi,bi)=mi⋅x^i(bi,b−i)−p^i(bi,b−i) u_i(m_i,b_i)=m_i· x_i(b_i,b_-i)- p_i(b_i,b_-i) for bidding bib_i when the true type is mim_i, and finally compute Agent 1’s relative regret from truthful bidding: Regret(mi)=maxbiu^i(mi,bi)−u^i(mi,mi)|u^i(mi,mi)|,Regret(m_i)= _b_i\, u_i(m_i,b_i)- u_i(m_i,m_i)| u_i(m_i,m_i)|, (9) maximizing over all bids on a grid. (a) Base: A woman with a tray of food at a cafeteria, Agent 1: McDonald’s fries, Agent 2: Pepsi can. (b) Base: A person walking down a city street, Agent 1: Louis Vuitton handbag, Agent 2: H&M storefront. Figure 8: Allocation rule (top) and relative regret from truthful bidding (bottom) under the Myerson payment rule, with Agent 2’s bid fixed at b2=0.3b_2=0.3 and Agent 1’s bid varied over [0,1][0,1] in increments of 0.050.05. The allocation rule uses k=5k=5 diffusion samples. To estimate the expected alignment induced by our allocation rule we sample from the allocation rule 55 times and average the alignment scores from these 55 repetitions. Relative regret stays below 4%4\% across all true values, confirming near incentive compatibility. Figure 8 shows the results for two representative prompts in a two-agent setting. As seen earlier, the allocation curves are approximately monotone non-decreasing, confirming the precondition of Myerson’s lemma. The relative regret remains below 4% across all tested true values mi∈0.1,0.2,…,0.9m_i∈\0.1,0.2,…,0.9\, with most values much lower, indicating that the mechanism with Myerson payments has very good incentive properties. 4.4.2 Approximate Truthfulness from Clarke-Based Payments As discussed in Section 3.5, a main disadvantage of payments computed via Myerson’s lemma is that it takes time to perform numerical integration of the allocation curve. This motivated us to propose an alternative payment rule based on Clarke’s payment rule in the VCG mechanism, in Section 3.5.2. In this section, we estimate the regret of the agents for not reporting truthfully. Since Clarke payments are faster to compute, we also study the ex post regret of the agents. Ex Ante Regret In Figure 9, we plot our estimates of the bidders’ (ex ante) regrets for not bidding truthfully when Clarke payments are charged, in the same settings as those of Figure 8. To estimate the (ex ante) Clarke payments and utilities, we run the allocation rule 55 times and average the results. We use k=5k=5 for the allocation rule. The relative regrets are found to be controlled, for the most part below 1010%, but they are about an order of magnitude worse than those guaranteed by Myerson lemma-based payments. (a) Base: A woman with a tray of food at a cafeteria, Agent 1: McDonald’s fries, Agent 2: Pepsi can. (b) Base: A person walking down a city street, Agent 1: Louis Vuitton handbag, Agent 2: H&M storefront. Figure 9: Relative regret from truthful bidding under the Clarke payment rule for the exact same settings as those in Figure 8. The allocation rule uses k=5k=5 diffusion samples. To estimate the (ex ante) Clarke payments and utilities, we run the allocation rule 55 times and average the results. The relative regret is worse than that under Myerson lemma-based payments, by about an order of magnitude. (a) Relative ex post regret. (b) Absolute ex post regret. Figure 10: Relative and absolute ex post regret of Agent 1, for k=25k=25 and k=50k=50 Monte Carlo samples in the allocation rule, for 5 different prompt configurations in the two-agent setting, and averaged over possible values of the agents in a grid over [0,1]×[0,1][0,1]×[0,1]. Ex Post Regret. We also study the ex post regret experienced by the bidders, i.e. the regret they experience when the allocation rule is run once to select an image, and is run another one time per bidder to estimate their Clarke payments. Figure 11: LAION image quality scores in the 3-agent setting. Scores are shown for different bid configurations for the agents. Scores are averaged across all the prompt configurations we consider in Appendix A. Across five prompt configurations in the two-agent setting, we sweep Agent 1’s true value from 0.0 to 1.0 in steps of 0.1 and Agent 2’s true value from 0.0 to 1.0 in steps of 0.25. For every combination of true values (m1,m2)(m_1,m_2), we fix agent 2’s bid to be truthful and allow agent 1 to bid a range of values. Figure 10(a) shows the relative regret experienced by Agent 1 across the five prompt configurations, averaged across realized bidder types. We report results for k∈25,50k∈\25,50\ Monte Carlo samples in the allocation rule. For k=50k=50, the average relative regret remains below 15% across all prompts, reaching as low as 7% for individual prompts. Figure 10(b) reports the averaged, across realized bidder types, absolute regret, i.e. the difference of Agent 1’s utility when they bid their utility-maximizing bid vs their true value, across five prompts. For k=50k=50, the average truthfulness deviation decreases to as low as 0.14. 4.5 Image Quality Preservation A possible concern from the composition of multiple agent preferences in our allocation rule is that this may result in image quality degradation. To quantitatively evaluate this, we use LAION Aesthetic Score, a metric trained on human aesthetic preferences from web-scale data (Schuhmann et al., 2022). LAION scores, averaged across all prompt configurations we consider in this paper (see Appendix A), were consistently above 5.75, which indicates high image quality, for all settings we considered in terms of number of agents and bid configurations. For n=3n=3 agents, our allocation rule achieves scores ranging from 5.77 to 6.02; see Figure 11. Full LAION image quality scores for up to 20 agents are shown in Appendix D.2. As an alternative, we also evaluate image quality via CLIP alignment, shown in Appendix D.3. 4.6 Competitive Bidding We conducted additional experiments specifically testing our mechanism with semantically similar, directly competing products. We evaluate 20 scenarios where two agents bid for competing brands in the same product category (e.g., Dunkin vs. Starbucks, see Table 2). These scenarios are interesting to test in terms of whether there still exist welfare improvement opportunities. They also represent challenging cases as embedding space distinctions are inherently weaker than our original diverse prompt set. Comprehensive prompts are included in Appendix D.5. Table 2: Example prompt configurations in 2-Agent competitive scenarios Base Prompt Agent 1 Prompt Agent 2 Prompt Someone drinking from a coffee cup in an office meeting Starbucks coffee cup Dunkin coffee cup A person drinking from a beverage can while working at a desk Coca-Cola can Pepsi can Someone wearing athletic shoes while jogging in a park Nike running shoes Adidas running shoes (a) Welfare improvement over baseline (b) LAION image quality scores Figure 12: Competitive 2-agent bidding results. Our allocation rule still achieves welfare gains over the single-winner baseline of up to 3%, though the magnitude is reduced compared to when the prompts are complementary; see Figure 12(a). Average alignment scores between the image chosen by the allocation rule and agents’ prompts are approximately increasing with their bids, demonstrating that the allocation rule is approximately bid monotone; see Figure 13(a). The images consistently achieve LAION scores above 5.75, indicating high image quality no matter the bid combinations; see Figure 12(b). (a) Approximate bid monotonicity. (b) Example bidding scenario with Dunkin and Starbucks (0.5/0.5). Figure 13: Allocation analysis for competitive 2-agent scenario. These competitive bidding results address some of the most challenging real-world advertising scenarios. If advertisers want to avoid being shown next to their competitors, as in Figure 13(b), they can add additional instructions in their prompts that would reduce the welfare of such images, and therefore the propensity that such images are chosen by the allocation rule. 5 Discussion High-Level Takeaway This work makes the argument that using Generative AI we are able to “increase abundance,” i.e. create opportunities to improve welfare. We explore this in the context of banner ad auctions, showing that mechanism design theory can be combined with diffusion model practice to create mechanisms that are approximately truthful and attain higher welfare compared to standard single-winner mechanisms, by allowing advertisers to mix their advertising content in the image selected by the mechanism. Applications The framework we present offers strong potential for real-world applications, particularly in online advertising. Consider a search engine displaying banner ads on web pages: using our mechanism, it can generate visually compelling, contextually relevant images that reflect the preferences of multiple advertisers simultaneously. Our finding, that this generative mechanism yields higher welfare than single-winner mechanisms, provides a compelling incentive for platforms to adopt such methods. Advertisers benefit from having their branding or products meaningfully integrated into the generated content, with visibility and influence aligned with their bids. Beyond static images, our approach extends naturally to dynamic media. For example, a video platform could use our mechanism to embed branded elements, enabling multiple agents to bid for subtle, context-aware product placement. This opens new possibilities for non-intrusive, personalized advertising across multimedia formats. Limitations A challenge for our setting and our approach arises from the fact that we are working with a rich allocation space, namely all natural images, which has no analytical description. Thus, we cannot optimize over it directly and resort to Monte Carlo sampling from a diffusion model to obtain samples in the high-weflare region of the allocation space. The inherent probabilistic nature of denoising diffusion models, coupled with idiosyncrasy in how well text prompts are interpreted by the diffusion model, means that we can only hope to approximately optimize welfare for a given set of bids and prompts. This implies that truthfulness will only be approximate and some welfare will also be left on the table. While increasing the number of samples in the allocation rule is found to improve welfare and reduces sampling variance, improving the incentives, this comes at the cost of increased computational resources and generation time. There is thus a trade-off between economic and computational efficiency. Future work. Our work is a first step at using diffusion models to improve efficiency in mechanism design settings, such as banner ad auctions, that can benefit from expanding the allocation space. There are several exciting directions to pursue next, including studying and controlling the impact of prompt manipulation by the bidders, evaluating the effect of directives in the bidder prompts, such as avoiding certain content or co-existence with competitors, designing more sophisticated bidding languages that go beyond a single prompt and value, exploring revenue-maximizing versions of the mechanism, and adapting this mechanism to other modalities like video. 6 Conclusion Our work presents compelling evidence that diffusion models can be leveraged to increase abundance in mechanism design settings. We show how they can be used to express complex preferences and how they can be combined with mechanism design principles to give mechanisms that improve welfare compared to standard baselines and attain approximate incentive compatibility. We apply our approach to banner ad auctions, where diffusion models are leveraged to select images that aggregate the preferences of bidders according to the strengths of their bids. To this goal, we propose a score composition technique that enables prompt- and bid-dependent control over the content sampled by the diffusion model, in conjunction with payment rules that result in approximate incentive compatibility. Our comprehensive empirical analysis, conducted on a diverse dataset, comprising various prompt and bid combinations and considering up to 20-agent settings, provides compelling evidence for our mechanism’s effectiveness, demonstrating improved social welfare over single-winner baselines and good incentive properties. Our research adds to the growing literature on the interface of Generative AI and Mechanism Design, and lays the groundwork for future investigations of how diffusion models and mechanism design can be combined to improve upon the properties of our mechanism as well as to extend it to other mechanism design objectives and other allocation modalities. References Dhariwal and Nichol (2021) P. Dhariwal and A. Q. Nichol Diffusion models beat gans on image synthesis. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), p. 8780–8794. Cited by: §2.2. Dubey et al. (2024) K. A. Dubey, Z. Feng, R. Kidambi, A. Mehta, and D. Wang Auctions with LLM summaries. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), p. 713–722. Cited by: §1, §2.1. Dütting et al. (2024) P. Dütting, V. Mirrokni, R. Paes Leme, H. Xu, and S. Zuo Mechanism design for large language models. In Proceedings of the ACM Web Conference 2024 (W), p. 144–155. Cited by: §1, §2.1. Esser et al. (2024) P. Esser, S. Kulal, A. Blattmann, R. Entezari, J. Müller, H. Saini, Y. Levi, D. Lorenz, A. Sauer, F. Boesel, D. Podell, T. Dockhorn, Z. English, K. Lacey, A. Goodwin, Y. Marek, and R. Rombach Scaling rectified flow transformers for high-resolution image synthesis. In Proceedings of the 41st International Conference on Machine Learning (ICML), Cited by: §2.2. Feizi et al. (2023) S. Feizi, M. Hajiaghayi, K. Rezaei, and S. Shin Online advertisements with LLMs: opportunities and challenges. External Links: 2311.07601, Link Cited by: §1, §2.1. Hajiaghayi et al. (2024) M. Hajiaghayi, S. Lahaie, K. Rezaei, and S. Shin Ad auctions for LLMs via retrieval augmented generation. In Proceedings of the 38th Annual Conference on Neural Information Processing Systems (NeurIPS), p. 18445–18480. Cited by: §1, §2.1. Ho et al. (2020) J. Ho, A. Jain, and P. Abbeel Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, Vol. 33, p. 6840–6851. Cited by: §2.2. Ho and Salimans (2021) J. Ho and T. Salimans Classifier-free diffusion guidance. In NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications, Cited by: §1, §1, §2.2, §3.1.2. Liu et al. (2023) X. Liu, C. Gong, and Q. Liu Flow straight and fast: learning to generate and transfer data with rectified flow. In Proceedings of the 11th International Conference on Learning Representations (ICLR), Cited by: §2.2. Myerson (1981) R. B. Myerson Optimal auction design. Mathematics of operations research 6 (1), p. 58–73. Cited by: §3.5.1, §4.4.1. Nichol et al. (2022) A. Nichol, P. Dhariwal, A. Ramesh, P. Shyam, P. Mishkin, B. McGrew, I. Sutskever, and M. Chen GLIDE: towards photorealistic image generation and editing with text-guided diffusion models. In Proceedings of the 39th International Conference on Machine Learning (ICML), p. 16784–16804. Cited by: §2.2. Radford et al. (2021) A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever Learning transferable visual models from natural language supervision. In Proceedings of the 38th International Conference on Machine Learning (ICML), p. 8748–8763. Cited by: §4.1. Rombach et al. (2022) R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 10684–10695. Cited by: §2.2. Saharia et al. (2022) C. Saharia, W. Chan, S. Saxena, L. Li, J. Whang, E. L. Denton, K. Ghasemipour, R. Gontijo Lopes, B. Karagol Ayan, T. Salimans, J. Ho, D. J. Fleet, and M. Norouzi Photorealistic text-to-image diffusion models with deep language understanding. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS), p. 36479–36494. Cited by: §2.2. Schuhmann et al. (2022) C. Schuhmann, R. Beaumont, R. Vencu, C. Gordon, R. Wightman, M. Cherti, T. Coombes, A. Katta, C. Mullis, M. Wortsman, P. Schramowski, S. Kundurthy, K. Crowson, L. Schmidt, R. Kaczmarczyk, and J. Jitsev LAION-5b: an open large-scale dataset for training next generation image-text models. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS), p. 25278–25294. Cited by: §4.5. Sohl-Dickstein et al. (2015) J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning (ICML), p. 2256–2265. Cited by: §2.2. Song and Ermon (2019) Y. Song and S. Ermon Generative modeling by estimating gradients of the data distribution. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), Cited by: §2.2. Song et al. (2021) Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole Score-based generative modeling through stochastic differential equations. In Proceedings of the 9th International Conference on Learning Representations (ICLR), Cited by: §2.2. Appendix A Prompts We prompted Claude to systematically generate base scenes spanning diverse everyday settings, each paired with real-world brand prompts drawn from different product categories (food/beverage, tech, fashion, automotive, energy). Table 3: Example prompt configurations across 2020 three-agent scenarios Base Prompt Agent 1 Prompt Agent 2 Prompt Agent 3 Prompt Two friends chatting over coffee at a cafe Starbucks mug Apple MacBook Air New York Times newspaper People enjoying a sunny day at the beach Wilson volleyball Red Bull cooler Banana Boat sunscreen A person relaxing on a living-room sofa Lay’s potato chips M&M’s candy Netflix show on TV A hiker resting on a mountain trail North Face backpack Gatorade bottle Garmin watch A professional working at a desk in a bright office Dell monitor Deer Park water bottle Moleskine notebook A woman with a tray of food at a cafeteria McDonald’s fries Pepsi can Heinz ketchup packet A person walking down a city street Louis Vuitton handbag H&M storefront Nike sneakers Friends gathered for a movie night at home Doritos chips Coca-Cola cans Amazon Fire TV remote A car driving along a scenic coastal highway Tesla car ExxonMobil sign Goodyear tires Skiers waiting in a ski-lift line Patagonia jacket GoPro camera Beats wireless headphones A man waiting at a bus stop Adidas backpack Samsung Galaxy phone Sony headphones A student studying in a university library MacBook Pro laptop Red Bull energy drink Coca-Cola can A chef cooking in a restaurant kitchen KitchenAid stand mixer Coca-Cola glass bottle Heinz ketchup bottle A couple shopping at a farmers market Whole Foods tote bag iPhone camera Patagonia fleece jacket A teenager gaming in their bedroom PlayStation 5 controller Monster Energy drink Razer gaming headset A businesswoman in an airport lounge Louis Vuitton luggage Starbucks coffee cup iPad Pro tablet A mechanic working in an auto garage Ford truck DeWalt power drill Mobil 1 motor oil A barista working in a trendy coffee shop Starbucks coffee machine Spotify playlist screen Levi’s denim apron A fitness trainer at a modern gym Under Armour workout shirt Beats wireless headphones Hydroflask water bottle A doctor in a hospital break room MacBook Air laptop Starbucks coffee cup Samsung tablet Table 4: Number of Prompts per Agent Configuration Number of Agents Number of Prompts 2 200 3 133 5 85 10 44 20 25 Appendix B Generalized Score Composition The score composition can be extended to n agents (st(1:n)(x)s^(1:n)_t(x)) by recursively defining it in terms of score compositions for n−1n-1 agents, n−2n-2 agents, etc. Assume, without loss of generality, that agents 11 to n submit bids in decreasing value: b1≥b2≥…≥bnb_1≥ b_2≥…≥ b_n. Denote bj(0)=bjb_j^(0)=b_j. For recursive step i, take bj(i)=bj(i−1)∑k=1n−i+1bk(i−1)b_j^(i)= b_j^(i-1) _k=1^n-i+1b_k^(i-1) to be the normalized bids and w(i)=(n−i+1n−i∑j=1n−ibj(i)−1)w^(i)= (n-i+1 n-i _j=1^n-ib_j^(i)-1 ) to be the normalized weights. Denote by c1:i=c1,c2,…,cic_1:i=\c_1,c_2,…,c_i\ the concatenated prompt of agents 11 through i, and take st(1:1)(x):=s(x|c,c1)s^(1:1)_t(x):=s(x|c,c_1) to be the conditional score conditioning on the dominant agent’s prompt (and the base prompt if any). We then define the composite score st(1:n)(x)s^(1:n)_t(x) of all n agents by separating out the least dominant agent, n, and computing the score function for the remaining n−1n-1 agents recursively as follows: st(1:n)(x)=(1−w(1))s(x|c,c1:n)+w(1)st(1:n−1)(x)s^(1:n)_t(x)=(1-w^(1))\,s(x|c,c_1:n)+w^(1)\,s^(1:n-1)_t(x) (10) st(1:i)(x)=(1−w(n−i+1))s(x|c,c1:i)+w(n−i+1)st(1:i−1)(x)s^(1:i)_t(x)=(1-w^(n-i+1))\,s(x|c,c_1:i)+w^(n-i+1)\,s^(1:i-1)_t(x) (11) We can also derive a closed-form expression for st(1:n)(x)s^(1:n)_t(x). st(1:n)(x)=∏i=1n−1w(i)s(x|c,c1)+∑i=2n[(∏j=1n−iw(j))(1−w(n−i+1))s(x|c,c1:i)]s^(1:n)_t(x)= _i=1^n-1w^(i)\,s(x|c,c_1)+ _i=2^n [ ( _j=1^n-iw^(j) )(1-w^(n-i+1))\,s(x|c,c_1:i) ] (12) Appendix C Linear Aggregation We had first considered the linear aggregation function. st(1,2)(x)=(1−w(1))st(x|c,c1)+(w(1))st(x|c,c2)s^(1,2)_t(x)=(1-w^(1))s_t(x|c,c_1)+(w^(1))s_t(x|c,c_2) (13) However, we observed that it did not yield compositional images. Instead, the objects were faded on top of one another, leading to visually incoherent outcomes (Figure 14). Figure 14: Linear aggregation function without the joint score fails to produce compositional images. Appendix D Comprehensive Empirical Evaluation D.1 Welfare Improvement (a) 2 agents, 200 prompts (b) 3 agents, 133 prompts (c) 5 agents, 85 prompts (d) 10 agents, 44 prompts (e) 20 agents, 25 prompts Figure 15: Welfare improvement over single-winner baseline from 2 to 20 agents with varying bid combinations, exhibiting up to 23% increase in the 5 agent setting. D.2 LAION Image Quality (a) 2 agents (b) 3 agents (c) 5 agents (d) 10 agents (e) 20 agents Figure 16: LAION aesthetic quality scores for varying numbers of agents. Scores are shown for different bid configurations for the agents. Scores are computed across all the prompt configurations we consider in Appendix A. Scores consistently remain above 5.75 across, indicating high image quality is preserved regardless of the number of agents or bid configurations. D.3 Image Quality using CLIP Alignment Table 5: Image quality in the 2 agent setting according to CLIP alignment score. Computed across prompt configurations in Appendix A and various bid combinations. Agent 1 Agent 2 Mean SD 0.0 1.0 0.5081 0.0028 0.1 0.9 0.5084 0.0030 0.3 0.7 0.5083 0.0031 0.5 0.5 0.5082 0.0030 0.7 0.3 0.5085 0.0028 0.9 0.1 0.5090 0.0027 1.0 0.0 0.5089 0.0028 Table 6: Image quality in the 3 agent setting according to CLIP alignment score. Computed across prompt configurations in Appendix A and various bid combinations. Agent 1 Agent 2 Agent 3 Mean SD 0.33 0.33 0.33 0.5084 0.0029 0.40 0.40 0.20 0.5083 0.0030 0.60 0.30 0.10 0.5082 0.0029 0.60 0.20 0.20 0.5086 0.0029 1.00 0.00 0.00 0.5088 0.0027 D.4 Monte Carlo Samples Ablation (a) 2 agents (b) 3 agents (c) 5 agents (d) 10 agents (e) 20 agents Figure 17: Welfare improvement over the single-winner baseline as a function of the number k of Monte Carlo samples in the allocation rule. For 2, 3, 5, 10 agents, welfare improvement plateaus around k=5k=5 samples, where it reaches at least 90% of the welfare improvement attained with k=20k=20. For 20 agents, there is room for improvement beyond k=5k=5, but k=15k=15 attains at least 95% of the welfare improvement at k=20k=20. D.5 Competitive Bidding Table 7: Prompt configurations across 2020 two-agent competitive scenarios Base Prompt Agent 1 Prompt Agent 2 Prompt A person drinking from a beverage can while working at a desk Coca-Cola can Pepsi can Someone wearing athletic shoes while jogging in a park Nike running shoes Adidas running shoes A person wearing a smartwatch while exercising at the gym Apple Watch Samsung Galaxy Watch Someone drinking from a water bottle during a yoga class Hydro Flask water bottle Yeti water bottle A driver filling up their car at a gas station Shell gas station Chevron gas station A customer holding a shopping bag from a clothing store Zara shopping bag H&M shopping bag A person wearing wireless earbuds while commuting Apple AirPods Samsung Galaxy Buds Someone drinking an energy drink at a skateboard park Red Bull can Monster Energy can A person carrying a backpack while hiking on a trail North Face backpack Patagonia backpack Someone using a smartphone at a coffee shop iPhone smartphone Samsung Galaxy phone A person wearing a baseball cap at a sports game New York Yankees cap Boston Red Sox cap Someone drinking from a coffee cup in an office meeting Starbucks coffee cup Dunkin coffee cup A customer carrying a fast food bag on a city street McDonald’s bag Burger King bag A person wearing running shorts during a marathon Nike running shorts Adidas running shorts Someone eating chips while watching TV at home Lay’s chips bag Doritos bag A person wearing a winter jacket in a snowy setting Canada Goose jacket North Face jacket Someone drinking orange juice at breakfast Tropicana orange juice Minute Maid orange juice A person wearing a fitness tracker at a cycling class Fitbit tracker Garmin tracker Someone holding a pizza box at a house party Domino’s pizza box Pizza Hut box A person wearing a hoodie at a college campus Champion hoodie Nike hoodie Appendix E Bid Combination Values Table 8: Bid Combinations for 2 Bidders Combination Name Bid Values Equal Split 0.50 (0.50,0.50)(0.50,0.50) Dominant 0.70 (0.30,0.70)(0.30,0.70) Dominant 0.90 (0.10,0.90)(0.10,0.90) Table 9: Bid Combinations for 3 Bidders Combination Name Bid Values Equal Split 0.33 (0.33,0.33,0.33)(0.33,0.33,0.33) Two Dominant 0.40 (0.40,0.40,0.20)(0.40,0.40,0.20) Two Dominant 0.50 (0.50,0.50,0.00)(0.50,0.50,0.00) Dominant 0.50 (0.50,0.30,0.20)(0.50,0.30,0.20) Dominant 0.60 (0.60,0.30,0.10)(0.60,0.30,0.10) Dominant 0.60 (0.60,0.20,0.20)(0.60,0.20,0.20) Table 10: Bid Combinations for 5 Bidders Combination Name Bid Values Equal Split 0.20 (0.20,0.20,0.20,0.20,0.20)(0.20,0.20,0.20,0.20,0.20) Three Dominant 0.25 (0.25,0.25,0.25,0.15,0.10)(0.25,0.25,0.25,0.15,0.10) Two Dominant 0.30 (0.30,0.30,0.20,0.10,0.10)(0.30,0.30,0.20,0.10,0.10) Dominant 0.40 (0.40,0.30,0.20,0.05,0.05)(0.40,0.30,0.20,0.05,0.05) Dominant 0.50 (0.50,0.25,0.15,0.07,0.03)(0.50,0.25,0.15,0.07,0.03) Dominant 0.60 (0.60,0.20,0.10,0.05,0.05)(0.60,0.20,0.10,0.05,0.05) Table 11: Bid Combinations for 10 Bidders Combination Name Bid Values Equal Split 0.10 (0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10)(0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10) Three Dominant 0.20 (0.20,0.20,0.20,0.15,0.10,0.05,0.05,0.03,0.01,0.01)(0.20,0.20,0.20,0.15,0.10,0.05,0.05,0.03,0.01,0.01) Dominant 0.25 (0.25,0.20,0.15,0.12,0.10,0.08,0.05,0.03,0.01,0.01)(0.25,0.20,0.15,0.12,0.10,0.08,0.05,0.03,0.01,0.01) Dominant 0.30 (0.30,0.20,0.15,0.12,0.10,0.07,0.04,0.01,0.00,0.01)(0.30,0.20,0.15,0.12,0.10,0.07,0.04,0.01,0.00,0.01) Dominant 0.35 (0.35,0.15,0.12,0.10,0.08,0.07,0.05,0.04,0.02,0.02)(0.35,0.15,0.12,0.10,0.08,0.07,0.05,0.04,0.02,0.02) Table 12: Bid Combinations for 20 Bidders Combination Name Bid Values Equal Split 0.05 (0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05CLOSE,(0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05, OPEN0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05)0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05) Four Dominant 0.10 (0.10,0.10,0.10,0.10,0.08,0.08,0.08,0.07,0.07,0.07CLOSE,(0.10,0.10,0.10,0.10,0.08,0.08,0.08,0.07,0.07,0.07, OPEN0.05,0.05,0.05,0.02,0.02,0.02,0.01,0.01,0.01,0.01)0.05,0.05,0.05,0.02,0.02,0.02,0.01,0.01,0.01,0.01) Dominant 0.15 (0.15,0.12,0.10,0.08,0.07,0.06,0.05,0.05,0.04,0.04CLOSE,(0.15,0.12,0.10,0.08,0.07,0.06,0.05,0.05,0.04,0.04, OPEN0.03,0.03,0.02,0.02,0.02,0.01,0.01,0.01,0.01,0.01)0.03,0.03,0.02,0.02,0.02,0.01,0.01,0.01,0.01,0.01) Dominant 0.20 (0.20,0.12,0.10,0.08,0.07,0.06,0.05,0.04,0.03,0.03CLOSE,(0.20,0.12,0.10,0.08,0.07,0.06,0.05,0.04,0.03,0.03, OPEN0.03,0.02,0.02,0.02,0.01,0.01,0.01,0.01,0.01,0.01)0.03,0.02,0.02,0.02,0.01,0.01,0.01,0.01,0.01,0.01)