Optimally Curating an Event

1 Introduction

Mechanism design, especially auction design, has been one of the most foundational frameworks in recent decades, with numerous applications to online advertisements, spectrum auctions, and crowdsourcing platforms, to name a few-highlighted by the Nobel Prize in Economics in 2007 awarded to Myerson, Hurwicz, and Maskin for their foundation of mechanism design. In particular, two-sided mechanisms, also known as double auctions, serve as a primary tool to transfer goods between agents to maximize social efficiency. Most of the literature, however, has largely centered on two canonical objectives: maximizing revenue for the broker who governs the trade [Myerson and Satterthwaite, 1983; Kuang et al., 2023], or maximizing social welfare [Deng et al., 2022], typically defined as a function of agents' private valuations and payments. On the other hand, many modern platforms may realize arbitrary utilities depending on who is involved in the trades, independent of the agents' private valuations or transfers between them. Nevertheless, there have been only a few works studying such general objective functions, mostly in procurement auction frameworks-e.g., budget-feasible mechanism design [Singer, 2010; Anari et al., 2014; Balkanski and Hartline, 2016] or all-pay auctions for crowdsourcing contests [Chawla et al., 2019; DiPalantino and Vojnovic, 2009].

We discuss two representative examples to motivate our problem.

Example 1: Conference curation. As an illustrative example, consider the challenge faced by the organizer of a prestigious event, such as an academic conference. The success of the event depends on how many attendees it attracts, or alternatively, how much welfare it provides to attendees. On one hand, the organizer seeks to attract renowned keynote speakers, popular artists, or flagship exhibitors. These participants generate significant positive value and draw more attendees, but they often require invitation fees, travel stipends, or other costs to secure their involvement. On the other hand, the organizer must fund these costs by securing corporate sponsorships or inviting advertisers. These participants provide essential revenue but may detract from the overall experience if their presence becomes overwhelming or overly commercial. The organizer's ultimate goal is to curate the optimal mix of these agents to maximize the attendees' utilities, ensuring that the organizer does not run a deficit by implementing the event.

Example 2: Double auction for LLMs. As another example, consider an LLM provider, such as Google with its Gemini model, which aims to deliver the most helpful and accurate responses to users. On one hand, to enhance the quality of its service, the provider can procure access to high-quality, up-to-date information from various plus agents such as news publishers, academic journals, or specialized data providers. Integrating these documents into a retrieval-augmented generation (RAG) framework allows the LLM to reduce hallucinations and provide more relevant answers, creating significant positive utility for the user. However, these content providers are strategic agents with private costs, and the LLM provider must design a mechanism to pay them for the right to use their data. On the other hand, the provider can fund these content acquisition costs by selling space within the LLM's output to minus agents, i.e., advertisers. 1 These advertisers have private valuations for reaching the user and provide the necessary revenue, but their inclusion may detract from the user experience and the perceived objectivity of the answer. The LLM provider's challenge is to design a joint mechanism, balancing a procurement system for documents with an ad auction, to curate the optimal blend of retrieved knowledge and advertisements, thereby maximizing user satisfaction in a budget-balanced, self-financing ecosystem.

1 There has been increasing attention to integrating ads into LLM outputs, e.g., see [Duetting et al., 2024; Dubey et al., 2024; Hajiaghayi et al., 2024; Balseiro et al., 2025].

Our model. To formally capture this complex trade-off, we introduce a novel two-sided mechanism design problem for the optimal curation of agents with exogenous utilities, providing the first general framework for two-sided mechanisms where the designer's objective is neither revenue nor social welfare, but originates from an exogenous (possibly combinatorial) utility function.

Our model consists of two types of agents: plus agents, who contribute positively to the event's value but incur a private cost to participate, and minus agents, who have a private valuation for joining and are willing to pay, but may impose a negative externality on the event. The mechanism designer aims to maximize an exogenous utility function that maps an allocation to a nonnegative real value, which is monotone increasing in plus agents and monotone decreasing in minus agents, while satisfying (i) dominant-strategy incentive compatibility (DSIC) or Bayesian incentive compatibility (BIC), i.e., agents report their true values; (ii) individual rationality (IR), i.e., agents are not worse off by participating in the trade; and (iii) budget balance, i.e., the mechanism does not run a deficit. We consider an additive utility function that can be represented as a simple sum of individual contributions, as well as a more complex combinatorial function capturing synergistic or substitution effects between agents. We analyze this curation problem primarily in the Bayesian setting, where the designer has statistical knowledge of agent types.

