Search

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 where 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 towards 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 towards Poisson games., Mathematics of Operations Research, Forthcoming, 2022

In “Technical Note—Ranking Distributions When Only Means and Variances Are Known,” Müller, Scarsini, Tsetlin, and Winkler address the question of ranking distributions when only the first two moments—that is, means and variances—are known. This is important in decision making under uncertainty, with potential applications in economics, finance, statistics, and other areas. Previous results require some assumptions about the shape of the distributions, while this paper’s approach is to impose bounds on how much marginal utility can change, thus constraining risk preferences. Such a ranking is consistent with almost stochastic dominance and provides a new connection between the Sharpe and Omega ratios from finance.

In finite games mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies, and the payoffs are i.i.d. with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth and a central limit theorem, with bounds for the approximation error. Moreover, by using a new link between percolation models and game theory, we describe in detail the geometry of Nash equilibria and show that, when the probability of ties is small, a best-response dynamics reaches a Nash equilibrium with a probability that quickly approaches one as the number of players grows. We show that a multitude of phase transitions depend only on a single parameter of the model, that is, the probability of having ties., 29 pages, 7 figures

Optimal Policies for Online Platforms When Social Learning Occurs Before buying products online, consumers read the reviews written by the previous customers. If they buy the product, they write a review themselves. When the product is of unknown quality, consumers learn it over time; that is, social learning occurs. If consumers have various purchase options of similar products of different brands, the platform that they use may affect this social learning by choosing the order in which the products appear on its website. In “Product Ranking in the Presence of Social Learning,” Maglaras, Scarsini, Shin, and Vaccari compare various policies that the platform may adopt, with the goal of maximizing its revenue collected from commission fees for sold items. The criterion to compare the policies is the worst-case regret with respect to a fully informed platform benchmark.

Orthogonal direct-sum decompositions of finite games into potential, harmonic and nonstrategic components exist in the literature. In this paper we study the issue of decomposing games that are strategically equivalent from a game-theoretical point of view, for instance games obtained via transformations such as duplications of strategies or positive affine mappings of the payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompositions.