<figure><img src="image_1.png" /></figure>

HAL
open science

# Price of Anarchy in Resource Allocation and Auto-Bidding Advertising via Duality in Linear/Convex Programming

Nguyễn Kim Thắng

► To cite this version:

Nguyễn Kim Thắng. Price of Anarchy in Resource Allocation and Auto-Bidding Advertising via Duality in Linear/Convex Programming. 2025. hal-05187001

HAL Id: hal-05187001

https://hal.science/hal-05187001v1

Preprint submitted on 25 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Price of Anarchy in Resource Allocation and Auto-Bidding Advertising via Duality in Linear/Convex Programming

Nguyễn Kim Thắng

LIG, University Grenoble-Alpes, France

## Abstract

Driven by the context of budget-constrained players, liquid welfare has been widely studied across various domains, especially in online advertising. This focus naturally raises both opportunities and challenges in analyzing equilibria and evaluating the efficiency of auctions with liquid welfare objectives.

In this paper, we consider an approach based on duality and the Karush-Kuhn-Tucker (KKT) conditions in linear and convex programming to establish the price of anarchy (PoA) in such auctions. The method is conceptually simple yet effective in deriving PoA bounds, particularly in determining tight bounds for resource allocation and auto-bidding advertising problems.

## 1 Introduction

In an auction/a mechanism, each player $i$ has a private valuation (or type) $v_i$ taking values in a parameter space $\mathcal{V}_i$. Given an action profile $\mathbf{a} = (a_1, \dots, a_n)$ where $a_i \in \mathcal{A}_i$ is a chosen action by player $i$ for $1 \le i \le n$, the auctioneer decides an allocation and a payment $p_i(\mathbf{a})$ for each player $i$. Then, the utility of player $i$ with valuation $v_i$ is defined as $u_i(\mathbf{a}) = v_i(\mathbf{a}) - p_i(\mathbf{a})$. In a mechanism, the social welfare is typically considered as the objective, that is defined as the total valuation of all players: $\mathrm{Sw}(\mathbf{a}; \mathbf{v}) = \sum_{i=1}^n v_i(\mathbf{a})$. However, in more realistic settings in which players $i$ have (private) budgets $W_i$, a more suitable efficiency benchmark is the liquid welfare which is the total valuation of each player capped by her budget, i.e., $\mathrm{Lw}(\mathbf{a}; \mathbf{v}) = \sum_{i=1}^n \min\{W_i, v_i(\mathbf{a})\}$. In particular, liquid welfare is widely motivated and studied in the context of auto-bidding and auctions in online advertising [2]. In this paper, we focus on the liquid welfare and the price of anarchy, a standard measure of auction efficiency, in this benchmark. The price of anarchy (PoA) is defined as the largest ratio between the liquid welfare of an optimal solution and that of an equilibrium.

The price of anarchy (PoA) has been extensively studied across various games, leading to the development of several analytical techniques. Among them, the widely recognized smoothness argument [29, 32] remains the most prominent. This argument is commonly employed to establish PoA bounds in different games and auctions. However, these PoA analyses for liquid welfare tend to be more involved/complex than those for traditional social welfare, as they often require a deeper understanding of equilibrium properties to derive tighter PoA bounds. A crucial aspect of such analyses lies in game-specific characterizations, which often stem from insightful observations and arguments. As noted in [31, 8], extending these characterizations is essential for obtaining tight PoA bounds or similar PoA bounds but for more general equilibrium concepts—yet, for many interesting games, this remains a challenging task. This raises an intriguing question:

*How can we design a more principled, rather than ad hoc, approach for establishing PoA bounds in auctions with liquid welfare?*
In this paper, we consider a unified framework for analyzing PoA, with applications to resource allocation and metagame in auto-bidding settings. (The following descriptions are concise to support the subsequent discussion. For additional details and context, please refer to Section 1.2 and Section 2.)

**Resource Allocation in Auto-Bidding Setting.** In this setting, there are $m$ different divisible items, and they are fractionally distributed among $n$ players. Each player $i$ has a private monotone non-decreasing, concave, and differentiable valuation function $v_i: [0, 1]^m \to \mathbb{R}_{\ge 0}$ so that $v_i(d_{i1}, \dots, d_{ij})$ represents the valuation that player $i$ achieves by receiving fractions $0 \le d_{ij} \le 1$ from items $j$. In the context of online advertising, the valuation $v_i(d_i)$ is typically $v_i(d_i) = \sum_{j=1}^m v_{ij}d_{ij}$ where $v_{ij} \in \mathbb{R}_{\ge 0}$ represents the value player $i$ derives from fully acquiring item $j$. Additionally, player $i$ has a private budget $W_i$, which restricts her payment. Each player $1 \le i \le n$ strategically submits bids $b_{ij} \in \mathbb{R}_{\ge 0}$ on item $1 \le j \le m$. After collecting all bids $b_{1j}, \dots, b_{nj}$ on item $j$, the auctioneer determines for each item $j$ the allocation $d_{ij} \in [0, 1]$ such that $\sum_{i=1}^n d_{ij} = 1$ and the corresponding payment $p_{ij} \ge 0$ for each player $i$. Each player $i$ has a BUDGET constraint $\sum_{j=1}^m p_{ij} \le W_i$, and a ROS (return-on-spend) constraint $v_i(d_i) \ge \tau_i \cdot \sum_{j=1}^m p_{ij}$ where $\tau_i$ is a specific parameter of player $i$ and $d_i = (d_{i1}, \dots, d_{im})$. By [11], w.l.o.g., we can assume that $\tau_i = 1$ for all $i$. Moreover, each player $i$ aims to maximize her own objective of $v_i(d_i) - \rho_i \sum_{j=1}^m p_{ij}$. This hybrid objective encapsulates both the valuation-maximizing and the utility-maximizing ones, corresponding to $\rho_i = 0$ and $\rho_i = 1$, respectively.

We consider the Proportional (Kelly) Mechanism in this setting. After collecting all the bids, player $i$ will receive a fraction of $d_{ij} = \frac{b_{ij}}{b_{1,j} + \dots + b_{n,j}}$ of item $j$, that is proportional to her submitted bid $b_{ij}$ on item $j$ and player $i$ is charged to the total value of submitted bids. Specifically, given a submitted bid vector $b = (b_1, \dots, b_n)$ where $b_i = (b_{i1}, \dots, b_{im})$, the hybrid objective of player $1 \le i \le n$ is

$$v_i \left( \frac{b_{i1}}{b_{1,1} + \dots + b_{n,1}}, \dots, \frac{b_{i,m}}{b_{1,m} + \dots + b_{n,m}} \right) - \rho_i \sum_{j=1}^{m} b_{ij}$$

Player $i$ aims to maximize this objective under the BUDGET constraint $\sum_{j=1}^m b_{ij} \le W_i$, and the ROS constraint $v_i(d_i) \ge \sum_{j=1}^m b_{ij}$. The liquid welfare under the bid vector $b$ is $\sum_{i=1}^n \min\{W_i, v_i(d_i)\}$.

Most of work are done in the classic setting in which players have utility-maximizing objectives. For a single item setting ($m = 1$), after a long line of works including [7, 9], Caragiannis and Voudouris [8] showed the tight PoA bound of 2 for pure Nash equilibria. Their proof is based on a structural characterization of equilibria. [9] considered the multiple-item setting and provided a PoA upper bound of 2.618, which applies to more general classes of equilibria (precisely, coarse-correlated equilibria). However, as observed by [8], extending the characterization in [8] or the smoothness arguments in [7, 9] to achieve tight bounds for general equilibrium concepts seems elusive. Moreover, if players' valuations are general concave function then every mechanism has Bayes-Nash PoA at least $\Omega(\sqrt{m})$ [9].

**Metagame in Auto-Bidding Advertising.** There are $m$ divisible items (impressions) that can be fractionally distributed to $n$ players (advertisers). Each player $i$ has a private monotone non-decreasing, concave, and differentiable valuation function $v_i: [0, 1]^m \to \mathbb{R}_{\ge 0}$ and a private budget $W_i$. Additionally, parameter $\phi_{ij}$ denotes the click-through-rate of each item $j$ for player $i$. An outcome of a mechanism is an allocation $x_i = (x_{i1}, \dots, x_{im})$ of items to each player $i$ and the per-unit prices $p_j \ge 0$ for $1 \le j \le m$. In this outcome, the payment of player $i$ is $t_i = \sum_{j=1}^m p_j x_{ij}$.
and the utility of player i in the first-price pacing equilibrium [10, 14] is

$$u_i = \begin{cases} v_i \left( \left( \max_{1 \le j \le m} \frac{\phi_{ij}}{p_j} \right) \cdot t_i \right) - c_i(t_i) & \text{if } t_i \le W_i, \\ -\infty & \text{otherwise.} \end{cases}$$

