Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising Nguyễn Kim Thắng
arXiv:2604.12799v1 [cs.GT] 14 Apr 2026
LIG, Grenoble INP, University Grenoble-Alpes, France April 15, 2026
Abstract The rise of automated bidding strategies in online advertising presents new challenges in designing and analyzing efficient auction mechanisms. In this paper, we focus on proportional mechanisms within the context of auto-bidding and study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA), under the liquid welfare objective. We first establish a tight PoA bound of 2 for the standard proportional mechanism. Next, we introduce a modified version with an alternative payment scheme that achieves a PoA bound of 1 + O(1) n−1 where n ≥ 2 denotes the number of bidding agents. This improvement surpasses the existing PoA barrier of 2 and approaches full efficiency as the number of agents increases. Our methodology leverages duality and the Karush-Kuhn-Tucker (KKT) conditions from linear and convex programming. Despite its conceptual simplicity, our approach proves powerful and may offer broader applications for establishing PoA bounds.
1
Introduction
The online advertising ecosystem has been rapidly evolving with the widespread adoption of autobidding systems by advertisers and markets [2]. Traditionally, advertising platforms required advertisers to manually submit detailed bids. However, with advancements in AI technologies, intelligent models can now serve as virtual consultants—assisting advertisers with analysis, strategy formulation, and decision-making. Specifically, an auto-bidding agent can translate an advertiser’s goals and constraints into strategic bids to optimize their objectives. This automation simplifies the advertiser’s role, enabling them to delegate complex tasks to the agent. At the same time, the growing presence of numerous optimized auto-bidding agents, each pursuing different goals, increases the complexity of the overall system. This introduces significant research challenges, particularly in understanding system equilibria and designing effective mechanisms. As a result, auto-bidding has become a prominent focus of recent research [1, 2, 15, 19, 8] within the advertising domain.
1.1
Model and Definitions
We define the problem faced by the autobidding agents and the auctioneer in an ad-auction environment. There are n autobidding agents (indexed by i) and m divisible items (indexed by j), and each item is sold in an independent auction. Each agent has a private function vi : [0, 1]m → R≥0 which defines its valuation over fractional allocations of items and a private budget Wi representing the maximum total amount agent i is willing to pay. We assume that functions vi ’s are continuous, 1
differentiable, concave, and non-decreasing on every component. For each item j, each agent i submits a bid bij ∈ R≥0 . After collecting all bids b1j , . . . , bnj on item j, the auctioneer determines the P allocation dij ∈ [0, 1] such that ni=1 dij = 1 and the corresponding payment pij ≥ 0 for each agent i. Let di = (di1 , . . . , di,m ) denote the item fractions received by agent i. The valuation of agent i in this P allocation is vi (di ). In the context of online advertising, the valuation vi (di ) is typically vi (di ) = m j=1 vij dij where vij ∈ R≥0 represents the value agent i derives from fully acquiring item j. In this work, we consider more general forms of valuation functions to capture a broader range of advertiser preferences. Agents’ objectives and constraints. In autobidding, agents have different objectives subject to their own constraints. The following are widely used objectives and their generalization. P • Utility-maximizing objective: vi (di ) − m j=1 pij . • Valuation-maximizing objective: vi (di ). P • Hybrid objective: vi (di ) − ρi m j=1 pij where 0 ≤ ρi ≤ 1 is a parameter specific to agent i. This objective generalizes the ones above that correspond to ρi = 1 and ρi = 0. In the context of online advertising, utility-maximizing agents aim to optimize the difference between their valuation and the payment made. This objective is standard in auction and mechanism design theory. However, it can be challenging for advertisers to quantify their valuation in purely monetary terms [2]. In contrast, valuation-maximizing agents focus on directly maximizing outcomes such as clicks or conversions—captured by their valuation functions—while considering payments only indirectly, typically through budget or other constraints (as discussed below). Finally, hybrid agents pursue a combination of both goals, balancing the desire for high valuation outcomes and the payment incurred. The most common constraints for agents 1 ≤ i ≤ n are the budget and the return-on-spend constraints. P • Budget constraint (Budget): m j=1 pij ≤ Wi P • Return-on-spend constraint (RoS): vi (di ) ≥ τi · m j=1 pij . By [8], without loss of generality, we can assume τi = 1 for all i. The budget constraint is natural for agents to control their expenses in an ad campaign. In addition, the RoS constraint captures a variety of considerations, such as cost-per-action constraint, returnon-investment constraint, individual rationality constraint, etc. It is particularly useful when certain ad campaign goals cannot converted into explicit monetary terms. To summarize, the problem of a bidding agent i can be formulated as the following (convex) program: m X max vi di − ρi pij j=1
subject to:
m X
pij ≤ Wi (Budget),
j=1
and
m X vi di ≥ pij (RoS) j=1
Auction objective. On the side of the auctioneer, the objective is to maximize the liquid welfare, defined as the total valuation of each agent capped by its budget, i.e., Lw(b; v, W ) = Pn min W , v (d i i i ) where v = (v1 , . . . , vn ) and W = (W1 , . . . , Wn ) are the valuation and budi=1 get profiles of agents. Pn It has been observed that liquid welfare is more suitable than the classic social welfare (i.e., i=1 vi (di )) since the latter cannot be well-approximated when agents are constrained. Moreover, liquid welfare represents the highest possible revenue that can be attained with full information on the agents’ information. 2
Equilibrium concepts and the PoA. In this paper, we focus on pure Nash equilibria. A pure Nash equilibrium is a bidding profile b such that no agent can increase its objective via a unilateral deviation; that is, for every agent i and every strategy b′i = (b′i1 , . . . , b′i,m ), ui (b) ≥ ui (b′i , b−i ) where b−i denotes the bids chosen by all agents other than i in b and ui denote the objective of agent i (which can be its utility, valuation, or hybrid objective with its own parameter ρi depending on the agent). To quantify the efficiency of an auction, we consider the standard price of anarchy. The price of anarchy (PoA) is defined as the largest ratio between the liquid welfare of an optimal solution and that of an equilibrium. Specifically, the price of anarchy of pure equilibria is defined as Opt(v,W ) Lw(b;v,W ) where Opt(v, W ) is the optimal liquid welfare with valuation and budget profiles v, W .
1.2
State of the Art and Our Contributions
The PoA has been extensively analyzed across a variety of auction settings: including firstprice and second-price auctions; scenarios involving only valuation-maximizing agents, only utilitymaximizing agents, both types, or hybrid agents; environments constrained solely by budgets, solely by Return on Spend (RoS), or by both; as well as auction formats that incorporate reserve prices, additive boosts, and randomization. (We refer the reader to Section 1.3 and the survey [2, Section 4] for details.) Through those results (a part is summarized in Table 1), the PoA bound of 2 emerges as a barrier. This bound is tight for certain auction formats and can only be surpassed under special conditions, such as when there are exactly two agents [15], or when additional assumptions or external information (e.g., machine learning-based predictions) are introduced. However, in general, this represents a strong barrier. This barrier is plausibly supported by [15] in which they showed the PoA lower bound of 2 for a broad class of randomized mechanisms satisfying some natural properties. Aggarwal et al. [2] raised the following intriguing question: Design a mechanism that has a PoA of strictly less than 2 and furthermore compute the PoA as a function of n.
Agents objectives
Agents’ constraints
valuation maximizing
RoS
Budget + RoS
PoA(FPA) = 2 [15]
PoA(FPA) = n [16], PoA(q−FPA) = 2 [16] PoA(SPA) = 2 [1]
mix: both valuation
PoA(FPA) = 2.188 [8]
PoA(PM) = 2
and utility maximizing PoA(m−PM) = 1 + O(1) n−1
hybrid
Table 1: Summary of results on the PoA(of pure Nash equilibria) for different auction formats: first and second price auctions (FPA and SPA), quasi-proportional FPA (q−FPA). Our contributions are in red w.r.t the proportional mechanism (PM) and its variant (m-PM). In this paper, we answer positively this question in a general setting in which valuation functions are concave and there is a mix of utility-maximizing, valuation-maximizing agents, and also hybrid agents. Specifically, we consider the proportional mechanisms in which for each item j, agent i bij of item j, and the payment of agent i on item j is its bid bij in the receives a fraction of b1j +...+b n,j (traditional) proportional mechanism (known also as Kelly mechanism) or in general is a function 3
of the bids of all agents for other variants of proportional mechanism. Our contributions are the following. 1. We establish the PoA upper bound of 2 for the proportional mechanism in settings that include both utility-maximizing and valuation-maximizing agents, and under both Budget and RoS constraints. Combing with the lower bound from [4] (which holds even in the restricted case of only utility-maximizing agents and Budget constraint), this bound is tight for the proportional mechanism. 2. We introduce a variant of the proportional mechanism with an alternative payment scheme that achieves a PoA bound of 1+ O(1) n−1 where n ≥ 2 denotes the number of bidding agents. This result not only surpasses the strong PoA barrier of 2, but also approaches full efficiency (i.e., PoA → 1) as the number of agents increases. As a notable consequence, our result circumvents previously established impossibility results in the context of autobidding [15] and resource allocation mechanisms [5]. The results and further details are provided in Section 4. P For the typical valuation functions vi (di ) = m j=1 vij dij in the context of online advertising, the proportional mechanisms can be converted into randomized mechanisms. Our approach is based on linear programming duality and optimality conditions in convex programming to analyze the PoA. At the level of agents, we characterize equilibrium structures using Karush-Kuhn-Tucker (KKT) conditions applied to convex programs of the agents’ problems. At the level of the auctioneer, we employ a primal-dual approach to bound PoA. Specifically, we formulate a configuration integer program that represents the underlying optimization problem of the auctioneer. By relaxing the integer constraints, we derive the corresponding dual linear program, which, by weak duality, provides an upper bound on the optimal liquid welfare. Given an equilibrium, we leverage KKT-derived properties to construct feasible dual solutions, allowing us to bound PoA by analyzing the ratio between the primal objective (the liquid welfare at equilibrium) and the dual objective (an upper bound on the optimal liquid welfare).
1.3
Further Related Works
Auto-bidding Advertising and PoA. The PoA in auto-bidding advertising has been actively studied recently in various auctions [1, 15, 19, 8]. A summary of PoA for pure Nash equilibria is given in Table 1. Beyond pure strategies, PoA has also been studied under more general equilibrium concepts, particularly mixed equilibria. Notably, [8] extended the PoA upper bound of 2 to mixed equilibria in first-price auctions involving valuation-maximizing agents subject to RoS constraints. Furthermore, they established a PoA bound of 2.188 in settings with both utility-maximizing and valuation-maximizing agents. Randomized mechanisms have also been a focus of recent study. For the two-agent case (i.e., n = 2), [19] showed a PoA of 1.9, which was subsequently improved to 1.8 in [15]. In the work, the authors also proved a PoA lower bound of 2 PoA for a broad class of randomized mechanisms that satisfy certain natural properties. Beyond equilibrium analysis, auto-bidding has been examined under no-regret learning dynamics with theoretical guarantees [10, 11, 17] and in machine-learningaugmented auctions that incorporate predictive models to improve bidding strategies [3, 8] Proportional mechanism in resource allocation. The proportional mechanism, also known as the Kelly mechanism, has been studied by [13] in the context of classic social welfare in which the tight PoA bound for pure Nash equilibria has been proven. Bridging the classic welfare and the liquid welfare, [20] proved that the social welfare at equilibria of the proportional mechanism 4
is at most a constant factor away from the optimal liquid welfare. In the single-item setting (i.e., m = 1), building on a long line of works ([4, 6] among others), [5] showed the tight PoA bound of 2 for pure Nash equilibria. [6] considered the multiple-item setting and provided a PoA upper bound of 2.618 under more general equilibrium concepts, specifically coarse correlated equilibria. Proportional mechanisms with different payment schemes have been proposed. In settings with only utility-maximizing agents and no Budget or constraints, full efficiency (i.e., PoA = 1) has been achieved using different payment designs [18, 21, 14]. However, [5] also established an impossibility result: no mechanism can achieve a PoA better than 2 for general concave valuation functions. In Section 4, we revisit this limitation and demonstrate that it can be overcome under additional, natural assumptions.
2
Preliminaries
In this section, we define the class of proportional mechanisms considered in this paper and establish the existence of pure Nash equilibria within this framework. We also describe a transformation from a proportional mechanism—designed for divisible items—to a corresponding randomized mechanism applicable to indivisible items in autobidding settings. Finally, we formulate a suitable configuration linear program (LP) that serves for analyzing PoA in our paper. Proportional Mechanisms. Recall that in the setting, there are m different divisible items, and they are fractionally distributed among n agents. Each agent i has a private monotone nondecreasing, concave, and differentiable valuation function vi : [0, 1]m → R≥0 so that vi (di1 , . . . , dij ) represents the value that agent i achieves by receiving fractions dij from items j. Additionally, agent i has a private budget Wi , which restricts its payment. P Each agent 1 ≤ i ≤ n strategically submits bids bij ≥ 0 on item 1 ≤ j ≤ m subject to its budget m j=1 bij ≤ Wi . After collecting all b
ij the bids, agent i will receive a fraction of b1,j +...+b of item j, that is proportional to its submitted n,j bid bij on item j. In the traditional proportional mechanism (Kelly mechanism), the payment pij of agent i on item j is its submitted bid bij . Different payment schemes have been proposed [18, 21, 14]. In this paper, we consider the following scheme inspired by the one in [18]. P X X Z bij g t + i′ ̸=i bi′ j pij = bi′ j · bi′ j (1) 2 dt + h P 0 t + i′ ̸=i bi′ j i′ ̸=i i′ ̸=i
where g : R≥0 → R≥0 is a non-decreasing function and h : R≥0 → R≥0 is a function independent 2 of bij . The traditional proportional mechanism corresponds to the case where g(u) = P ′ u b ′ and i ̸=i i j P bi,m bi1 h ≡ 0. Recall that the liquid welfare is ni=1 min Wi , vi bi1 +...+b , . . . , . bi1 +...+bi,m i,m Proposition 1 There always exists a pure Nash equilibrium in the proportional mechanisms with the payment schemes defined in Equation (1) where g(u) = C1 u2+r with r ≥ 0. Proof Recall that the problem of each agent i with its parameter 0 ≤ ρi ≤ 1 is the following m X max vi di − ρi pij j=1
subject to:
m X
pij ≤ Wi (Budget),
j=1
and
m X vi di ≥ pij (RoS) j=1
b
ij where in the proportional mechanism dij = b1,j +...+b . By the classic theorem of [7, 9, 12], a n,j pure Nash equilibrium exists if the three following conditions hold: (i) compact and convex of the
5
strategy set of each agent; (ii) continuity of each agent’s objective w.r.t the strategy profile; and (iii) quasiconcavity of the agent objective in the agent strategy set. By the definition of payments and assumption on the functions vi (continuous differential concave) and the set of constraints, the two first conditions are fulfilled. For the last condition, it is sufficient to verify whether the payment pij is a convex function on bij . In particular, for function g(u) = C1 u2+r with r ≥ 0 and C is a non-negative constant, the second derivation of pij w.r.t bij is X r−1 1 X bi′ j · bij + bi′ j ≥0 rC ′ ′ i ̸=i
i ̸=i
Therefore, the payment is convex and so the agent objective is concave. The theorem follows.
□
Conversion to randomized algorithm. Due to the allocation rule in proportional mechanisms, it is particularly convenient to transform such mechanisms into randomized mechanisms for autobidding Pm advertising settings, especially when working with typical valuation functions vi (di ) = j=1 vij dij . Specifically, given a proportional mechanism with payment pij , do the following. For each item j, given bids b1j , . . . , bn,j , assign item j to agent i with probability b1j +...+bn,j bij pij . Hence, the expected valuation of agent i b1j +...+bn,j and charge agent i a payment of bij Pm Pm bij is j=1 b1j +...+bn,j vij and its expected payment is j=1 pij — exactly the valuation and payment in the proportional mechanism. The Budget and RoS constraints now hold in expectation. Formulation. One of the key steps in our approach is to formulate a suitable configuration LP corresponding to the underlying optimization problem of the auctioneer to which we can apply the primal-dual analysis. Notice that we consider here the underlying optimization problem independent of any specific mechanism. Fix an arbitrarily small constant ϵ > 0. Let D(ϵ) = {k · ϵ : 0 ≤ k ≤ 1ϵ } be a discretized set of fractions. In the formulation, we will assume that an item can only be divided into fractions that belong to the set D(ϵ). As ϵ can be chosen arbitrarily small and the valuations are continuous, this assumption will result in an arbitrarily small loss of the liquid welfare. For simplicity, as ϵ is fixed, we use the notation D instead of D(ϵ) as long as it is clear from the context. A (fractional) assignment (a solution) Pn of items to agents is a set S = {(i, j, dij ) : 1 ≤ i ≤ n, 1 ≤ j ≤ m, dij ∈ D} such that i=1 dij ≤ 1 for all items 1 ≤ j ≤ m. Intuitively, a tuple (i, j, dij ) means that a fraction dij of item j is assigned to agent i. Denote S a set of allP(fractional) assignments. Let cS be the total effective welfare of the assignment S, i.e., cS = ni=1 min{Wi , vi (di,1 , . . . , di,m )} where dij is the fraction of item j that agent i receives in the assignment S for 1 ≤ i ≤ n and 1 ≤ j ≤ m. Let zS be a 0-1 variable indicating whether the assignment is chosen. Consider the following formulation.
max
X
cS zS
min
S∈S
(αj )
n X X i=1 dij
(β)
dij
X
zS = 1
X
∀j
(i,j,dij )∈S
zS = 1
S∈S
zS ∈ {0, 1}
αj + β
j=1
S:(i,j,dij )∈S
X
m X
∀S ∈ S
6
dij αj + β ≥ cS
∀S ∈ S
In the formulation, the second constraint guarantees that an assignment must be selected. Moreover, by the integral constraint zS ∈ {0, 1}, there is exactly one selected assignment, i.e., all zS ’s but one are equal to 0. To understand the first constraint,Pobserve that if one fixes an item j, an agent i, and an assigned fraction dij of j to agent i, the sum S:(i,j,dij )∈S zS equals to 1 iff zS = 1 for some S that contains P (i, j, dij ), or equals to 0 if zS = 0 for all S that contain (i, j, dij ). In other words, the value of S:(i,j,dij )∈S zS (which equals either 0 or 1) indicates whether agent i receives exactly the fraction of dijP of item j in the solution. Therefore, summing up over all fractions in P D, the term dij ∈D dij · S:(i,j,dij )∈S zS represents the fraction of item j attributed to agent i. P P P Consequently, the constraint ni=1 dij ∈D dij · S:(i,j,dij )∈S zS = 1 ensures the total fractions of item j assigned to all agents sum up to 1. The objective is to maximize the total effective welfare. By relaxing the integrality of zS , one can compute the dual LP on the right-hand side, representing an upper bound of the total liquid welfare. High level of our analysis strategy. Given an equilibrium bid vector, we build a feasible dual solution of the above formulation. By the weak duality, the corresponding dual objective represents a lower bound of the optimal liquid welfare. Subsequently, we derive the PoA by bounding the dual objective to the liquid welfare of the equilibrium.
3
Efficiency of (Standard) Proportional Mechanism
In this section, we settle the PoA of the standard proportional mechanism in the presence of both valuation-maximizing and utility-maximizing agents. Let b∗ be an arbitrary pure Nash equilibrium and let d∗ij (b∗ ) = b∗ij /(b∗1,j + . . . + b∗n,j ) be the fraction of item j assigned to agent i by the proportional mechanism in the equilibrium b∗ . When b∗ is clear fromPthe context, for simplicity, we drop the parameter b∗ and simply use d∗ij . Moreover, n ∗ denote Bj∗ = i=1 bij for every item 1 ≤ j ≤ m. In the mechanism, the payments equal the corresponding bids. The problem of agent i is the following. max
bi1 ,...,bi,m
vi
bi1 +
b Pi1
∗ i′ ̸=i bi′ ,1
,...,
bi,m +
bi,m P
∗ i′ ̸=i bi′ ,m m X
(λi )
− ρi
m X
b∗ij
j=1
bij ≤ Wi
(Budget)
j=1
(µi )
vi
bi1 +
b Pi1
∗ ,..., b i,m + i′ ̸=i bi′ ,1
bi,m P
∗ i′ ̸=i bi′ ,m
≥
m X
bij ≥ 0
(ξij )
bij
(RoS)
j=1
∀1 ≤ j ≤ m
Recall that, in the above program, if i is utility-maximizing agent, ρi = 1, and if i is valuationmaximizing agent, ρi = 0. In the equilibrium b∗ , every agent i maximizes its objective w.r.t the constraints. Given that the agent valuations are continuous and concave, the KKT condition (derivatives of the corresponding
7
Lagrangian w.r.t variables bij ) reads: for every 1 ≤ j ≤ m, P ∗ ∂vi d∗i1 , . . . , d∗i,m i′ ̸=i bi′ ,j − ρi − λi + ξij 2 · Pn ∗ ∂dij b ′ ′ i =1 i ,j P ∗ ∂vi d∗i1 , . . . , d∗i,m i′ ̸=i bi′ ,j + µi Pn −1 =0 2 · ∂dij b∗′ ′ i =1 i ,j
Hence, (1 − d∗ij ) ·
∂vi d∗i1 , . . . , d∗i,m µi + ρi + λi − ξij ∗ = Bj ∂dij 1 + µi
∀1 ≤ j ≤ m
P ∗ ∗ If m j=1 bij < Wi (so λi = 0 by the slackness complementary condition) and bij > 0 (so ξij = 0) then for every (either valuation-maximizing or utility-maximizing) agent i, it holds that ∂vi d∗i1 , . . . , d∗i,m ρi + µi ∗ ∗ = B ≤ Bj∗ ∀1 ≤ j ≤ m (2) (1 − dij ) ∂dij 1 + µi j P ∗ ∗ In particular, if i is a utility-maximizing agent (i.e., ρi = 1) and m j=1 bij < Wi and bij > 0, then the inequality in Equation (2) becomes equality. DualPvariable definition. Define the dual variables as the following: αj = β = ni=1 βi where variables βi are defined in the following.
Pn
∗ ∗ i=1 bij = Bj and
• if i is valuation-maximizing agent then βi = min{Wi , vi (d∗i )} • if i is utility-maximizing agent then ( Wi βi = P ∂vi (d∗i1 ,...,d∗i,m ) ∗ ∗ 2vi (d∗i1 , . . . , d∗im ) − m j=1 dij · (1 − dij ) · ∂dij
if vi (d∗i1 , . . . , d∗i,m ) ≥ Wi , otherwise.
Lemma 1 The dual variables defined above are feasible. Proof Fix an arbitrary (fractional) assignment S (consisting of tuples (i, j, dij )). The dual constraint reads: X dij · αj + β ≥ cS (i,j,dij )∈S
⇔
X (i,j,dij )∈S
dij Bj∗ +
n X i=1
βi ≥
n X
min{Wi , vi (di,1 , . . . , di,m )}
i=1
To prove the above inequality, it is sufficient to prove that for every fixed agent 1 ≤ i ≤ n: m X
dij Bj∗ + βi ≥ min{Wi , vi (di,1 , . . . , di,m )}
(3)
j=1
Fix an agent i. If βi = Wi , then Equation (3) follows trivially. Until the end of the proof, assume that βi ̸= Wi . We consider different cases. 8
Case 1: i is valuation-maximizing agent. As βi ̸= Wi , it implies βi = vi (d∗i ) and vi (d∗i ) < Wi . By Equation (2), we have m m ∗ , . . . , d∗ X X ∂v d i i1 i,m + vi (d∗i ) dij Bj∗ + βi ≥ dij (1 − d∗ij ) ∂dij j=1 j=1 m X ∂vi d∗i1 , . . . , d∗i,m ∗ ≥ + vi (d∗i ) (dij − dij ) ∂dij j=1
≥ vi (di1 , . . . , di,m ) ≥ min{Wi , vi (di1 , . . . , di,m )} where the second inequality holds since dij ≤ 1 and the last inequality follows the concavity of vi . Case 2: i is utility-maximizing agent. As βi ̸= Wi , it means that βi = 2vi (d∗i1 , . . . , d∗im ) −
m X
d∗ij (1 − d∗ij )
j=1
∂vi (d∗i1 , . . . , d∗i,m ) ∂dij
(and also, vi (d∗i ) < Wi ). By Equation (2) and definition of βi , we have m X
dij Bj∗ + βi
j=1 m X
m X ∂vi (d∗i1 , . . . , d∗i,m ) ∂vi d∗i1 , . . . , d∗i,m ≥ · + 2vi (d∗i1 , . . . , d∗im ) − d∗ij (1 − d∗ij ) ∂dij ∂dij j=1 j=1 m X ∂vi d∗i1 , . . . , d∗i,m = vi (d∗i1 , . . . , d∗im ) + vi (d∗i1 , . . . , d∗im ) + dij − d∗ij · ∂dij j=1 m X ∂vi d∗i1 , . . . , d∗i,m ∗ ∗ − dij dij − dij · ∂dij j=1 m X ∂vi d∗i1 , . . . , d∗i,m ∗ ∗ ∗ ∗ ≥ vi (di1 , . . . , dim ) + vi (di1 , . . . , dim ) − dij dij − dij · ∂dij j=1 m X ∂vi d∗i1 , . . . , d∗i,m ∗ ∗ ≥ vi (di1 , . . . , dim ) + vi (di1 , . . . , dim ) − d∗ij · ∂dij dij 1 − d∗ij
j=1
≥ vi (di1 , . . . , dim ) + vi (0, . . . , 0) ≥ vi (di1 , . . . , dim ) The first and third inequalities are due to the concavity of vi (·). The second inequality holds since dij , d∗ij ≤ 1 and so dij − d∗ij ≤ 1. The last inequality follows vi (0, . . . , 0) ≥ 0. Combining all the cases above, the dual feasibility follows. □ Theorem 1 The PoA of pure Nash equilibria for liquid welfare in the proportional mechanism is at most 2. Proof We are bounding the liquid welfare ofPthe (arbitrary) equilibrium b∗ and the dualPobjective of the defined dual solution. The former is ni=1 min{Wi , vi (d∗i )} whereas the latter is m j=1 αj + 9
Pn
i=1 βi =
Pm Pn j=1
∗ i=1 bij +
Pn
i=1 βi =
each 1 ≤ i ≤ n,
m X
Pn
i=1 (
Pm
∗ j=1 bij + βi ). Again, it is sufficient to prove that for
b∗ij + βi ≤ 2 min{Wi , vi (d∗i )}.
j=1
P ∗ ∗ If i is valuation-maximizing agent, m j=1 bij ≤ min{Wi , vi (di )}. By definition of dual variables, ∗ βi = min{Wi , vi (di )}. Therefore, the above inequality follows. In the following, consider a utilitymaximizing agent i. Case 1: βi = Wi .
This case also means that vi (d∗i ) ≥ Wi . Therefore, m X
b∗ij + βi =
j=1
m X
b∗ij + Wi ≤ 2Wi = 2 min{Wi , vi (d∗i )} .
j=1
Pm ∗ ∗ ) ≤ W and bij < Wi . Case 2: βi ̸= W . By definition of β , the case assumption implies v (d i i i i i Pj=1 Pm ∗ m ∗ (Otherwise, if j=1 bij = Wi then by the non-negativity of agent i’s utility, vi (di ) ≥ j=1 b∗ij = Wi and that implies βi = Wi — contradicting to the case assumption.) Hence, m X
b∗ij + βi =
j=1
m X
b∗ij + 2vi (d∗i1 , . . . , d∗im ) −
j=1
=
X
m X j=1
b∗ij + 2vi (d∗i1 , . . . , d∗im ) −
j:b∗ij ̸=0
=
X
d∗ij (1 − d∗ij ) · X
∂vi (d∗i1 , . . . , d∗i,m ) ∂dij
d∗ij Bj∗
j:b∗ij ̸=0
b∗ij + 2vi (d∗i1 , . . . , d∗im ) −
j:b∗ij ̸=0
X
b∗ij
j:b∗ij ̸=0
= 2vi (d∗i1 , . . . , d∗im ) = 2 min{Wi , vi (d∗i )} where the second equality is due to Equation (2) with equality for utility-maximizing agents. The theorem follows. □
4
Mechanism with asymptotically full efficiency
In this section, we study a proportional mechanism with a different payment scheme in the setting with general hybrid agents (each has its own parameter ρi ). Fix an arbitrarily small constant 1 ϵ ≥ n−1 . The payment is specifically in the form of Equation (1) in which function g(u) = u1+(n−1)ϵ g(u) and h(u) = (n−1)ϵ . This choice of function g will be clear later. The payment is explicitly given in Equation (4). To guarantee the existence of pure Nash equilibria, by Proposition 1, one needs to 1 . choose ϵ such that 1 + (n − 1)ϵ ≥ 2, that explains the condition ϵ ≥ n−1 ∗ ∗ ∗ Let b be an arbitrary pure Nash equilibrium and let dij (b ) be the fraction of item j assigned to agent i by the proportional mechanism given b∗ . When b∗ is clear from thePcontext, for simplicity, n ∗ we drop the parameter b∗ and simply use d∗ij . Moreover, denote Bj∗ = i=1 bij for every item
10
1 ≤ j ≤ m. We recall the problem of (hybrid) agent i with a new payment scheme. max
b Pi1
vi
bi,m P
,...,
− ρi ·
m X
pij bi1 + i′ ̸=i b∗i′ ,1 bi,m + i′ ̸=i b∗i′ ,m j=1 P P X Z bij ∗ ∗ g t + b g b ′ ′ ′ ′ i ̸=i i j i ̸=i i j ∗ P pij = bi′ j · 2 dt + P (n − 1)ϵ · i′ ̸=i b∗i′ j 0 t + i′ ̸=i b∗i′ j i′ ̸=i bi1 ,...,bi,m
(λi )
m X
∀1 ≤ j ≤ m
pij ≤ Wi
(4)
(Budget)
j=1
(µi ) (ξij )
vi
bi1 +
b Pi1
∗ i′ ̸=i bi′ ,1
,...,
bi,m +
bi,m P
∗ i′ ̸=i bi′ ,m
≥
m X
pij
(RoS)
j=1
bij ≥ 0
∀1 ≤ j ≤ m
Given that the agent valuations are continuous, differentiable, and concave, the KKT condition (derivatives of the corresponding Lagrangian function w.r.t variables bij ) reads: for every 1 ≤ i ≤ n, 1 ≤ j ≤ m, P P X X n n ∗ ∗ ∂vi d∗i1 , . . . , d∗i,m i′ ̸=i bi′ ,j i′ ̸=i bi′ ,j ∗ ∗ + ξij − λi Pn bi′ j bi′ j − ρi · g 2 · 2 · g Pn ∗ ∗ ∂dij b b ′ ′ ′ ′ ′ ′ i =1 i ,j i =1 i ,j i =1 i =1 P X n ∗ ∗ , . . . , d∗ b ∂v d i i1 i′ ̸=i i′ ,j i,m + µ i Pn =0 b∗i′ j −g 2 · ∗ ∂d ij i′ =1 bi′ ,j i′ =1 P ∗ Consequently, if m j=1 pij < Wi (so λi = 0 by the slackness complementary condition), then, as ξij ≥ 0, it holds that: X n n ∂vi d∗i1 , . . . , d∗i,m ρi + µi X ∗ ∗ ∀i, j (5) bi′ j bi′ j ≤ g ≤ g ∂dij 1 + µi ′ ′ i =1
i =1
Dual variables.
P Define the dual variables as the following: αj = g Bj∗ and β = ni=1 βi where βi =
vi (d∗i ) −
W
∗
∗
∗ ∂vi di1 ,...,di,m j=1 dij ∂dij
Pm
if vi (d∗i ) < Wi , otherwise.
i
Lemma 2 For every item 1 ≤ j ≤ m, it holds that ϵ ·
Pn
∗ i=1 pij = g
Pn
∗ i=1 bij
.
Proof P Fix an arbitrary item Pn1 ≤ ∗j ≤ m. For simplicity, as j is fixed, denote (only in this proof) ∗ = ∗ and B ∗ = B−i b i′ ̸=i i′ j i′ =1 bi′ j without the subindex j. We have: P P Z b ∗ ∗ ∗ g ij g t + i′ ̸=i bi′ j i′ ̸=i bi′ j P · dt + P ∗ 2 (n − 1)ϵ · i′ ̸=i b∗i′ j 0 t + b ′ ′ ′ i ̸=i i j i ̸=i Z b∗ ∗ ij g t + B ∗ g B −i −i ∗ = B−i · 2 dt + ∗ (n − 1)ϵ · B−i 0 t + B∗
p∗ij =
X
b∗i′ j
−i
11
By the choice of g(u) = e(1+(n−1)ϵ) ln u = u1+(n−1)ϵ , we have Z b∗ Z b∗ ij g t + B ∗ ij 1 1 −i ∗ (n−1)ϵ ∗ (n−1)ϵ dt = (B ) − (B ) dt = −i ∗ 2 ∗ 1−(n−1)ϵ (n − 1)ϵ 0 0 t + B−i t + B−i ∗ 1+(n−1)ϵ ∗ )1+(n−1)ϵ (B−i 1 (B ) = − ∗ (n − 1)ϵ B∗ B−i ∗ ) 1 g(B ∗ ) g(B−i = − ∗ (n − 1)ϵ B ∗ B−i
(6)
Therefore, n X
p∗ij =
i=1
where
n X i=1
n
∗ g(B ∗ ) X ∗ 1 1 1 ∗ g(B ) B−i = B−i = g(B ∗ ) (n − 1)ϵ B∗ (n − 1)ϵ B ∗ ϵ i=1
Pn
∗ ∗ i=1 B−i = (n − 1)B .
□
Remark. We choose g(u) = e(1+(n−1)ϵ) ln u = u1+(n−1)ϵ to fullfil Lemma 2. Specifically, g(u) = e(1+(n−1)ϵ) ln u is a solution of the following differential equation: g(u) g(u) d = 2 du (n − 1)ϵ · u u This equation is needed in the proof of Lemma 2, specifically, Equation (6). Lemma 3 The dual variables defined above are feasible. Proof Fix an arbitrary (fractional) assignment S (consisting of tuples (i, j, dij )). The dual constraint reads: X dij · αj + β ≥ cS (i,j,dij )∈S
⇔
X
dij g(Bj∗ ) +
n X
βi ≥
i=1
(i,j,dij )∈S
n X
min Wi , vi (di,1 , . . . , di,m )
i=1
To prove the above inequality, it is sufficient to prove that for every fixed agent 1 ≤ i ≤ n: m X
dij g(Bj∗ ) + βi ≥ min Wi , vi (di,1 , . . . , di,m )
(7)
j=1
Fix an agent i. If βi = Wi then Equation (7) Pholds∗trivially.∗ Assume that βi < Wi . By definition of βi and the RoS constraint, it implies that m j=1 pij ≤ vi (di ) < Wi . By Equation (5), we have m m m ∗ , . . . , d∗ ∗ , . . . , d∗ X X X ∂v d ∂v d i i i1 i,m i,m i1 dij g Bj∗ + βi ≥ dij + vi (d∗i ) − d∗ij ∂dij ∂dij j=1 j=1 j=1 m X ∂vi d∗i1 , . . . , d∗i,m = (dij − d∗ij ) + vi (d∗i ) ∂dij j=1
≥ vi (di1 , . . . , di,m ) where the last inequality is due to the concavity of vi . The lemma follows. 12
□
1 . Theorem 2 The price of anarchy of the auction is at most 1 + ϵ for any ϵ ≥ n−1
Proof We dual objective by the equilibrium’s liquid welfare. Note that, by the definition, bound the ∗ βi ≤ min Wi , vi (di ) . We have: m X j=1
αj +
n X
βi ≤
i=1
≤
m X
g Bj∗
j=1 n X
m X
i=1
j=1
ϵ
+
n X
min Wi , vi (d∗i )
i=1
p∗ij + min
Wi , vi (d∗i )
≤ (1 + ϵ)
n X
min Wi , vi (d∗i )
i=1
where the second equality holds by Lemma 2, and the last inequality follows the RoS and Budget constraints, i.e., the total payment of agent i is less than its valuation and its budget. By the weak duality, the theorem follows. □ Discussion. As a notable consequence of Theorem 2, our result circumvents previously established impossibility results in the context of autobidding [15] and resource allocation mechanisms [5]. A crucial condition in their impossibility result is that an agent’s payment must not exceed their submitted bid. In our mechanism, however, the payment pij (defined in Equation (4)) can exceed bij (but always satisfies Budget and RoS constraints), thus allowing us to bypass this limitation and achieve the improved PoA stated in Theorem 2.
4.1
A modified mechanism
While the only required constraints in auto-bidding setting are Budget and RoS, an additional desirable property in classic mechanism design is that payments do not exceed submitted bids. We propose a modified mechanism that upholds this property under the following mild and realistic assumption: • there exist a publicly known parameter W such that all agents’ bids are bounded by W . Note that in our setting, given a (finite) budget bound Wi , it follows that in proportional mechanisms, whether using the traditional payment rule or the one defined in Equation (4), every agent i will naturally submit bounded bids (depending on its budget Wi ). One can consider parameter W in the assumption as a sufficiently large upper bound of all Wi . 1 . Collect all submitted bids b̃ij ’s and compute Mechanism. Fix an arbitrary constant ϵ ≥ n−1 1 1 modified bids bij := nW max{b̃ij − (n−1)ϵ , 0} for every item 1 ≤ j ≤ m and agent 1 ≤ i ≤ n. Run the proportional mechanism with the payment scheme Equation (4) on the modified bid vectors bij ’s. 1 acts as a threshold to filter bids, serving a role intuitively At a high level, the value of (n−1)ϵ similar (but not the same) to that of a reserve price. The mechanism’s payment is always determined by Equation (4) applied to the modified bids. In this formulation, all modified bids are uniformly 1 1 scaled by a factor of nW (ensuring that bij ≤ n1 ). The scaling and the value of (n−1)ϵ are chosen for the purpose of Lemma 4, and are used solely for payment computation. The allocation in the proportional mechanism can be computed without this scaling factor.
Lemma 4 By the payment scheme defined by Equation (4), it always holds that the payments do not exceed submitted bids, i.e., pij ≤ b̃ij for all i, j. 13
Proof Given the bids b̃ij ’s and the corresponding modified bids bij ’s, let Bj = Equation (4), the payment pij is: P P X Z bij g t + i′ ̸=i bi′ j g i′ ̸=i bi′ j P pij = bi′ j · 2 dt + P (n − 1)ϵ · i′ ̸=i bi′ j 0 t + i′ ̸=i bi′ j i′ ̸=i (n−1)ϵ
≤ Bj since Bj =
bij +
Pn
i=1 bij .
By
1 1 1+(n−1)ϵ B ≤ bij + ≤ b̃ij (n − 1)ϵ j C
Pn
C i=1 bij ≤ 1 and ϵ = n .
□
Theorem 3 For any constant ϵ ≥ 1/(n − 1), let b̃ be a pure Nash equilibrium. Then, the liquid welfare of equilibrium b̃ is at most 1 + ϵ times that of the optimal solution. Proof The proof of this theorem is literally the same as the one in Theorem 2. The only subtle point is to verify that for each item j, there exists a modified bid bij > 0, i.e, there exists a bid b̃ij > nϵ. It is required to use Equation (5) (as a consequence of the KKT conditions) by avoiding the division by 0. In particular, one can observe that in an equilibrium b̃, if for any item j, if b̃i′ j ≤ nϵ for all 1 ≤ i′ ≤ n then an agent i has an incentive to submit a bid bij > nϵ. By doing that, agent i get the entire item j with the payment of 0 (by Equation (4)) and strictly increase its objective (for whatever the value of ρi since its valuation strictly increases and the payment is equal to 0). Hence, for every item j, there exists a modified bid bij > 0. By the same steps in Theorem 2, the theorem follows. □
5
Conclusion
In this paper, we have established the tight PoA bound of 2 for the standard proportional mechanism. Furthermore, we introduced a variant with a modified payment scheme that asymptotically achieves full efficiency as the number of agents increases. Our methodology leverages duality and the KKT conditions from linear and convex programming. The approach may offer broader applications for establishing PoA bounds in the auto-bidding or blockchain settings.
References [1] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In Proc. 15th Conference on Web and Internet Economics, pages 17–30, 2019. [2] Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. Auto-bidding and auctions in online advertising: A survey. ACM SIGecom Exchanges, 22(1): 159–183, 2024. [3] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34: 17777–17788, 2021. [4] Ioannis Caragiannis and Alexandros A. Voudouris. Welfare guarantees for proportional allocations. Theory Comput. Syst., 59(4):581–599, 2016. 14
[5] Ioannis Caragiannis and Alexandros A. Voudouris. The efficiency of resource allocation mechanisms for budget-constrained users. Math. Oper. Res., 46(2):503–523, 2021. [6] George Christodoulou, Alkmini Sgouritsa, and Bo Tang. On the efficiency of the proportional allocation mechanism for divisible resources. Theory Comput. Syst., 59(4):600–618, 2016. [7] Gerard Debreu. A social equilibrium existence theorem. Proceedings of the national academy of sciences, 38(10):886–893, 1952. [8] Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. Efficiency of the firstprice auction in the autobidding world. Advances in Neural Information Processing Systems, 37:139270–139293, 2024. [9] Ky Fan. Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings of the National Academy of Sciences, 38(2):121–126, 1952. [10] Giannis Fikioris and Éva Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proc. 24th Conference on Economics and Computation, pages 678–698, 2023. [11] Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. In 14th Innovations in Theoretical Computer Science Conference, pages 52–1, 2023. [12] Irving L Glicksberg. A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 3(1): 170–174, 1952. [13] Ramesh Johari and John N Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407–435, 2004. [14] Ramesh Johari and John N Tsitsiklis. Efficiency of scalar-parameterized mechanisms. Operations Research, 57(4):823–839, 2009. [15] Christopher Liaw, Aranyak Mehta, and Andres Perlroth. Efficiency of non-truthful auctions in auto-bidding: The power of randomization. In Proceedings of the ACM Web Conference 2023, pages 3561–3571, 2023. [16] Christopher Liaw, Aranyak Mehta, and Wennan Zhu. Efficiency of non-truthful auctions in auto-bidding with budget constraints. In Proceedings of the ACM Web Conference, pages 223–234, 2024. [17] Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. In Proc. 37th Annual Conference on Learning Theory, pages 3642–3643, 2024. [18] Rajiv Maheswaran and Tamer Basar. Efficient signal proportional allocation (espa) mechanisms: Decentralized social welfare maximization for divisible resources. IEEE Journal on Selected Areas in Communications, 24(5):1000–1009, 2006. [19] Aranyak Mehta. Auction design in an auto-bidding setting: Randomization improves efficiency beyond vcg. In Proceedings of the ACM Web Conference, pages 173–181, 2022.
15
[20] Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 211–220. ACM, 2013. [21] Sichao Yang and Bruce Hajek. Vcg-kelly mechanisms for allocation of divisible goods: Adapting vcg mechanisms to one-dimensional signals. IEEE Journal on Selected Areas in Communications, 25(6):1237–1243, 2007.
16