To highlight our main results:

1. For the case of additive utilities in the Bayesian setting, we provide a complete characterization of the optimal DSIC and IR mechanism under ex-ante BB constraint, and the optimal BIC and IR mechanism under ex-post BB constraint, both of which are efficiently computable.
2. For separable submodular utility, we provide a posted pricing mechanism under regular distributions with polynomial running time that is a constant-factor approximation to the optimal Bayesian mechanism.

In what follows, we overview our main results and techniques. Then, we introduce the formal problem setup, results, and their implications. Additional results, including irregulardistribution analysis, a simpler submodular mechanism, comparative statics, and prior-free analysis for additive utility under a large-market assumption, are deferred to the extended version.

1.1 Our Results and Techniques

We briefly introduce our main results and the techniques used to obtain them. We begin with the additive utility setting in Section 4, where each plus agent imposes a fixed positive surplus pi ≥ 0 upon selection, and each minus agent induces a fixed negative impact nj ≤ 0 upon inclusion. 2 In this case, we provide a complete characterization of the optimal mechanism that maximizes the expected utility while remaining ex-ante BB, DSIC, and IR. We extend the classic Myersonian framework by characterizing the payment rule and deriving the two-sided monotonicity of the allocation rule for any DSIC mechanism. This allows us to rewrite the budgetbalancedness constraint as a function of the virtual costs and valuations of plus and minus agents, respectively. Then, we write the Lagrangian of the designer's resulting optimization problem. Finally, using the Karush-Kuhn-Tucker (KKT) conditions of the Lagrangian, we show that we can find the closed-form solution for the optimal Bayesian mechanism by determining the optimal Lagrange multiplier of the budget constraint-known as the shadow price-and deriving the resulting allocation function. Then, by applying the interim transformation technique by [Brustle et al., 2017], we show that our mechanism extends to the optimal BIC mechanism under ex-post BB constraint. Further discussions on the case of irregular distributions and ex-post BB DSIC mechanism are provided in the extended version.

Second, we move beyond the additive utility to the submodular utility case and consider a utility function that is separable into the plus and minus agent sides. Namely, including a plus agent and excluding a minus agent both increase the utility in a concave manner. 3 We first argue that the decision version of the offline problem setup (assuming truthful bids) is already NP-hard to approximate within some constant factor, via a reduction from the submodular maximization problem with knapsack constraints. Accordingly, we provide a simple posted pricing mechanism under regular distributions that can be efficiently computed and achieves a constant-factor approximation to the optimal mechanism. Overall, our mechanism first generates a set of candidate budgets that can be used for plus agents. Then, we solve the plus and minus agent sides separately to exploit and procure the targeted budget-iteratively for each budget candidate-via the multilinear extension of the original optimization problems. Such multilinear extensions are guaranteed to approximate the optimal performance within a constant factor, thanks to the bounded correlation gap of submodular set functions shown by [Agrawal et al., 2010]. Finally, we select the optimal budget that maximizes the expected utility among the candidates. Equipped with the fact that the expected utility under the multilinear extension is concave in the budget, we show that the error from using discretized budget candidates can be made small, implying that the resulting maximal mechanism is a good approximation to the optimal one.

2 RelatedWork

Budget-feasible mechanism design. Our problem, in particular the plus agents' side market, has a close connection to the seminal budget-feasible mechanism design introduced by [Singer, 2010], where a buyer needs to procure a set of items from sellers given an exogenous budget constraint and a set function. [Singer, 2010] show that the standard VCG framework does not work, and provide several constant-factor approximate prior-free mechanisms for submodular utility. [Balkanski and Hartline, 2016] consider a Bayesian mechanism, where the benchmark is the optimal Bayesian mechanism rather than the offline benchmark. [Anari et al., 2014] consider a budget-feasible mechanism with applications to the crowdsourcing market, justifying a large market assumption to derive stronger approximation guarantees. Since then, there have been numerous works [Balkanski et al., 2022; Jalaly and Tardos, 2021; Han et al., 2023; Klumper and Sch¨afer, 2022] improving the approximation factors and generalizing the objective function.