where $c_i : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ is the monotone non-decreasing, convex and differentiable cost function mapping from the payment to the disutility of spending money. Notice that the players' utilities are non-quasi-linear in contrast to the popular quasi-linear models in literature. The liquid welfare in this setting is defined as $\sum_{i=1}^n \min\{W_i, c_i^{-1}(v_i(\sum_{j=1}^m \phi_{ij}x_{ij}))\}$.

Feng et al. [14] have proved a tight PoA bound of 2 for pure Nash equilibria. They extended their proof techniques and showed that PoA for mixed Nash equilibria is at most 4. This bound also holds for Bayes-Nash equilibria. The difficulty in proving tight bounds for more general equilibrium concepts relies again on extending the structural properties of such equilibria.

## 1.1 Approach and Results

We consider an approach based on linear programming duality and optimality conditions in convex programming—specifically, the Karush-Kuhn-Tucker (KKT) conditions—to analyze the price of anarchy (PoA) in games and auctions with liquid welfare objectives. Intuitively, analyzing the efficiency of an equilibrium (a local fixed point) under a global objective (liquid welfare) requires extracting local equilibrium properties and linking them to the global objective.

In the framework, we characterize equilibrium structures at the local level using KKT conditions applied to convex programs — those are optimized, and the (local) optimum is achieved by players in an equilibrium. At the global level, we employ a primal-dual approach to bound PoA. Specifically, we formulate a configuration integer program that represents the underlying optimization problem of the given game or auction. 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).

This systematic approach offers a powerful technique for proving PoA bounds. Furthermore, as it is rooted in linear and convex programming, it is both robust and adaptable, extending naturally to more general equilibrium concepts while achieving tight bounds.

Applying the method to resource allocation mechanisms and metagame in the auto-bidding setting, we obtain the following results, completing the picture in terms of equilibrium efficiency for those problems.

1. We establish a tight PoA bound of 2 for pure Nash equilibria in resource allocation settings with multiple items. We then focus on a class of continuous diminishing-return submodular valuation functions (formal definition given in Section 3.2), that captures the diminishing-return phenomenon [5, 33], This class includes the typical valuations $v_i(d_i) = \sum_{j=1}^m v_{ij}d_{ij}$ in online advertising applications. For this setting, we propose a variant of the proportional mechanism that achieves a tight PoA bound of 2 for Bayesian coarse-correlated equilibria. Notably, for these specific valuations, our result surpasses the previously established lower bound of $\Omega(\sqrt{m})$ [9], which applies to general concave valuations.

2. We prove a tight PoA bound of 2 for Bayesian coarse-correlated equilibria in the metagame. The result closes the gap of PoA (in [2, 4]) for mixed equilibria provided in [14] and extends to the general equilibrium concept of coarse-correlated equilibria.
Notably, the KKT conditions provide simple yet powerful characterizations that, when applied in a primal-dual framework, yield tight PoA bounds. Moreover, the approach is robust and extendable to broader equilibrium concepts while preserving its effectiveness.

## 1.2 Further Related Works

**Liquid welfare.** Liquid welfare has been introduced by [12] and, independently by Syrgkanis and Tardos [32], who call it effective welfare, as appropriate and realistic objectives for budget-constrained players. The relevance of the liquid welfare has been emphasized in the surveys [31, 2]. The liquid welfare has been studied in the context of the design of truthful mechanisms (see [12, 22, 23] and the analysis of combinatorial Walrasian equilibria with budgets [13]). In the context of the price of anarchy, it was considered in simultaneous first-price auctions in [3].

**PoA of the proportional mechanism in resource allocation.** The proportional mechanism, also known as the Kelly mechanism, has been studied by [18] in the context of classic social welfare in which the tight PoA bound for pure Nash equilibria has been proven. Relating the classic welfare and the liquid welfare, Syrgkanis and Tardos [32] proved that the social welfare at equilibria of the proportional mechanism is at most a constant factor away from the optimal liquid welfare. For the liquid welfare, Caragiannis and Voudouris [7] showed upper and lower bounds of 2.78 and 2 on the PoA, respectively. Christodoulou et al. [9] improved the upper bound to 2.618 and extended the results to more general settings involving multiple items. The techniques from those papers are in the spirit of the smoothness argument (see [29, 32]), in particular, bounding the utility of each player by the utility she would have when deviating to carefully designed action strategies. Subsequently, Caragiannis and Voudouris [8] have shown a tight PoA bound of 2 for pure Nash equilibria. Beyond the smoothness argument, their technique is based on insightful characterization of pure Nash equilibria. However, it is also a bottleneck to extend for the setting of multiple items.

**Auto-bidding Advertising and PoA.** Auto-bidding systems become increasingly important in the online advertising ecosystem, adopted by advertisers and markets. That subsequently embraces research opportunities and challenges in different topics, including the study of PoA of such systems [2]. The PoA in auto-bidding advertising has been actively studied recently in various auctions [1, 21, 26, 11]. Recently, Deng et al. [11] extended the PoA upper bound of 2 to mixed equilibria in first-price auctions involving valuation-maximizing players subject to (only) RoS constraints. Furthermore, they established a PoA bound of 2.188 in settings with both utility-maximizing and valuation-maximizing players. Our results on proportional mechanisms provide an improved bound in a more general setting. Beyond equilibrium analysis, auto-bidding has been examined under no-regret learning dynamics with theoretical guarantees [15, 16, 24] and in machine-learning-augmented auctions that incorporate predictive models to improve bidding strategies [4, 11].

The first-price pacing equilibrium is introduced by Conitzer et al. [10] to study budgeted players in an advertising market. Subsequently, Feng et al. [14] formalized the meta-game that generally captures the advertisers' game on constraint selection and the bidding game between auto-bidders. They proved a tight PoA bound of 2 for pure Nash equilibria and a PoA upper bound of 4 for mixed Nash equilibria. One key element in their proof is a characterization of the allocation for each player and per-unit prices in the bidding game. Again, extending and improving such characterization is primordial to achieve tight bounds for mixed and even more general classes of equilibria.

**Techniques.** The most popular technique to analyze the PoA of games is the smoothness argument, and a large of the literature mentioned above follows this framework to establish PoA bounds.
However, to derive improved bounds, as observed in particular in [31, 8], a deeper understanding of the equilibrium structure and a technique different from the smoothness one are primordial. Approaches based on linear programming and duality have been proposed in the literature [6, 20, 28]. At a high level, we follow the framework introduced in [28], which employs a primal-dual approach and configuration LPs to study the Price of Anarchy (PoA) of equilibria. Our work distinguishes itself in two key ways. First, we formulate a novel configuration LP that is well-suited for analyzing liquid welfare maximization. Second, we leverage the KKT conditions of an inner convex program to guide the construction of dual-feasible solutions. As a result, our approach contributes new elements that enrich and extend the existing literature on LP-based techniques for PoA analysis.

## 2 Preliminaries

