Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling
Authors: Yoav Kolumbus
Menahem Levy
Noam Nisan
Venue: NeurIPS 2023 poster (2023)
Keywords: Asynchronous Dynamics
Fisher Markets
Proportional Response
Best Response
Game Dynamics
Competitive Equilibrium
Convergence
TL;DR: We study asynchronous dynamics in Fisher markets under adversarial scheduling and prove convergence properties of proportional response, best response, and regret minimization dynamics.

Abstract: We study Proportional Response Dynamics (PRD) in linear Fisher markets, where participants act asynchronously. We model this scenario as a sequential process in which at each step, an adversary selects a subset of the players to update their bids, subject to liveness constraints. We show that if every bidder individually applies the PRD update rule whenever they are included in the group of bidders selected by the adversary, then, in the generic case, the entire dynamic converges to a competitive equilibrium of the market. Our proof technique reveals additional properties of linear Fisher markets, such as the uniqueness of the market equilibrium for generic parameters and the convergence of associated no swap regret dynamics and best response dynamics under certain conditions.

Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling
Yoav Kolumbus
Menahem Levy
Cornell University
The Hebrew University of Jerusalem menahem wat.hemmm.eemmmmil..1..m Sesvymmail.hui..... ac.
yoav. boav.kow kolumbus@cooeell..........mm edu
Noam Nisan
The Hebrew University of Jerusalem noamêcs huji. ac. il
Abstract
We study Proportional Response Dynamics (PRD) in linear Fisher markets, where participants act asynchronously. We model this scemario as sequential process which at each step, adversary selects subset of the players to update their bids, subject to liveness constraints. We show that every bidder individually applies the PRD update rule whenever they included in the group of bidders selected by the adversary, then, in the generic case, the entire dynamic converges to a competitive equilibrium of the market. Our proof technique reveals additional properties of linear Fisher markets, such as the uniqueness of the market equilibrium for generic parameters and the convergence of associated swap regret dynamics and best response dynamics under certain conditions.
Introduction
A central notion in the study of markets is the equilibrium: state of affairs where single party wishes to unilaterally deviate from The main benefit of focusing on the notion equilibria lies in what it ignores: how the market can reach equilibrium (if at all). This latter question is obviously of much interest as well, especially when considering computational aspects and a significant amount of research has been dedicated to the study of "market dynamics" and their possible convergence to an equilibrium. Almost all works that study market dynamics consider synchronous dynamics.
Synchronous Dynamics: At each time step I, all participants simultaneously update their behavior based on the state at time t 1. 1.
Such synchronization clearly difficult achieve in real markets, and one might naturally wonder to what extent full synchrony is needed or whether convergence of market dynamics occurs even asynchronously. There are various possible levels of generality simplest model considers a sequential scenario in which, at every time step f, adversary chooses single participant, and only this participant updates their behavior based on the state at time 1- 1. The adversary is constrained to adhere to some liveness condition, such scheduling every participant infinitely often or at least once every T steps. In the most general model [59], the adversary may also introduce message delays, leading players to respond to dated information. In this paper, focus on an intermediate level of permissible asynchrony where updates may occur in an arbitrary asynchronous manner, but message delays always shorter than the granularity of activation. In our proofs, the adversary's ' goal is to select the schedule of strategy updates by the players in way that prevents the dynamic from converging market equilibrium.
asynchrony to consider. The
As we know that finding an equilibrium may be computationally intractable in general.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Activation Asynchrony Every time step t, an arbitrary subset of participants is chosen by the adversary and all of these participants update their behavior based on the state time t 1. The adversary must adhere to the liveness condition where for every participant some set that includes them must be chosen at least once every T consecutive steps.
The market dynamics that we study in this paper are linear Fisher markets [9] with proportional
response dynamics (PRD), model that has received much previous attention [5] I0
19 74 and
for which synchronous convergence to equilibrium is known. While there are a few asynchronous convergence results known for other dynamics, specifically for tatonnement dynamics [ 23 there are no such results known for proportional response dynamics, and achieving such results has been mentioned as an open problem in [19 74).
Fisher Markets with Linear Utilities: There are n players and goods. Each player has budget B, and each good j has, w.l.o.g., a total quantity of one. Buyer i's utility from getting an allocation
r; = (Ia .... Tim) is given by (xxx;) = E; Azjzij. where the parameters dij 2 0 are part of the definition of the market. A market equilibrium is allocation X (2iy) (where 0 zaj 1) and a pricing p = (p5) with the following properties. (1) Market clearing: for every good j it holds that Σ, Fig
1; (2) budget feasibility: for every player it holds that E, TipP S B; and
(3) utility maximization: for every player and every alternative allocation y (y1, ... Vmn with Σ, BoPs BソbpP3 I
B, we have that (244 2 (v).
Proportional Response Dynamics: At each time step t, each player i will make a bid by 2 0 for every good j. where Σ, B,. In the first step, the bid is arbitrary. Once bids for time i are announced, we calculate p) = Σ, biy and allocate the goods proportionally: zly = bb / providing each player with utility u = E, a.jzyy- At this point, player i updates its bids for the next step by
bidding on each good proportionally the utility obtained from that good: b/ B, - -...ay.. agyzly/ /u/.
From the perspective of the player, proportional response updates can be thought of as a simple parameter-free online learning heuristic, with some similarity to regret-matching [R] in its propor- tional updates, but one that considers the utilities directly, rather than the more sophisticated regret vector loss.
It not difficult to see that a fixed point of this proportional response dynamic is indeed an equilibrium of the Fisher market. Significantly, it was shown in [5] that this dynamic does converge, in the synchronous model, to an equilibrium. As mentioned, the question of asynchronous convergence was left open. We provide the first analysis of proportional response dynamics in the asynchronous setting, and provide a positive answer to this open question in our "intermdiate" level of asynchrony.
Theorem 1.
For linear Fisher markets, proportional response dynamics with adversarial activation asynchrony, where each player is activated least once every steps, approach the set of market equilibrium bid profiles. The prices in the dynamics converge to the unique equilibrium prices.
The dynamics approaching the set of equilibria means that the distance between the bids at time and the set of market equilibrium bid profiles converges zero t co. Additionally, in Section 7 we show that for generic parameters (i.e., except for measure zero of possible (ai5) ) )'s), the market equilibrium bid profile is unique, and thus Theorem [ iimplie convergence of the bids to a point in the strategy space. We do not know whether the genericity condition is required for asynchronous convergence of the bids a point, and leave this minor open problem. We did not analyze the rate of convergence to equilibrium; we leave such analysis as a second open problem. Our main open problem, however, is the generalization to full asynchrony with message delays.
Open Problem: Does such convergence occur also in the full asynchronous model where the adversary may introduce arbitrary message delays?
Our techniques rely on considering an associated game obtained by using "modified" utility functions for each of the players: (bcbb) = -E, bij In(a.)) + E, (1 In(p,)). We show that competitive market equilibrium (with the original utility functions) corresponds to Nash equilibrium in the associated game These modified utility functions are an adaptation to an individual utility of a
In 55 this was termed "simultaneous."
II is worthwhile to emphasize, though, that a competitive market equilibrium is not a Nash equilibrium in the original market, since the players are price takers rather than fully rational. See Section 3

---

function ((b) = E, byy In(as))++ En (11((11n((p)) that was proposed in 665 as an objective for
convex program for equilibrium computation | This function was first linked with proportional response dynamics in [5] where it was proven that synchronous proportional response dynamics act as mirror descent on this function. We show that & serves as a potential in our associated game.
The following three sets of bid profiles are identical: (1) the set of pure strategy Nash equilibria of the associated game, (2) the set of market equilibria of the Fisher market, and (3) the maximizing set of the potential function $
Theorem 2.
The technical core of our proof is to show that not only does a synchronized proportional response step by all the players increase the potential function & but, in fact, every proportional response step by any subset of the players increases this potential function.
The point of view of market equilibria as Nash equilibria of the associated game offers several other advantages, e.g., suggesting several other dynamics that are related to proportional response that can be of interest. For example, we show that letting players best-respond in the associated game corresponds to the limit of sequence of proportional response steps by a single player, but can be implemented as single step of such a best-response, which can be computed efficiently by the players and may converge faster to the market equilibrium. Another possibility is using some (internal) minimiiiiinnntiinn dynamics (for the associated game), which would also converge to cquilibrium in the generic case since, applying [56], it is the unique correlated Equilibrium as well.
The structure of the rest of the paper is as follows. In Section 2 we provide further formal details and notations that will be useful for our analysis. Section 3 we present the associated game and its relation to the competitive equilibria of the market. In Section 4 we study best response dynamics
in the associated game and their relation to PRD. In Section 5 we present a key lemma regarding the potential function of the associated game under bid updates by subsets of the players. Then, in Section [6 we complete our proof of convergence for asynchronous PRD. Section 7 we show the uniqueness of the market equilibrium for generic markets. In Section 8 we provide simulation results that compare the convergence of proportional response dynamics with best response dynamics in the associated game in terms of the actual economic parameters in the market, namely, social welfare and the convergence of the bid profiles. Finally, in Section 9 we conclude and discuss the limitations of our technique and open questions. All proofs in this paper are deferred to the appendix.
1.1 Further Related Work
Proportional response dynamics (PRD) were originally studied in the context of bandwidth allocation in file-sharing systems, where it was proven to converge to equilibrium, albeit only for a restrictive setting 77].. Since then, PRD has been studied in a variety of other contexts, including Fisher markets, linear exchange economies, and production markets. See [TO for further references. In Fisher markets, synchronous PRD has been shown to converge to market equilibrium for Constant Elasticity of Substitution (CES) utilities in the substitutes regime [74). For the linear Fisher market setting, synchronous PRD was explained in [5] as mirror descent on a convex program, previously discovered while developing an algorithm to compute the market equilibrium (65), and later proven to be equivalent to the famous Eisenberg- Gale program (22]. By advancing the approach of citebirn- baum201 I distributed, synchronous PRD with mild modifications was proven to converge to market equilibrium for CES utilities in the complements regime as well [19] In linear exchange economies, synchronous PRD has been shown to converge to equilibrium in the space of utilities and allocations while prices do not converge and may cycle, whereas for damped version of PRD, also the prices converge [II. In production markets, synchronous PRD has been shown to increase both growth and incqualities in the market [3]. PRD has also been proven to converge with quasi-linear utilitics (3), and to remain close to market equilibrium for markets with parameters that vary over time [20]. All the above works consider simultancous updates by all the players, and the question of analyzing asynchronous dynamics and whether they converge raised by several authors as open problem
19 74).
Asynchronous dynamics in markets have been the subject of study in several recent works. However, these works examine different models and dynamics than ours, and to our knowledge, our work presents the first analysis of asynchronous proportional response bidding dynamics. In [23] it is
'Notice that & is not the sum of the ū 's, the second term appears only once.
3

---

shown that tatonnement dynamics under the activation asynchrony model converge to equilibrium. with results for settings both with and without earryover effects between time units. later work, [18. showed that tatonnement price dynamics converge to market equilibrium under a model of sequential activation where in every step single agent activated, and where additionally, the information available to the activated seller about the current demand may be inaccurate within some interval that depends on the range of past demands. A different approach taken in [29] assumes that each seller has a set of rules affected by the other players' actions and governing its price updates; is shown that the dynamics in which sellers update the prices based on such rules converge to a unique equilibrium of prices in the activation asynchrony model.
Online learning with delayed feedback has been studied for a single agent in [1], which established regret bounds that are sub-lime sub-linear in the total delay. A different approach, presented in [52], extends online gradient descent by estimating gradients when the reward of an action is not yet available due to delays. When considering multiple agents, [75] extended the results of [61]. They demonstrated that in continuous games with particular stability property, if agents experience equal delays in each round, online mirror descent converges to the set of Nash equilibria and a modification of the algorithm converges even when delays are not equal.
Classic results regarding the computation of competitive equilibria in markets mostly consider centralized computation and vary from combinatorial approaches using flow networks 26
28
interior point [72). and ellipsoid [2] 44 methods, and many more 3 25| 26
30
39
40
63
Eisenberg and Gale devised convex program which captures competitive equilibria of the Fisher
model as its solution [31. Notable also is the tatonnement model of price convergence in markets
dated back to Walras 70 and studied extensively from Arrow 1 and in later works.
More broadly, in the game theoretic literature, our study is related to long line of work on learning in games, starting from seminal works in the 1950s 66 [4| 42 62). and continuing be an active field of theoretical research [24] 33
49 60) 66 also covering a wide range of classic economic
settings including competition in markets
bilateral trade T6 32], and auctions 2 34
as well as applications such as blockchain fee markets [50] 51 57 and strategic queuing systems [36] 33,. For broad introduction the field of learning in games, see [17 (33. The vast majority of this literature studies repeated games under the synchronous dynamics model. Notable examples of analyses of games with asynchronous dynamics are [46), which study best response dynamics with sequential activation, and [59]. which explore best response dynamics in a full asynchrony setting which includes also information delays, and show that in class of games called max max-solvable, convergence of best response dynamics is guaranteed. Our analysis of best response dynamics in Section|Jtake takes a different route, and does not conclude whether the associated game that we study is max- mox-solvable or not; such an analysis seems to require new ideas.
Our work is also related a large literature on asynchronous distributed algorithms. We refer to a survey on this literature [41]. The liveness constraint that we consider in the dynamics F is
related to those, e.g., in 4 677. Recent works that are conceptually more closely related are 15 69 73), which propose asynchronous distributed algorithms for computing Nash equilibria in network games. Notably, [S] propose an algorithm that converges to an equilibrium in a large class of games in asynchronous settings with information delays. Their approach, however, does not capture proportional response dynamics and does not apply to our case of linear Fisher markets.
2 Model and Preliminaries
The Fisher market: We consider the classic Fisher model of a networked market in which there is set of buyers and set of divisible goods G. We denote the number of buyers and number of goods as n [B], = [9]. respectively, and index buyers with and goods with j. Buyers
assigned budgets B; E IR+ + and have some value a.j 2 0 for each good j. Buyers' valuations are normalized such that E, Diy = 1. It is convenient to write the budgets as vector B = (B,) and the valuations
as a matrix Anxm (a:j). such that A, B are the parameters defining the market. We denote the allocation of goods to buyers as a matrix X = (2:1)) where zij 2 0 is the (fractional) amount of good
Intuitively, if one allows some of the parameters in the dynamic not update, these parameters become irrelevant, as they will remain frozen, and thus one cannot hope to see any convergence of the entire system. For the case of exposition, our proof's use w.l.o.g. ag > 0. This is since in all cases where 0.j = 0 might have any implication on the proof, such as In(a;)). these expressions are multiplied by zero in our dynamics.
4

---

j that buyer i obtained. We assume w.l.ogg. (by proper normalization) that there is a unit quantity of each good. The price of good j (which depends on the players' actions in the market, as explained below) is denoted by Pj 2 0 and prices are listed vector p (pz). Buyers have a linear utility function (xxe) = Σ; aiyTas with the budget constraint Σ, TıyPj S B, We assume w.l.o.g. that the economy is normalized, i.e., Σ, B; = P, =1.
Market equilibrium:
The competitive equilibrium (or "market equilibrium") is defined in terms of allocations and prices as follows.
Definition 1. (Market Equilibrium); A pair of allocations and prices (X', .p') is said to be market equilibrium if the following properties hold:
1. Market clearing:
Vj, E, =
2. Budget feasibillty:
Vi, Σ, Fizs S Bi
3. Utility maximization:
Vi, x² arg maxx; uz (xa)).
In words, under equilibrium prices all the goods are allocated, all budgets are used, and no player has an incentive to change their bids given that the prices remain fixed. Notice that this notion of equilibrium is different from Nash equilibrium of the game where the buyers select their bids strategically, since in the former case, players do not consider the direct effect of possible deviation in their bids on the prices. We discuss this further in Section 3 For linear Fisher markets, it is well established that competitive equilibrium utilities u" and prices p" are unique, equilibrium allocations are known to form a convex set, and the following conditions are satisfied.
agj
u B
V
and Tij
B;
This is a detailed characterization of the equilibrium allocation: every buyer gets a bundle of goods in which all goods maximize the value per unit of money. The quantity a:y/p; is informally known as "bang-per- (ch. 5 & 6 in (58), the marginal profit from adding a small investment in good j.
Market equilibrium bids are also known to maximize the Nash social welfare function (see (31) NSW = Iheg (2, B. and to be Pareto efficient, i.c., no buyer can improve their utility without making anyone else worse off (as stated in the first welfare theorem).
The trading post mechanism and the market game Shapley-Shubik, First described in 664 and studied under different names [33 47,, the trading post mechanism is an allocation and pricing mechanism which attempts to capture how a price is modified by demand. Buyers place bids on goods, where buyer places bid by on good j. Then, the mechanism computes the good's ' price as the total amount spent on that good and allocates the good proportionally to the bids, i.e., for bids b:
biz P5
bij
PJ
baj
Tiy
0
otherwise.
Note that the trading post mechanism guarantees market clearing for every bid profile in which all goods have at least one buyer who is interested in buying. The feasible bid set of a buyer under Σ,by bij = B.), i.e., scaled simplex. Denote N S; and S_, [L Sg. Considering the buyers as strategic, one can define the market game as G = {B, (es)) (u))Ee)) where the utility functions can be written explicitly as u, (b) u.(x;(b) ンー buy We sometimes use the notation u; (b:, b_.), where b; is the bid Py
the budget constraint is S; (b. E RT bij
vector of player and b_ denotes the bids of the other players.
Potential function and Nash equilibrium: For completeness, we add the following definitions.
Potential function: A function & is exact potential function (53) if vi E B, Vb_; E S_, and Vb, B3 E S; we have that (bb,, b.,) - (bb,, b_:) = (,bb,, b_:) )) - u, (b,, b-i), with u; being i's utility function in the game. Best response: by is best response to b_, if Vb; E St u,(b; b-.) 2 (b, b..). That is, no other response of i can yield a higher utility. Nash equilibrium: ba is Nash equilibrium if Vi by is best response to bi, (no player is incentivized to change their strategy).
Proportional response dynamics: As explained in the introduction, the proportional response dynamic is specified by an initial bid profile 69, with 6/ > 0 whenever az > 0, and the following
5

---

update rule for every player that activated by the adversary: bt+1 0.44 further details on activation of subsets of the players.
Br See Section 5 for u.(=?)
3 The Associated Game
As mentioned above, the Fisher market can be naturally thought of as a game which every one of the n players aims to optimize their individual utility u, (b, b-:) (see Section 2 for the formal definition). However, it is known that the set of Nash equilibria of this game does not coincide with the set of market equilibria (33] and solution to this game (if indeed the players reach Nash equilibrium) is economically inefficient [12].
A natural question that arises is whether there is some other objective for an individual player that when maximized by all the players, yields the market equilibrium. We answer positively to this question and show that there is family of urility functions such that in the "associated games" with these utilities for the players, the set of Nash equilibria is identical to the set of market equilibria of the original game (for further details, see also Appendix A).
However, the fact that Nash equilibrium of associated game is a market equilibrium still does guarantee that the players' dynamics will indeed reach this equilibrium. A key element in our proof technique is that we identify. among this family of associated games. single game, defined by the "associated utility" (b) = E, bij In In(a,y) + Σ3 P5 In (n(p)), which admits an exact potential. We then use relation which we show between this game and the proportional response update rule to prove the convergence of our dynamics (Theorem D.
Definition 2. (The Associated Game): Let G' be market game. Define the associated utility of player as (b) E, big In(asj) + ΣSpp( P5(1 - In(p))). The associated game G is the game with the associated utilities for the players and the same parameters as in G.
Theorem For every Fisher market, the associated game G admits an exact potential function that is given by ((b) = Eig big In(aig) + E, In(p,)).
Ō is constructed such that the function & is its potential. Note that although having similar structure, ū and & differ via summation on only in the first term (& is not the sum of the players' utilities).
Once having the potential function defined, the proof is straightforward: the derivatives of the utilities ú and the potential & with respect to are equal for all i. Theorem 2 formally restated below, connects between the associated game, the market equilibria and the potential.
Theorem. (Restatement of Theorem D) The following three sets of bid profiles are equal. (1) The set
of stre-strategy Nash equilibria of the associated game: N = (bb) vb E (ū(b²) 2 n. (b)): (2) the set of market equilibrium bid profiles of the Fisher market: {b" (x(b*) p,b())) satisfy Def. and (3) the maximizing set of the potential from Theorem arg maxies ((b).
The proof uses different associated game G" that has simpler structure than G, but does not have an exact potential, and shows that: (i) Nash equilibria of G' are the market equilibria; (ii) all the best responses of players to bid profiles b_, in G' are the same as those in G; and (iii) every equilibrium of & maximizes the potential & (immediate by the definition of potential).
4 Best Response Dynamics
In this section we explore another property of the associated game: we show that if instead of using the proportional response update rule, each player myopically plays their best response to the last bid profile with respect to their associated utility, then the entire asynchronous sequence of bids converges to a market equilibrium, as stated in the following theorem. We then show that there is a close relation between best response and proportional response dynamics.
"Since we discuss the players' associated utilities, we consider maximization of this potential. Of course, if the reader feels more comfortable with minimizing the potential, one can think of the negative function.

---

Theorem 4. For generic linear Fisher markets in a sequential asynchrony model where in every step a single player is activated, best response dynamics converge to the Market Equilibrium. For non-generic markets the prices are guaranteed to converge to the equilibrium prices.
The idea of the proof is to show that the best-response functions are single valued (Vi, b-s : ū,(;, b-4) has unique maximizer) and continuous (using the structure of hest-response bids). Together with the existence of the potential function $ it holds that the analysis of [46] applies for these dynamics with the associated utillitie and thus convergence is guaranteed.
One of the appealing points about proportional response dynamics is their simplicity - in each update, player observes the obtained utilities and can easily compute the next set of bids. We show that also the best response of a player can be computed efficiently by reducing the calculation to a search over small part of the subsets of all goods which can be solved by simple iterative process.
Proposition 1. For every player and any fixed bid profile f-r the other players, the best response of is unique and can be computed in polynomial time.
Roughly, best responses are characterized uniquely by one-dimensional variable c². For every subset goods we define variable c₂ and prove that c* the maximum amongst all c.. So finding c" is equivalent to searching a specific subset with maximal cs. The optimal subset of goods admits a certain property that allows to narrow down the search domain from all subsets to only m subsets.
The relation between the best response and proportional response updates can intuitively be thought of follows. While in PRD players split their budget between all the goods according the utility that each good yields, and so gradually shift more budget to the more profitable subset of goods, best response bids of player i with respect i can be understood spending the entire budget on subset of goods which, after bidding so (considering the effect of bids on prices), will jointly have the maximum bang-per-buck (in our notation a.j/p) /p)) amongst all subsets of goods, given the bids bf, of the other players. Those bids can be regarded as "water-filling" bids as they level the bang-per-buce amongst all goods purchased by player i (for a further discussion see the appendix).
turns out that there is a clear formal connection between the best response of a player in the associated game and the proportional response update rule in the true game: the best response bids are the limit point of an infinite sequence of proportional response updates by the same player when the bids of the others are held fixed, as expressed in the following proposition.
Fix any player i and fix any bid profile b-i for the other players. Let bj argmazs (b, b-i) and let (b))²z be a sequence of consecutive proportional response steps applied by player i, where b_q is held fixed at all times t. Then limy by [6 b;.
Proposition 2.
5 Simultaneous Play by Subsets of Agents
In this section, we shift our focus back to proportional response dynamics under the activation asynchrony model in which the adversary can choose in every step any subset of players update their bids. Towards proving that proportional response dynamics converges to a market equilibrium in this setting, we utilize the associated game and potential function presented Section 3 to show that any activated subset of players performing PRD step will increase the potential. Formally, let C B be subset of players activated by the adversary and let (b) be a function that applies proportional response to members of e and acts as the identity function for all the other players. The update for time + 1 when the adversary activates a subset of the players of C B is therefore:
B.
i of otherwise.
6 = (fo)
Lemma 1. For all v C. B and all b E S it holds that (b) > {bb), unless (b( = b.
The proof shows that for any subset of players v', a PRD step b' is the solution to some maximiza- tion problem of a function g (b) different from t, such that ((b++)) > g'(b+1) 2 g²())) ((b')
'Note that while the best-reply function with respect to the standard utility function is formally undetined at zero, the associated utility and its best-reply function well detined and continuous at zero
7

---

Notable to mention is the sequential case where all subsets are singletons, i.e., for all t, vz = { for some i' B. In that case, the above result yields that the best-response bids can be expressed as the solution to an optimization problem over the bids b on function that is monotone in the KI. divergence between the prices induced by b and the current prices, whereas PRD the solution to an optimization problem on a similar function, but one that depends on the KI. divergence between the bids 6 and the current bids. Thus, sequential PRD can be regarded as relaxation of best response; on the one hand, it is somewhat simpler to compute a step, and on the other hand, it takes more steps to reach the best response (see Proposition and the simulations in Section 8)
Convergence of Asynchronous Proportional Response Dynamies
With the results from the previous sections under our belts (namely, the associated game, Theorems 2 abbuu its potential and equilibria, and Lemma about updates by several players simultaneously), we are now ready to complete the proof of Theorem I on the convergence of asynchronous proportional response dynamics. We explain here the idea of the proof. The full proof is in the appendix.
Proof idea of Theorem I Our starting point is that we now know that Proportional Response Dynamies (PRD) steps by subsets of players increase the potential. Therefore, the bids should somehow converge to reach the maximum potential, which is obtained only at the set of market cquilibria. Technically, since the sequence of bids b$ is bounded, must have condensation points. The proof then proceeds by way of contradiction. If the sequence does not converge to the set of cquilibrium bid profiles, M E' subsequence that converges to a bid profile b** outside of this set, which by Theorem 2 must achieve a lower potential than any b* E M E (since it not a market equilibrium, and recall that only market equilibria maximize the potential function).
{6> b* a market equilibrium bid profile), then there is some
From this point, the main idea is to show that if the dynamic preserves "livness" property where the maximum time interval between consecutive updates of a player is bounded by some constant T, then the dynamic must reach a point where the bids are sufficiently close to b such that there must be some future update by some subset of the players under which the potential increases to more than ((b**), contradicting the existence of condensation points other than market equilibria (note that the sequence of potential values (bb)) is increasing in f). To show this, the proof requires several additional arguments on the continuity of compositions of PRD update functions that arise under adversarial scheduling, and the impact of such compositions on the potential function. The full proof is in the appendix.
7 Generic Markets
Here we show that in the generic case, linear Fisher markets have a unique equilibrium bid profile. While it is well known that in linear Fisher markets equilibrium prices and utilities are unique, and the equilibrium bids and allocations form convex sets (see section 2). we show that multiplicity of equilibrium bid profiles can result only from special degeneracy in the market parameters that has measure zero in the parameter space. In other words, if the market parameters are not carefully tailored to satisfy a particular equality (formally described below), or, equivalently, if the parameters are slightly perturbed, the market will have a unique equilibrium. Similar property was known for linear exchange markets [8] and we present a simple and concise proof for the Fisher model.
Definition 3. A Fisher market called generic if the non-zero valuations of the buyers (a;)) do not admit any multiplicative equality. That is, for any distinct and non empty K, K' C B x G it holds that H0.Se asj # II( azz-
Theorem 5. Every generic linear fisher market has unique market equilibrium bid profile b*.
Before diseussing the proof of Theorem we have the following corollaries.
Corollary 1. For generic linear Fisher markets, proportional response dynamics with adversarial activation asynchrony, where each player is activated at least once every T steps, converge to the unique market equilibrium.
The main theorem, Theorem suggests that proportional response dynamics with adversarial activation asynchrony converges to the set of market equilibria. Since the previous theorem guarantees
8

---

that generic market has a unique market equilibrium bid profile, it is clear the dynamics converges to that bid profile.
In generic linear Fisher markets, no-swap regret dynamics in the associated game converge to the market equilibrium.
Corollary 2.
This follows from [56]. who showed that in games with convex strategy sets and continuously differentiable potential function (as in our case), the set of correlated equilibria consists of mixtures of elements in arg max, Φ. Theorem 2 yields that arg max; & b", and there is unique correlated equilibrium, which is the market equilibrium, and we have that no-swap regret guarantees convergence it.
To prove Theorem 5 we use a representation of the bids in the market as a bipartite graph of players and goods r(b) (V, E} with V B U g and E = {{i,j] by 0}. The proof shows that if market has more than one equilibrium bid profile, then there has to be an equilibrium with l(6) containing cycle, whereas the following lemma forbids this for generic markets.
Lemma 2. bf are equilibrium bids a generic linear Fisher market, then l(b') has no cycles.
key observation for proving this lemma is that at market equilibrium, for particular buyer the quantity dty/P is constant amongst goods purchased, and so it is possible to trace a cycle and have all the pž cancel out and obtain an equation contradicting the genericity condition.
An observation that arises from Lemma Dis that when the number of buyers in the market is of the same order of magnitude the number of goods larger, then, in equilibrium, most buyers will only buy a small number of goods. Since there are no cycles in r(b*) and there are n + m vertices, there most m edges. Thus, with buyers, the average degree of buyer is
8 Simulations
Next, we look at simulations of the dynamics that we study and compare the convergence of proportional response dynamics best response dynamics in the associated game, as discussed in Section The metrics we focus on here for every dynamic are the Nash social welfare (55), which, as mentioned in Section 2 maximized the market equilibrium, and the Buclidean distance between the bids at time and the equilibrium bids. Additionally, we look at the progression over time of the value of the potential (b') (for the definition, see Section 3
Figure D presents simulations of an ensemble of markets, each with ten buyers and ten goods. The parameters in each market (defined in the matrices A and B) are uniformly sampled, ensuring that the genericity condition (defined in Section 2 holds with probability one. These parameters are also normalized, as explained in Section 2 For each market, the parameters remain fixed throughout the dynamics. The initial condition in all simulation runs is the uniform distribution of bids over items, and the schedule is sequential, such that single player updates their bids in each time step.
Figure la (main plot) show our metrics for PRD averaged over a sample of 300 such simulations. The insets show the plots of a random sample of 50 individual simulations (without averaging) over longer time period. Figure lb show similar plots for best response dynamics.
As could be expected based on our analysis in Section best response dynamics converge faster than PRD, as can be seen in the different time scales on the horizontal axes. closer look at the individual bid dynamics depicted in the insets reveals a qualitative difference between the two types of dynamics: in PRD, the bids in each dynamic smoothly approach the equilibrium profile, whereas best response bid dynamics are more irregular. Additionally, the collection of curves for the individual simulations shows that under uniformly distributed market parameters, both dynamics exhibit variance in convergence times, with a skewed distribution. In most markets, the dynamics converge quickly, but there is a distribution tail of slower- converion dynamics.
Conclusion
We have shown that proportional response bid dynamics converge to a market equilibrium a setting where the schedule of bid updates can be chosen adversarially, allowing for sequential or

---

1.00
1.00
0.75
0.6
0.5
0.25
0.4
0.00
0.4
000
Nash Social Welfare
Potential
||0
200
300
400
500
20
60
100
125
(a) Proportional Response
(b) Best Response
Figure I: Proportional response and best response dynamics. The main figures show the progression of the average metries over time and insets show a collection individual dynamics over longer time period.
simultaneous updates for any subset of players. We proposed novel approach address this problem by identifying a family of associated games related to proportional response dynamics, showing their relation to the competitive equilibria of the market, and leveraging these relations to prove convergence of the dynamics. En route, we showed that other types dynamics, such as myopic best note that
response and no swap regret, also converge in the associated game. Additionally, result on the uniqueness market equilibria in the generic case (c.g.. the market parameters have some element of randomness) may also be of interest for future research in the Fisher market setting.
One main open question that did not analyze is whether proportional response dynamics converge under the full asynchrony model, which includes information delays. The analysis of this model raises several complications, as it creates further coupling between past and current bid profiles. We conjecture that if information delays are bounded, then convergence also occurs in this model. However, is not clear whether our approach could be extended to argue that proportional response updates by subsets of players with respect to delayed information increase the potential in associated game, or whether proving convergence in this setting will require new methods. One limitation of our analysis is that provide a guarantee that under any bid update by any subset of players chosen by an adversary, the potential function of the associated game increases, but our technique does not specify by how much the potential increases in every step, and therefore, do not provide speed of convergence results. Such analysis seems to require new techniques, and we see this an interesting open problem for future work.
Acknowledgments
This work was supported by the European Research Council (ERC) under the European Union's 's Horizon 2020 Research and Innovation Programme (grant agreement no. 740282) and by a grant from the Israeli Science Foundation (ISF number 505/23). During part of this project, Yoav Kolumbus has been affiliated with the Hebrew University Jerusalem.
10

---

References
[1] Kenneth J Arrow, Henry D Block, and Leonid Hurwicz. On the stability of the competitive equilibrium, ii. Econometrica: Journal of the Econometric Society, pages 82-109, 1959.
[2] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-3966, 2019.
[3] Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending pricc algorithms for unknown markets.
ACM Transactions on Algorithms (TALG), 15(3):1-33, 2019.
[4] Dimitri P Bertsekas. Distributed asynchronous computation of fixed points. Matherattiaa Programming, 27(1):107-120, 1983.
[5] Benjamin Birnbaum, Nikhil Devanur, and Lin Xiao. Distributed algorithms via gradient descent for fisher markets. In Proceedings of the 12th ACM conference on Electronic commerce, pages 127-136, 2011.
[6] David Blackwell et al. Controlled random walks. In Proceedings of the international congress of mathematicians, volume 3, pages 336-338, 1954.
[7] Avrim Blum, MohammadTaghh Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimiza- tion and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 373-382, 2008.
[8] Jean-Marc Bonnisseau, Michael Florig, and Alejandro Jofré. Continuity and uniqueness of equilibria for linear exchange economies. Journal of Optimization Theory and Applications, 109:237-263, 2001.
[9] William Brainard and Herbert Scarf. How to compute equilibrium prices in 1891. American Journal of Economics and Sociology, 64(1):57-83, 2005.
[10] Simina Brânzei. Exchange markets: proportional response dynamics and beyond. ACM SIGecom Exchanges, 19(2):37-45, 2021.
[11] Simina Brânzei, Nikhil Devanur, and Yuval Rabani. Proportional dynamies exchange economies. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 180-201, 2021.
[12] Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. Nash social welfare approximation for strategic agents. Operations Research, 70(1):402-415, 2022.
[13] Simina Branzei, Ruta Mehta, and Noam Nisan. Universal growth in production economies. In and R. Garnett, editors.
Bengio. H. Wallach, Larochelle. K. Grauman, N. Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[14] George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
[15] Carlo Cenedese, Giuseppe Belgioioso, Sergio Grammatico, and Ming Cao. An asynchronous distributed and scalable generalized nash equilibrium seeking algorithm for strongly monotone games. European Journal of Control, 141,151, 2021.
[16] Nicolò Cesa- -isacBBinchh, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade; A regret minimization perspective. Mathematics of Operations Research, 2023.
[17] Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[18] Yun Kuen Cheung and Richard Cole. Amortized Analysis of Asynchronous Price Dynamics. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPlcs), pages 18:1-18:15, 2018.
11

---

[19] Yun Kuen Cheung, Richard Cole, and Yixin Tao. Dynamics of distributed updating in fisher markets. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 351-368, 2018.
[20] Yun Kuen Cheung, Martin Hoefer, and Paresh Nakhe. Tracing equilibrium in dynamic markets via distributed adaptation. arXiv preprint arXiv: 1804.08017, 2018.
[21] Bruno Codenotti, Sriram V Pemmaraju, and Kasturi R Varadarajan. On the polynomial time computation of equilibria for certain exchange economies. In SODA, volume 5, pages 72-81, 2005.
[22] Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, fisher markets, and nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 459-460, 2017.
[23] Richard Cole and Lisa Fleischer. Fast-converging tatonnement algorithms for one-time and ongoing market problems. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 315-324, 2008.
[24] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 2021.
[25] Xiaotie Deng, Christos Papadimitriou, and Shmuel Safra. On the complexity of price equilibria. Journal of Computer and System Sciences, 1113331133 2003.
[26] Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market equilibrium via a primal -ualll algorithm for a convex program. Journal of the ACM (JACM), 55(5):1-18, 2008.
[27] Nikhil R Devanur and Vijay V Vazirani. An improved approximation scheme for computing arrow-debreu prices for the linear case. FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science; 23rd Conference, Mumbai, India, December 15-17, 2003. Proceedings 23, pages 149-155. Springer, 2003.
[28] Ran Duan and Kurt Mehlhorn. A combinatorial polynomial algorithm for the linear arrow- debreu market. Information and Computation, 243:1 12-132, 2015.
[29] Krishnamurthy Dvijotham, Yuval Rabani, and Leonard J Schulman. Convergence of incentive- driven dynamics in fisher markets. Games and Economic Behavior, 134:361-375, 2022.
[30] Federico Echenique and Adam Wierman. Finding walrasian equilibrium is easy for fixed number of agents. 2011.
[31] Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematicul Statistics, 30(1):165-168, 1959.
[32] Kfir Eliaz and Alexander Frug. Bilateral trade with strategic gradual learning. Games and Economic Behavior, 107:380-392 108000395,22 2018.
[33] Michal Feldman, Kevin Lai, and Li Zhang. The proportional-share allocation market for computational resources. IEEE Transactions on Parallel and Distributed Systems, 20(8):0075 1088, 2008.
[34] Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18 page 505-522, New York, NY, USA, 2018. Association for Computing Machinery.
[35] Dylan J Foster, Noah Golowich, and Sham M Kakade. Hardness of independent learning and sparse equilibrium computation in markov games. arXiv preprint arXiv:2303. 12287, 2023.
[36] Jason Gaitonde and Êva Tardos. Stability and learning in strategic queuing systems. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 319-347, 2020.
12

---

[37] Jason Gaitonde and Eva Tardos. Virtues of patience in strategic queuing systems. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 520-540, 2021.
[38] Yuan Gao and Christian Kroer. First-order methods for large-scale market equilibrium computa- tion. Advances in Neural Information Processing Systems, 08:21738-2177 2020.
[39] Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V Vazirani. A complementary pivot (practical) algorithm for market equilibrium under separable, piecewise- linear concave utilities.
[40] Rahul Garg and Sanjiv Kapoor. Auction algorithms for market equilibrium. In Proceedings of the sixit annual ACM symposium on Theory of computing, pages 511-518, 2004.
[41] Felix C Gärtner. Fundamentals of fault-tolerant distributed computing in asynchronous environ- ments. ACM Computing Surveys (CSUR), 31(1):1-26, 1999.
[42] James Hanman, Approximation to bayes risk in repeated play. In Contributions to the Theory of Games (AM-39), Volume III, pages 97-139 Princeton University Press, 1957.
[43] Sergiu Hart and Andreu Mas-Colell. Simple adaptive strategies: from regret-matching to uncoupled dynamics, volume 4. World Scientific, 2013.
[44] Kamal Jain. A polynomial time algorithm for computing an arrow-debreu market equilibrium for linear utilities. SIAM Journal on Computing, 37(1):303-318, 2007.
[45] Kamal Jain, Mohammad Mahdian, and Amin Saberi. Approximating market equilibria. In 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, 2003. Springer, 2003.
[46] Martin Kaae Jensen. Stability of pure strategy nash equilibrium in best-reply potential games. University of Birmingham, Tech. Rep. 2009.
[47] Frank Kelly. Charging and rate control for elastic traffic. European transactions on Telecommu- nications, 8(1):33-37, 1997.
[48] Yoav Kolumbus and Noam Nisan. Auctions between regret-mininizing agents. In Proceedings of the ACM Web Conference 2022, pages 100-111, 2022.
[49] Yoav Kolumbus and Noam Nisan. How and why to manipulate your own agent: On the incentives of users of learning agents. Advances in Neural Information Processing Systems, 35:28080-28088 28094, 2022.
[50] Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Efstratios Skoulakis, and Georgios Piliouras. Dynamical analysis of the eip- 1559 ethereum fee market. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 114, 2021.
[51] Stefanos Leonardos, Daniël Reijsbergen, Daniël Reijshergen, Barnabé Monnot, and Georgios Piliouras. Optimality despite chaos in fee markets. arXiv preprint arXiv:2212.07175, 2022.
[52] Panayotis Mertikopoulos, Zhengyuan Zhou, et al. Gradient-free online learning in games with delayed rewards. In International Conference on Machine Learning. International Machine Learning Society (IMLS), 2020.
[53] Dov Monderer and Lloyd Shapley. Potential games. Games and economic behavior, 14(1):124-
143, 1996.
[54] Uri Nadav and Georgios Piliouras. No regret learning in oligopolies: Cournot vs. bertrand. In Algorithmic Game Theory: Third International Symposium, SAGT 2010, Athens, Greece, October 18- 20, 2010. Proceedings 3, pages 300-311. Springer, 2010.
[55] John F Nash Jr. The bargaining problem. Econometrica: Journal of the econometric society. pages 155-162, 1950.
[56] Abraham Neyman. Correlated equilibrium and potential games. International Journal of Game Theory, 26(2):223-227, 1997.
13

---

[57] Noam Nisan. Serial monopoly on blockchains
welcome. 2023.
[58] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007.
[59] Noam Nisan, Michael Schapira, and Aviv Zohar. Asynchronous best-reply dynamics. In Internet and Network Economics: 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings 4, pages 531-538. Springer, 2008
[60] Christos Papadimitriou and Georgios Piliouras. From nash equilibria to chain recurrent sets: An algorithmic solution concept for game theory. Entropy, 20(10):782, 2018.
[61] Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. Advances in neural information processing systems, 28, 2015.
[62] Julia Robinson. An iterative method of solving game, Annals of mathematics, pages 296-301, 1951.
[63] Herbert E Scarf. The computation of equilibrium prices: an exposition. Handbook of mathemat- ical economics, 2:1007-1061, 1982.
[64] Lloyd Shapley and Martin Shubik. Trade using one commodity means of payment. Journal of political economy, 85(5):937-968, 1977.
[65] Vadim I Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3(4):505, 2009.
[66] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire, Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28:2989- 2997, 2015.
[67] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions automatic control, 3 31())803--112, 1986.
[68] Mark Voorneveld. Best-response potential games. Economics letters, 66(3):289-295, 2000.
[69] Mohamed Wahbi and Kenneth N Brown. A distributed asynchronous solver for nash equilibria in hypergraphical games. In Frontiers Artificial Intelligence and Applications, pages 1291-1299, 2016.
[70] Léon Walras. Éléments d' é'ccoommii politique pure: ou, Théorie de lu richesse sociale. F. Rouge, 1900.
[71] Fang Wu and Li Zhang. Proportional response dynamics leads to market equilibrium. In Proceedings the thirty-ninth annual ACM symposium on Theory of computing, pages 354- 363, 2007.
[72] Yinyu Ye. A path to the arrow-debreu competitive market equilibrium. Mathematical Program- ming, 111(1-2)3155-5) 348, 2008
[73] Peng and Lacra Pavel. Asynchronous distributed algorithms for seeking generalized nash equilibria under full and partial-decision information. IEEE transactions on cybernetics, 50(6):2514-2526, 2019.
[74] Li Zhang. Proportional response dynamics in the fisher market. Theoretical Computer Science, 412(24):2691-269) 2011.
[75] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W Glynn, and Claire Tomlin. Countering feedback delays multi-agent learning. Advances in Neural Information Processing Systems, 30, 2017.
14

---

Appendices
In the following sections we provide the proofs for the results presented in the main text as well as further technical details and discussion.
In the following, we use V denote the gradient of function f with respect to the bids of player only. We use J to denote the partial derivative with respect to the bid of player on good j. and 02 f to denote the second derivative. We denote by 0, = Enzs by as the 'pre-prices, which represent the prices excluding the bids b, (and so, for every player i and every bid profiee, p = 0, + b,). In some of the proofs, we use the abbreviated notation (/)+ max(ff,) O). All other notations are as defined in the main text.
Appendix A
The Associated Game
Proof. (Theorem
A sufficient condition for d being an exact potential [3 is
Vi Vb, ((s, = V., (e(b,, bz).
And indeed, in our case we have:
Db, = :I((aa)) In(py) In (ij
Pj
0b.zūr b.) = In(a:y) In(p)) = In
pj
In order to prove Theorem 2 we first define a different associated game denoted G' that differs from G only in having a different associated utility function u/ = =,, aig In(p;).
In fact, & and G' part of family of associated games of the market game G, which have the property that they all share the same best responses to bid profiles (and therefore, also the same Nash equilibria) and for all these games, the function & is a best-response potential (see [68] for the definition of best-responss potential games). Among this family of games, we are particularly interested in the games G and G since the former admits & as an exact potential, and the latter has particularly simple derivative for its utility u/, which has a clear economic interpretation: Gb., (b) Ptj This is simply the bang- sang-per-bel per-buck of player from good (see the model section in the main text).
Next, we present several technical lemmas that will assist us in proving Theorem and which will also be useful in proofs later on.
Lemma 3. For any player i and fixed b-., both (b,,, b-s) and (d,(b,, b-4) strictly concave in b
Proof. We will show the proof for ū. We compute the Hessian and show that it is negative definite. The diagonal elements are
2i Ge b:) Pj
and all of the off-diagonal elements are
Don Po., ú. (b., bi) = 0.
Therefore, the Hessian is a diagonal matrix with all of its elements being negative, and thus, ū; is strictly concave. The same argument works for ut as well.
Lemma 4. Fix a player and any bid profile b- E S-; of the other players, then the following two facts hold.
1. 6 arg maNN6es (bs, b-i) if and only it holds that VU, E S, Σ, 2n 6 where pi- =0,- +,6.
4: Σ,
p.
15

---

2. bj = arg Es. ū,(b,, b-i) if and only if it holds that vo, E S; Σ, In Orj Σj Inl dei Jbsg, where P3 0tg + big. by
bi pj
2
Proof. We will show the proof for (1), and the proof for (2) is similar. Let Dy be a best response to b-; and let U/ be some other strategy. Consider the restriction of (b;b)) to the line segment [8, b, as follows; define f({) = (b)( for (5) = by + b/) where & E [0, 1). As uy is strictly concave and bq is the unique maximizer of ud, holds that f strictly concave and monotone increasing in ze
Therefore the derivative of must satisfy at the maximum point E 1 that d [(1 2 0. This is explicitly given by
)(()= Vb, (0:((() - -;).
dg
Therefore, when substituting & = 1 in the derivative we get (1) = bj. and
d (() Vb, Vo,4((b))(5 - -1))
0 s de
O&j Dis
Σ
Old B'g.
Pj
P3
which implies Σ, by
O42 P3
big. required.
To complete the second direction of the proof of (1), consider by for which the expression stated in right hand side of (1) is true for all 8/. Then, fix any and again consider the restriction of u' to [6,, b7]. By direct calculation, as before but the inverse direction, it holds that f(1) 2 0, and as uf and ((() are strictly concave, it thus must be that d ({) is monotone decreasing in &. Thus, for all z
we have de f(E) Z dg f(1) 2 O. This must mean that g 1 is the maximizer of f(E) since for all ç. d (() 2 0 implies that f(E) is monotone increasing and therefore u((b;) 2 (b)). Finally, note de
that this holds for any b% and hence by must be global maximum of ut.
Lemma 5. Let (cj)jE(m) E R", if there exists x" E nh (the m-dimensional simplex) such that Vx E Am it holds that Ej Cjzz E, c5zz == then:
1. for all we have that ej S and
2. if x > 0 then Gj = = a.
Proof. (1) Assume for the sake of contradiction that there exists i with e > a then x = 6 (the "one-hot" vector with at the k'th coordinate and O in all other coordinates) yields E, Cjæj = >
E, caary, contradiction.
Now, to prove (2), assume for the sake of contradiction that there exists h with of > 0 and Ck < a = C < aat. From (1) we have that Cj S a = Cjaj azz, summing the strict inequality with the weak ones over all j yields E, cjz E, azj = a, a contradiction.
Fix player i and any bid profile b-t E S_i of the other players, then the following properties of best best-response bids hold in the modified games G and G'.
Lemma 6.
1. The support set of bf, defined as 8 for every j s we have that c
Libby > 0}, is equal to the set (ilaij c'Osz] and
2. Best-response bids with respect to the utilities uf and ūn are equal and unique. That is, in the definition from Lemma we have 6," = by (denoted simply as b;),
3. Best Best-response bids are given by bi, ( 0zs)+ for unique constant c² E (0, m/B.).
16

---

Proof. By Lemma it; and us are strictly concave in b; for any fixed b-i, and so each admits unique maximizer. To see that they are equal, we use Lemma and introduce constants c, obtain
auj bis pj
aij Urj
4b;
Σ
and
B₁
B
46,
Σ
In
Gij
bii
n
O
d, B
B
P
where p²" = 0,j + b and pj = 0zj + b
For the ease of exposition, assume that 0ig 0 for all j. All the results stated below remain valid also when 8, = 0 for some j.
Proof of (1): Applying Lemma 5 to each of those inequalities (once with J. b and twice with x 1 bę) and denoting the support sets of b/ bi, as s't 8 respectively, obtain the following. = c and Vjj & 8"* we have + S c. Therefore, Vj E s'* bids are positive
B,
(1) Vjj E sr* we have fi
ag and c = dsj B.y B
ag S c, hence az while Vj & s"* the bids are zero, and 04j S 04y Fi 0;j 0gy0
<
Bi
8"* {ile <
Bx 0.g
}. To prove the second inequality, we use the same argument but with = In O4
and so we have that 8* = file" <
0n 0;
Proof of (2): We will show that e = d and thus obtain that the vectors by", by are identical. Assume by way of contradiction that c < e", then j E 3"
=
j j s't, i... S" S s'
For all j E 8 it holds that By = c < ed By = Fi inequalities over 8 and extend to the support s contradiction:
by < bzz Now we sum those By using the subset relation we proved, we obtain
F7 <
<
B
b B,
JES
The case where ed < c follows similar arguments with inverse roles of ,", Thus, c = ed and 8²* 5*, which implies og meaning that the prices equal as well for all goods purchased.
3".
P
Therefore 8,"" = i;-
- O.j. while otherwise by = 0, and "y Ozz < 0. For the bounds on notice that by definition it is equal to "I and that uº (0,m) as can receive as little as almost zero (by the definition of the allocation H.
Proof of (3): Finally, observe that for j E s"*
mechanism, if i places bid on good it will receive a fraction of this good, no matter how tiny) and receive at most (almost) all the goods.
The intuition of the above Lemma i that it shows a property of the structure of best-response bids. If we consider all the goods sorted by the parameter aig, then the best-response bids are 0:3"
characterized by some value e* which partitions the goods into two parts: goods that can offer the player a support s* When a player increases its bid on some good j. the bang-per- nanng-per-buckk buck offered by that good decreases, so clearly, any good with c* < ais cannot be considered in any optimal bundle. Consider
of value c* and those that cannot. The former set of goods is exactly the
0g
the situation where the player has started spending money on goods with Ry
ai > c", and that for some
goods j and & we have that dy ask. then if the player increases the bid on without increasing Py 0'
the bid on k; this means that the bids are not optimal since the player could have received higher bang-pec pep--eereeeeee buck by bidding on k. The optimal option is 'water-fin fatter-filligg one: to split the remaining
budget and use it to place bids on both j and k, yielding equal bang-per- -er---eerbbbue for both (as Lemma shows).
With the above lemmas, we are now ready to prove Theorem 2
17

---

Proof. (Theorem 2 We start by making the following claim.
Claim: The set of Market equilibria is equal to the set of Nash equilibria in the game G'.
Proof. By definition, b" is a Nash equilibrium of G' if and only if for every it holds that bj arg maxie es, ((b,,b.), where by Lemma 3 for any fixed b-., the bid profile by is unique, By Lemma 4 we have that for zij = b2p and any other 2'j- = byp ux()) 2 u,(()) if and only if (x* p
market equilibrium (market clearing and budget feasibility hold trivially). That is, the set of Nash equilibria of the game G' corresponds to the set of market equilibria (i.e., every bid profile b* which is a market equilibrium must be Nash equilibrium of G', and vice versa).
Then, by Lemma 6 best responses by every player to any bid profile b-; of the other players with respect to ü; and with respect to of are the same. Therefore, every Nash equilibrium one game must be a Nash equilibrium in the other. Thus, we have that Nash equilibria of the game & are market equilibria, and vice versa - every market equilibrium must be Nash equilibrium of G. Finally, at Nash equilibrium, no player can unilaterally improve their utility, so no improvement possible to the potential, and in the converse, if the potential is not maximized, then there exists some player with an action that improves the potential, and so by definition their utility function as well, thus contradicting the definition of Nash equilibrium. Therefore, we have that every bid profile that maximizes the potential is Nash equilibrium of G and market equilibrium (and vice versa). N
Appendix B Best Response Dynamics
We start with the following characterizations of best-response bids in the games G and G'.
Eye, oz
Lemma 7. Fix Oç and let bū be i's best response 0g with support s" Define C, B,, 0bg for
every subset s S [m]. Let ct be described in Lemma 6 Then, it holds that e Co- Ce for all s S [m]. Furthermore, if s &f s then Cg- > Ca.
Proof. Let by be a best response 8 with support s". By Lemma 6 we have that big (1i 01y)²
By summing over s" we obtain that B, = Ejess c Ozj. Rearranging yields c" Enjer
Σ
Li. O.g
which is cs- by definition. Now we prove that c* = max C.. A key observation to the proof is that, by Lemma j E s" then 0z0 < aij and otherwise 0.g 2 aij-
For a set distinct from s" we have two cases:
Case (1): s* s's Consider bid profile by that for every good in s' nn** (if the intersection is not empty) places a bid higher by e > than bi and distributes the rest of i's budget uniformly between all other goods in s:
s'.
big
TijEsn ifjes'ss'
B. E Eier' (cg
otherwise.
10'
For small enough, we have Ejes' b/y3 B, and the support of D; is indeed s'. For every j E 8" sis' we have b,y > bi, and by adding B,y to both sides we obtain p'} > pf: multiplying both sides by c* yields (i) c'p', > c²p} aij. where the equality by Lemma 6 while for every j e s'),s* it holds that c'Oy 2 azy by which adding b'byy, to the left hand side only increases it and implies (ii) e'pl, > asj- Summing over inequalities (i) and (ii) for all appropriately, we obtain e* Ejes' p', Ejes agj observe that Ejer p'J = Exe (b,y + 01z) = B, - Ejer Ozj. and thus by division, we obtain the Eger 4ig result: C² B.-
Car.
Case (2): 8" C S'. In this case, the idea used above can not be applied since adding to every bid bi Σye,- ai would create bids by that exceed the budget B: As stated above, the equality c² B.+2 By holds where the sums are taken over all members of s", by rearranging we get c* B,+ EyEs- Bij Ejer aij. For all j e s' \ s* it holds that c² 02g 2 aij and by summing those inequalities for all
18

---

and adding the equality above we obtain: c* cBB, + c E'Eess Oej 2 Ejeee Oi Rearranging yields the Lg ats
result: B, B.-2,jen' 0tz
Cgr.
And so c² is obtained as the maximum over all Cs, as required.
Lemma 8. The function BR, S_; - St which maps b-s to its best response by is continuous.
Proof. By Lemma 6 best-response bids given by big max = Ozg. 0}. with support sf. We wish to show that b; a continuous in b-g. We do so by showing that bi is obtained by composition of continuous functions. As 0, is a sum of elements from b-s. it suffices prove continuity in the variable 0, The expression for byy is the maximum between zero and continuous function of Oij. which is continuous in 0., and so we are left to prove that Gi O.j is continuous in 0,. More specifically, suffices to show that c* as defined in Lemma 6 continuous in 6,.
By Lemma 7 c* is obtained as the maximum over all functions, where each is continuous function itself in 0g, and thus c* is continuous in 6,.
To prove Theorem D on the convergence of best-response dynamics we use the following known result (for further details see [46]).
Theorem (Jensen 2009 [46]): Let G be best-reply potential game with single-valued, continuous best-reply functions and compact strategy sets. Then any admissible sequential best-reply path converges to the set of pure strategy Nash equilibria.
Proof. (Theorem 4 G' is potential game, which is stricter notion than being best-reply potential game (i.e., every potential game is also a best-reply potential game). By Lemma 66] best replies are unique, and so the function BR; is single valued. Furthermore, Lemma 8 shows that it is also continuous function. By definition, for every the strategy set S, is compact, and so their product S is compact well. Note that while the best-reply function with respect to the standard utility function is formally undefined when the bids of other players on some good j are zero, what need is for the best-reply function to the associated utility to be continuous, and this is indeed the case. Admissibility of the dynamics is also guaranteed by the liveness constraint on adversarial scheduling of the dynamics, and thus by the theorem cited above, best-reply dynamics converges to the set of Nash equilibria of G. Since every element in this set market equilibrium (by Theorem 2) and equilibrium prices are unique (see the model section in the main text). we have that any dynamic of the prices are guaranteed converge equilibrium prices. Furthermore for a generic market there a unique market equilibrium (by Theorem 5 and convergence to the set in fact means convergence to the point b", the market-equilibrium bid profile.
Proof. (Proposition Dc Fix a player fix any bid profile b_. of the other players and let by be i's best response to b-;, by Lemma by = ( 0i,)* + for e being a unique constant. We present simple algorithm which computes c* and has a run-time of Om log(m)).
Algorithm 1 Compute e"
Require: 0;, B;, 0;
Sort the values a,, 0, according to Og in a descending order. If there are goods with 0,j- = 0, sort 8, them separately according to oij and place them a prefix (lower indices) before the other sorted goods. Equal values are sorted in a lexicographical order.
Set: + 0, 1-0 O, Co +0, 0, c² 5+0
for j L....,,, m do
a + a aij, 0 +- + Oz
c - 0+B;
6² + max (c", cc)
end for return
19

---

To see that this process indeed reaches c², assume w.l.o.g. that the goods are sorted by as in descending order. For ease of exposition, assume 0zj 0 for all j; the case with 0,j 0 for some goods similar. By Lemma 6 we have s" = [j]ay > c c00sp )- And so, if h < and E s* then & E s", since in this case Bis Big
da2 c*. Therefore, s* must be one of the following sets:
[1], [). [3)....,I [m]. By Lemma 7
we have c* = mmx Cs. For any set mentioned, the algorithm
Eee, on computes Co n, Eze Bi and finds the maximal among all such C.. and therefore it finds c².
As for the running time of the algorithm, it is dominated by the running time of the sorting operation which is Om log(m)).
After proving that the best response to a bid profile can be computed efficiently, we can prove now that proportional response, applied by single player while all the other players' bids are held fix, converges in the limit to that best response.
Proof. (Proposition 2 Fix player i and fix any bid profile b_; of the other players, let bj be the best response of i to b- with support 8* and let (b)) be a sequence of consecutive proportional responses made by i. That is, b f(())). We start the proof with several claims proving that any sub-sequence of (b))g= cannot converge any fixed point of fa other than bj- After establishing this, we prove that the sequence indeed converges to b;
Claim 1: Every fixed point of Proportional Response Dynamic has equal "bang-per-buck for all u,"
for every good j with goods with a positive bid. That is, if b;" is fixed point of f; then ti = B, bij > O, where ut" is the utility achieved for i with the bids 6,*
Proof: By substituting by" into the PRD update rule, we have
6 f((b?")
as/p; Vj bij ui' wi'/B.
bij
either bij = 0 as/p;" vi¹ "i'/Bu.
Claim 2: The following properties of by hold.
1. Except bj, there are no other fixed points of fo with support that contains the support of 6;. Formally, there are no fixed points 6,* + bū of fa with support s** such that s" S
2. The bids by achieve higher utility in the original game G, denoted uf than any other fixed point of Proportional Response Dynamics. Formally, let 6, be any fixed point other than 6ū. with utility u²* in the original game G, then uf uf"
Proof: Let b; be any fixed point of St. By the previous claim it holds that بي di whenever bij > Multiplying by pj yields aig 2h pj. Summing over j with bij > 0 and rearranging yields
py
m: E,e, Gu C, as defined in Lemma with support 8. By that lemma, we have that c., 2 ca for any set distinct from s" Thus, we have that wi/B, = C.- 2 Cgee = wi"/B, for b being a fixed point of Sa other than by with support ** and utility value uf*
B. E,e.
Assume for the sake of contradiction that 8 C 8t Jf E s* then j E 8*x By Claim I for every such j the following inequality holds,
0ij
aij
Pj
B
B
implying that p 2 P). Subtracting 0ig from both sides yields b 2 blz- Summing over j s* yields a contradiction:
B
Σ b/
bij = B.
JEs
jEs
"E
20

---

where the first inequality is as explained above, and the last by the strict set containment s* C C's". Finally, as there are fixed points with support 8** containing 8", by Lemma] 7 the inequality stated above is strict, that is Cg- > Ca-- and so up > "
Claim 3: If 6," bb is a fixed point of fi then 6g" is not limit point of any sub-sequence of (6))==
Proof: The proof considers two cases: (1) When uy is continuous at b** (2) when continuity doesn't tt (b >==1 (0'x)==1 be converging subsequence of (b)))=
hold. Let
Case (1): The utility function u, is continuous at 6," when for every good j it holds that 0,y > 0 or bij > 0. i.e. that there is no good j with both O.j = 0 and bij 0. This is implied directly from the
allocation rule Tij Biytbu (see the formal definition in Section 2 and the fact that u, = -, "ijaig. Examine the support of 6," by Claim 2 there are no fixed points with support set 8* containing 8*. Therefore s* L s** implying that there exists a good j E 8* \ 8"* That is, by definition of the supports, there exists with bi > 0 and bij O. Consider such and assume for the sake of contradiction that 6," is indeed a limit point. Then, by definition, for every 8** > 0 exists a T s.t. if t > T then ||6T* - big1 || < 8t Specifically it means that 161; bū < 8* whenever > T.
beg
By Claim 2, u > - Then, by continuity there exists 8' s.t. if ||,;" bbill < 8' then (u, (b,) - < " -u"" Take 8tx < min(8', (8', big) and, by the assumption of convergence, there is a s.t. for 1 > T
and we have that 1|650 b;"ll || < 8".. This implies (I) |b4 0 < 8" < big as būj and (II)
|u2" u1"l u.; u," u < ut From these two, we can conclude that
tx
Osg Pj
O3j Ozj
03g
05
B;
B,
"u/l"" "/t//, b2. implying that
Finally, observe that by rearranging the PRD update rule we get 6/71
"ss/s"" t
+ >
b since
> 1 for > T and bg > 0. This means that for all t& > T we have
/ Bi 12 That is, bit cannot converge to zero and thus the subsequence cannot converge to 65*h contradiction.
15
Case (2): When there exists a good j with 0,g = 0 and b5j = 0 we have that u, is not continuous at 6,* and the previous idea doesn't tt work. Instead we will contradict the PRD update rule. Assume of the sake of contradiction that 6/* is limit point of a subsequence of PRD updates. Therefore for every exists T s.t. if lg > T then 1bt and so, for tu > '' holds that
bjj < Note that bij 0 in this case and set < SM B,
as by
>
ma TR.
Also note that p = 0 + 6 b/t and that the maximal
utility a buyer may have is m (when it is allocated every good entirely). Then overall we have that 5x
The PRD update rule is 8%
is greater bty And so every subsequent element of the subsequence is bounded
"43/23² b.C But since the ratio '/'/8
a3s/r ,///m
than it must be that b +1 below by FT+1 > 0 and as before, we reach a contradiction as the subsequence cannot converge to 6,*
Finally we can prove the convergence of the sequence (6)) As the action space S is compact, there exists a converging subsequence beth with the limit 6," If b, = by for any such subsequence, then we are done. Otherwise, assume b, A bद. By the previous claim any fixed point of f. other than 6r is not limit point of any subsequence, thus 67* is not fixed point of ft. By Lemma D any subset of players performing proportional response, strictly increase the potential function unless performed at fixed point. When discussing a proportional response of a single player, with all others remaining fixed, this implies, by the defnition of potential function, that ü, is increased at each such step. Let < ūz ()(")) (b,"))) )), this quantity is positive since 67" is not fixed point. The function ü; fi is a continuous function and b.* converges to b," therefore there exists T such that for all L. > T we have that [āz({((b²*)
(1.(()))) ))] < e. Substituting yields ū. (fb*))) - ü, (J(())))) < ū, (f(()))) (,(**) which implies ū,(b**) ) < (,(()(b))) = (b==-11) S ã. (b(+11)) That is, the
21

---

sequence u.(b,' is bounded away from (b(b"*) and since ù; is a continuous function, this implies that b/th is bounded away from b a contradiction to convergence.
L
Appendix C Simultaneous Play by Subsets of Agents
In order to prove Lemma we first need some further definitions and technical lemmas. We use the notation (arlly) to denote the KI. divergence between the vectors x and y, i.e., Dxrllyy) = dn In( y; )- For a subset of the players v C B, the subseript of the vector to the coordinates of the players in v, that is, for a vector b we use the notation b, (bi))sen.jE(m)) to express the restriction to the subset. Eg (bui b,) denotes the linear approximation of c that is, lo (b,; b.) = ((b)) + Va, ((b,) (he - -;).
).
vectors denotes the restriction
The idea described in the next lemma to present the potential function as a linear approximation term and divergence term was first described in [5] for a different scenario when all agents act together in synchronized manner using mirror descent; we extend this idea our asynchronous setting which requires using different methods and as well as embedding it in game.
Lemma 9. Fix a subset of the players all by By E Sy we have that ((b)) = La (b,;; by) - D(plpp',, where = Liςn bij + Eieo big and
B and a bid profile b- the the other players. Then, for
p' = Eigo bij + +iie Ky.-
Proof. Calculating the difference l(b,) - lo (abbbi b() yields
(bb)) - Lo (be; bb,) = ((b,) - (bb,) Vo. ((b,)(b, - -b,)-
We rearrange the term (bb,) ((b,)) as follows.
((bb,) ((b.))
Σ (big bly) In(aes) E (p, In(p;) - D In(p)))
E(s, - p/)
iEu.jE(m]
Σ
(bij b/y)) In(azs) - -(p, In(p)) p'J In(p))).
SEv.JE[m]
where the last equality is since E, P, = 1 for any set of prices because the economy is normalized (see the model section in the main text).
The term VE, (bb,)(b - -b)) is expanded as follows.
V5, (bb.) - -b,)= = E
In aij (bis Bbi))
iEr.E((m]
Σ
In(a:r)
bbz)
Σ In(p))(be b(y).
iEn.Ei[m]
(EV.jE[m)
Subtracting the latter from the former cancels out the term Eienje(m) In(ac))(b)) - bly), and we are left with the following.
(bb,) (o (bbb)) ((K)) Vo, (lK.) - (())
Σ In(p)) - -by) - Σ (p, In(p)) - p/, In(p)))
#Eo.jE[ml
Σ py p))p(())) - -1/s Σ b/s
bis) In(p/)
sE0
iEv
Σ P3 py(n(,)) - -(Buj + Σ
bey)) In (n(p)))
J
i
Σ
PS In(ps) p. In(p/))
5
-p(lll'')
22

---

Lemma 10. For any subset of the players C B and any bid profile b-v of the other players and for every by by Sy it holds that D(plly') I D(b,,1bb), with equality only when b, = by.
Proof. We begin by proving simpler case where = {i} for some player i and use it to prove the more general statement. Fix and b-g. which implies fixing some 0,. KL divergence is convex in both arguments with equality only if the arguments are equal; formally, for À E (0, 1) it holds
that D(A;; + (1 - X)b; A8; + (1 2) I | + (1 ((; [K), which is equivalent to D(A0; + (1 A)6; A6; + (1 ))oe) S (1 - (b; (.). with equality only if b 8/ (since
D(O: |10.) 0). Substituting À = 2 and noting that pj- = Ozg + bij (and the same for p/J and b/y), ) we
obtain the following relation.
D DI pll )1)) Di, 0:
1
2 20l11
1
] %)
$ (bb (b:(((b))
On the other hand, the expression D(Epl =1)) can be evaluated as follows.
D 2 D²)
Σ
Σ
p2/ In(
1/2p3
1/225$
1
Σ
Py In( 2/)
2
3
マタ D(pllp').
And therefore, we have D(plip') (bbillb),, with equality only if b, b/.
Now we can prove the general case, as stated fix v and b- and let b,, b2 S,, We know that for all i E v it is true that D(plip') < (bb [K]), summing those inequalities for all i yields [o) D(Plle/) & Eieo D(b [B(), on the one hand clearly D(pllr') I (pllly))) and on the other hand Eiev D(billb,) Eiev E, big In (bs D(bollb,, and the result is obtained.
(2)
Lemma 11. Let S. B, let fo S + S be proportional response update function for mem- bers of e and identity for the others, and let t' E S be some bid profile. Then, (f)())), = arg es, (bo b,) D(b..(bb)).
Proof. By adding and removing constants that do not change the maximizer of the expression on the right hand side, we obtain that the maximizer is exactly the proportional response update rule:
arg max (b.:bl.) ((b.11b()) = arg max ( E..
) + V., (bb))(,, .(.) ((bb.166))
b, E.
arg max (Vo, (b, )b. - ((bal1bb.)) E.
arg max (Vo @bb)),, D(b.llb)) Σ B, Inf lnt b. E..
}
B
sev
23

---

Rearranging the last expression by elements yields the following result,
u
Ve L(b,)b,
-
Σ iEv
B,
In
Bi
bjj In
u B
Σ
big In(
bij
Σ
bug
In(
V/
vEv.jE/m)
(Ev.jE/ml
Big big
Bg
Σ
Dey In
p2 big ub
vEr.jE[m]
E iEv.je(m)
big In(
big
big
Σ
byg
In(
aes B
[Ev.jE|m]
which is exactly -D -D(b, since (Jo(3))ss = يلووي B3 for i by definition. That is, our maximization problem is equivalent to arg min (iinnD(b,lllee ((l,Il().(()))) Finally, note that KL divergence is minimized when both of its arguments are identical, and (b,)), S., the domain of the minimization.
Proof. (Lemmal) I): Let u S B be a subset players and let b E S be some bid profile. By combining the lemmas proved in this section have that
(b)( 2 La (f.((bb): - ((f.(b)llb) 2 to (b: Dbblb) = ((b).
where the first inequality is by Lemmas 9 and 10 with the inequality being strict whenever fb(b) + b. and the second inequality is by Lemma II as (b) was shown to be the maximizer of this expression over all b E S.
An interesting case to note here is when v = i. In this case, the lemmas above show that if the players' bids are 1f and i is being activated by the adversary, then the best response bids of i to 6", are the solutions to the optimization problem arg max {La, b)); - (pllp")) On the other hand, the proportional response to 6L,, is the solution to the optimization problem arg maxi, cS, (fi, (b;; b9) D(b,,i(bb [[[]). This can be seen as a relaxation of the former, as proportional response does not increase ū, (or equivalently the potential) as much as best response does. However, proportional response is somewhat easier to compute.
Appendix D Convergence of Asynchronous Proportional Response Dynamics
Proof. (Theorem) T Denote the distance between point and a set S as ((xx inf |x-r"|l By Theorem 2 we have that the set of potential maximizing bid profiles is identical to the set of market equilibria. Denote this set by ME and the maximum value of the potential by T. More specifically, every b' E E achieves (bb²) = xb", and t" is achieved only by elements in ME.
We start with the following lemma.
Lemma 12. For every >> 0 there exists 8 > 0 such that ((b) > o- 8
8 implies ((6.M)
Proof. Assume otherwise that for some 6n there exist a sequence (b.) such that (bb,) + oh" but |b, inf 6*11 > 6o for all Note that for all 6* ME we have that x(b") = x* and [lb, 6 2 infVEME 1b, b']l 2 en for all f. Take a condensation point 6** of this sequence and a subsequence (t,) that converges to 6** Thus by our assumption we have d(b**) lim ((b,,) ".
For any 6" E . E we have 1|6^ b* || lim [bb,, b* 2 co 0. The former equality must imply 6"x . E, but the latter implies 6** of ME..
24

---

Next, for a subset of players A C B let fA [0, - 10, 1 be the continuous function where i A do proportional response update and the other players play the identity function. (i.e., do not change their bids, see Section in the main text).
By Lemma from the main text we have that (i) For all A we have that fa(b) b if and only if for all i E A it holds that (b) b; and (ii) (fa(b)) > ((6) unless (b) = b.
Definition. The stable set bf is defined to be S(b**) {il5a(b**) = =.
A corollary (i) and (ii) above is that if A C S(b*)) then fa(b**) = b²* but if A ((("*)) j #0 then (fa((b))) > ((b*)).
Lemma 13. Let (0(*)) < 6- Then there exists > 0 such that every ||b b*1l || S á and every A A\5((b)) + 0 we have that & (f)(b)) > $(b**).
Proof. Fix a set A such that A A) S("**) jf 0 and let ((((("')) -((7))))))))) > 0. Since ((fa()) is continuous, there exists ō so that |bb ba*l < 5 implies ((Ia(b*)) (fx(6)) < a and thus
(b.t) )
(f)( > "(b**). Now take the minimum ó for all finitely many A.
Lemma 14. Let ((b'*) < t0' and let F be a finite family of continuous functions such that for every f E F we have that f(b")== b Then there exists > O such that for every b such that ||b bnll S c and every f E F and every A A3, S(b**) ) + 0 we have that ((a(((()) > $(b
Proof. Fix f E F and let 5 be as promised by the previous lemma, i.e. for every ||= b*"1 S 5 and
every A A S(b**) # we have that ((fx(z)) > $(b**). Since f(b"* = b* and f is continuous
there exists > 0 so that [lb - b²1ll S implies (b) fbb"")ll = (b) - b"ll S 8 and thus
((a()())) > D(b**). Now take the minimum e over the finitely many f f F.
Definition. a sequence of sets A, B is called T Tllive for every i and every there exists some t t to S t++ + T such that i E St-.
Lemma 15. Fix a sequence b = (be) where b = fA. (be) such that the sequence Ae is T-live There are no condensation points of (be) outside of ME.
Proof. Assume that exists a condensation point b** & M E and subsequence that converges to it, then ((b*)) < {bb"). Notice that (b,) a non decresssgg sequence and so (b,) S $ ((b*)) for all
t. Let F be a set of functions achieved by composition of at most T functions from {f A C (} So for every f E F we have that f(b**)
6" while for every B \ S(b*)) * we have that ((sn(b**) > ((b*)). Let 6 be as promised by the previous lemma, i.e., for every ||b 6** S and every f E F and every such that B \, S((** o 0 we have that (ff((f())) > ((b*). Since the subsequence converges to h*a there exists lj in the subsequence so that [1br - b** Se Now let t > fú be the first time that A, (S(b**) jf 0. Now b = fa,(f(b,)), where f is the composition of all fA for the times tj to t. We can now apply the previous lemma to get that ((b++1) = & (ffA. (f(bi,)) > (bb*),, a contradiction.
Lemma 16. Fix a sequence b = (bc) where bit1 = (bi) such that the sequence A, is T-live. Then, it holds that lim d(be, ME) O.
Proof. By lemma 1 we have that abb++1 2 (bb²) making the sequence ((b²) monotone and bounded from above (d(-) is a bounded function). Hence converges to some limit L. Either L = 4* or L < 4- In the former case, the result is immediate by lemma 12 and b' approaches the set M. We show that the latter yields a contradiction. If L 4- this implies that b² is bounded away from ME, i.e. there exists > O such that for all t d(b', ME) 2 Cu- To see why this is true for all and not just in the limit, we observe that since the sequence (bb)) is monotone, if we have d(bb. E)= assume is not the case. Therefore, every subsequence of bt is bounded away from M,, implying that every condensation point of b' is not in E... The sequence b' is bounded and therefore has a converging subsequence with condensation point not in M F, which is a contradiction to the previous lemma
at some time T, then we have ((b') = x* for all t > T, which we currently
25

---

Regarding convergence of prices, as stated in section 2 equilibrium prices for each Fisher market are unique and attained by any bid profile b* E E, thus, since the prices are continuous function of the bids, the convergence of bids to this set implies the convergence of prices p' + p".
The last lemma concludes our proof of the Theorem T
Appendix E Generic Markets
Proof. (Theorem 5) Assume by way of contradiction that generic linear Fisher market has two distinct market equilibrium bid profiles by * b". For any market equilibrium it must hold that: (I) Vj bi Pj since equilibrium prices are unique, and (2) Vi Σ, bij B; by budget feasibility. As * 6** there exists a pair (i.j) with bf * bij. meaning that buyer i has a different bid on good j between b* and 6**, and so by (1) it must be that exists a buyer & whose bid on good was also changed so that the price Pł remains fixed; formally, D/5 * bgg- In such case, by (2) there must be a good for which buyer & has different bid well, since it's budget Bg is fixed and fully utilized; formally be + bez. As the graph r {B U G, }} with E = {fi, j} b/g & by is finite, following the process described above while satisfying the constraints (1) and (2) must lead cycle in the graph I.
Finally, we will show that there exists market equilibrium with cycle in its corresponding graph. Define 1/ = \か* + (1 A)b** for some À E (0, 1) and note that D' is also market equilibrium as the set of market equilibria is convex set (see the model section in the main text). Let [(b')
{B U G, E(b)} with Ebb" = {iij)Hb, > 0} be the corresponding graph of 6' Observe that E C E(8') since if b/ * bij then it must be that bi > 0 or b > 0 and in any such case b/y > 0. Thus, the graph r(66) contains a cycle, contradicting Lemma 2 from the main text
Assume for the sake of contradiction that exists a cycle C r(b*), w.l.o.g. name the vertices of buyers and goods participating in the cycle in an ascending order; that is, C big1b292-- ... ---1-1hhh where and gi represent buyers and goods respectively. Recall that for any market equilibrium if mi > 0 then "y = for some constant (see the model section in pj
Proof. (Lemma 2
the main text). Applying this to the cycle yields the following equations. (1) By considering edges 0,, c,p, and (2) by considering edges
from buyers to goods b, 9: obtain for i [k- from goods to buyers gi - bi+1 we obtain for i E [k [--1] 1] a,+1,; = + IP, and the edge closing the cycle yields 01,A = cpt- Finally, by considering the product of ratios between valuations of buyers participating in the cycle we have the following condition.
021 032 443
actla
dg.--1
C2Pi Cap2 cap3
C+IP
CxPh-1 CIP
Q11 a22 433
01
1--1 OK
cIPi C2P5
caps
cpp
Ck- 1P-1Ph-1 CAP
C2 03 C4
Cs
Ci
C2 C3
C
Ck-1 Cj
1,
which contradicts the genericity condition.
26


Reviews:
[{"review_id": "yPJGO0Yxci", "reviewer": "Reviewer_zQMj", "summary": "Summary: The paper studies the Fisher market model, where there is a set of m sellers and n buyers. Each seller brings a unit of a divisible commodity for sale and each buyer brings a budget. The vendors value the money while the buyers value the commodities (goods).  A substantial amount of research has been done to develop methods for computing market equilibria and to understand the computational complexity of this problem. \n\nThis paper makes progress on understanding a well known type of dynamics called proportional response dynamics, where the market starts in some initial configuration and evolves over time. The agents modify their bids based on past engagements with other agents and former market state(s). Specifically, in proportional response dynamics, each agent adjusts their bids relative to the utility value of the goods in  the preceding round. Previous studies demonstrated that proportional response dynamics gravitate towards market equilibria in diverse scenarios; these dynamics are also interpretable. \n\nSynchronous dynamics, where the players adapt their strategies with the same speed were studied extensively in the past work, but the more realistic asynchronous setting is less well understood (and before this paper not understood at all for the family of proportional response dynamics). The contribution of the paper is to study asynchronous proportional response dynamics in a very general setting where at each step a subset of players, adversarially chosen, update their strategies, with the constraint that each player has some minimum frequency of responding.\n\nThe main results of the paper are:\n\n(1) For generic linear Fisher markets, proportional response dynamics with adversarial activation asynchrony, where each player is activated at least once every T steps, converge to the unique market equilibrium.\n\n(2) The paper also finds a connection between the Fisher market and an associated game, such that the set of market equilibria of the Fisher market are the same as the set of Nash equilibria of the associated game and, furthermore, the same with the set of points that maximize a potential function \\Phi (for which synchronous proportional response was shown in prior work to behave as mirror descent on this function). The paper shows that every proportional response step by any subset of players increases the potential function \\Phi.\n\nEvaluation: The paper makes several nice and significant contributions in a fundamental setting, contributing to the development of a theory of markets with learning agents. Such dynamics capture settings such as the stock market, which evolve over time. The paper raises intriguing questions for further study, such as how far asynchrony can be pushed, quantifying the rate of convergence depending on the extent of asynchrony, and investigating the correspondence identified in the paper between the proportional response dynamics and the associated game.\n\nVarious comments:\n\nPage 2, line 60: “intermdiate” level of asynchrony -> intermediate\n\nPage 6, line 236: \"\\Phi is it’s potential\" -> its potential\n\nPage 7, Lemma 1: \"for all\" should be capitalized -> For all\n\nGeneral suggestion -- some long inequalities or inequalities with fractions of sums are inlined (see e.g. page 5 line 205 in the main text, or page 3 in the appendix line 92 or page 5 in the appendix) and they are harder to read for this reason, it would be nicer to use displaymath or another environment like that. There are also some long paragraphs (e.g. when introducing the Fisher market) which could be divided into several shorter paragraphs for improved readability.\n\n", "questions": "There is something that I don't understand and may be missing. Does the associated game have a compact strategy space? For instance if all players bid zero on a good, then the price of that good is zero. The best response is not well defined at such a strategy profile, as  there can always be an improved response by a player - for instance, if the price of a certain good is zero and the player finds the good appealing, the player could bid 1 to acquire all of the good, but then bidding 1/2 would still enable them to secure the entire good while leaving some budget to increase the bid on other goods, and so forth. Essentially, the game seems to exhibit discontinuities at the strategy profiles where the price of a certain good is zero. Is Jensen's theorem applied to this game? If so, how does it work? (specifically, how does condition (1) in Jensen paper play out).\n\nNote there are theorems that deal with games with discontinuous payoffs (e.g. https://link.springer.com/article/10.1007/s00199-015-0934-3 and https://www.jstor.org/stable/41237788). \n", "limitations": "The authors have acknowledged the limitations of the paper and explicitly stated the open problems remaining to be solved, including analyzing the rate of convergence, studying even stronger degree of asynchrony, and so forth.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ The paper makes several nice and significant contributions in a fundamental setting. \n+ The paper is clearly written and of interest to researchers working in the space of games and learning.\n+ Raises good questions for future work, such as how far asynchrony can be pushed, quantifying the rate of convergence depending on the extent of asynchrony, and investigating the correspondence identified in the paper between the proportional response dynamics and the associated game.\n", "weaknesses": "- Rate of convergence is not shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Yes, the strategy space is compact, it forms the full polytope where each buyer allocates its budget arbitrarily among the items. While you are correct that the best-reply function with respect to the standard utility function is formally undefined at zero, what we need is for the best-reply function to the *associated* utility to be continuous, and this is indeed the case. We note that the best reply to the associated utility function does not imply minimizing the bid on a good for which all the others bid zero, but rather there is a finite bid that equalizes the bang-per-buck. We will add a clarification about this in Section 4 and emphasize this further in the proof of Theorem 4. \n\n\nEditing comments: Thank you for these helpful comments, we will incorporate them into the paper.\n"}, {"review_id": "I9C8RYYy7I", "reviewer": "Reviewer_h7DH", "summary": "This paper studies the problem of convergence in Proportional Response Dynamics (PRD) in linear Fisher markets when participants update in the dynamics under adversarial scheduling, i.e. an adversary specifies which subset of agents update their dynamics in a given round, subject to the constraint that each agent must be activated once every $T$ rounds at least. By leveraging auxiliary games and potential functions, it is shown that these asynchronous dynamics converge in generic settings; moreover, this analysis and connections also show that other natural dynamics also converge.", "questions": "---While I am not an expert on this particular setting, all in all, this paper seems to make significant progress on an open problem in convergence of PRD. Moreover, the analysis appears both conceptually clean while novel (or rather, a nice twist on an existing approach), which may lead to further progress towards the remaining open problems highlighted in this work. I would defer to other reviewers on the significance of these results.\n\n---The related work section and discussion appeared quite extensive, though I (again) am not an expert on this particular line of work. \n\n---I could not verify all the details in the Supplementary Material; however, the arguments sketched in the main text seemed to make reasonable sense.\n\n---Towards making progress on the main open problem posed in this work (i.e. total asynchronicity with delays), are there intermediate versions of this that may be amenable to a similar analysis? For instance, if there are stochastic or deterministic (i.e. nonadversarial) delays?", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work makes substantial progress on an open problem on the convergence of adversarially scheduled PRD. En route to this result, this work also derives implications for other dynamics by exploiting new structural properties of auxiliary games they consider for the analysis. In general, this paper is quite well-written and the arguments in the main text are well-explained.", "weaknesses": "While this work makes substantial progress, it feels like attaining rates of convergence should be achievable under some adaptation of the (seemingly new) arguments provided here; however, the current analysis relies on compactness-style arguments so do not seem directly amenable to answering this question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Regarding the question about intermediate asynchrony models, we agree that intermediate levels of asynchrony with information delays are an interesting avenue to explore which can be useful for making progress in (or at least gaining insights on) the analysis of full asynchrony. Considering stochastic delays is an interesting direction that we have not yet explored. Another approach to consider when examining intermediate models is to start the analysis with very limited adversarial information delays (e.g., delays of a single step). We believe that it might be possible to extend our methods to handle such adversarial delays, but we have not pursued this route in the present paper and leave this analysis for future work.\n"}, {"review_id": "s26R1l0gxt", "reviewer": "Reviewer_pHCS", "summary": "The paper studies the convergence of Proportional Response Dynamics in linear Fisher Markets.\nFisher Markets are markets consisting of m divisible goods that should be shared among n agents with a linear utility function on items. The market not only must to decide the allocation, but it must also assign a payment to each agent for the fraction of each good she receives. We want that all items are sold (market clearing), that no agent spends more than her own budget (budget feasibility), and we are willing to allocate items so that there is no alternative market clearing and budget feasible allocation that an agent would prefer to the returned allocation (equilibrium).\n\nIt is known that a market equilibrium exists and can be computed in polynomial time by a centralized algorithm. Moreover there is a decentralized algorithm (known as tatonnement dynamics) that enable agents to quickly converge to the equilibrium, even if an adversary can choose at each time step which non-empty subset of agents would apply the dynamics update rule (subject to some fairness constraint).\n\nIn this work instead it is considered another dynamics (proportional response dynamics) that has been proved to converge when all agents update at each time step, but it was unknown whether this convergence property holds even against the above described adversary. This paper addresses this problem, by providing a positive answer.\n\nThe result is proved by observing that PRD for linear Fisher markets are equivalent to best response dynamics for a suitable potential game.", "questions": "See above.", "limitations": "Partially", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and presentation is very well-articulated and clear.\nWhile the result re-uses some ideas previously established, it built an original framework to prove the main theorems on top of these ideas.", "weaknesses": "My first doubt about this paper is the relevance of this paper for this venue. While Fisher markets have been a very successful topic in economical and game theoretic literature, and computational aspects related to these markets have been of interest for theoretical computer science, these markets have not attracted very much the attention of AI community, maybe for the scarce practical applications (this can be seen also from the reference list of the paper). The paper does not make any effort to justify the study of these market within this community, neither it provides relevant applications.\n\nMy second doubt is about the relevance of these results. Why should we interested in proportional response dynamics if there is already a distributed dynamics that is known to converge to equilibrium even in an adversarial setting, that does it quickly, and that is a quite natural dynamics? Is there some motivation behind PRD that is not common also to tatonnement? The paper cites about similarity to a learning approach. Why this cannot be said also about tatonnement? And why should we interested to PRD convergence without bound on convergence time whenever we know that another dynamics converges quickly?\n\nBased on this last comment it would be interesting to see in the experimental session a comparison about convergence of PRD and convergence of tatonnement, that is instead absent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We address below the specific points raised in the review.\n\n\nRelevance: While we agree of course that our analysis is theoretical, we believe that the paper is relevant to NeurIPS: Natural dynamics in markets (such as the PRD that we study) can be viewed as the aggregate emergent outcome of joint simple learning strategies of the participants.  We believe that studying the emergent outcome of multiple interacting learning agents is an important and timely research area in machine learning, both theoretically in general and for economic applications.  Additionally, we note that the NeurIPS call for papers this year explicitly includes \"Algorithmic Game Theory\" in its list of topics.\n\n\nMotivation for exploring PRD: We agree, there is no doubt that tatonnement may also be viewed as a type of multi-agent learning, although with \"goods players\" responding to the excess demand rather than bidders responding to prices. Both models are interesting and have been widely studied. We believe that there is still much work left to be done on both dynamics, especially considering the perspective mentioned above of emergent behavior by multiple interacting learning agents. \n"}, {"review_id": "JTxcYI0QYI", "reviewer": "Reviewer_j9g9", "summary": "In this paper, the authors examined Proportional Response Dynamics (PRD) in linear Fisher markets in a setting where participants act asynchronously. In particular, they considered a setting where at each step, an adversary selects a subset of players to update their bids. The paper showed that in the generic case, if each bidder individually uses the PRD update rule when included in the selected group, then the entire dynamic converges to the market equilibrium. As part of their proof, they have also established other properties such as uniqueness of the market equilibrium and the convergence of best-response dynamics in an associated game.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper studies an interesting setup of the linear Fisher market where the activation can be asynchronous. \n2. The theoretical results of this paper appear quite sound. The authors adopted novel proof techniques; in particular, they established an important connection between the associated game and the original game, which helped prove the convergence of asynchronous PRD.\n", "weaknesses": "1. One thing that appears missing from the current paper is the motivation behind studying the linear Fisher market with asynchronous PRD. It is essential to provide a rationale for studying this particular setting and justify why it is important. Since the authors only allow an intermediate level of allowed asynchrony, it becomes even more crucial to justify why this specific setting is worth investigating.\n2. The organization of the paper is unclear, especially regarding the relationship between the results presented in Sections 3-5 and the proof of Theorem 1. I find it a bit difficult to follow the flow and understand which results contribute to proving Theorem 1 and which are significant on their own. Additionally, the role of Section 4 is unclear to me in the overall discussion of the paper (it seems to me that this section investigate some property of the associated game; but I don't see how it contributes to other results).\n3. The definition of the \"generic case\" needs more clarity. It would be helpful to provide more explanation as to why this assumption is necessary and what it signifies in the context of the paper.\n4. The authors mentioned that the convergence of PRD under the full asynchrony model remains unclear. It would be beneficial to specify the main challenges associated with achieving convergence in this model. Additionally, it'd be good if the authors could elaborate on their conjecture that convergence occurs if information delays are bounded.\n5. If the convergence of PRD is shown by the potential function of the associated game being strictly increasing, is it true that the convergence could be arbitrarily slow? This might be related to the second open question (i.e., no speed of convergence result is provided). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We address below the specific points raised in the review.\n\n\nMotivation: Natural dynamics in markets (such as the PRD that we study) can be viewed as the aggregate emergent outcome of joint simple learning strategies of the participants. We believe that studying the emergent outcome of multiple interacting learning agents is an important and timely research area in machine learning, both theoretically in general and for economic applications. We do not suggest that we have a concrete application for this particular model but rather that we are advancing the theoretical study of such dynamics which are of significant general interest. \n\n\nOrganization of the paper: Thank you for this comment. We will try to improve and clarify the organization of the paper further. \n\n\nGeneric markets: The genericity condition is described in the introduction and formally defined in Definition 3. Intuitively, this means that there are no degeneracies in the market parameters (such as multiple values that are exactly equal), and we show that the absence of such degeneracies implies the uniqueness of the equilibrium. This in turn allows showing convergence to a point. Additionally, as mentioned in the conclusion, if there is some randomness in the process generating these parameters, the market would be generic with high probability. We will add further clarification in the introduction and include a reference to the formal definition.\n\n\nMain open problem: A significant challenge in the full asynchrony model is that one cannot directly employ potential-function arguments, as it may no longer be true that the standard potential function improves in every step. The motivation behind the conjecture that convergence still occurs when information delays are bounded is that the bids update in small steps. Thus, there is hope that over an epoch (a series of updates where everyone has updated their bids at least once), the potential will improve. However, we have not analyzed this model in this paper and leave such an analysis for future work.   \n\n\nSpeed of convergence: As we discuss in the paper, our current techniques allowed us to prove convergence with asynchronous bid updates but not the speed of convergence. We actually suspect that convergence is in polynomial time (in the problem parameters and 1/epsilon), but such an analysis may require some new ideas and we view it as an interesting and natural direction for further work. \n\n"}, {"review_id": "VJcWsADC8g", "reviewer": "Reviewer_pfur", "summary": "This paper studies asynchronous proportional response dynamics (PRD) in linear Fisher markets under adversarial scheduling. The authors proposed an associated game with specific player utilities which admits an exact potential function. Then, the authors show that the set of pure NE of the associated game is the same as the set of market equilibrium bids, which is also the same as the set of maximizers of the potential function. Next, the authors show that the best response dynamics (BRD), where a single player is activated in each round, converges to the equilibrium prices. In terms of PRD with subsets of active players in each round, the authors discussed its connection with BRD and showed that PRD strictly increases the potential function value unless there is no update in bids. Finally, they show that a “generic” linear Fisher market (i.e., no multiplicative equality/degeneracy) exhibits unique equilibrium bids. With the above developments, and through mathematical analysis arguments, the authors prove the main theorem: if the market is generic, and if players are activated in subsets (arbitrarily, but each at least once in every $T$ rounds), then PRD converges to the unique market equilibrium.", "questions": "For a non-generic market, does async PRD lead to price convergence, that is, $p^t = \\sum_i b^t_{ij} \\rightarrow p^*$? Can this be stated as a corollary somewhere in this work? Either way, it would be good to point this out (immediate, require some derivation, or still unclear).\n\nEditorial suggestions.\n\n- Line 236: $\\Phi$ undefined (yet)?\n- Line 329: Extra “a”.\n- [nit] I would use \"limit point\" instead pf \"condensation point\" when discussing the convergence of bids, as the latter is slightly uncommon, although I believe it's used in Rudin's textbook.\n- Appendix Line 316: “works” should be \"work\"? The authors are discussing the implications of multiple previous lemmas.", "limitations": "N.A.\n\nMore details:\n- This work do not have (hidden, unstated) limitations. All claims in the abstract have been addressed in the work.\n- This work is on theoretical properties of (variants of) well-konwn market dynamics and do not have immediate or potential negative societal impacts.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The authors presented many interesting results that will likely be key foundational results for future research in game and market dynamics.\n- These results are presented clearly with highly informative proof sketches and clear connections to other results.", "weaknesses": "None that I could think of. See **Questions**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Regarding the question about price convergence in non-generic markets: We believe that you are correct and prices do converge in general for PRD (as we did show for best-reply dynamics). However, we were not able to prove this with our current techniques and so the status is still unclear. We will point this out in the paper.\n\n\nEditing comments: Thank you for these helpful comments, we will incorporate them into the paper.\n"}]

Author rebuttal:
We thank all the reviewers for their valuable feedback, we will use it to improve the paper. We reply to specific points of each reviewer separately.


Meta-review: This paper examines the proportional response (PR) algorithm for Fisher markets in the presence of delays and asynchronicities. The authors' main result is that, in generic linear Fisher markets where each player is activated with positive frequency over time (but otherwise possibly adversarially), the PR dynamics converge to the unique market equilibrium of the game. The authors also examine the convergence of the best-response dynamics (with a single agent updating at each stage), and they provide a range of numerical experiments to validate their findings.

The reviewers appreciated the paper's technical contributions, and the authors addressed the reviewers' concerns satisfactorily during the discussion phase. Most of the discussion revolved around the motivation for using the PR dynamics over tatonnement processes (which, however, may cycle in linear markets) but, in the end, there were no objections to an "accept" recommendation. I concur with this assessment, and I am happy to recommend acceptance as well.

In addition to the reviewers' comments, I would like to draw the authors attention to the extensive literature on the convergence of mirror descent in asynchronous / delayed settings. The PR algorithm is a special case of mirror descent with entropic regularization (I believe this observation goes back at least to Birnbaum, Devanur and Xiao, EC 2011) and, as such, I would invite the authors to discuss possible connections with the work of Quanrud and Khashabi online learning with delays ("Online learning with adversarial delays", NIPS 2015) and Zhou et al. ("Countering feedback delays in multi-agent learning", NIPS 2017) and Héliou et al. ("Gradient-free online learning in continuous games with delayed rewards", ICML 2020) in the multi-agent case.
Decision: Accept (poster)