2 We refer to Section 3 for the detailed problem setup.

3 In LLM auctions, one ad causes little distraction, but many ads collectively harm quality, motivating our supermodular negativeimpact assumption. Since only a few ads are shown to preserve user experience, marginal degradation becomes significant.

Two-sided market. Plus and minus agents in our problem can be viewed as buyers and sellers in a two-sided market [McAfee, 1992; Myerson and Satterthwaite, 1983]. While seminal works in the literature [Myerson and Satterthwaite, 1983] focus on deriving optimal mechanisms for restricted cases or prove impossibility results, a recent work [Deng et al., 2022] first proved that the gains-from-trade, a measure of social efficiency, can be approximated within a constant factor of the first-best outcome. Since then, there have been many works analyzing approximation factors or weakening the assumptions [Blumrosen and Dobzinski, 2014; Blumrosen and Dobzinski, 2021; Deng et al., 2025]. Notably, similar to our problem where the mechanism designer aims to maximize a self-interested utility function, there has been a line of works studying the mechanism of the broker-who governs the trade-to maximize the broker's own profit [Kuang et al., 2023; Eilat and Pauzner, 2021; Hajiaghayi et al., 2025]. In stark contrast, in our setting, the designer has an exogenous utility function that can depend (possibly combinatorially) on the allocation function.

3 Model

There are n plus-agents (e.g., keynote speakers) and m minus-agents (e.g., advertisers), denoted by N = {1, . . . , n} and M = {n + 1, . . . , n + m}, respectively. We consider a Bayesian setting where each plus agent i has a private cost ci sampled from a distribution Gi supported on [cmin, cmax] which represents how much it wants to be paid to participate in the event. Analogously, each minus agent j has a private valuation vj sampled from a distribution Fj supported on [vmin, vmax], denoting the willingness-to-pay to join the event. Let F and G be the product distributions of Fj's and Gi's. We will use boldface to denote vectors, e.g., c and v for vectors of costs and values, respectively.

We consider a direct mechanism (x, t) that maps the reported bids (˜c, ˜v) from the agents to an allocation vector x = (x1, . . . , xn+m) ∈ {0, 1}n+m denoting whether each agent is selected to join the event and a payment vector t = (t1, . . . , tn+m) ∈ Rn+m ≥0 representing how much money each agent should pay or will be paid. 4 In particular, we will assume that ti ≥ 0 will be paid to plus agent i and tj ≥ 0 will be charged to minus agent j.

4 One can easily check that it is without loss of generality to consider direct mechanisms by the revelation principle.

Given a direct mechanism (x, t), we write b = (b1, . . . , bn+m) to denote the reported bids of the agents and b-i to represent the vector of reports from all agents except agent i. Accordingly, we write ti(b) = ti(bi, b-i) and xi(b) = xi(bi, b-i) to denote the payment and allocation specific to agent i reporting bi given others' bids b-i.

Utilities. Given an allocation vector x ∈ {0, 1}n+m, the utility of the mechanism designer is defined by a set function u : {0, 1}n+m → R≥0. In particular, u(·) is monotone increasing over plus agents in a sense that for two allocation vectors x and y such that xi ≤ yi for i ∈ N and xj = yj for j ∈ M, we have u(x) ≤ u(y), i.e., allocating more plus agents does not decrease the utility. Similarly, u(·) is monotone decreasing over minus agents in a sense that for two allocation vectors x and y such that xj ≤ yj for j ∈ M and xi = yi for i ∈ N, we have u(x) ≥ u(y), i.e., allocating more minus agents does not increase the utility. In words, plus agents increase the utility but it requires cost to hire them, whereas minus agents decrease the utility but one can extract revenue from them. We write 1n to denote (1, 1, . . . , 1) ∈ Rn , and similarly 0n to denote (0, 0, . . . , 0) ∈ Rn . We assume that the utility function is always nonnegative, or equivalently u(0n, 1m) ≥ 0. We often abuse notation and write a set as the input, e.g., u(N) or u(M), to denote the utility value given corresponding allocation vector.

