Simina Brânzei
Research Subjects
Research Interests
Simina Brânzei has a total of 42 co-authors. Here are the top co-authors by number of shared publications:
- Aris Filos-Ratsikas
University of Edinburgh, Edinburgh, UK
3 shared publications - Noam Nisan
School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel
3 shared publications Jiawei Li
The University of Texas at Austin, USA
2 shared publications- Nicholas Recker
Purdue University
2 shared publications - Peter Bro Miltersen
Aarhus University Denmark
2 shared publications - Reed Phillips
Purdue University
2 shared publications
Latest Publications
- 17 March 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 9 (3) , 145-198
The query complexity of local search and Brouwer in rounds
We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a local minimum of the loss function when training deep neural networks. In such applications, each query is an expensive loss evaluation, making it crucial to parallelize computations. This motivates our study of local search where at most k rounds of interaction (aka adaptivity) with the oracle are allowed.We focus on the d -dimensional grid \{1, 2, \ldots, n \}^{d} , where the dimension d \geq 2 is a constant. Our main contribution is to give algorithms and lower bounds that characterize the query complexity of finding a local minimum in k rounds, when k is constant and polynomial in n , respectively. Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds.
- 17 March 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 9 (3) , 145-198
The query complexity of local search and Brouwer in rounds
We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a local minimum of the loss function when training deep neural networks. In such applications, each query is an expensive loss evaluation, making it crucial to parallelize computations. This motivates our study of local search where at most k rounds of interaction (aka adaptivity) with the oracle are allowed.We focus on the d -dimensional grid \{1, 2, \ldots, n \}^{d} , where the dimension d \geq 2 is a constant. Our main contribution is to give algorithms and lower bounds that characterize the query complexity of finding a local minimum in k rounds, when k is constant and polynomial in n , respectively. Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds.
- Open Access
Dueling over Multiple Pieces of Dessert
We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over $T$ rounds. Alice aims to minimize her regret relative to the Stackelberg value -- the maximum utility she could achieve if she knew Bob's private valuation. We show that if Alice uses arbitrary measurable partitions, achieving strongly sublinear regret is impossible; she suffers a regret of $Ω\Bigl(\frac{T}{\log^2 T}\Bigr)$ regret even against a myopic Bob. However, when Alice uses at most $k$ cuts, the learning landscape becomes tractable. We analyze Alice's performance based on her knowledge of Bob's strategic sophistication (his regret budget). When Bob's learning rate is public, we establish a hierarchy of polynomial regret bounds determined by $k$ and Bob's regret budget. In contrast, when this learning rate is private, Alice can universally guarantee $O\Bigl(\frac{T}{\log T}\Bigr)$ regret, but any attempt to secure a polynomial rate $O(T^β)$ (for $β< 1$) leaves her vulnerable to incurring strictly linear regret against some Bob. Finally, as a corollary of our online learning dynamics, we characterize the randomized query complexity of finding approximate Stackelberg allocations with a constant number of cuts in the Robertson-Webb model.Open AccessDueling over Multiple Pieces of Dessert
We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over $T$ rounds. Alice aims to minimize her regret relative to the Stackelberg value -- the maximum utility she could achieve if she knew Bob's private valuation. We show that if Alice uses arbitrary measurable partitions, achieving strongly sublinear regret is impossible; she suffers a regret of $Ω\Bigl(\frac{T}{\log^2 T}\Bigr)$ regret even against a myopic Bob. However, when Alice uses at most $k$ cuts, the learning landscape becomes tractable. We analyze Alice's performance based on her knowledge of Bob's strategic sophistication (his regret budget). When Bob's learning rate is public, we establish a hierarchy of polynomial regret bounds determined by $k$ and Bob's regret budget. In contrast, when this learning rate is private, Alice can universally guarantee $O\Bigl(\frac{T}{\log T}\Bigr)$ regret, but any attempt to secure a polynomial rate $O(T^β)$ (for $β< 1$) leaves her vulnerable to incurring strictly linear regret against some Bob. Finally, as a corollary of our online learning dynamics, we characterize the randomized query complexity of finding approximate Stackelberg allocations with a constant number of cuts in the Robertson-Webb model. - Open Access
Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
We present a simple local search algorithm for computing EFX (envy-free up to any good) allocations of $m$ indivisible goods among $n$ agents with additive valuations. EFX is a compelling fairness notion, and whether such allocations always exist remains a major open question in fair division. Our algorithm employs simulated annealing with the total number of EFX violations as an objective function together with a single-transfer neighborhood structure to move through the space of allocations. It found an EFX allocation in all the instances tested, which included thousands of randomly generated inputs, and scaled to settings with hundreds of agents and/or thousands of items. The algorithm's simplicity, along with its strong empirical performance makes it a simple benchmark for evaluating future approaches. On the theoretical side, we provide a potential function for identical additive valuations, which ensures that any strict-descent procedure under the single-transfer neighborhood ends at an EFX allocation. This represents an alternative proof of existence for identical valuations.Open AccessComputing Envy-Free up to Any Good (EFX) Allocations via Local Search
We present a simple local search algorithm for computing EFX (envy-free up to any good) allocations of $m$ indivisible goods among $n$ agents with additive valuations. EFX is a compelling fairness notion, and whether such allocations always exist remains a major open question in fair division. Our algorithm employs simulated annealing with the total number of EFX violations as an objective function together with a single-transfer neighborhood structure to move through the space of allocations. It found an EFX allocation in all the instances tested, which included thousands of randomly generated inputs, and scaled to settings with hundreds of agents and/or thousands of items. The algorithm's simplicity, along with its strong empirical performance makes it a simple benchmark for evaluating future approaches. On the theoretical side, we provide a potential function for identical additive valuations, which ensures that any strict-descent procedure under the single-transfer neighborhood ends at an EFX allocation. This represents an alternative proof of existence for identical valuations. - Open Access
- 22 January 2025
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 481 (2306)
Tit-for-tat strategies drive growth and inequality in production economies
We consider production economies where multiple agents make goods according to their inherent production recipe. Daily agents bring goods to the market along with a monetary budget that they allocate across these goods in competitive bids. Goods are distributed in proportion to the bids they attract, with sellers collecting the corresponding revenues. Agents then use their acquired bundles as raw ingredients for the next day’s production. We analyse a dynamic known as proportional response, where agents adjust their bids on goods proportionally to returns on past investments: a tit-for-tat like market behaviour. We show these dynamics lead to growth of the economy, whenever growth is feasible within the parameters of the model. The dynamics implicitly learn a key global feature of the network—the most efficient production cycles—through local interactions among the agents who communicate only with their immediate neighbours, with information flowing across the network edges. However, the dynamics also lead to unbounded inequality, i.e. very rich and very poor agents emerge and the gaps between their fortunes expand over time. We analyse several other phenomena, such as the existence of free-riding in star networks, where an agent may have growing fortune without participating in any efficient production cycle if they have strong enough connections with the centre.
- 22 January 2025
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 481 (2306)
Open AccessTit-for-tat strategies drive growth and inequality in production economies
We consider production economies where multiple agents make goods according to their inherent production recipe. Daily agents bring goods to the market along with a monetary budget that they allocate across these goods in competitive bids. Goods are distributed in proportion to the bids they attract, with sellers collecting the corresponding revenues. Agents then use their acquired bundles as raw ingredients for the next day’s production. We analyse a dynamic known as proportional response, where agents adjust their bids on goods proportionally to returns on past investments: a tit-for-tat like market behaviour. We show these dynamics lead to growth of the economy, whenever growth is feasible within the parameters of the model. The dynamics implicitly learn a key global feature of the network—the most efficient production cycles—through local interactions among the agents who communicate only with their immediate neighbours, with information flowing across the network edges. However, the dynamics also lead to unbounded inequality, i.e. very rich and very poor agents emerge and the gaps between their fortunes expand over time. We analyse several other phenomena, such as the existence of free-riding in star networks, where an agent may have growing fortune without participating in any efficient production cycle if they have strong enough connections with the centre.
- Open Access
A note on quantum lower bounds for local search via congestion and expansion
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $β$-expander with maximum degree $Δ$, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $O\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.Open AccessA note on quantum lower bounds for local search via congestion and expansion
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $β$-expander with maximum degree $Δ$, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $O\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs. - Open Access
Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is identical to the ones in previous rounds. Alice cuts the cake at a point of her choice, while Bob chooses the left piece or the right piece, leaving the remainder for Alice. We consider two versions: sequential, where Bob observes Alice's cut point before choosing left/right, and simultaneous, where he only observes her cut point after making his choice. The simultaneous version was first considered by Aumann and Maschler (1995). We observe that if Bob is almost myopic and chooses his favorite piece too often, then he can be systematically exploited by Alice through a strategy akin to a binary search. This strategy allows Alice to approximate Bob's preferences with increasing precision, thereby securing a disproportionate share of the resource over time. We analyze the limits of how much a player can exploit the other one and show that fair utility profiles are in fact achievable. Specifically, the players can enforce the equitable utility profile of $(1/2, 1/2)$ in the limit on every trajectory of play, by keeping the other player's utility to approximately $1/2$ on average while guaranteeing they themselves get at least approximately $1/2$ on average. We show this theorem using a connection with Blackwell approachability. Finally, we analyze a natural dynamic known as fictitious play, where players best respond to the empirical distribution of the other player. We show that fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a rate of $O(1/\sqrt{T})$.Open AccessDueling Over Dessert, Mastering the Art of Repeated Cake Cutting
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is identical to the ones in previous rounds. Alice cuts the cake at a point of her choice, while Bob chooses the left piece or the right piece, leaving the remainder for Alice. We consider two versions: sequential, where Bob observes Alice's cut point before choosing left/right, and simultaneous, where he only observes her cut point after making his choice. The simultaneous version was first considered by Aumann and Maschler (1995). We observe that if Bob is almost myopic and chooses his favorite piece too often, then he can be systematically exploited by Alice through a strategy akin to a binary search. This strategy allows Alice to approximate Bob's preferences with increasing precision, thereby securing a disproportionate share of the resource over time. We analyze the limits of how much a player can exploit the other one and show that fair utility profiles are in fact achievable. Specifically, the players can enforce the equitable utility profile of $(1/2, 1/2)$ in the limit on every trajectory of play, by keeping the other player's utility to approximately $1/2$ on average while guaranteeing they themselves get at least approximately $1/2$ on average. We show this theorem using a connection with Blackwell approachability. Finally, we analyze a natural dynamic known as fictitious play, where players best respond to the empirical distribution of the other player. We show that fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a rate of $O(1/\sqrt{T})$. - Open Access
- 29 January 2024
- Published by IOP Publishing in Nonlinearity
- Vol. 37 (3) , 035006
Tit-for-tat dynamics and market volatility
We consider tit-for-tat dynamics in production markets, where there is a set of n players connected via a weighted graph. Each player i can produce an eponymous good using its linear production function, given as input various amounts of goods in the system. In the tit-for-tat dynamic, each player i shares its good with its neighbours in fractions proportional to how much they helped player i’s production in the last round. Our contribution is to characterize the asymptotic behaviour of the dynamic as a function of the graph structure, finding that the fortune of a player grows in the long term if and only if the player has a good self loop (i.e. the player works well alone) or works well with at least one other player. We also consider a generalized damped update, where the players may update their strategies with different speeds, and obtain a lower bound on their rate of growth by identifying a function that gives insight into the behaviour of the dynamical system. The model can capture circular economies, where players use each other’s products, and organizational partnerships, where fostering long-term growth of an organization hinges on creating relationships in which reciprocal exchanges between the agents in the organization are paramount.
- 29 January 2024
- Published by IOP Publishing in Nonlinearity
- Vol. 37 (3) , 035006
Open AccessTit-for-tat dynamics and market volatility
We consider tit-for-tat dynamics in production markets, where there is a set of n players connected via a weighted graph. Each player i can produce an eponymous good using its linear production function, given as input various amounts of goods in the system. In the tit-for-tat dynamic, each player i shares its good with its neighbours in fractions proportional to how much they helped player i’s production in the last round. Our contribution is to characterize the asymptotic behaviour of the dynamic as a function of the graph structure, finding that the fortune of a player grows in the long term if and only if the player has a good self loop (i.e. the player works well alone) or works well with at least one other player. We also consider a generalized damped update, where the players may update their strategies with different speeds, and obtain a lower bound on their rate of growth by identifying a function that gives insight into the behaviour of the dynamical system. The model can capture circular economies, where players use each other’s products, and organizational partnerships, where fostering long-term growth of an organization hinges on creating relationships in which reciprocal exchanges between the agents in the organization are paramount.
- Open Access
Learning and Collusion in Multi-unit Auctions
We consider repeated multi-unit auctions with uniform pricing, which are widely used in practice for allocating goods such as carbon licenses. In each round, $K$ identical units of a good are sold to a group of buyers that have valuations with diminishing marginal returns. The buyers submit bids for the units, and then a price $p$ is set per unit so that all the units are sold. We consider two variants of the auction, where the price is set to the $K$-th highest bid and $(K+1)$-st highest bid, respectively. We analyze the properties of this auction in both the offline and online settings. In the offline setting, we consider the problem that one player $i$ is facing: given access to a data set that contains the bids submitted by competitors in past auctions, find a bid vector that maximizes player $i$'s cumulative utility on the data set. We design a polynomial time algorithm for this problem, by showing it is equivalent to finding a maximum-weight path on a carefully constructed directed acyclic graph. In the online setting, the players run learning algorithms to update their bids as they participate in the auction over time. Based on our offline algorithm, we design efficient online learning algorithms for bidding. The algorithms have sublinear regret, under both full information and bandit feedback structures. We complement our online learning algorithms with regret lower bounds. Finally, we analyze the quality of the equilibria in the worst case through the lens of the core solution concept in the game among the bidders. We show that the $(K+1)$-st price format is susceptible to collusion among the bidders; meanwhile, the $K$-th price format does not have this issue.Open AccessLearning and Collusion in Multi-unit Auctions
We consider repeated multi-unit auctions with uniform pricing, which are widely used in practice for allocating goods such as carbon licenses. In each round, $K$ identical units of a good are sold to a group of buyers that have valuations with diminishing marginal returns. The buyers submit bids for the units, and then a price $p$ is set per unit so that all the units are sold. We consider two variants of the auction, where the price is set to the $K$-th highest bid and $(K+1)$-st highest bid, respectively. We analyze the properties of this auction in both the offline and online settings. In the offline setting, we consider the problem that one player $i$ is facing: given access to a data set that contains the bids submitted by competitors in past auctions, find a bid vector that maximizes player $i$'s cumulative utility on the data set. We design a polynomial time algorithm for this problem, by showing it is equivalent to finding a maximum-weight path on a carefully constructed directed acyclic graph. In the online setting, the players run learning algorithms to update their bids as they participate in the auction over time. Based on our offline algorithm, we design efficient online learning algorithms for bidding. The algorithms have sublinear regret, under both full information and bandit feedback structures. We complement our online learning algorithms with regret lower bounds. Finally, we analyze the quality of the equilibria in the worst case through the lens of the core solution concept in the game among the bidders. We show that the $(K+1)$-st price format is susceptible to collusion among the bidders; meanwhile, the $K$-th price format does not have this issue. - Open Access
Tit-for-Tat Dynamics and Market Volatility
We consider tit-for-tat dynamics in production markets, where there is a set of $n$ players connected via a weighted graph. Each player $i$ can produce an eponymous good using its linear production function, given as input various amounts of goods in the system. In the tit-for-tat dynamic, each player $i$ shares its good with its neighbors in fractions proportional to how much they helped player $i$'s production in the last round. Our contribution is to characterize the asymptotic behavior of the dynamic as a function of the graph structure, finding that the fortune of a player grows in the long term if and only if the player has a good self loop (i.e. the player works well alone) or works well with at least one other player. We also consider a generalized damped update, where the players may update their strategies with different speeds, and obtain a lower bound on their rate of growth by identifying a function that gives insight into the behavior of the dynamical system. The model can capture circular economies, where players use each other's products, and organizational partnerships, where fostering long-term growth of an organization hinges on creating relationships in which reciprocal exchanges between the agents in the organization are paramount.Open AccessTit-for-Tat Dynamics and Market Volatility
We consider tit-for-tat dynamics in production markets, where there is a set of $n$ players connected via a weighted graph. Each player $i$ can produce an eponymous good using its linear production function, given as input various amounts of goods in the system. In the tit-for-tat dynamic, each player $i$ shares its good with its neighbors in fractions proportional to how much they helped player $i$'s production in the last round. Our contribution is to characterize the asymptotic behavior of the dynamic as a function of the graph structure, finding that the fortune of a player grows in the long term if and only if the player has a good self loop (i.e. the player works well alone) or works well with at least one other player. We also consider a generalized damped update, where the players may update their strategies with different speeds, and obtain a lower bound on their rate of growth by identifying a function that gives insight into the behavior of the dynamical system. The model can capture circular economies, where players use each other's products, and organizational partnerships, where fostering long-term growth of an organization hinges on creating relationships in which reciprocal exchanges between the agents in the organization are paramount. - Open Access
Phase Transitions of Diversity in Stochastic Block Model Dynamics
This paper proposes a stochastic block model with dynamics where the population grows using preferential attachment. Nodes with higher weighted degree are more likely to recruit new nodes, and nodes always recruit nodes from their own community. This model can capture how communities grow or shrink based on their collaborations with other nodes in the network, where an edge represents collaboration on a project. Focusing on the case of two communities, we derive a deterministic approximation to the dynamics and characterize the phase transitions for diversity, i.e. the parameter regimes in which either one of the communities dies out or the two communities reach parity over time. In particular, we find that the minority may vanish when the probability of cross-community edges is low, even when cross-community projects are more valuable than projects with collaborators from the same community.
Open AccessPhase Transitions of Diversity in Stochastic Block Model Dynamics
This paper proposes a stochastic block model with dynamics where the population grows using preferential attachment. Nodes with higher weighted degree are more likely to recruit new nodes, and nodes always recruit nodes from their own community. This model can capture how communities grow or shrink based on their collaborations with other nodes in the network, where an edge represents collaboration on a project. Focusing on the case of two communities, we derive a deterministic approximation to the dynamics and characterize the phase transitions for diversity, i.e. the parameter regimes in which either one of the communities dies out or the two communities reach parity over time. In particular, we find that the minority may vanish when the probability of cross-community edges is low, even when cross-community projects are more valuable than projects with collaborators from the same community.