NSNicolas E. Stier-Moses

Nicolas E. Stier-Moses

*This is an algorithmically generated author record based on publicly available information.

Nicolas E. Stier-Moses has a total of 62 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Top Cited Papers

    Introduction to the Special Issue on the Human-Algorithm Connection

    by Felipe Caro, Jean-Edouard Colliard, Elena Katok, Axel Ockenfels, Nicolas Stier-Moses, Catherine Tucker, D. J. Wu


  • Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games

    by Roberto Cominetti, Marco Scarsini, Marc Schröder, Nicolas E. Stier-Moses

    Uncertain Demand in Transportation Reduces Worst-Case Congestion In “Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games,” Cominetti, Scarsini, Schröder, and Stier-Moses characterize the inefficiency introduced by self-minded travelers in congested networks, such as those in big cities. When the likelihood that travelers are present in a congested network is smaller, the uncertainty affects the resulting conditions but also what a social planner would do. Contrary to what might be expected, the consequence is a reduction of the worst-case expressions for the inefficiency of the prevailing traffic conditions with respect to the routes of a social planner. This reduction holds under two possible informational assumptions for the social planner. An ordinary planner only has statistical information based on past data in terms of the expected number of travelers, whereas a prophet planner is informed of the participation outcomes right when travelers start their trips.


  • Open Access

    Fair Allocation Over Time, with Applications to Content Moderation

    by Amine Allouah, Christian Kroer, Xuan Zhang, Vashist Avadhanula, Nona Bohanon, Anil Dania, Caner Gocmen, Sergey Pupyrev, Parikshit Shah, Nicolas Stier-Moses, et al.

  • Approximation and Convergence of Large Atomic Congestion Games

    by Roberto Cominetti, Marco Scarsini, Marc Schröder, Nicolás Stier-Moses

    We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games in which each player’s weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation toward Poisson random variables whose expected values are Wardrop equilibria of a different nonatomic game with suitably defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings, we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players toward Poisson games.Funding: R. Cominetti gratefully acknowledges the support of Proyecto Anillo [Grant ANID/PIA/ACT192094]. M. Scarsini’s work was partially supported by the Gruppo Nazionale per l’Analisi Matematica, la Probabilità e le loro Applicazioni, Istituto Nazionale di Alta Matematica [Grant 2020 “Random walks on random games”] and the Progetti di Rilevante Interesse Nazionale 2017 [Grant “Algorithms, Games, and Digital Markets”]. This research also received partial support from the European Cooperation in Science and Technology [Action European Network for Game Theory].


  • Pacing Equilibrium in First Price Auction Markets

    by Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E. Stier-Moses, Eric Sodomka, Christopher A. Wilkens

    Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives—instead of individual auctions—and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg–Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers, and regrets all have a positive association in statistical terms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: D. Panigrahi was supported in part by the National Science Foundation [Awards CCF 1535972, CCF 1750140, and CCF 1955703]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.4310 .


  • Top Cited Papers

    Multiplicative Pacing Equilibria in Auction Markets

    by Vincent Conitzer, Christian Kroer, Eric Sodomka, Nicolas E. Stier-Moses

    Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at pacing in an ad marketplace using the lens of game theory. The goal is understanding how bids must be shaded to maximize advertiser welfare, at equilibrium. Motivated by the real-world auction mechanism, they construct a game where advertisers in the auctions choose a multiplicative factor not larger than 1 to possibly reduce their bids and best respond to the other advertisers. The article studies the theoretical properties of the game such as existence and uniqueness of equilibria, offers an exact algorithm to compute them, connects the game to well-known abstractions such as Fisher markets, and performs a computational study with real-world-inspired instances. The main insights are that the solutions to the studied game can be used to improve the outcomes achieved by a closer-to-reality dynamic pacing algorithm and that buyers do not have an incentive to misreport bids or budgets when there are enough participants in the auction.


  • Call for Papers—Management Science Special Issue on the Human-Algorithm Connection

    by Felipe Caro, Jean-Edouard Colliard, Elena Katok, Axel Ockenfels, Nicolas Stier-Moses, Catherine Tucker, D. J. Wu


  • Computing Large Market Equilibria Using Abstractions

    by Christian Kroer, Alexander Peysakhovich, Eric Sodomka, Nicolas E. Stier-Moses

    Computing market equilibria is an important practical problem for market design, for example, in fair division of items. However, computing equilibria requires large amounts of information (typically the valuation of every buyer for every item) and computing power. We consider ameliorating these issues by applying a method used for solving complex games: constructing a coarsened abstraction of a given market, solving for the equilibrium in the abstraction, and lifting the prices and allocations back to the original market. We show how to bound important quantities such as regret, envy, Nash social welfare, Pareto optimality, and maximin share/proportionality when the abstracted prices and allocations are used in place of the real equilibrium. We then study two abstraction methods of interest for practitioners: (1) filling in unknown valuations using techniques from matrix completion and (2) reducing the problem size by aggregating groups of buyers/items into smaller numbers of representative buyers/items and solving for equilibrium in this coarsened market. We find that in real data allocations/prices that are relatively close to equilibria can be computed from even very coarse abstractions.


  • Risk-Averse Selfish Routing

    by Thanasis Lianeas, Evdokia Nikolova, Nicolas E. Stier-Moses

    We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on edge flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers by introducing jitter in transmission delays, which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the price of risk aversion (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk neutral....


  • Technical Note—The Competitive Facility Location Problem in a Duopoly: Advances Beyond Trees

    by Yonatan Gur, Daniela Saban, Nicolas E. Stier-Moses

    We consider a competitive facility location problem on a network where consumers located on vertices wish to connect to the nearest facility. Knowing this, each competitor locates a facility on a vertex, trying to maximize market share. We focus on the two-player case and study conditions that guarantee the existence of a pure-strategy Nash equilibrium for progressively more complicated classes of networks. For general graphs, we show that attention can be restricted to a subset of vertices referred to as the central block. By constructing trees of maximal bi-connected components, we obtain sufficient conditions for equilibrium existence. Moreover, when the central block is a vertex or a cycle (for example, in cactus graphs), this provides a complete and efficient characterization of equilibria. In that case, we show that both competitors locate their facilities in a solution to the 1-median problem, generalizing a well-known insight arising from Hotelling’s model. We further show that an equilibrium must solve the 1-median problem in other classes of graphs, including grids, which essentially capture the topology of urban networks. In addition, when both players select a 1-median, the solution must be at equilibrium for strongly-chordal graphs, generalizing a previously known result for trees. The electronic companion is available at https://doi.org/10.1287/opre.2017.1694 .