A set function f : 2S ↦→ R≥0 with finite set S is submodular if f(X ∪ {x}) - f(X) ≥ f(Y ∪ {x}) - f(Y ) for any X ⊆ Y ⊆ S and x ∈ S \ Y , and supermodular if the inverse of the inequality holds. We say f is monotone if f(X) ≤ f(Y ) whenever X ⊆ Y . Note that these notations naturally extend to our utility function u(·).

Desiderata. Our objective is to design a mechanism that maximizes the utility while respecting several desirable properties. First, given others' bids b-i, plus agent i's payoff from reporting ˜ ci when its true cost is ci is:

Similarly, for fixed b-j , minus agent j's utility from reporting ˜ vj when its true value is vj is:

We say a mechanism is dominant strategy incentivecompatible (DSIC) if deviating from truthful reports does not increase the agents' payoffs. Formally, for any plus agent i, any true cost ci, any lie c′i , and any reports b-i:

and for any minus agent j, any true value vj, any lie v′j , and any reports b-j:

Further, we aim to design an individually rational mechanism such that no agent gets a negative payoff from participating in the mechanism. Formally, for plus agent i with cost ci and minus agent j with value vj, the following must hold, respectively:

Our mechanism designer should not run a deficit by running the mechanism, i.e., it should be ex-ante (weakly) budget-balanced (BB):

We often consider ex-post budget-balancedness (ex-post BB) where the budget constraint holds for every realization of valuations:

We finally introduce virtual valuations and costs. Let fj and gi be the density functions of Fj and Gi, respectively.

Definition 1 (Virtual valuation and cost). The virtual cost of plus agent i is defined as:

The virtual valuation of minus agent j is defined as:

We say the agents' distributions are regular if ψi(ci) and ϕj(vj) are monotone increasing for every i and j. Unless specified otherwise, we will restrict our focus to the regular distributions.

4 Optimal Mechanism for Additive Utility

We first consider a simple setting where the utility function is additive over each agent. Formally, the utility function is additive if it can be written as

where pi ≥ 0 and nj ≤ 0. 5 That is, each plus agent i induces a fixed positive impact pi upon its selection whereas each minus agent j incurs a negative effect of nj upon inclusion in the event. Note that it is without loss of generality to consider the domain of the allocation vector to be [0, 1]n+m, due to the linearity of expectation given that the utility function is additive.

4.1 Optimal Ex-ante BB DSICMechanism

The following generalizes Myerson's lemma:

5 This is for the sake of exposition, while our results easily generalize without such restrictions.

Lemma 2. For any DSIC mechanism, the allocation rule x is monotone decreasing in plus agent i's cost, and monotone increasing in minus agent j's value. Further, given others' bids b-i and b-j , the payment rule for plus agent i and minus agent j can uniquely be characterized by:

The next crucial step is to analyze the expected payment from each agent from the designer's perspective. This allows us to replace payments with virtual costs and valuations. Under the standard assumption that the integration constants Ui,0 and Uj,0 are zero, we have the following.

Lemma 3. The expected expenditure to plus agent i and expected revenue from minus agent j can be written as:

We can now combine the characterization of implementable mechanisms with the concept of virtual valuations and costs to solve the designer's problem. The following theorem describes the optimal mechanism.

Theorem 4. Under regular distributions, the mechanism described in Algorithm 1 is DSIC, IR, ex-ante BB, and maximizes the utility.

The proof proceeds by first expressing the budgetbalancedness constraint in terms of virtual valuations and costs. Then, we write the Lagrangian of the designer's optimization problem, which is solely a function of allocation probabilities, pi's and nj's, and virtual valuations and costs. Then, we can regroup the terms by agent type, along with the corresponding allocation probability. The KKT stationarity condition gives us the allocation rule described in the algorithm. Further, the complementary slackness guarantees that the budget constraint must bind or the Lagrange multiplier should be zero, resulting in our choice of shadow price λ∗ .

4.2 Optimal Ex-post BB BICMechanism

In this section we formalize the (now standard) payment transformation that converts any DSIC & ex-ante BB mechanism into a BIC & ex-post BB (indeed, SBB) mechanism without changing the allocation rule. We then use it to argue that the DSIC & ex-ante BB optimal mechanism from Theorem 4 yields an optimal BIC & ex-post BB mechanism after the transformation.

Recall that ex-ante BB requires

Algorithm 1 Optimal Mechanism for Additive Utility

Input: Reported bids c and v

• 1: Find the smallest shadow price λ∗ ≥ 0 such that the exante budget balance constraint is met:

• 2: Define the final allocation rule x∗ = x(λ∗ ) based on the found shadow price:
• 3: x∗i ← I[pi -λ∗ψi(ci) ≥ 0] for all i ∈ N.
• 4: x∗j ← I[nj +λ∗ϕj(vj) ≥ 0] for all j ∈M.
• 5: Compute the final payments t∗ = t(λ∗ ) based on the allocation rule x∗ using (4.1) and (4.2).
• 6: return (x∗ , t∗ )

Ex-post BB requires the above to hold pointwise for every realized profile; strong budget balance (SBB) requires equality ex post:∑

Interim Transformation. We state the transformation theorem first. It preserves the allocation rule and any objective that depends only on x.

Lemma 5 (Payment transformation by [Brustle et al., 2017]). Let (x, t) be a mechanism that is BIC, interim IR, and ex-ante BB with a nonnegative payment rule (i.e., ti(·) ≥ 0 for i ∈ N and tj(·) ≥ 0 for j ∈ M). Then there exists another payment rule t′ such that:

1. Allocation preserved: (x, t′ ) uses the same allocation rule x.
2. BIC & interim IR preserved: (x, t′ ) remains BIC and interim IR, and each agent's interim expected payment is unchanged.
3. Ex-post SBB: For every profile (v, c),

Moreover, the converse holds: any BIC, interim IR, SBB mechanism with nonnegative payments can be converted to a BIC, interim IR, ex-ante BB mechanism with the same allocation by an inverse linear transformation of payments.

Remark 6 (On "same allocation"). Lemma 5 preserves the ex-post allocation rule x(·) profile-by-profile; in particular, interim allocation probabilities remain identical. Since all of our objectives in this paper depend only on the allocation (transfers do not enter the objective), the designer's value is unchanged by the transformation.

Optimality. We now show that the DSIC & ex-ante BB optimum characterized in Section 4 yields an optimal BIC & ex-post BB mechanism after the transformation in Lemma 5.

Theorem7 (Optimal BIC& ex-post BB). In the additive setting under regular distributions, let (x∗ , t∗ ) be the DSIC, IR, ex-ante BB mechanism from Theorem 4. Then there exists a payment rule ̂t such that (x∗ ,̂t) is BIC, IR, and ex-post BB (indeed SBB), achieves the same expected utility as (x∗ , t∗ ), and is optimal among all BIC, IR, ex-post BB mechanisms.

Corollary 8 (Equality of optimal values). In the additive setting with regular distributions,

where x∗ is the allocation from Theorem 4.

5 Beyond Additive Utility

When the utility function u(·) is not additive but combinatorial, e.g., submodular, the previous framework does not work. In particular, even the offline optimization problem, assuming truthful bids, is well-known to be NP-hard to solve for many classes of functions. Thus, we aim to derive a mechanism that approximates the optimal mechanism.

Let S be the set of selected agents given an allocation vector x. Accordingly, we consider the following class of separable functions

where Sp and Sm are the sets of selected plus and minus agents, respectively. Further, we assume vp is monotone increasing submodular and vm is monotone decreasing supermodular. This is practical since the marginal decrease in the audience experience can grow significantly as we assign more advertisements, even though a few of them might be fine. From theoretical perspectives, this is reasonable since if we alternatively assume vm is submodular, then the resulting function is the sum of a submodular vp and a supermodular -vm, which admits no polynomial approximation algorithm. 6

