Paper deep dive
Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising
Nguyen Kim Thang
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 4/15/2026, 1:43:44 AM
Summary
This paper analyzes the efficiency of proportional mechanisms in online auto-bidding advertising. It establishes a tight Price of Anarchy (PoA) bound of 2 for the standard proportional mechanism and introduces a modified payment scheme that achieves a PoA bound of 1 + O(1)/(n-1), approaching full efficiency as the number of agents increases. The analysis utilizes linear programming duality and KKT conditions.
Entities (5)
Relation Signals (3)
Proportional Mechanism → haspoabound → 2
confidence 100% · We first establish a tight PoA bound of 2 for the standard proportional mechanism.
Modified Proportional Mechanism → haspoabound → 1 + O(1)/(n-1)
confidence 100% · we introduce a modified version with an alternative payment scheme that achieves a PoA bound of 1 + O(1)/(n-1)
Liquid Welfare → isoptimizedby → Auctioneer
confidence 90% · On the side of the auctioneer, the objective is to maximize the liquid welfare
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 + \frac{O(1)}{n-1}$ where $n \geq 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.12799v1
- Canonical: https://arxiv.org/abs/2604.12799v1
Trouble viewing inline? Open PDF directly →
Full Text
56,132 characters extracted from source content.
Expand or collapse full text
Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising Nguyễn Kim Th´ăng 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−11+ O(1)n-1 where n≥2n≥ 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 auto-bidding systems by advertisers and markets [1]. 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 [2, 1, 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→ℝ≥0v_i:[0,1]^m _≥ 0 which defines its valuation over fractional allocations of items and a private budget WiW_i representing the maximum total amount agent i is willing to pay. We assume that functions viv_i’s are continuous, differentiable, concave, and non-decreasing on every component. For each item j, each agent i submits a bid bij∈ℝ≥0b_ij _≥ 0. After collecting all bids b1j,…,bnjb_1j,…,b_nj on item j, the auctioneer determines the allocation dij∈[0,1]d_ij∈[0,1] such that ∑i=1ndij=1 _i=1^nd_ij=1 and the corresponding payment pij≥0p_ij≥ 0 for each agent i. Let di=(di1,…,di,m)d_i=(d_i1,…,d_i,m) denote the item fractions received by agent i. The valuation of agent i in this allocation is vi(di)v_i(d_i). In the context of online advertising, the valuation vi(di)v_i(d_i) is typically vi(di)=∑j=1mvijdijv_i(d_i)= _j=1^mv_ijd_ij where vij∈ℝ≥0v_ij _≥ 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. • Utility-maximizing objective: vi(di)−∑j=1mpijv_i(d_i)- _j=1^mp_ij. • Valuation-maximizing objective: vi(di)v_i(d_i). • Hybrid objective: vi(di)−ρi∑j=1mpijv_i(d_i)- _i _j=1^mp_ij where 0≤ρi≤10≤ _i≤ 1 is a parameter specific to agent i. This objective generalizes the ones above that correspond to ρi=1 _i=1 and ρi=0 _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 [1]. 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≤n1≤ i≤ n are the budget and the return-on-spend constraints. • Budget constraint (Budget): ∑j=1mpij≤Wi _j=1^mp_ij≤ W_i • Return-on-spend constraint (RoS): vi(di)≥τi⋅∑j=1mpijv_i(d_i)≥ _i· _j=1^mp_ij. By [8], without loss of generality, we can assume τi=1 _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, return-on-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: maxvi(di)−ρi∑j=1mpijsubject to:∑j=1mpij≤Wi(Budget),andvi(di)≥∑j=1mpij(RoS) v_i (d_i )- _i _j=1^mp_ij to: _j=1^mp_ij≤ W_i~( Budget), v_i (d_i )≥ _j=1^mp_ij~( RoS) 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(;,)=∑i=1nminWi,vi(di) Lw( b; v, W)= _i=1^n \W_i,v_i(d_i) \ where =(v1,…,vn) v=(v_1,…,v_n) and =(W1,…,Wn) W=(W_1,…,W_n) are the valuation and budget profiles of agents. It has been observed that liquid welfare is more suitable than the classic social welfare (i.e., ∑i=1nvi(di) _i=1^nv_i(d_i)) 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. 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 bi′=(bi1′,…,bi,m′)b _i=(b _i1,…,b _i,m), ui()≥ui(bi′,−i)u_i( b)≥ u_i(b _i, b_-i) where −i b_-i denotes the bids chosen by all agents other than i in b and uiu_i denote the objective of agent i (which can be its utility, valuation, or hybrid objective with its own parameter ρi _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(,)Lw(;,) Opt( v, W) Lw( b; v, W) where Opt(,) 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 first-price and second-price auctions; scenarios involving only valuation-maximizing agents, only utility-maximizing 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 [1, 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. [1] 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’ constraints RoS Budget + RoS Agents objectives valuation maximizing PoA(FPA) = 2 [15] PoA(FPA) =n=n [16], PoA(q−q-FPA) =2=2 [16] PoA(SPA) = 2 [2] mix: both valuation PoA(FPA) = 2.188 [8] PoA(PM) = 2 and utility maximizing hybrid PoA(m−m-PM) = 1+O(1)n−11+ O(1)n-1 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−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 receives a fraction of bijb1j+…+bn,j b_ijb_1j+…+b_n,j of item j, and the payment of agent i on item j is its bid bijb_ij in the (traditional) proportional mechanism (known also as Kelly mechanism) or in general is a function 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−11+ O(1)n-1 where n≥2n≥ 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→ 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. For the typical valuation functions vi(di)=∑j=1mvijdijv_i(d_i)= _j=1^mv_ijd_ij 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 [2, 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=2n=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-learning-augmented 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 is at most a constant factor away from the optimal liquid welfare. In the single-item setting (i.e., m=1m=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 non-decreasing, concave, and differentiable valuation function vi:[0,1]m→ℝ≥0v_i:[0,1]^m _≥ 0 so that vi(di1,…,dij)v_i(d_i1,…,d_ij) represents the value that agent i achieves by receiving fractions dijd_ij from items j. Additionally, agent i has a private budget WiW_i, which restricts its payment. Each agent 1≤i≤n1≤ i≤ n strategically submits bids bij≥0b_ij≥ 0 on item 1≤j≤m1≤ j≤ m subject to its budget ∑j=1mbij≤Wi _j=1^mb_ij≤ W_i. After collecting all the bids, agent i will receive a fraction of bijb1,j+…+bn,j b_ijb_1,j+…+b_n,j of item j, that is proportional to its submitted bid bijb_ij on item j. In the traditional proportional mechanism (Kelly mechanism), the payment pijp_ij of agent i on item j is its submitted bid bijb_ij. Different payment schemes have been proposed [18, 21, 14]. In this paper, we consider the following scheme inspired by the one in [18]. pij=(∑i′≠ibi′j)⋅∫0bijg(t+∑i′≠ibi′j)(t+∑i′≠ibi′j)2t+h(∑i′≠ibi′j)p_ij= ( _i ≠ ib_i j )· _0^b_ij g (t+ _i ≠ ib_i j ) (t+ _i ≠ ib_i j )^2dt+h ( _i ≠ ib_i j ) (1) where g:ℝ≥0→ℝ≥0g:R_≥ 0 _≥ 0 is a non-decreasing function and h:ℝ≥0→ℝ≥0h:R_≥ 0 _≥ 0 is a function independent of bijb_ij. The traditional proportional mechanism corresponds to the case where g(u)=u2∑i′≠ibi′jg(u)= u^2 _i ≠ ib_i j and h≡0h≡ 0. Recall that the liquid welfare is ∑i=1nminWi,vi(bi1bi1+…+bi,m,…,bi,mbi1+…+bi,m) _i=1^n \W_i,v_i ( b_i1b_i1+…+b_i,m,…, b_i,mb_i1+…+b_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)=1Cu2+rg(u)= 1Cu^2+r with r≥0r≥ 0. Proof Recall that the problem of each agent i with its parameter 0≤ρi≤10≤ _i≤ 1 is the following maxvi(di)−ρi∑j=1mpijsubject to:∑j=1mpij≤Wi(Budget),andvi(di)≥∑j=1mpij(RoS) v_i (d_i )- _i _j=1^mp_ij to: _j=1^mp_ij≤ W_i~( Budget), v_i (d_i )≥ _j=1^mp_ij~( RoS) where in the proportional mechanism dij=bijb1,j+…+bn,jd_ij= b_ijb_1,j+…+b_n,j. By the classic theorem of [7, 9, 12], a pure Nash equilibrium exists if the three following conditions hold: (i) compact and convex of the strategy set of each agent; (i) continuity of each agent’s objective w.r.t the strategy profile; and (i) quasiconcavity of the agent objective in the agent strategy set. By the definition of payments and assumption on the functions viv_i (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 pijp_ij is a convex function on bijb_ij. In particular, for function g(u)=1Cu2+rg(u)= 1Cu^2+r with r≥0r≥ 0 and C is a non-negative constant, the second derivation of pijp_ij w.r.t bijb_ij is 1rC(∑i′≠ibi′j)⋅(bij+∑i′≠ibi′j)r−1≥0 1rC ( _i ≠ ib_i j )· (b_ij+ _i ≠ ib_i j )^r-1≥ 0 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 advertising settings, especially when working with typical valuation functions vi(di)=∑j=1mvijdijv_i(d_i)= _j=1^mv_ijd_ij. Specifically, given a proportional mechanism with payment pijp_ij, do the following. For each item j, given bids b1j,…,bn,jb_1j,…,b_n,j, assign item j to agent i with probability bijb1j+…+bn,j b_ijb_1j+…+b_n,j and charge agent i a payment of b1j+…+bn,jbijpij b_1j+…+b_n,jb_ijp_ij. Hence, the expected valuation of agent i is ∑j=1mbijb1j+…+bn,jvij _j=1^m b_ijb_1j+…+b_n,jv_ij and its expected payment is ∑j=1mpij _j=1^mp_ij — 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ε>0. Let (ϵ)=k⋅ϵ:0≤k≤1ϵ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) of items to agents is a set S=(i,j,dij):1≤i≤n,1≤j≤m,dij∈S=\(i,j,d_ij):1≤ i≤ n,1≤ j≤ m,d_ij \ such that ∑i=1ndij≤1 _i=1^nd_ij≤ 1 for all items 1≤j≤m1≤ j≤ m. Intuitively, a tuple (i,j,dij)(i,j,d_ij) means that a fraction dijd_ij of item j is assigned to agent i. Denote S a set of all (fractional) assignments. Let cSc_S be the total effective welfare of the assignment S, i.e., cS=∑i=1nminWi,vi(di,1,…,di,m)c_S= _i=1^n \W_i,v_i(d_i,1,…,d_i,m)\ where dijd_ij is the fraction of item j that agent i receives in the assignment S for 1≤i≤n1≤ i≤ n and 1≤j≤m1≤ j≤ m. Let zSz_S be a 0-1 variable indicating whether the assignment is chosen. Consider the following formulation. max∑S∈ _S cSzS c_S\ z_S (αj) ( _j) ∑i=1n∑dijdij∑S:(i,j,dij)∈SzS _i=1^n _d_ijd_ij _S:(i,j,d_ij)∈ Sz_S =1 =1 ∀j ∀ j (β) (β) ∑S∈zS _S z_S =1 =1 zS z_S ∈0,1 ∈\0,1\ ∀S∈ ∀ S min∑j=1mαj _j=1^m _j +β +β ∑(i,j,dij)∈Sdijαj+β _(i,j,d_ij)∈ Sd_ij _j+β ≥cS ≥ c_S ∀S∈ ∀ S In the formulation, the second constraint guarantees that an assignment must be selected. Moreover, by the integral constraint zS∈0,1z_S∈\0,1\, there is exactly one selected assignment, i.e., all zSz_S’s but one are equal to 0. To understand the first constraint, observe that if one fixes an item j, an agent i, and an assigned fraction dijd_ij of j to agent i, the sum ∑S:(i,j,dij)∈SzS _S:(i,j,d_ij)∈ Sz_S equals to 1 iff zS=1z_S=1 for some S that contains (i,j,dij)(i,j,d_ij), or equals to 0 if zS=0z_S=0 for all S that contain (i,j,dij)(i,j,d_ij). In other words, the value of ∑S:(i,j,dij)∈SzS _S:(i,j,d_ij)∈ Sz_S (which equals either 0 or 1) indicates whether agent i receives exactly the fraction of dijd_ij of item j in the solution. Therefore, summing up over all fractions in D, the term ∑dij∈dij⋅∑S:(i,j,dij)∈SzS _d_ij d_ij· _S:(i,j,d_ij)∈ Sz_S represents the fraction of item j attributed to agent i. Consequently, the constraint ∑i=1n∑dij∈dij⋅∑S:(i,j,dij)∈SzS=1 _i=1^n _d_ij d_ij· _S:(i,j,d_ij)∈ Sz_S=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 zSz_S, 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 dij∗(∗)=bij∗/(b1,j∗+…+bn,j∗)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 from the context, for simplicity, we drop the parameter ∗ b^* and simply use dij∗d^*_ij. Moreover, denote Bj∗=∑i=1nbij∗B^*_j= _i=1^nb^*_ij for every item 1≤j≤m1≤ j≤ m. In the mechanism, the payments equal the corresponding bids. The problem of agent i is the following. maxbi1,…,bi,mvi(bi1bi1+∑i′≠ibi′,1∗,…,bi,mbi,m+∑i′≠ibi′,m∗ _b_i1,…,b_i,m~v_i ( b_i1b_i1+ _i ≠ ib^*_i ,1,…, b_i,mb_i,m+ _i ≠ ib^*_i ,m )−ρi∑j=1mb∗ij )- _i _j=1^mb^*_ij (λi) ( _i) ∑j=1mbij _j=1^mb_ij ≤Wi ≤ W_i (Budget) ( Budget) (μi) ( _i) vi(bi1bi1+∑i′≠ibi′,1∗,…,bi,mbi,m+∑i′≠ibi′,m∗) v_i ( b_i1b_i1+ _i ≠ ib^*_i ,1,…, b_i,mb_i,m+ _i ≠ ib^*_i ,m ) ≥∑j=1mbij ≥ _j=1^mb_ij (RoS) ( RoS) (ξij) ( _ij) bij b_ij ≥0∀1≤j≤m ≥ 0 ∀ 1≤ j≤ m Recall that, in the above program, if i is utility-maximizing agent, ρi=1 _i=1, and if i is valuation-maximizing agent, ρi=0 _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 Lagrangian w.r.t variables bijb_ij) reads: for every 1≤j≤m1≤ j≤ m, ∑i′≠ibi′,j∗(∑i′=1nbi′,j∗)2 _i ≠ ib^*_i ,j ( _i =1^nb^*_i ,j )^2 ⋅∂vi(di1∗,…,di,m∗)∂dij−ρi−λi+ξij · ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij- _i- _i+ _ij +μi(∑i′≠ibi′,j∗(∑i′=1nbi′,j∗)2⋅∂vi(di1∗,…,di,m∗)∂dij−1)=0 + _i ( _i ≠ ib^*_i ,j ( _i =1^nb^*_i ,j )^2· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij-1 )=0 Hence, (1−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij=μi+ρi+λi−ξij1+μiBj∗∀1≤j≤m (1-d^*_ij)· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij= _i+ _i+ _i- _ij1+ _iB^*_j ∀ 1≤ j≤ m If ∑j=1mbij∗<Wi _j=1^mb^*_ij<W_i (so λi=0 _i=0 by the slackness complementary condition) and bij∗>0b^*_ij>0 (so ξij=0 _ij=0) then for every (either valuation-maximizing or utility-maximizing) agent i, it holds that (1−dij∗)∂vi(di1∗,…,di,m∗)∂dij=ρi+μi1+μiBj∗≤Bj∗∀1≤j≤m (1-d^*_ij) ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij= _i+ _i1+ _iB^*_j≤ B^*_j ∀ 1≤ j≤ m (2) In particular, if i is a utility-maximizing agent (i.e., ρi=1 _i=1) and ∑j=1mbij∗<Wi _j=1^mb^*_ij<W_i and bij∗>0b^*_ij>0, then the inequality in Equation 2 becomes equality. Dual variable definition. Define the dual variables as the following: αj=∑i=1nbij∗=Bj∗ _j= _i=1^nb^*_ij=B^*_j and β=∑i=1nβiβ= _i=1^n _i where variables βi _i are defined in the following. • if i is valuation-maximizing agent then βi=minWi,vi(di∗) _i= \W_i,v_i(d^*_i)\ • if i is utility-maximizing agent then βi=Wiif vi(di1∗,…,di,m∗)≥Wi,2vi(di1∗,…,dim∗)−∑j=1mdij∗⋅(1−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dijotherwise. _i= casesW_i&if v_i(d^*_i1,…,d^*_i,m)≥ W_i,\\ 2v_i(d^*_i1,…,d^*_im)- _j=1^md^*_ij·(1-d^*_ij)· ∂ v_i(d^*_i1,…,d^*_i,m)∂ d_ij&otherwise. cases Lemma 1 The dual variables defined above are feasible. Proof Fix an arbitrary (fractional) assignment S (consisting of tuples (i,j,dij)(i,j,d_ij)). The dual constraint reads: ∑(i,j,dij)∈Sdij⋅αj+β _(i,j,d_ij)∈ Sd_ij· _j+β ≥cS ≥ c_S ⇔∑(i,j,dij)∈SdijBj∗+∑i=1nβi _(i,j,d_ij)∈ Sd_ijB^*_j+ _i=1^n _i ≥∑i=1nminWi,vi(di,1,…,di,m) ≥ _i=1^n \W_i,v_i(d_i,1,…,d_i,m)\ To prove the above inequality, it is sufficient to prove that for every fixed agent 1≤i≤n1≤ i≤ n: ∑j=1mdijBj∗+βi≥minWi,vi(di,1,…,di,m) _j=1^md_ijB^*_j+ _i≥ \W_i,v_i(d_i,1,…,d_i,m)\ (3) Fix an agent i. If βi=Wi _i=W_i, then Equation 3 follows trivially. Until the end of the proof, assume that βi≠Wi _i≠ W_i. We consider different cases. Case 1: i is valuation-maximizing agent. As βi≠Wi _i≠ W_i, it implies βi=vi(di∗) _i=v_i(d^*_i) and vi(di∗)<Wiv_i(d^*_i)<W_i. By Equation 2, we have ∑j=1mdijBj∗+βi _j=1^md_ijB^*_j+ _i ≥∑j=1mdij(1−dij∗)∂vi(di1∗,…,di,m∗)∂dij+vi(di∗) ≥ _j=1^md_ij(1-d^*_ij) ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij+v_i(d^*_i) ≥∑j=1m(dij−dij∗)∂vi(di1∗,…,di,m∗)∂dij+vi(di∗) ≥ _j=1^m(d_ij-d^*_ij) ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij+v_i(d^*_i) ≥vi(di1,…,di,m)≥minWi,vi(di1,…,di,m) ≥ v_i(d_i1,…,d_i,m)≥ \W_i,v_i(d_i1,…,d_i,m)\ where the second inequality holds since dij≤1d_ij≤ 1 and the last inequality follows the concavity of viv_i. Case 2: i is utility-maximizing agent. As βi≠Wi _i≠ W_i, it means that βi=2vi(di1∗,…,dim∗)−∑j=1mdij∗(1−dij∗)∂vi(di1∗,…,di,m∗)∂dij _i=2v_i(d^*_i1,…,d^*_im)- _j=1^md^*_ij(1-d^*_ij) ∂ v_i(d^*_i1,…,d^*_i,m)∂ d_ij (and also, vi(di∗)<Wiv_i(d^*_i)<W_i). By Equation 2 and definition of βi _i, we have ∑j=1mdijBj∗+βi _j=1^md_ijB^*_j+ _i ≥∑j=1mdij(1−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij+2vi(di1∗,…,dim∗)−∑j=1mdij∗(1−dij∗)∂vi(di1∗,…,di,m∗)∂dij ≥ _j=1^md_ij (1-d^*_ij )· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij+2v_i(d^*_i1,…,d^*_im)- _j=1^md^*_ij(1-d^*_ij) ∂ v_i(d^*_i1,…,d^*_i,m)∂ d_ij =vi(di1∗,…,dim∗)+vi(di1∗,…,dim∗)+∑j=1m(dij−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij =v_i(d^*_i1,…,d^*_im)+v_i(d^*_i1,…,d^*_im)+ _j=1^m (d_ij-d^*_ij )· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij −∑j=1mdij∗(dij−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij - _j=1^md^*_ij (d_ij-d^*_ij )· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij ≥vi(di1∗,…,dim∗)+vi(di1,…,dim)−∑j=1mdij∗(dij−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij ≥ v_i(d^*_i1,…,d^*_im)+v_i(d_i1,…,d_im)- _j=1^md^*_ij (d_ij-d^*_ij )· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij ≥vi(di1,…,dim)+vi(di1∗,…,dim∗)−∑j=1mdij∗⋅∂vi(di1∗,…,di,m∗)∂dij ≥ v_i(d_i1,…,d_im)+v_i(d^*_i1,…,d^*_im)- _j=1^md^*_ij· ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij ≥vi(di1,…,dim)+vi(0,…,0)≥vi(di1,…,dim) ≥ v_i(d_i1,…,d_im)+v_i(0,…,0)≥ v_i(d_i1,…,d_im) The first and third inequalities are due to the concavity of vi(⋅)v_i(·). The second inequality holds since dij,dij∗≤1d_ij,d^*_ij≤ 1 and so dij−dij∗≤1d_ij-d^*_ij≤ 1. The last inequality follows vi(0,…,0)≥0v_i(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 of the (arbitrary) equilibrium ∗ b^* and the dual objective of the defined dual solution. The former is ∑i=1nminWi,vi(di∗) _i=1^n \W_i,v_i(d^*_i)\ whereas the latter is ∑j=1mαj+∑i=1nβi=∑j=1m∑i=1nbij∗+∑i=1nβi=∑i=1n(∑j=1mbij∗+βi) _j=1^m _j+ _i=1^n _i= _j=1^m _i=1^nb^*_ij+ _i=1^n _i= _i=1^n( _j=1^mb^*_ij+ _i). Again, it is sufficient to prove that for each 1≤i≤n1≤ i≤ n, ∑j=1mbij∗+βi≤2minWi,vi(di∗). _j=1^mb^*_ij+ _i≤ 2 \W_i,v_i(d^*_i)\. If i is valuation-maximizing agent, ∑j=1mbij∗≤minWi,vi(di∗) _j=1^mb^*_ij≤ \W_i,v_i(d^*_i)\. By definition of dual variables, βi=minWi,vi(di∗) _i= \W_i,v_i(d^*_i)\. Therefore, the above inequality follows. In the following, consider a utility-maximizing agent i. Case 1: βi=Wi _i=W_i. This case also means that vi(di∗)≥Wiv_i(d^*_i)≥ W_i. Therefore, ∑j=1mbij∗+βi=∑j=1mbij∗+Wi≤2Wi=2minWi,vi(di∗)]. _j=1^mb^*_ij+ _i= _j=1^mb^*_ij+W_i≤ 2W_i=2 \W_i,v_i(d^*_i)\ ]. Case 2: βi≠Wi _i≠ W_i. By definition of βi _i, the case assumption implies vi(di∗)≤Wiv_i(d^*_i)≤ W_i and ∑j=1mbij∗<Wi _j=1^mb^*_ij<W_i. (Otherwise, if ∑j=1mbij∗=Wi _j=1^mb^*_ij=W_i then by the non-negativity of agent i’s utility, vi(di∗)≥∑j=1mbij∗=Wiv_i(d^*_i)≥ _j=1^mb^*_ij=W_i and that implies βi=Wi _i=W_i — contradicting to the case assumption.) Hence, ∑j=1mbij∗+βi _j=1^mb^*_ij+ _i =∑j=1mbij∗+2vi(di1∗,…,dim∗)−∑j=1mdij∗(1−dij∗)⋅∂vi(di1∗,…,di,m∗)∂dij = _j=1^mb^*_ij+2v_i(d^*_i1,…,d^*_im)- _j=1^md^*_ij(1-d^*_ij)· ∂ v_i(d^*_i1,…,d^*_i,m)∂ d_ij =∑j:bij∗≠0bij∗+2vi(di1∗,…,dim∗)−∑j:bij∗≠0dij∗Bj∗ = _j:b^*_ij≠ 0b^*_ij+2v_i(d^*_i1,…,d^*_im)- _j:b^*_ij≠ 0d^*_ijB^*_j =∑j:bij∗≠0bij∗+2vi(di1∗,…,dim∗)−∑j:bij∗≠0bij∗ = _j:b^*_ij≠ 0b^*_ij+2v_i(d^*_i1,…,d^*_im)- _j:b^*_ij≠ 0b^*_ij =2vi(di1∗,…,dim∗)=2minWi,vi(di∗) =2v_i(d^*_i1,…,d^*_im)=2 \W_i,v_i(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 _i). Fix an arbitrarily small constant ϵ≥1n−1ε≥ 1n-1. The payment is specifically in the form of Equation 1 in which function g(u)=u1+(n−1)ϵg(u)=u^1+(n-1)ε and h(u)=g(u)(n−1)ϵh(u)= g(u)(n-1)ε. This choice of function g will be clear later. The payment is explicitly given in Section 4. To guarantee the existence of pure Nash equilibria, by Proposition 1, one needs to choose ϵε such that 1+(n−1)ϵ≥21+(n-1)ε≥ 2, that explains the condition ϵ≥1n−1ε≥ 1n-1. Let ∗ b^* be an arbitrary pure Nash equilibrium and let dij∗(∗)d^*_ij( b^*) be the fraction of item j assigned to agent i by the proportional mechanism given ∗ b^*. When ∗ b^* is clear from the context, for simplicity, we drop the parameter ∗ b^* and simply use dij∗d^*_ij. Moreover, denote Bj∗=∑i=1nbij∗B^*_j= _i=1^nb^*_ij for every item 1≤j≤m1≤ j≤ m. We recall the problem of (hybrid) agent i with a new payment scheme. maxbi1,…,bi,mvi(bi1bi1+∑i′≠ibi′,1∗,…,bi,mbi,m+∑i′≠ibi′,m∗)−ρi⋅∑j=1mpij _b_i1,…,b_i,m~v_i ( b_i1b_i1+ _i ≠ ib^*_i ,1,…, b_i,mb_i,m+ _i ≠ ib^*_i ,m )- _i· _j=1^mp_ij pij=(∑i′≠ibi′j∗)⋅[∫0bijg(t+∑i′≠ibi′j∗)(t+∑i′≠ibi′j∗)2t+g(∑i′≠ibi′j∗)(n−1)ϵ⋅∑i′≠ibi′j∗] p_ij= ( _i ≠ ib^*_i j )· [ _0^b_ij g (t+ _i ≠ ib^*_i j ) (t+ _i ≠ ib^*_i j )^2dt+ g ( _i ≠ ib^*_i j )(n-1)ε· _i ≠ ib^*_i j ] ∀1≤j≤m ∀ 1≤ j≤ m (4) (λi) ( _i) ∑j=1mpij≤Wi _j=1^mp_ij≤ W_i (Budget) ( Budget) (μi) ( _i) vi(bi1bi1+∑i′≠ibi′,1∗,…,bi,mbi,m+∑i′≠ibi′,m∗)≥∑j=1mpij v_i ( b_i1b_i1+ _i ≠ ib^*_i ,1,…, b_i,mb_i,m+ _i ≠ ib^*_i ,m )≥ _j=1^mp_ij (RoS) ( RoS) (ξij) ( _ij) bij≥0 b_ij≥ 0 ∀1≤j≤m ∀ 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 bijb_ij) reads: for every 1≤i≤n1≤ i≤ n, 1≤j≤m1≤ j≤ m, ∑i′≠ibi′,j∗(∑i′=1nbi′,j∗)2 _i ≠ ib^*_i ,j ( _i =1^nb^*_i ,j )^2 ⋅[∂vi(di1∗,…,di,m∗)∂dij−ρi⋅g(∑i′=1nbi′j∗)]+ξij−λi∑i′≠ibi′,j∗(∑i′=1nbi′,j∗)2⋅g(∑i′=1nbi′j∗) · [ ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij- _i· g ( _i =1^nb^*_i j ) ]+ _ij- _i _i ≠ ib^*_i ,j ( _i =1^nb^*_i ,j )^2· g ( _i =1^nb^*_i j ) +μi∑i′≠ibi′,j∗(∑i′=1nbi′,j∗)2⋅[∂vi(di1∗,…,di,m∗)∂dij−g(∑i′=1nbi′j∗)]=0 + _i _i ≠ ib^*_i ,j ( _i =1^nb^*_i ,j )^2· [ ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij-g ( _i =1^nb^*_i j ) ]=0 Consequently, if ∑j=1mpij∗<Wi _j=1^mp^*_ij<W_i (so λi=0 _i=0 by the slackness complementary condition), then, as ξij≥0 _ij≥ 0, it holds that: ∂vi(di1∗,…,di,m∗)∂dij≤ρi+μi1+μig(∑i′=1nbi′j∗)≤g(∑i′=1nbi′j∗)∀i,j ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij≤ _i+ _i1+ _ig ( _i =1^nb^*_i j )≤ g ( _i =1^nb^*_i j ) ∀ i,j (5) Dual variables. Define the dual variables as the following: αj=g(Bj∗) _j=g (B^*_j ) and β=∑i=1nβiβ= _i=1^n _i where βi=vi(di∗)−∑j=1mdij∗∂vi(di1∗,…,di,m∗)∂dij if vi(di∗)<Wi,Wi otherwise. _i= casesv_i(d^*_i)- _j=1^md^*_ij ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij& if v_i(d^*_i)<W_i,\\ W_i& otherwise. cases Lemma 2 For every item 1≤j≤m1≤ j≤ m, it holds that ϵ⋅∑i=1npij∗=g(∑i=1nbij∗)ε· _i=1^np^*_ij=g ( _i=1^nb^*_ij ). Proof Fix an arbitrary item 1≤j≤m1≤ j≤ m. For simplicity, as j is fixed, denote (only in this proof) B−i∗=∑i′≠ibi′j∗B^*_-i= _i ≠ ib^*_i j and B∗=∑i′=1nbi′j∗B^*= _i =1^nb^*_i j without the subindex j. We have: pij∗ p^*_ij =(∑i′≠ibi′j∗)⋅[∫0bij∗g(t+∑i′≠ibi′j∗)(t+∑i′≠ibi′j∗)2t+g(∑i′≠ibi′j∗)(n−1)ϵ⋅∑i′≠ibi′j∗] = ( _i ≠ ib^*_i j )· [ _0^b^*_ij g (t+ _i ≠ ib^*_i j ) (t+ _i ≠ ib^*_i j )^2dt+ g ( _i ≠ ib^*_i j )(n-1)ε· _i ≠ ib^*_i j ] =B−i∗⋅[∫0bij∗g(t+B−i∗)(t+B−i∗)2t+g(B−i∗)(n−1)ϵ⋅B−i∗] =B^*_-i· [ _0^b^*_ij g (t+B^*_-i ) (t+B^*_-i )^2dt+ g (B^*_-i )(n-1)ε· B^*_-i ] By the choice of g(u)=e(1+(n−1)ϵ)lnu=u1+(n−1)ϵg(u)=e^(1+(n-1)ε) u=u^1+(n-1)ε, we have ∫0bij∗g(t+B−i∗)(t+B−i∗)2t _0^b^*_ij g (t+B^*_-i ) (t+B^*_-i )^2dt =∫0bij∗1(t+B−i∗)1−(n−1)ϵt=1(n−1)ϵ[(B∗)(n−1)ϵ−(B−i∗)(n−1)ϵ] = _0^b^*_ij 1 (t+B^*_-i )^1-(n-1)εdt= 1(n-1)ε [(B^*)^(n-1)ε-(B^*_-i)^(n-1)ε ] =1(n−1)ϵ[(B∗)1+(n−1)ϵB∗−(B−i∗)1+(n−1)ϵB−i∗] = 1(n-1)ε [ (B^*)^1+(n-1)εB^*- (B^*_-i)^1+(n-1)εB^*_-i ] =1(n−1)ϵ[g(B∗)B∗−g(B−i∗)B−i∗] = 1(n-1)ε [ g(B^*)B^*- g(B^*_-i)B^*_-i ] (6) Therefore, ∑i=1npij∗ _i=1^np^*_ij =∑i=1n1(n−1)ϵB−i∗g(B∗)B∗=1(n−1)ϵg(B∗)B∗∑i=1nB−i∗=1ϵg(B∗) = _i=1^n 1(n-1)εB^*_-i g(B^*)B^*= 1(n-1)ε g(B^*)B^* _i=1^nB^*_-i= 1εg(B^*) where ∑i=1nB−i∗=(n−1)B∗ _i=1^nB^*_-i=(n-1)B^*. □ Remark. We choose g(u)=e(1+(n−1)ϵ)lnu=u1+(n−1)ϵg(u)=e^(1+(n-1)ε) u=u^1+(n-1)ε to fullfil Lemma 2. Specifically, g(u)=e(1+(n−1)ϵ)lnug(u)=e^(1+(n-1)ε) u is a solution of the following differential equation: du(g(u)(n−1)ϵ⋅u)=g(u)u2 ddu ( g(u)(n-1)ε· u )= g(u)u^2 This equation is needed in the proof of Lemma 2, specifically, Section 4. Lemma 3 The dual variables defined above are feasible. Proof Fix an arbitrary (fractional) assignment S (consisting of tuples (i,j,dij)(i,j,d_ij)). The dual constraint reads: ∑(i,j,dij)∈Sdij⋅αj+β _(i,j,d_ij)∈ Sd_ij· _j+β ≥cS ≥ c_S ⇔∑(i,j,dij)∈Sdijg(Bj∗)+∑i=1nβi _(i,j,d_ij)∈ Sd_ijg(B^*_j)+ _i=1^n _i ≥∑i=1nminWi,vi(di,1,…,di,m) ≥ _i=1^n \W_i,v_i(d_i,1,…,d_i,m) \ To prove the above inequality, it is sufficient to prove that for every fixed agent 1≤i≤n1≤ i≤ n: ∑j=1mdijg(Bj∗)+βi≥minWi,vi(di,1,…,di,m) _j=1^md_ijg(B^*_j)+ _i≥ \W_i,v_i(d_i,1,…,d_i,m) \ (7) Fix an agent i. If βi=Wi _i=W_i then Equation 7 holds trivially. Assume that βi<Wi _i<W_i. By definition of βi _i and the RoS constraint, it implies that ∑j=1mpij∗≤vi(di∗)<Wi _j=1^mp^*_ij≤ v_i(d^*_i)<W_i. By Equation 5, we have ∑j=1mdijg(Bj∗)+βi _j=1^md_ijg (B^*_j )+ _i ≥∑j=1mdij∂vi(di1∗,…,di,m∗)∂dij+vi(di∗)−∑j=1mdij∗∂vi(di1∗,…,di,m∗)∂dij ≥ _j=1^md_ij ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij+v_i(d^*_i)- _j=1^md^*_ij ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij =∑j=1m(dij−dij∗)∂vi(di1∗,…,di,m∗)∂dij+vi(di∗) = _j=1^m(d_ij-d^*_ij) ∂ v_i (d^*_i1,…,d^*_i,m )∂ d_ij+v_i(d^*_i) ≥vi(di1,…,di,m) ≥ v_i(d_i1,…,d_i,m) where the last inequality is due to the concavity of viv_i. The lemma follows. □ Theorem 2 The price of anarchy of the auction is at most 1+ϵ1+ε for any ϵ≥1n−1ε≥ 1n-1. Proof We bound the dual objective by the equilibrium’s liquid welfare. Note that, by the definition, βi≤minWi,vi(di∗) _i≤ \W_i,v_i(d^*_i) \. We have: ∑j=1mαj+∑i=1nβi _j=1^m _j+ _i=1^n _i ≤∑j=1mg(Bj∗)+∑i=1nminWi,vi(di∗) ≤ _j=1^mg (B^*_j )+ _i=1^n \W_i,v_i(d^*_i) \ ≤∑i=1n(ϵ∑j=1mpij∗+minWi,vi(di∗))≤(1+ϵ)∑i=1nminWi,vi(di∗) ≤ _i=1^n (ε _j=1^mp^*_ij+ \W_i,v_i(d^*_i) \ )≤(1+ε) _i=1^n \W_i,v_i(d^*_i) \ 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 pijp_ij (defined in Section 4) can exceed bijb_ij (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 WiW_i, it follows that in proportional mechanisms, whether using the traditional payment rule or the one defined in Section 4, every agent i will naturally submit bounded bids (depending on its budget WiW_i). One can consider parameter W in the assumption as a sufficiently large upper bound of all WiW_i. Mechanism. Fix an arbitrary constant ϵ≥1n−1ε≥ 1n-1. Collect all submitted bids b~ij b_ij’s and compute modified bids bij:=1nWmaxb~ij−1(n−1)ϵ,0b_ij:= 1nW \ b_ij- 1(n-1)ε,0\ for every item 1≤j≤m1≤ j≤ m and agent 1≤i≤n1≤ i≤ n. Run the proportional mechanism with the payment scheme Section 4 on the modified bid vectors bijb_ij’s. At a high level, the value of 1(n−1)ϵ 1(n-1)ε acts as a threshold to filter bids, serving a role intuitively similar (but not the same) to that of a reserve price. The mechanism’s payment is always determined by Section 4 applied to the modified bids. In this formulation, all modified bids are uniformly scaled by a factor of 1nW 1nW (ensuring that bij≤1nb_ij≤ 1n). The scaling and the value of 1(n−1)ϵ 1(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 Section 4, it always holds that the payments do not exceed submitted bids, i.e., pij≤b~ijp_ij≤ b_ij for all i,ji,j. Proof Given the bids b~ij b_ij’s and the corresponding modified bids bijb_ij’s, let Bj=∑i=1nbijB_j= _i=1^nb_ij. By Section 4, the payment pijp_ij is: pij p_ij =(∑i′≠ibi′j)⋅[∫0bijg(t+∑i′≠ibi′j)(t+∑i′≠ibi′j)2t+g(∑i′≠ibi′j)(n−1)ϵ⋅∑i′≠ibi′j] = ( _i ≠ ib_i j )· [ _0^b_ij g (t+ _i ≠ ib_i j ) (t+ _i ≠ ib_i j )^2dt+ g ( _i ≠ ib_i j )(n-1)ε· _i ≠ ib_i j ] ≤Bj(n−1)ϵbij+1(n−1)ϵBj1+(n−1)ϵ≤bij+1C≤b~ij ≤ B_j^(n-1)εb_ij+ 1(n-1)εB_j^1+(n-1)ε≤ b_ij+ 1C≤ b_ij since Bj=∑i=1nbij≤1B_j= _i=1^nb_ij≤ 1 and ϵ=Cnε= Cn. □ Theorem 3 For any constant ϵ≥1/(n−1)ε≥ 1/(n-1), let ~ b be a pure Nash equilibrium. Then, the liquid welfare of equilibrium ~ b is at most 1+ϵ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>0b_ij>0, i.e, there exists a bid b~ij>nϵ 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ϵ b_i j≤ nε for all 1≤i′≤n1≤ i ≤ n then an agent i has an incentive to submit a bid bij>nϵb_ij>nε. By doing that, agent i get the entire item j with the payment of 0 (by Section 4) and strictly increase its objective (for whatever the value of ρi _i since its valuation strictly increases and the payment is equal to 0). Hence, for every item j, there exists a modified bid bij>0b_ij>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] G. Aggarwal, A. Badanidiyuru, S. R. Balseiro, K. Bhawalkar, Y. Deng, Z. Feng, G. Goel, C. Liaw, H. Lu, M. Mahdian, et al. (2024) Auto-bidding and auctions in online advertising: a survey. ACM SIGecom Exchanges 22 (1), p. 159–183. Cited by: §1.1, §1.2, §1. [2] G. Aggarwal, A. Badanidiyuru, and A. Mehta (2019) Autobidding with constraints. In Proc. 15th Conference on Web and Internet Economics, p. 17–30. Cited by: §1.3, Table 1, §1. [3] S. Balseiro, Y. Deng, J. Mao, V. Mirrokni, and S. Zuo (2021) Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems 34, p. 17777–17788. Cited by: §1.3. [4] I. Caragiannis and A. A. Voudouris (2016) Welfare guarantees for proportional allocations. Theory Comput. Syst. 59 (4), p. 581–599. Cited by: item 1, §1.3. [5] I. Caragiannis and A. A. Voudouris (2021) The efficiency of resource allocation mechanisms for budget-constrained users. Math. Oper. Res. 46 (2), p. 503–523. Cited by: item 2, §1.3, §4. [6] G. Christodoulou, A. Sgouritsa, and B. Tang (2016) On the efficiency of the proportional allocation mechanism for divisible resources. Theory Comput. Syst. 59 (4), p. 600–618. Cited by: §1.3. [7] G. Debreu (1952) A social equilibrium existence theorem. Proceedings of the national academy of sciences 38 (10), p. 886–893. Cited by: §2. [8] Y. Deng, J. Mao, V. Mirrokni, H. Zhang, and S. Zuo (2024) Efficiency of the first-price auction in the autobidding world. Advances in Neural Information Processing Systems 37, p. 139270–139293. Cited by: 2nd item, §1.3, §1.3, Table 1, §1. [9] K. Fan (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings of the National Academy of Sciences 38 (2), p. 121–126. Cited by: §2. [10] G. Fikioris and É. Tardos (2023) Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proc. 24th Conference on Economics and Computation, p. 678–698. Cited by: §1.3. [11] J. Gaitonde, Y. Li, B. Light, B. Lucier, and A. Slivkins (2023) Budget pacing in repeated auctions: regret and efficiency without convergence. In 14th Innovations in Theoretical Computer Science Conference, p. 52–1. Cited by: §1.3. [12] I. L. Glicksberg (1952) A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society 3 (1), p. 170–174. Cited by: §2. [13] R. Johari and J. N. Tsitsiklis (2004) Efficiency loss in a network resource allocation game. Mathematics of Operations Research 29 (3), p. 407–435. Cited by: §1.3. [14] R. Johari and J. N. Tsitsiklis (2009) Efficiency of scalar-parameterized mechanisms. Operations Research 57 (4), p. 823–839. Cited by: §1.3, §2. [15] C. Liaw, A. Mehta, and A. Perlroth (2023) Efficiency of non-truthful auctions in auto-bidding: the power of randomization. In Proceedings of the ACM Web Conference 2023, p. 3561–3571. Cited by: item 2, §1.2, §1.3, §1.3, Table 1, §1, §4. [16] C. Liaw, A. Mehta, and W. Zhu (2024) Efficiency of non-truthful auctions in auto-bidding with budget constraints. In Proceedings of the ACM Web Conference, p. 223–234. Cited by: Table 1. [17] B. Lucier, S. Pattathil, A. Slivkins, and M. Zhang (2024) Autobidders with budget and roi constraints: efficiency, regret, and pacing dynamics. In Proc. 37th Annual Conference on Learning Theory, p. 3642–3643. Cited by: §1.3. [18] R. Maheswaran and T. Basar (2006) Efficient signal proportional allocation (espa) mechanisms: decentralized social welfare maximization for divisible resources. IEEE Journal on Selected Areas in Communications 24 (5), p. 1000–1009. Cited by: §1.3, §2. [19] A. Mehta (2022) Auction design in an auto-bidding setting: randomization improves efficiency beyond vcg. In Proceedings of the ACM Web Conference, p. 173–181. Cited by: §1.3, §1.3, §1. [20] V. Syrgkanis and E. Tardos (2013) Composable and efficient mechanisms. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, p. 211–220. Cited by: §1.3. [21] S. Yang and B. Hajek (2007) VCG-kelly mechanisms for allocation of divisible goods: adapting vcg mechanisms to one-dimensional signals. IEEE Journal on Selected Areas in Communications 25 (6), p. 1237–1243. Cited by: §1.3, §2.