**Equilibrium concepts and the PoA.** In an auction/a mechanism, given player valuations $v_i(\cdot)$ for $1 \le i \le n$ and an action profile $\mathbf{a} = (a_1, \dots, a_n)$, recall that player $i$'s utility is $u_i(\mathbf{a}; v_i) = v_i(\mathbf{a}) - p_i(\mathbf{a})$ where $p_i(\mathbf{a})$ is its payment. A pure Nash equilibrium is an action profile $\mathbf{a}$ such that no player can decrease its cost via a unilateral deviation; that is, for every player $i$ and every strategy $a'_i \in A_i$, $u_i(\mathbf{a}; v_i) \ge u_i(a'_i, \mathbf{a}_{-i}; v_i)$ where $\mathbf{a}_{-i}$ denotes the actions chosen by all players other than $i$ in $\mathbf{a}$. The notion of Nash equilibrium is extended to the following more general equilibrium concepts, such as mixed, correlated, and coarse-correlated equilibria. The most general one is the coarse correlated equilibrium concept [27]. A coarse correlated equilibrium of a game is a joint probability distribution $\sigma$ over the action profile such that:

$$ \mathbb{E}_{\mathbf{a} \sim \sigma}[u_i(\mathbf{a}; v_i)] \ge \mathbb{E}_{\mathbf{a} \sim \sigma}[u_i(a'_i, \mathbf{a}_{-i}; v_i)] $$

for every $i$ and $a'_i \in A_i$. For the details and intuitions about equilibrium concepts, we refer the reader to [30].

Equilibrium concepts extend naturally to incomplete-information settings. In contrast to the full-information settings where private valuations are deterministically determined, in incomplete-information settings the valuation vectors $\mathbf{v}$ (in which each component is the valuation of a player) is drawn from a publicly known distribution $\mathbf{F}$ with density function $f$. Let $\Delta(A_i)$ be the set of probability distributions over the actions in $A_i$. A strategy of a player is a mapping $\sigma_i: V_i \to \Delta(A_i)$ from a valuation $v_i \in V_i$ to a distribution over actions $\sigma_i(v_i) \in \Delta(A_i)$. The notions of pure, mixed, correlated, and coarse-correlated equilibria can be generalized in the incomplete-information settings by taking the expectations over the players' valuations. Those notions are distinguished by the mapping profile $\sigma$ whether it is a deterministic or (independent/correlated/coarse correlated) randomized probability distribution. In general, a strategy profile $\sigma = (\sigma_1, \dots, \sigma_n)$ is a Bayes-Nash equilibrium (BNE) if for every player $i$, for every valuation $v_i \in V_i$, and for every action $a'_i \in A_i$:

$$ \mathbb{E}_{v_{-i} \sim \mathbf{F}_{-i}(v_i)} [\mathbb{E}_{\mathbf{a} \sim \sigma(v)} [u_i(\mathbf{a}; v_i)]] \ge \mathbb{E}_{v_{-i} \sim \mathbf{F}_{-i}(v_i)} [\mathbb{E}_{\mathbf{a} \sim \sigma(v)} [u_i(a'_i, \mathbf{a}_{-i}; v_i)]] $$

where $\mathbf{F}_{-i}(v_i)$ stands for the probability distribution over all players other than $i$ conditioned on the valuation $v_i$ of player $i$.

The price of anarchy of Bayes-Nash equilibria of an auction is defined as

$$ \sup_{\mathbf{F},\sigma} \frac{\mathbb{E}_{v \sim \mathbf{F}} [\mathrm{OPT}(\mathbf{v})]}{\mathbb{E}_{v \sim \mathbf{F}} [\mathbb{E}_{\mathbf{a} \sim \sigma(v)} [\mathrm{LW}(\mathbf{a}; \mathbf{v})]]} $$

where the infimum is taken over Bayes-Nash equilibria $\sigma$ and $\mathrm{OPT}(\mathbf{v})$ is the optimal liquid welfare with valuation profile $\mathbf{v}$. For the definition in complete-information settings, one simply removes the expectation over valuation profile $\mathbf{v}$.
**Resource Allocation in Auto-bidding Setting.** Resource allocation has been extensively studied in mechanism design, both in the context of standard social welfare [18, 25, 19] and liquid welfare [7, 9]. A common assumption in these settings is that players aim to maximize their own utility. However, with recent advances in AI technologies, intelligent models are increasingly acting as virtual consultant players, assisting with strategy formulation and decision-making. These players often operate under more general objectives and constraints than those assumed in traditional models [2]. In particular, the emerging auto-bidding setting presents a richer space of player behaviors. Regarding objectives, a player i may aim to maximize utility (the classic objective in mechanism design) $v_i(d_i) - \sum_{j=1}^{m} p_{ij}$, or to maximize valuation alone $v_i(d_i)$. These can be unified via a hybrid objective of the form: $v_i(d_i) - \rho_i \sum_{j=1}^{m} p_{ij}$ where $0 \le \rho_i \le 1$. In this work, we consider players with such general hybrid objectives (of different $\rho_i$). On the constraints side, in addition to the standard BUDGET constraint $\sum_{j=1}^{m} p_{ij} \le W_i$, there is a return-on-spend RoS constraint $v_i(d_i) \ge \tau_i \cdot \sum_{j=1}^{m} p_{ij}$. By [11], w.l.o.g., we can assume that $\tau_i = 1$ for all i. Note that the RoS constraint generalizes the individual rationality constraint from classic models $v_i(d_i) \ge \sum_{j=1}^{m} p_{ij}$. Motivated by these developments, we study the problem of resource allocation in the auto-bidding setting, where players have hybrid objectives and are subject to both BUDGET and RoS constraints.

**Metagame in Auto-bidding Advertising.** Metagame in auto-bidding advertising has been concisely defined in Section 1. In this section, we provide more context about auto-bidding advertising. There are $n$ players (advertisers) and $m$ divisible items (impressions). For each player $i$, there is a private monotone non-decreasing, concave, and differentiable valuation function $v_i: [0, 1]^m \to \mathbb{R}_{\ge 0}$, a private budget $W_i$, and a monotone non-decreasing, convex and differentiable cost function $c_i: \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ mapping from the payment to the disutility of spending money. The outcome for player $i$ is an allocation $x_i = (x_{i1}, \dots, x_{im}) \in [0, 1]^m$, where $x_{ij}$ is the fraction of item $j$ assigned to $i$, and a payment $t_i \ge 0$. For each player $i$ and each item $j$, there is a corresponding click-through-rate parameter $\phi_{ij}$. Given an outcome $(x_i, t_i)$, player $i$ receives $\sum_{j=1}^{m} \phi_{ij} x_{ij}$ number of clicks and its utility is defined as

$$u_i(x_i, t_i) = \begin{cases} v_i(\sum_{j=1}^{m} \phi_{ij} x_{ij}) - c_i(t_i) & \text{if } t_i \le W_i, \\ -\infty & \text{otherwise.} \end{cases}$$

This general utility definition encompasses several classic ones, such as linear utility, budgeted utility, and value-maximizing utility [14]. We are interested in the first-price pacing equilibrium, introduced by [10] to study budgeted players in an advertising market. Given budgeted players with type $(v_i, W_i, c_i)$, a first-price pacing equilibrium (FPPE) is a tuple $(x, p, t)$ of per-unit prices $p_j \ge 0$ for all items $1 \le j \le m$, of allocation $x_i \in [0, 1]^m$ and payment $t_i$ for all players $1 \le i \le n$ that satisfies the following properties:

* (highest bang-per-buck) if $x_{ij} > 0$ then $j \in \arg\max_{1 \le j' \le m} \frac{v_i \phi_{ij}'}{p_{j'}}$ and $\frac{v_i \phi_{ij}'}{p_j} \ge 1$

* (supply feasibility) $\sum_{i=1}^{n} x_{ij} \le 1$ and equality holds if $p_j > 0$

* (payment) $t_i = \sum_{j=1}^{m} p_j x_{ij}$

* (budget feasibility) $t_i \le W_i$ and equality holds if $\max_{1 \le j' \le m} \frac{v_i \phi_{ij}'}{p_{j'}} > 1$

The FPPE can be interpreted as follows: if we fix the per-unit price $p_j$ for items $1 \le j \le m$, the allocation $x_i$ maximizes the utility of player $i$ subject to the budget $W_i$ without accounting for the
supply feasibility. In our approach, we will refer to this interpretation rather than the previous properties.

A metagame is an auction in which given submitted messages ($v_i, W_i, c_i$) of players, the auctioneer decides an allocation $x_i$ and payment $p_i$ for all players $1 \le i \le n$ induced by the FPPE, assuming that players have budgeted utility with types ($v_i, W_i, c_i$). Feng et al. [14] showed that in the metagame, for given players' types ($v_i, W_i, c_i$), the utility of player $i$ is

$$u_i = \begin{cases} v_i \left( \left( \max_{1 \le j \le m} \frac{\phi_{ij}}{p_j} \right) \cdot t_i \right) - c_i(t_i) & \text{if } t_i \le W_i, \\ -\infty & \text{otherwise.} \end{cases}$$

where $t_i$ is the payment of player $i$ and $p_j$'s are the per-unit prices of the inner FPPE. Given a randomized allocation $x_i$ (following a probability distribution $\sigma_i$) of player $i$, the player $i$'s willingness to pay for allocation $x_i$ is

$$LW_i(x_i) = \min \left\{ W_i, c_i^{-1} \left( \mathbb{E}_{x_i \sim \sigma_i} \left[ v_i \left( \sum_{j=1}^{m} \phi_{ij} x_{ij} \right) \right] \right) \right\}$$

The liquid welfare of a randomized allocation $\boldsymbol{x}$ is $LW(\boldsymbol{x}) = \sum_{i=1}^{n} LW_i(x_i)$.

**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 $\epsilon > 0$. Let $\mathcal{D}(\epsilon) = \{k \cdot \epsilon : 0 \le k \le 1/\epsilon\}$ 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 $\mathcal{D}(\epsilon)$. As $\epsilon$ 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 $\epsilon$ is fixed, we use the notation $\mathcal{D}$ instead of $\mathcal{D}(\epsilon)$ as long as it is clear from the context. A (fractional) assignment (a solution) of items to buyers is a set $S = \{(i, j, d_{ij}) : 1 \le i \le n, 1 \le j \le m, d_{ij} \in \mathcal{D}\}$ such that $\sum_{i=1}^{n} d_{ij} \le 1$ for all items $1 \le j \le m$. Intuitively, a tuple $(i, j, d_{ij})$ means that a fraction $d_{ij}$ of item $j$ is assigned to player $i$. Let $c_S$ be the total liquid welfare of the assignment $S$, i.e., $c_S = \sum_{i=1}^{n} \min\{W_i, v_i(d_{i,1}, \dots, d_{i,m})\}$ where $d_{ij}$ is the fraction of item $j$ that player $i$ receives in the assignment $S$ for $1 \le i \le n$ and $1 \le j \le m$. Let $z_S$ be a 0-1 variable indicating whether the assignment is chosen. Consider the following formulation.

$$\begin{array}{lll}
\max & \displaystyle\sum_{S \subseteq \mathcal{S}} c_S z_S & \\
(\alpha_j) & \displaystyle\sum_{i=1}^{n} \sum_{d_{ij}} d_{ij} \quad \sum_{S:(i,j,d_{ij}) \in \mathcal{S}} z_S = 1 & \forall j \\
(\beta) & \displaystyle\sum_{S \subseteq \mathcal{S}} z_S = 1 & \\
& z_S \in \{0, 1\} & \forall S
\end{array}
\quad
\begin{array}{ll}
\min & \displaystyle\sum_{j=1}^{m} \alpha_j + \beta \\
& \sum_{(i,j,d_{ij}) \in \mathcal{S}} d_{ij} \alpha_j + \beta \ge c_S & \forall S
\end{array}$$

In the formulation, the second constraint guarantees that an assignment must be selected. Moreover, by the integral constraint $z_S \in \{0, 1\}$, there is exactly one selected assignment, i.e., all $z_S$'s but one are equal to 0. To understand the first constraint, observe that if one fixes an item $j$, a player $i$, and an assigned fraction $d_{ij}$ of $j$ to player $i$, the sum $\sum_{S:(i,j,d_{ij}) \in \mathcal{S}} z_S$ equals to 1 iff $z_S = 1$
for some $S$ that contains $(i, j, d_{ij})$, or equals to 0 if $z_S = 0$ for all $S$ that contain $(i, j, d_{ij})$. In other words, the value of $\sum_{S:(i,j,d_{ij}) \in S} z_S$ (which equals either 0 or 1) indicates whether player $i$ receives exactly the fraction of $d_{ij}$ of item $j$ in the solution. Therefore, summing up over all fractions in $D$, the term $\sum_{d_{ij} \in D} d_{ij} \cdot \sum_{S:(i,j,d_{ij}) \in S} z_S$ represents the fraction of item $j$ attributed to player $i$. Consequently, the constraint $\sum_{i=1}^n \sum_{d_{ij} \in D} d_{ij} \cdot \sum_{S:(i,j,d_{ij}) \in S} z_S = 1$ ensures the total fractions of item $j$ assigned to all buyers sum up to 1. The objective is to maximize the total liquid welfare. By relaxing the integrality of $z_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 Resource Allocation in Auto-Bidding Setting

## 3.1 PoA of pure Nash equilibria in Proportional Mechanism

In this section, we settle the PoA of the standard proportional mechanism in the presence of general hybrid players.

Let $b^*$ be an arbitrary pure Nash equilibrium and let $d_{ij}^*(b^*) = b_{i,j}^*/(b_{1,j}^* + \dots + b_{n,j}^*)$ be the fraction of item $j$ assigned to player $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 $d_{ij}^*$. Moreover, denote $B_j^* = \sum_{i=1}^n b_{ij}^*$ for every item $1 \le j \le m$. In the mechanism, the payments equal the corresponding bids. The problem of player $i$ is the following.

$$ (\lambda_i) \qquad \max_{b_{i1}, \dots, b_{i,m}} v_i \left( \frac{b_{i1}}{b_{i1} + \sum_{i' \neq i} b_{i',1}^*}, \dots, \frac{b_{i,m}}{b_{i,m} + \sum_{i' \neq i} b_{i',m}^*} \right) - \rho_i \sum_{j=1}^m b_{ij}^* \qquad \sum_{j=1}^m b_{ij} \le W_i \qquad (\text{BUDGET}) $$

$$ (\mu_i) \qquad v_i \left( \frac{b_{i1}}{b_{i1} + \sum_{i' \neq i} b_{i',1}^*}, \dots, \frac{b_{i,m}}{b_{i,m} + \sum_{i' \neq i} b_{i',m}^*} \right) \ge \sum_{j=1}^m b_{ij} \qquad (\text{ROS}) $$

$$ (\xi_{ij}) \qquad b_{ij} \ge 0 \quad \forall 1 \le j \le m $$

Recall that for in the above program $0 \le \rho_i \le 1$. In particular, if $i$ is utility-maximizing player, $\rho_i = 1$, and if $i$ is valuation-maximizing player, $\rho_i = 0$.

In the equilibrium $b^*$, every player $i$ maximizes its objective w.r.t the constraints. Given that the player valuations are continuous and strictly concave, the KKT condition reads, for every $1 \le j \le m$,

$$ \frac{\sum_{i' \neq i} b_{i',j}^*}{(\sum_{i'=1}^n b_{i',j}^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - \rho_i - \lambda_i + \xi_{ij} \\ + \mu_i \left( \frac{\sum_{i' \neq i} b_{i',j}^*}{(\sum_{i'=1}^n b_{i',j}^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - 1 \right) = 0 \qquad (1) $$
Hence,

$$ (1 - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} = \frac{\mu_i + \rho_i + \lambda_i - \xi_{ij}}{1 + \mu_i} B_j^* \quad \forall 1 \le j \le m \quad (2) $$

Note that all dual variables $\lambda_i$, $\mu_i$ and $\xi_{ij}$ are non-negative.

Consequently, if $\sum_{j=1}^m b_{ij}^* < W_i$ (so $\lambda_i = 0$ by complementary slackness) then for every player $i$, it holds that

$$ (1 - d_{ij}^*) \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} = \frac{\rho_i + \mu_i - \xi_{ij}}{1 + \mu_i} B_j^* \le B_j^* \quad \forall 1 \le j \le m \quad (3) $$

since $\rho_i \le 1$ and $\xi_{ij} \ge 0$. In particular, if $i$ is a utility-maximizing player (so $\rho_i = 1$) and $\sum_{j=1}^m b_{ij}^* < W_i$ (so $\lambda_i = 0$ by complementary slackness) and $b_{ij}^* > 0$ (so $\xi_{ij} = 0$ by complementary slackness), then the inequality in Equation (3) becomes equality.

**Dual variable definition.** Following to our approach, we define the dual variables (for the linear program presented Section 2), prove the feasibility and bound the primal and the dual objectives. Define the dual variables as follows: $\alpha_j = \sum_{i=1}^n b_{ij}^* = B_j^*$ and $\beta = \sum_{i=1}^n \beta_i$ where variables $\beta_i$ are defined as $\beta_i = \min\{W_i, v_i(d_{i1}^*, \dots, d_{im}^*)\}$.

**Lemma 1** The dual variables defined above are feasible.

*Proof* Fix an arbitrary (fractional) assignment $S$ (consisting of tuples $(i, j, d_{ij})$). The dual constraint reads:

$$ \sum_{(i,j,d_{ij}) \in S} d_{ij} \cdot \alpha_j + \beta \ge c_S \\ \Leftrightarrow \sum_{(i,j,d_{ij}) \in S} d_{ij} B_j^* + \sum_{i=1}^n \beta_i \ge \sum_{i=1}^n \min\{W_i, v_i(d_{i,1}, \dots, d_{i,m})\} $$

To prove the above inequality, it is sufficient to prove that for every fixed player $1 \le i \le n$:

$$ \sum_{j=1}^{m} d_{ij} B_j^* + \beta_i \ge \min\{W_i, v_i(d_{i,1}, \dots, d_{i,m})\} \quad (4) $$

Fix an player $i$. If $\beta_i = W_i$, then Equation (4) follows trivially.

Until the end of the proof, assume that $\beta_i \ne W_i$, meaning that $\beta_i = v_i(d_{i1}^*, \dots, d_{i,m}^*) < W_i$. By the ROS constraint, $\sum_j b_{ij}^* \le v_i(d_{i1}^*, \dots, d_{i,m}^*) < W_i$. Therefore, by slackness complementary, $\lambda_i = 0$. Using Equation (3), we have

$$ \begin{aligned} \sum_{j=1}^{m} d_{ij} B_j^* + \beta_i &\ge \sum_{j=1}^{m} d_{ij} (1 - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} + v_i(d_{i1}^*, \dots, d_{im}^*) \\ &\ge \sum_{j=1}^{m} (d_{ij} - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} + v_i(d_{i1}^*, \dots, d_{im}^*) \\ &\ge v_i(d_{i1}, \dots, d_{im}) \end{aligned} $$

The second inequality holds since $d_{ij} \le 1$ and $\frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} \ge 0$. The last inequality follows the concavity of $v_i(\cdot)$.

Combining all the cases above, the lemma holds. $\square$
**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 $\sum_{i=1}^n \min\{W_i, v_i(d_i^*)\}$ whereas the latter is $\sum_{j=1}^m \alpha_j + \sum_{i=1}^n \beta_i = \sum_{j=1}^m \sum_{i=1}^n b_{ij}^* + \sum_{i=1}^n \beta_i = \sum_{i=1}^n (\sum_{j=1}^m b_{ij}^* + \beta_i)$. Again, it is sufficient to prove that for each $1 \le i \le n$,

$$ \sum_{j=1}^{m} b_{ij}^{*} + \beta_{i} \leq 2 \min\{W_{i}, v_{i}(d_{i}^{*})\}. $$

By definition of $\beta_i$, this is equivalent to

$$ \sum_{j=1}^{m} b_{ij}^{*} + \min\{W_i, v_i(d_i^*)\} \leq 2 \min\{W_i, v_i(d_i^*)\}. $$

This inequality holds since $\sum_{j=1}^m b_{ij}^*$ is bounded by both $W_i$ (by BUDGET constraint) and $v_i(d_i^*)$ (by ROS constraint). The theorem follows. $\square$

**Remark.** Caragiannis and Voudouris [8] showed that any mechanism in the resource allocation problem, even in the single-item setting, has PoA at least $2 - 1/n$. Coupling with this lower bound, the PoA bound is 2, and it is tight (when $n$ is large enough). Consequently, it also implies that the considered configuration LP has the tightest integrality gap. Besides, the result of this section holds with a weaker assumption on the valuation functions. As we will see in the next section, one can replace the concavity by the property of concavity in positive direction.

## 3.2 PoA of general equilibria in a modified proportional mechanism

In this section, we focus on settings where each player's valuation is modeled as a DR-submodular function, capturing the diminishing-return phenomenon. A function $v: [0, 1]^m \to \mathbb{R}_{\ge 0}$ is continuous submodular (or diminishing-return (DR) submodular) if for all vectors $d, d' \in [0, 1]^m$ such that $d_j \ge d'_j$ for all $1 \le j \le m$, any basis vector $e_j = (0, \dots, 0, 1, 0, \dots, 0)$ and any constant $\eta > 0$ such that $d + \eta e_j \in [0, 1]^m$, $d' + \eta e_j \in [0, 1]^m$, it holds that

$$ v(d + \alpha e_j) - v(x) \le v(d' + \alpha e_j) - d(d'). $$

This class of functions includes the typical form of valuations in auto-bidding, i.e., $v_i(d_{i1}, \dots, d_{im}) = \sum_{j=1}^m v_{ij}d_{ij}$. Moreover, it also contains the multilinear extensions of submodular functions. A function $f: 2^{[m]} \to \mathbb{R}_{\ge 0}$ is a submodular if $f(S) + f(T) \ge f(S \cup T) + f(S \cap T)$ for every sets $S, T \subseteq \{1, \dots, m\}$. The multilinear extension of $f$ is a function $F: [0, 1]^m \to \mathbb{R}_{\ge 0}$ defined as $F(x) = \sum_{S \subseteq [m]} f(S) \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i)$. The multilinear extension of a submodular function is continuous DR-submodular. In fact, the concept of DR-submodularity captures the diminishing returns property in a continuous domain, generalizing its discrete counterpart. This class of functions has been widely studied in literature with applications in economics, machine learning, etc (see [5, 33] and references therein).

By its definition, a monotone continuous differentiable DR-submodular function $v_i: [0, 1]^m \to \mathbb{R}_{\ge 0}$ satisfies the following properties that we will make use in our analysis.

(i) $v_i$ is continuous differentiable and non-decreasing in every coordinate;
(ii) $v_i$ is concave in positive direction, i.e., $v_i(d'_i) - v_i(d_i) \le (d'_i - d_i) \cdot \nabla v_i(d_i)$ for every $d'_i, d_i$ such that $d'_{ij} \ge d_{ij} \forall 1 \le j \le n$;

(iii) and, $\frac{\partial^2 v_i(d_{i1}, \dots, d_{i,m})}{\partial d_{ij} \partial d_{ij'}} \le 0 \forall 1 \le j, j' \le n$

Building on the technique of the previous section, we propose a modification of the proportional mechanism in which we settle the PoA for the general Bayesian coarse-correlated equilibria.

**A modified mechanism.** Let $\tilde{b}_{ij}$ be the submitted bid of player $i$ on item $j$. Given such bids $\tilde{b}_{ij}$ for all $i, j$, scale them by the same (large) factor $M$ so that $\frac{\tilde{b}_{ij}}{M} \le \frac{n-1}{n}$. Define the modified bids $b_{ij} := \frac{1}{n-1} + \frac{\tilde{b}_{ij}}{M}$ for all $i, j$. Run the proportional mechanism on the modified bids $b_{ij}$'s.

Given a coarse-correlated equilibrium $\tilde{\sigma}$ on the submitted bids, the above affine bid-modification transforms $\tilde{\sigma}$ to a coarse-correlated equilibrium $\sigma$ on modified bids. Until the end of the section, we will consider equilibrium $\sigma$ on modified bids instead of the one on submitted bids.

The goal of player $i$ is to maximize its objective under the constraints over the randomness of other players' valuations and their actions (bids). Given a valuation $v_i(\cdot)$, the problem of player $i$ can be formalized as follows.

$$ \begin{align*} & \max_{b_{i1}, \dots, b_{i,m}} \mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \left[ \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^* (v_i, v_{-i})} \left[ v_i \left( \frac{b_{i1}}{b_{i1} + \sum_{i' \neq i} b_{i',1}^*}, \dots, \frac{b_{i,m}}{b_{i,m} + \sum_{i' \neq i} b_{i',m}^*} \right) - \rho_i \sum_{j=1}^m b_{ij}^* \right] \right] \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad (\lambda_i) \qquad \sum_{j=1}^m b_{ij} \le W_i \qquad (\text{BUDGET}) \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad (\mu_i) \qquad v_i \left( \frac{b_{i1}}{b_{i1} + \sum_{i' \neq i} b_{i',1}^*}, \dots, \frac{b_{i,m}}{b_{i,m} + \sum_{i' \neq i} b_{i',m}^*} \right) \ge \sum_{j=1}^m b_{ij} \qquad (\text{ROS}) \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad (\xi_{ij}) \qquad b_{ij} \ge 0 \quad \forall 1 \le j \le m \end{align*} $$

where recall that $F_{-i}(v_i)$ stands for the probability distribution over all players other than $i$ conditioned on the valuation $v_i$ of player $i$.

In the equilibrium $\sigma^*$, every player $i$ maximizes its (expected) objective w.r.t the constraints. Note that as $v_i$ is not necessarily concave, the KKT condition does not straightforwardly hold. However, the linear independence constraint qualification holds, i.e., the gradients of active constraints are linearly independent at the $b_i^*$. Specifically, the gradient of the ROS constraint has all negative components. The gradient of BUDGET constraint is an all-1 vector; the gradients of the non-negative constraints $b_{ij} \ge 0$ are unit vectors. Nevertheless, the BUDGET constraint and all non-negative constraints cannot hold with equality altogether in the optimal solution $b_i^*$ to player $i$. Hence, all gradients of active constraints are linearly independent. Therefore, the KKT condition holds.

By the KKT condition, for every $1 \le j \le m$, given a fixed valuation $v_i(\cdot)$, for any strategy $b_i^* = (b_{i1}^*, \dots, b_{i,m}^*)$ of player $i$ in the support of $\sigma^*(v_i, v_{-i})$, it holds that

$$ \mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \left[ \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^* (v_i, v_{-i})} \left[ \frac{\sum_{i' \neq i} b_{i',j}^*}{(\sum_{i'=1}^n b_{i',j}^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - \rho_i - \lambda_i + \xi_{ij}} \right. \right. \\ \left. \left. + \mu_i \left( \frac{\sum_{i' \neq i} b_{i',j}^*}{(\sum_{i'=1}^n b_{i',j}^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - 1 \right) \right] \right] = 0 \quad (5) $$
The main difficulty in extending the Price of Anarchy (PoA) analysis from pure equilibria to more general equilibrium concepts lies in handling the expectations over randomness. In particular, one cannot directly multiply both sides of the corresponding equality by $B_j^*$ (which is now a random variable), as was done in the pure equilibrium case, specifically, in deriving Equation (2) from Equation (1).

Denote $B_{-i,j}^* = \sum_{i' \neq i} b_{i',j}^*$. To overcome this obstacle, we should analyze the correlation between random variables, in particular $\frac{B_{-i,j}^*}{(B_j^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}}$ and $B_j^*$. Indeed, the purpose of the bid-modification procedure in the mechanism is to establish the following lemma.

**Lemma 2** Fix $b_{ij}^*$ and consider the randomness over bids of other players $b_{i'}$ for $i' \neq i$. Then, the covariance of random variables $\frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2}$ and $B_{-i,j}^*$ is non-positive. The same holds for the covariance between $\frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2}$ and $B_j^*$ since $b_{ij}^*$ is fixed.

*Proof* A sufficient condition to show that the covariance is non-positive is to prove that for every $b_{i',j}$ where $i' \neq i$, it holds that

$$ \frac{\partial \left( \frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} \right)}{\partial b_{i',j}} \le 0 \quad \text{if} \quad \frac{\partial B_{-i,j}^*}{\partial b_{i',j}} \ge 0 $$

It is equivalent to proving that, if $\frac{\partial B_{-i,j}^*}{\partial b_{i',j}} \ge 0$ then

$$ \frac{\partial \left( \frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2} \right)}{\partial B_{-i,j}^*} \cdot \frac{\partial B_{-i,j}^*}{\partial b_{i',j}} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} + \frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2} \cdot \frac{\partial^2 v_i(d_{i1}^*, \dots, d_{i,m}^*)}{B_{i'} \partial d_{ij} \partial d_{i',j}} \le 0 $$

Given the properties of function $v_i$ (in the beginning of the section), it is sufficient to prove that

$$ \frac{\partial \left( \frac{B_{-i,j}^*}{(B_{-i,j}^*+b_{ij}^*)^2} \right)}{\partial B_{-i,j}^*} \le 0 \qquad (6) $$

For simplicity, in this proof, denote $b = b_{ij}^*$ and $t = B_{-i,j}^*$. Remark that by the bid-modification procedure, $b \le 1$ and $t = \sum_{i' \neq i} b_{ij}^* \ge (n-1)\frac{1}{n-1} = 1$. Consider function $g(t) = \frac{t}{(t+b)^2}$. We have

$$ g'(t) = \frac{b-t}{(t+b)^3} \le 0 \quad \text{since} \quad b \le 1 \le t. $$

Indeed, the bid-modification procedure is designed to make $g'(t) \le 0$. Hence, Equation (6) holds and subsequently, the lemma follows. $\square$

By Equation (5) and Lemma 2, we deduce that, for every $1 \le j \le m$, given a fixed valuation $v_i(\cdot)$, for any strategy $b_i^* = (b_{i1}^*, \dots, b_{im}^*)$ of player $i$ in the support of $\sigma^*(v_i, v_{-i})$:

$$ \begin{aligned} 0 &= \mathbb{E}[B_j^*] \cdot \mathbb{E} \left[ \frac{B_{-i,j}^*}{(B_j^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - \rho_i - \lambda_i + \xi_{ij} + \mu_i \left( \frac{B_{-i,j}^*}{(B_j^*)^2} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - 1 \right) \right] \\ &\ge \mathbb{E} \left[ (1 + \mu_i) \frac{B_{-i,j}^*}{B_j^*} \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{i,m}^*)}{\partial d_{ij}} - (\mu_i + \rho_i + \lambda_i - \xi_{ij}) B_j^* \right] \end{aligned} $$
where the expectation $\mathbb{E}$ stands for $\mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^*(v_i, v_{-i})}$. The inequality holds since for random variables $X, Y$ with $\text{Cov}(X, Y) \le 0$, $\mathbb{E}[X]\mathbb{E}[Y] \ge \mathbb{E}[XY]$.

If $\sum_{j=1}^m b_{ij}^* < W_i$ (so $\lambda_i = 0$), as $0 \le \rho_i \le 1$ and $\mu_i, \xi_{ij} \ge 0$, then $(\mu_i + \rho_i + \lambda_i - \xi_{ij}) \le (1 + \mu_i)$. Therefore,

$$ \mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^*(v_i, v_{-i})} \left[ (1 - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{im}^*)}{\partial d_{ij}} \right] \le \mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^*(v_i, v_{-i})} [B_j^*] \quad (7) $$

The remaining of the analysis is similar to the one in Section 3.1.

**Dual variable definition.** Define the dual variables as follows: $\alpha_j = \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} [B_j^*]$ and $\beta = \sum_{i=1}^n \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} [\beta_i]$ where random variables $\beta_i$'s are defined as $\beta_i = \min\{W_i, v_i(d_{i1}^*, \dots, d_{im}^*)\}$.

**Lemma 3** The dual variables defined above are feasible.

*Proof* Fix an arbitrary (fractional) assignment $S$ (consisting of tuples $(i, j, d_{ij})$). The dual constraint reads:

$$ \sum_{(i,j,d_{ij}) \in S} d_{ij} \cdot \alpha_j + \beta \ge c_S \\ \Leftrightarrow \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} \left[ \sum_{(i,j,d_{ij}) \in S} d_{ij} B_j^* + \sum_{i=1}^n \beta_i \right] \ge \sum_{i=1}^n \min\{W_i, v_i(d_{i1}, \dots, d_{im})\} $$

To prove the above inequality, it is sufficient to prove that for every fixed player $1 \le i \le n$, every fixed valuation $v_i(\cdot)$, for any strategy $b_i^* = (b_{i1}^*, \dots, b_{im}^*)$ of player $i$ in the support of $\sigma^*(v_i, v_{-i})$:

$$ \mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^*(v_i, v_{-i})} \left[ \sum_{j=1}^{m} d_{ij} B_j^* + \beta_i \right] \ge \min\{W_i, v_i(d_{i1}, \dots, d_{im})\} $$

For all events such that $\beta_i = W_i$, the above inequality follows trivially. In the remaining of the proof, we consider all events such that $\beta_i \ne W_i$. It means that $\beta_i = v_i(d_{i1}^*, \dots, d_{im}^*) < W_i$. By the ROS constraint, $\sum_j b_{ij}^* \le v_i(d_{i1}^*, \dots, d_{im}^*) < W_i$. Therefore, by complementary slackness, $\lambda_i = 0$. Using Equation (7), we have (for simplicity, we simply write $\mathbb{E}$ that stands for $\mathbb{E}_{v_{-i} \sim F_{-i}(v_i)} \mathbb{E}_{b_{-i}^* \sim \sigma_{-i}^*(v_i, v_{-i})}$):

$$ \begin{aligned} \sum_{j=1}^{m} d_{ij} \mathbb{E}[B_j^*] + \mathbb{E}[\beta_i] &\ge \sum_{j=1}^{m} d_{ij} \mathbb{E} \left[ (1 - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{im}^*)}{\partial d_{ij}} \right] + \mathbb{E} \left[ v_i(d_{i1}^*, \dots, d_{im}^*) \right] \\ &\ge \sum_{j:d_{ij} \ge d_{ij}^*} d_{ij} \mathbb{E} \left[ (1 - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{im}^*)}{\partial d_{ij}} \right] + \mathbb{E} \left[ v_i(d_{i1}^*, \dots, d_{im}^*) \right] \\ &\ge \mathbb{E} \left[ \sum_{j:d_{ij} \ge d_{ij}^*} (d_{ij} - d_{ij}^*) \cdot \frac{\partial v_i(d_{i1}^*, \dots, d_{im}^*)}{\partial d_{ij}} + v_i(d_{i1}^*, \dots, d_{im}^*) \right] \\ &\ge \mathbb{E} \left[ v_i(d_i') \right] \ge \mathbb{E} \left[ v_i(d_{i1}, \dots, d_{im}) \right] = v_i(d_{i1}, \dots, d_{im}) \end{aligned} $$

where $d_i'$ is the vector such that $d_{ij} = d_{ij}$ if $d_{ij} \ge d_{ij}^*$ and $d_{ij}' = d_{ij}^*$ otherwise for $1 \le j \le m$. In other words, $d_{ij}' = \max\{d_{ij}, d_{ij}^*\}$. The second inequality holds since all terms in the first sum are non-negative and we keep only a subset of them. The third inequality holds since $d_{ij} \le 1$ and
$$ \frac{\partial v_i(d_{i,1}^*,...,d_{i,m}^*)}{\partial d_{ij}} \geq 0. \text{ The fourth inequality follows the concavity in the positive directions of } v_i(\cdot). $$

The last inequality holds because $v_i$ is non-decreasing.

Combining all the cases above, the lemma holds. □

**Theorem 2** The PoA of Bayesian coarse-correlated equilibria for liquid welfare in the modified proportional mechanism is at most 2.

*Proof* We are bounding the liquid welfare of the (arbitrary) equilibrium $\sigma^*$ and the dual objective of the defined dual solution. The former is $\sum_{i=1}^n \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} [\min\{W_i, v_i(d_i^*)\}]$ whereas the latter is

$$ \sum_{j=1}^{m} \alpha_j + \beta = \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} \left[ \sum_{j=1}^{m} \sum_{i=1}^{n} b_{ij}^* + \sum_{i=1}^{n} \beta_i \right] = \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} \left[ \sum_{i=1}^{n} \left( \sum_{j=1}^{m} b_{ij}^* + \beta_i \right) \right] $$

Again, it is sufficient to prove that for each $1 \le i \le n$,

$$ \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} \left[ \sum_{j=1}^{m} b_{ij}^* + \beta_i \right] \le 2 \mathbb{E}_{v \sim F} \mathbb{E}_{b^* \sim \sigma^*(v)} \left[ \min\{W_i, v_i(d_i^*)\} \right] $$

By the BUDGET and ROS constraint, it holds that $\sum_{j=1}^m b_{ij}^* \le \min\{W_i, v_i(d_i^*)\}$. Together with the definition of $\beta_i = \min\{W_i, v_i(d_i^*)\}$, that implies the above inequality. The theorem follows. □

# 4 Metagame in Auto-bidding Advertising

In this section, we study the PoA of the metagame in auto-bidding advertising. We consider the same configuration LP described in Section 2. Given a (fractional) assignment of items to players $S = \{(i, j, d_{ij}) : 1 \le i \le n, 1 \le j \le m, d_{ij} \in \mathcal{D}\}$, the total expected liquid welfare of the assignment $S$ is $c_S = \mathbb{E}_{(v,W,c)}[\sum_{i=1}^n \min\{W_i, v_i(d_{i,1}, \dots, d_{i,m})\}]$ where $d_{ij}$ is the fraction of item $j$ that player $i$ receives in the assignment $S$ for $1 \le i \le n$ and $1 \le j \le m$ and the expectation is taken over players' types. (In the complete-information setting, one simply removes the expectation term in $c_S$.)

Fix $\sigma^*$ an arbitrary Bayesian coarse-correlated equilibrium. Suppose $p^*, x^*$ are the randomized per-unit prices and allocation of the inner FPPE in the equilibrium $\sigma^*(v, W, c)$, respectively. Recall that, in the equilibrium, given fixed players' types and fixed per-unit prices $p^*$, every player $i$ maximizes its expected utility described by the following convex optimization program.

$$ \max u_i(t_i) := v_i \left( \max_{1 \le j \le m} \frac{\phi_{ij}}{p_j^*} \cdot t_i \right) - c_i(t_i) $$

$$ (\lambda_i) \qquad t_i := \sum_{j=1}^{m} p_j^* x_{ij} \le W_i \qquad \forall i $$

$$ (\mu_i) \qquad t_i \ge 0 \qquad \forall i $$

By the KKT conditions, for any realization $x_i^*$ of the allocation of the inner FPPE, it holds that: for every $1 \le i \le n$, there exists Lagrangian multipliers $\lambda_i, \mu_j \ge 0$ such that

$$ \begin{align*} & u_i'(t_i^*) - \lambda_i + \mu_i = 0 \\ \Leftrightarrow \quad & \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \right) \cdot v_i' \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \cdot \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right) - c_i' \left( \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right) - \lambda_i + \mu_i = 0 \end{align*} $$
Moreover, if $t_i^* < W_i$ then by the slackness complementary conditions, $\lambda_i = 0$. In this case, as $\mu_i \ge 0$, we have

$$ \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \right) \cdot v_i' \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \cdot \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right) - c_i' \left( \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right) \le 0 \\ \Leftrightarrow \frac{v_i' \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \cdot \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right)}{c_i' \left( \sum_{j'=1}^{m} p_{j'}^* x_{ij'}^* \right)} \le \min_{1 \le j' \le m} \frac{p_{j'}^*}{\phi_{ij'}} \quad (8) $$

**Dual variables.** Define the dual variables as the following: $\alpha_j = \mathbb{E}_{(v,W,c)}\mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) [p_j^*]$ and $\beta = \mathbb{E}_{(v,W,c)}\mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) [\sum_{i=1}^n \mathrm{LW}_i(x_i^*)]$ where the expectations are taken over the randomness of all players' types and the equilibrium.

**Lemma 4** The dual variables defined above are feasible.

*Proof* Fix an arbitrary (fractional) assignment $S$ consisting of tuples $(i, j, d_{ij})$. Note that $S$ is independent of equilibrium $\sigma^*$. The dual constraint reads:

$$ \sum_{(i,j,d_{ij}) \in S} d_{ij} \cdot \alpha_j + \beta \ge c_S \\ \Leftrightarrow \mathbb{E}_{(v,W,c)}\mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) \left[ \sum_{(i,j,d_{ij}) \in S} d_{ij} p_j + \sum_i \mathrm{LW}_i(x_i^*) \right] \ge \mathbb{E}_{(v,W,c)}\left[ \sum_{i=1}^n \mathrm{LW}_i(d_i) \right] $$

To prove the above inequality, it is sufficient to prove that for every fixed type $(v, W, c)$, a fixed equilibrium $\sigma^*$, fixed per-unit equilibrium price $p^*$, every fixed player $1 \le i \le n$ and randomized allocation $x_i^*$,

$$ \sum_{j=1}^{m} d_{ij} \cdot p_{j}^{*} + \mathrm{LW}_{i}(x_{i}^{*}) \geq \mathrm{LW}_{i}(d_{i}) \quad (9) $$

Recall that

$$ \mathrm{LW}_i(x_i^*) = \min \left\{ W_i, c_i^{-1} \left( \mathbb{E}_{x_i^*} \left[ v_i \left( \sum_{j=1}^m \phi_{ij} x_{ij}^* \right) \right] \right) \right\} $$

where the expectation is taken over the randomness of the equilibrium allocation $x_i^*$. Again, for a fixed assignment $S$, as $d_i = (d_{i1}, \dots, d_{im})$ is fixed,

$$ \mathrm{LW}_i(d_i) = \min \left\{ W_i, c_i^{-1} \left( v_i \left( \sum_{j=1}^m \phi_{ij} d_{ij} \right) \right) \right\} $$

without the expectation term.

Notice that the utility of player $i$ is non-negative in the equilibrium, so

$$ v_i \left( \sum_{j=1}^{m} \phi_{ij} x_{ij}^* \right) \ge c_i \left( \sum_{j=1}^{m} p_j^* x_{ij}^* \right) \Rightarrow c_i^{-1} \left( v_i \left( \sum_{j=1}^{m} p_j^* x_{ij}^* \right) \right) \ge \sum_{j=1}^{m} p_j^* x_{ij}^* \quad (10) $$
First, we consider the event where player i's payment $t_i^* = W_i$, i.e., $\sum_{j=1}^m p_j^* x_{ij}^* = W_i$. Therefore, by the definition of $LW_i$, we have:

$$ 
\begin{aligned}
\mathbb{E}_{x_i^*} [LW_i(x_i^*) | t_i^* = W_i] &= \min \left\{ W_i, c_i^{-1} \left( \mathbb{E}_{x_i^*} \left[ v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right] \right) \middle| t_i^* = W_i \right\} \\
&\ge \min \left\{ W_i, \mathbb{E}_{x_i^*} \left[ c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) \right] \middle| t_i^* = W_i \right\} \\
&\ge \min \left\{ W_i, \mathbb{E}_{x_i^*} \left[ \sum_{j'=1}^m p_{j'} x_{ij'}^* \right] \middle| t_i^* = W_i \right\} \ge W_i
\end{aligned}
$$

where the first inequality is due to Jensen inequality (applied to concave function $c_i^{-1}$); the second one is due to Equation (10) and the last one is by the event assumption. We deduce that

$$ \mathbb{E}_{x_i^*} [LW_i(x_i^*) | t_i^* = W_i] + \sum_{j=1}^{m} d_{ij} \cdot p_j^* \geq W_i \geq LW_i(d_i) $$

In the following, consider the event where $t_i^* < W_i$. For any realization $x_i^*$, we have:

$$ 
\begin{aligned}
& c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j=1}^m d_{ij} \cdot p_j^* \\
&= c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j:p_j^* > 0} d_{ij} \cdot \phi_{ij} \cdot \frac{p_j^*}{\phi_{ij}} \\
&\ge c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j=1}^m d_{ij} \cdot \phi_{ij} \cdot \frac{v_i' \left( \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \cdot \sum_{j'=1}^m p_{j'}^* x_{ij'}^* \right)}{c_i' \left( \sum_{j'=1}^m p_{j'}^* x_{ij'}^* \right)} \\
&\ge c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j=1}^m (d_{ij} - x_{ij}^*) \cdot \phi_{ij} \cdot \frac{v_i' \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right)}{c_i' \left( \sum_{j'=1}^m p_{j'}^* x_{ij'}^* \right)} \\
&\ge c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j=1}^m (d_{ij} - x_{ij}^*) \cdot \frac{\phi_{ij} \cdot v_i' \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right)}{c_i' \left( c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} x_{ij'}^* \right) \right) \right)} \\
&\ge c_i^{-1} \left( v_i \left( \sum_{j'=1}^m \phi_{ij'} d_{ij'} \right) \right) \end{aligned} 
\quad (11) $$

The first inequality holds since $\frac{p_j^*}{\phi_{ij}} \ge \min_{1 \le j' \le m} \frac{p_{j'}^*}{\phi_{ij'}}$ and Equation (8). The second inequality holds since $x_{ij}^* \ge 0$ and note that $\max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*} \cdot \sum_{j'=1}^m p_{j'}^* x_{ij'}^* = \sum_{j'=1}^m \phi_{ij'} x_{ij'}^*$ since in a FPPE, if $x_{ij}^* > 0$ then $j \in \arg \max_{1 \le j' \le m} \frac{\phi_{ij'}}{p_{j'}^*}$. The third inequality follows Equation (10) and $c_i'(\cdot)$ is non-decreasing function ($c_i$ is convex). The last inequality is due to the concavity of $c_i^{-1}(\cdot)$ and remark that the derivative of $c_i^{-1}(\cdot)$ is $\frac{1}{c_i'(c_i^{-1}(\cdot))}$.
Therefore, in the event where $t_i^* < W_i$,

$$ 
\begin{aligned}
\mathbb{E}_{x_i^*} [\mathrm{LW}_i(x_i^*)] + \sum_{j=1}^{m} d_{ij} \cdot p_j^* &= \min \left\{ W_i, c_i^{-1} \left( \mathbb{E}_{x_i^*} \left[ v_i \left( \sum_{j'=1}^{m} \phi_{ij'} x_{ij'}^* \right) \right] \right) \right\} + \sum_{j=1}^{m} d_{ij} \cdot p_j^* \\
&\geq \min \left\{ W_i, \mathbb{E}_{x_i^*} \left[ c_i^{-1} \left( v_i \left( \sum_{j'=1}^{m} \phi_{ij'} x_{ij'}^* \right) \right) \right] \right\} + \sum_{j=1}^{m} d_{ij} \cdot p_j^* \\
&\geq \min \left\{ W_i, \mathbb{E}_{x_i^*} \left[ c_i^{-1} \left( v_i \left( \sum_{j'=1}^{m} \phi_{ij'} x_{ij'}^* \right) \right) + \sum_{j=1}^{m} d_{ij} \cdot p_j^* \right] \right\} \\
&\geq \min \left\{ W_i, c_i^{-1} \left( v_i \left( \sum_{j'=1}^{m} \phi_{ij'} d_{ij'} \right) \right) \right\} = \mathrm{LW}_i(d_i)
\end{aligned}
$$

where the first inequality is due to Jensen inequality applied to concave function $c_i^{-1}$ and the last inequality follows Equation (11).

By the two cases, Equation (9) holds, and the lemma follows. □

**Theorem 3** The PoA of Bayes-Nash equilibria or coarse-correlated equilibria is exactly 2.

*Proof* Recall that we are analyzing a fixed arbitrary equilibrium $\sigma^*$. We are bounding the dual objective of the configuration LP.

$$ 
\begin{aligned}
\sum_j \alpha_j + \beta &= \sum_{j=1}^{m} \mathbb{E}_{(v,W,c)} \mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) [p_j^*] + \mathbb{E}_{(v,W,c)} \mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) \left[ \sum_{i=1}^{n} \mathrm{LW}_i(x_i^*) \right] \\
&= \mathbb{E}_{(v,W,c)} \mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) \left[ \sum_{j:p_j^*>0} \left( p_j^* \sum_{i=1}^{n} x_{ij}^* \right) + \sum_{i=1}^{n} \mathrm{LW}_i(x_i^*) \right] \\
&= \mathbb{E}_{(v,W,c)} \mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) \left[ \sum_{i=1}^{n} \left( \mathrm{LW}_i(x_i^*) + \sum_{j:p_j^*>0} p_j^* x_{ij}^* \right) \right] \\
&\leq 2 \mathbb{E}_{(v,W,c)} \mathbb{E}_{(p^*,x^*)} \sim \sigma^*(v,W,c) \left[ \sum_{i=1}^{n} \mathrm{LW}_i(x_i^*) \right]
\end{aligned}
$$

The second equality holds since $\sum_{i=1}^n x_{ij}^* = 1$ for every item $j$ such that $p_j^* > 0$. The last inequality holds by Equation (10) and note that $\sum_{j:p_j^*>0} p_j^* x_{ij}^* \leq W_i$ by the budget constraint. The dual is bounded at most twice that of the expected liquid welfare of the equilibrium $\sigma^*$. Hence, the PoA is at most 2.

Coupling with the PoA lower bound of 2 for pure Nash equilibria in [14], the theorem follows. □

# 5 Conclusion

We have introduced an approach leveraging linear programming duality and KKT conditions in convex programming to analyze the price of anarchy (PoA) in resource allocation and auto-bidding advertising. This approach is adaptable, making it applicable to a wide range of problems that can be formulated as linear programs, with results extending to general equilibrium concepts.
A promising avenue for future research is exploring game efficiency through this framework in
settings that can be interpreted as bilevel optimization problems. A driven motivation would be a
framework described in [17] in which each player is augmented with an AI agent and can consult
the AI before taking actions in a game.

**Acknowledgements** This work was also partially funded by the project PREDICTIONS, grant ANR-23-CE48-0010 from the French National Research Agency (ANR).

References

[1] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with con-straints. 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] Yossi Azar, Michal Feldman, Nick Gravin, and Alan Roytman. Liquid price of anarchy. In *International Symposium on Algorithmic Game Theory*, pages 3–15, 2017.

[4] 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.

[5] Andrew An Bian, Kfir Levy, Andreas Krause, and Joachim M. Buhmann. Continuous DR-submodular maximization: Structure and algorithms. In *Neural Information Processing Systems (NIPS)*, 2017.

[6] Vittorio Bilò. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. *Theory of Computing Systems*, 62(5):1288–1317, 2018.

[7] Ioannis Caragiannis and Alexandros A. Voudouris. Welfare guarantees for proportional allo-cations. *Theory Comput. Syst.*, 59(4):581–599, 2016.

[8] Ioannis Caragiannis and Alexandros A. Voudouris. The efficiency of resource allocation mech-anisms for budget-constrained users. *Math. Oper. Res.*, 46(2):503–523, 2021.

[9] 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.

[10] Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka, and Christopher A Wilkens. Pacing equilibrium in first price auction markets. *Management Science*, 68(12):8515–8535, 2022.

[11] Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. Efficiency of the first-price auction in the autobidding world. *Advances in Neural Information Processing Systems*, 37:139270–139293, 2024.

[12] Shahar Dobzinski and Renato Paes Leme. Efficiency guarantees in auctions with budgets. In *International Colloquium on Automata, Languages, and Programming*, pages 392–404, 2014.
[13] Shaddin Dughmi, Alon Eden, Michal Feldman, Amos Fiat, and Stefano Leonardi. Lottery pricing equilibria. In Proc. 11th ACM Conference on Economics and Computation, pages 401–418, 2016.

[14] Yiding Feng, Brendan Lucier, and Aleksandrs Slivkins. Strategic budget selection in a competitive autobidding world. In Proc. 56th ACM Symposium on Theory of Computing, pages 213–224, 2024.

[15] 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.

[16] 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.

[17] Nicole Immorlica, Brendan Lucier, and Aleksandrs Slivkins. Generative ai as economic agents. ACM SIGecom Exchanges, 22(1):93–109, 2024.

[18] Ramesh Johari and John N Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407–435, 2004.

[19] Ramesh Johari and John N Tsitsiklis. Efficiency of scalar-parameterized mechanisms. Operations Research, 57(4):823–839, 2009.

[20] Janardhan Kulkarni and Vahab Mirrokni. Robust price of anarchy bounds via lp and fenchel duality. In Proc. 26th Symposium on Discrete Algorithms, pages 1030–1049, 2014.

[21] 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.

[22] Pinyan Lu and Tao Xiao. Improved efficiency guarantees in auctions with budgets. In Proc. 16th ACM Conference on Economics and Computation, pages 397–413, 2015.

[23] Pinyan Lu and Tao Xiao. Liquid welfare maximization in auctions with multiple items. In Proc. 10th Symposium on Algorithmic Game Theory, pages 41–52, 2017.

[24] 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.

[25] 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.

[26] 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.

[27] Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201–221, 1978.
[28] Kim Thang Nguyen. Game efficiency through linear programming duality. In Proc. 10th Innovations in Theoretical Computer Science Conference, volume 124, pages 66:1–66:20, 2019.

[29] Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM, 62(5): 32, 2015.

[30] Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.

[31] Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos. The price of anarchy in auctions. Journal of Artificial Intelligence Research, 59:59–101, 2017.

[32] 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.

[33] Nguyễn Kim Thắng and Abhinav Srivastav. Online non-monotone dr-submodular maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9868–9876, 2021.