Note that maximizing u is equivalent to maximizing

In particular, we can write um(Sm) = vm(M) - vm(Sm) as a monotone increasing submodular function defined on the set of excluded minus agents Sm. Thus, redefining Sm as the set of excluded minus agents for notational convenience, we will consider the utility function u(S) = up(Sp) + um(Sm) for monotone increasing nonnegative submodular functions up and um where Sp denotes the set of selected plus agents, and Sm the set of excluded minus agents.

5.1 Budget-enumeration Posted Pricing

We first introduce our main mechanism, the budgetenumeration posted pricing (BEPP) mechanism, presented in Algorithm 2. It takes a discretization parameter ε > 0 which controls the approximation factor as well as its time complexity. The following theorem formalizes the performance of the BEPP mechanism.

6 In general, maximizing a monotone supermodular function always requires an exponential number of queries.

Algorithm 2 BEPP Mechanism

Input: Parameter ε > 0

• 1: Compute Bmax, the maximum expected revenue extractable from the minus agents via Myerson's optimal auction.
• 2: Find minimal M such that (1+ ε)M > Bmax.
• 3: Define B ← {0} ∪ {(1+ ε)i : 0 ≤ i ≤M -1}.
• 4: for each budget target Bk ∈ B do
• 5: Find q(Bk) frommultilinear version of (5.1).
• 6: Find r(Bk) frommultilinear version of (5.2).
• 7: W ml (Bk) ← up(q(Bk)) +um(r(Bk)).
• 8: end for
• 9: Find the best budget B∗ ← argmaxBk∈BW ml (Bk).
• 10: Set tpi ← G-1 i (qi(B∗ )) for each i ∈ N and tmj ← F -1 j (rj(B∗ )) for each j ∈M.
• 11: return posted prices (tp , tm): pay tpi to plus agent i upon acceptance, and charge tmj from minus agent j upon acceptance.

Theorem 9. For any ε > 0, the BEPP mechanism is DSIC, IR, and ex-ante BB, runs in poly(n,m, 1/ε, logBmax) time, and achieves a (1 - 1/e - O(ε))-approximation to the optimal Bayesian mechanism for separable submodular utility and regular distributions.

Proof overview. We now provide the overall proof steps to show that the BEPP mechanism is a constant-factor approximation of the optimal Bayesian mechanism for separable submodular utilities. The proof proceeds by defining a series of relaxations for the plus-agent and minus-agent subproblems, establishing an upper bound on the optimal welfare, and then showing that the expected welfare of our posted-price mechanism is within a constant factor of this bound.

We first formally define the two key relaxations of a set function, following the approaches used by [Balkanski and Hartline, 2016]. Let u : 2O → R≥0 be a set function on a ground set O. Let p = (pk)k∈O be a vector of marginal probabilities. We now define the multilinear extension of u.

Definition 10 (Multilinear Extension). The multilinear extension of u, denoted U(p), is the expected value of the function when each element k ∈ O is included in a set S independently with probability pk.

The key feature in analyzing approximation factors derived frommultilinear extension is its relation to the following concave relaxation of u.

Definition 11 (Concave Closure). The concave closure of u, denoted U +(p), is the maximum expected value of the function over any correlated distribution D on subsets of O with marginal probabilities p.

Importantly, note here that the probability vectors can be correlated unlike the multilinear extension. The connection between these two relaxations is the following notion of correlation gap.

Theorem 12 ([Agrawal et al., 2010]). For any non-negative, monotone submodular function u(·), its multilinear extension and concave closure satisfy:

We structure the proof as a series of lemmas. First, we write concave closures of our original optimization problems for each side market. Define q = (q1, . . . , qn) as a vector that represents the marginal probability that plus agent i is selected, and similarly r = (r1, . . . , rm) as a vector that represents the probability that minus agent j is excluded. In particular, we consider the following program for the plus agent side for each Bk:

and the following for the minus agent side:

Multilinear versions of the above programs require the probabilities to be independent, whereas concave closure allows them to be correlated.

We will compare each optimization problem with the expected utilities obtainable from each side market. Formally, we will consider a class of mechanisms MEC(B) parameterized by B such that its total expected payment to plus agents is at most B, and its total expected revenue from minus agents is at least B. Given a budget B, we use the following notation:

• Wp(B) and Wm(B): the optimal expected utilities achievable by any DSIC and IR mechanism in MEC(B), on the plus and minus side respectively. We write W(B) = Wp(B) + Wm(B).
• W + p (B) andW + m (B): the optimal values of (PLUS) and (MINUS) under the concave closure.
• W ml p (B) and W ml m (B): the optimal values of (PLUS) and (MINUS) under the multilinear extension, with q(B) and r(B) denoting the corresponding optimal marginal probabilities.

Throughout, we assume without loss of generality (by rescaling costs and values) that W(x) ≤ (1 + ε)W(0) for all x ∈ (0, 1].

The performance of any mechanism given a budget, including the optimal one, will be upper-bounded by the concave closure as shown by the following lemma:

Lemma 13 (Concave relaxation). Given B > 0 and a mechanism MEC(B) that is DSIC, IR and ex-ante BB, its expected utility up from plus agents is upper bounded by W + p (B) and um (that from minus agents) is upper bounded by W + m (B).

Then, we consider multilinear versions of the programs (PLUS) and (MINUS), and solving them gives us prices to offer as depicted in Algorithm 2. Thanks to Theorem 12, these prices guarantee a constant-factor approximation to the concave closure given B.

Lemma 14 (Posted pricing given a budget). For any budget B, offering prices tp = G-1 (q(B)) to plus agents guarantees an expected utility of at least (1 - 1/e) · W + p (B) from plus agents, and offering tm = F -1 (r(B)) to minus agents guarantees an expected utility of at least (1 - 1/e) · W + m (B) from minus agents.

Therefore, one can conclude that if we know the expected budget used by the optimal mechanism, the corresponding posted pricing mechanism gives us the desired result. On the other hand, this is not known in advance, so we generate a finite list of candidate optimal budgets and select the candidate budget that maximizes the expected utility. Since this list cannot always include the optimal budget due to the continuity of the entire budget space, we require the following concavity of the optimal expected utility with respect to the budget.

Lemma 15 (Concavity of the optimal utility). Under regular agent distributions, the plus-agent's optimal utility Wp(B) and the minus-agent's optimal utility Wm(B) are both concave functions of B.

The above lemma results in the following lemma, implying that the error from the finiteness of the budget candidates can be made sufficiently small.

Lemma 16 (Error from budget discretization). Let W(B) = Wp(B) +Wm(B) be the total utility function given B. Let Bk and Bk+1 be consecutive grid points in B such that Bk ≤ B∗ ≤ Bk+1. Then, we have W(Bk) ≥ (1 - ε)W(B∗ ).

Combining the lemmas, let BOPT be the expected budget used by the optimal Bayesian mechanism, and let Bk,Bk+1 be consecutive grid points bracketing it (Bk ≤ BOPT ≤ Bk+1). Then

which yields the claimed (1 - 1/e - O(ε))-approximation.

6 Conclusion

In this paper, we introduced and analyzed a novel twosided mechanism design framework for self-financing events, where a designer's goal is to maximize an exogenous utility function by curating a set of participants. This problem requires balancing the recruitment of costly, high-impact plus agents with revenue-generating minus agents who may detract from the event's quality, all under a budget-balanced constraint.

Our analysis addresses this design problem primarily within the Bayesian setting. For the case of additive utilities, we fully characterize the optimal mechanisms that are incentive-compatible, IR, and BB. Extending our results to more general objectives, we then provide constant-factor approximation mechanisms for utility functions that are separable and submodular.

Key avenues for future work include extending our analysis beyond submodular separable utility functions to model the complex interplay between participants. Broadening the scope of prior-free results for this framework, by providing robust guarantees for submodular utilities or by relaxing the large market assumption, could also enhance its practical applicability.

Acknowledgements

This work is partially supported by DARPA expMath, NSF AF:Small #2218678, NSF AF:Small #2114269, ArmyResearch Laboratory (ARL) #W911NF2410052, and MURI on Algorithms, Learning and Game Theory.