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

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.

Motivated by the proliferation of user-generated product-review information and its widespread use, this note studies a market where consumers are heterogeneous in terms of their willingness to pay for a new product. Each consumer observes the binary reviews (like or dislike) of consumers who purchased the product in the past and uses Bayesian updating to infer the product quality. We show that the learning process is successful as long as the price is not prohibitive, and therefore at least some consumers, with sufficiently high idiosyncratic willingness to pay, will purchase the product irrespective of their posterior quality estimate. We examine some structural properties of the dynamics of the posterior beliefs. Finally, we study the seller's pricing problem, and we show that, if the set of possible prices is finite, then a stationary optimal pricing policy exists. If it costs the seller a constant amount for each additional unit sold, then under the optimal policy learning fails with positive probability.

We consider a discrete-time nonatomic routing game with variable demand and uncertain costs. Given a routing network with single origin and destination, the cost function of each edge depends on some uncertain persistent state parameter. At every period, a random traffic demand is routed through the network according to a Wardrop equilibrium. The realized costs are publicly observed and the public Bayesian belief about the state parameter is updated. We say that there is strong learning when beliefs converge to the truth and weak learning when the equilibrium flow converges to the complete-information flow. We characterize the networks for which learning occurs. We prove that these networks have a series-parallel structure and provide a counterexample to show that learning may fail in non-series-parallel networks., 20 pages, 4 figures

We consider an atomic congestion game in which each player participates in the game with an exogenous and known probability $p_{i}\in[0,1]$, independently of everybody else, or stays out and incurs no cost. We first prove that the resulting game is potential. Then, we compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior. It turns out that the price of anarchy as a function of the maximum participation probability $p=\max_{i} p_{i}$ is a nondecreasing function. The worst case is attained when players have the same participation probabilities $p_{i}\equiv p$. For the case of affine costs, we provide an analytic expression for the parameterized price of anarchy as a function of $p$. This function is continuous on $(0,1]$, is equal to $4/3$ for $0

We consider a game in which players are the vertices of a directed graph. Initially, Nature chooses one player according to some fixed distribution and gives her a buck, which represents the request to perform a chore. After completing the task, the player passes the buck to one of her out-neighbors in the graph. The procedure is repeated indefinitely and each player's cost is the asymptotic expected frequency of times that she receives the buck. We consider a deterministic and a stochastic version of the game depending on how players select the neighbor to pass the buck. In both cases we prove the existence of pure equilibria that do not depend on the initial distribution; this is achieved by showing the existence of a generalized ordinal potential. We then use the price of anarchy and price of stability to measure fairness of these equilibria. We also study a buck-holding variant of the game in which players want to maximize the frequency of times they hold the buck, which includes the PageRank game as a special case., 40 pages

International audience; This paper examines the behavior of the price of anarchy as a func- tion of the traffic inflow in nonatomic congestion games with multiple origin- destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the ques- tion: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network.

Motivated by the problem of utility allocation in a portfolio under a Markowitz mean-variance choice paradigm, we propose an allocation criterion for the variance of the sum of $n$ possibly dependent random variables. This criterion, the Shapley value, requires to translate the problem into a cooperative game. The Shapley value has nice properties, but, in general, is computationally demanding. The main result of this paper shows that in our particular case the Shapley value has a very simple form that can be easily computed. The same criterion is used also to allocate the standard deviation of the sum of $n$ random variables and a conjecture about the relation of the values in the two games is formulated., 20pages

We propose a model of discrete time dynamic congestion games with atomic players and a single source-destination pair. The latencies of edges are composed by free-flow transit times and possible queuing time due to capacity constraints. We give a precise description of the dynamics induced by the individual strategies of players and of the corresponding costs, either when the traffic is controlled by a planner, or when players act selfishly. In parallel networks, optimal and equilibrium behavior eventually coincides, but the selfish behavior of the first players has consequences that cannot be undone and are paid by all future generations. In more general topologies, our main contributions are three-fold. First, we show that equilibria are usually not unique. In particular, we prove that there exists a sequence of networks such that the price of anarchy is equal to $n-1$, where $n$ is the number of vertices, and the price of stability is equal to 1. Second, we illustrate a new dynamic version of Braess's paradox: the presence of initial queues in a network may decrease the long-run costs in equilibrium. This paradox may arise even in networks for which no Braess's paradox was previously known. Third, we propose an extension to model seasonalities by assuming that departure flows fluctuate periodically over time. We introduce a measure that captures the queues induced by periodicity of inflows. This measure is the increase in costs compared to uniform departures for optimal and equilibrium flows in parallel networks., 61 pages, 17 figures

We experimentally explore the effects of time limitation on decision making. Under different time allowance conditions, subjects are presented with a queueing situation and asked to join one of the two given queues. The results can be grouped under two main categories. The first one concerns the factors driving decisions in a queueing system. Only some subjects behave consistently with rationality principles and use the relevant information efficiently. The rest of the subjects seem to adopt a simpler strategy that does not incorporate some information into their decision. The second category is related to the effects of time limitation on decision performance. A substantial proportion of the population is not affected by time limitations and shows consistent behavior throughout the treatments. On the other hand, some subjects' performance is impaired by time limitations. More importantly, this impairment is not due to the stringency of the limitation but rather to being exposed to a time constraint. % changes in abstract Keywords: time pressure, decision times, join the shortest queue, experimentation

We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.

There exist several characterizations of concavity for univariate functions. One of them states that a function is concave if and only if it has nonincreasing differences. This definition provides a natural generalization of concavity for multivariate functions called inframodularity. Inframodular transfers are defined and it is shown that a finite lottery is preferred to another by all expected utility maximizers with an inframodular utility if and only if the first lottery can be obtained from the second via a sequence of inframodular transfers. This result is a natural multivariate generalization of Rothschild and Stiglitzʼs construction based on mean preserving spreads.

International audience; We consider a repeated congestion game with imperfect monitoring. At each stage, each player chooses to use some facilities and pays a cost that increases with the congestion. Two versions of the model are examined: a public monitoring setting where agents observe the cost of each available facility, and a private monitoring one where players observe only the cost of the facilities they use. A partial folk theorem holds: a Pareto-optimal outcome may result from selfish behavior and be sustained by a belief-free equilibrium of the repeated game. We prove this result assuming that players use strategies of bounded complexity and we estimate the strategic complexity needed to achieve efficiency. It is shown that, under some conditions on the number of players and the structure of the game, this complexity is very small even under private monitoring. The case of network routing games is examined in detail.

International audience; In the context of survival analysis it is possible that increasing the value of a covariate X has a beneficial effect on a failure time, but this effect is reversed when conditioning on any possible value of another covariate Y. When studying causal effects and influence of covariates on a failure time, this state of affairs appears paradoxical and raises questions about the real effect of X. Situations of this kind may be seen as a version of Simpson's paradox. In this paper, we study this phenomenon in terms of the linear transformation model. The introduction of a time variable makes the paradox more interesting and intricate: it may hold conditionally on a certain survival time, i.e. on an event of the type {T>t} for some but not all t, and it may hold only for some range of survival times.

International audience; We consider a repeated game where at each stage players simultaneously choose one of two rooms. The players who choose the less crowded room are rewarded with one euro. The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced, hence the game has imperfect public monitoring. An undiscounted version of this game was considered by Renault et al. (2005), who proved a folk theorem. Here we consider a discounted version and a finitely repeated version of the game, and we strengthen our previous result by showing that the set of equilibrium payos Hausdor-converges to the feasible set as either the discount factor goes to one or the number of repetition goes to infinity. We show that the set of public equilibria for this game is strictly smaller than the set of private equilibria.

International audience; We study a two-person zero-sum game where players simultaneously choose sequences of actions, and the overall payoff is the average of a one-shot payoff over the joint sequence. We consider the maxmin value of the game played in pure strategies by boundedly rational players and model bounded rationality by introducing complexity limitations. First we define the complexity of a sequence by its smallest period (a non-periodic sequence being of infinite complexity) and study the maxmin of the game where player~1 is restricted to strategies with complexity at most $n$ and player~2 is restricted to strategies with complexity at most $m$. We study the asymptotics of this value and a complete characterization in the matching pennies case. We extend the analysis of matching pennies to strategies with bounded recall.

We consider a game, called newsvendor game, where several retailers, who face a random demand, can pool their resources and build a centralized inventory that stocks a single item on their behalf. Profits have to be allocated in a way that is advantageous to all the retailers. A game in characteristic form is obtained by assigning to each coalition its optimal expected profit. A similar game (modeled in terms of costs) was considered by Muller et al. (2002), who proved that this game is balanced for every possible joint distribution of the random demands. In this paper we consider newsvendor games with possibly an infinite number of newsvendors. We prove in great generality results about balancedness of the game, and we show that in a game with a continuum of players, under a nonatomic condition on the demand, the core is a singleton. For a particular class of demands we show how the core shrinks to a singleton when the number of players increases.

A more general definition of MTP2 (multivariate total positivity of order 2) probability measure is given, without assuming the existence of a density. Under this definition the class of MTP2 measures is proved to be closed under weak convergence. Characterizations of the MTP2 property are proved under this more general definition. Then a precise definition of conditionally increasing measure is provided, and closure under weak convergence of the class of conditionally increasing measures is proved. As an application we investigate MTP2 properties of stationary distributions of Markov chains, which are of interest in actuarial science.

International audience; Unlike the usual stochastic order, total positivity order is closed under conditioning. Here we provide a general formulation of the preservation properties of the order under conditioning; we study certain properties of the order including translation properties and the implications of having equality in the inequality defining the order. Specializing to the multivariate normal distribution, the study of total positivity order leads to new cones defined in terms of covariance M-matrices related to positive dependence, whose properties we study.

International audience; This paper examines qualitative properties of efficient insurance contracts in the presence of background risk. In order to get results for all strictly risk-averse expected utility maximizers, the concept of “stochastic increasingness” is used. Different assumptions on the stochastic dependence between the insurable and uninsurable risk lead to different qualitative properties of the efficient contracts. The new results obtained under hypotheses of dependent risks are compared to classical results in the absence of background risk or to the case of independent risks. The theory is further generalized to nonexpected utility maximizers.

International audience; We study a particular case of repeated games with public signals. In the stage game an odd number of players have to choose simultaneously one of two rooms. The players who choose the less crowded room receive a reward of one euro (whence the name “minority game”). The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced. We show that in the infinitely repeated game any feasible payoff can be achieved as a uniform equilibrium payoff, and as an almost sure equilibrium payoff. In particular we construct an inefficient equilibrium where, with probability one, all players choose the same room at almost all stages. This equilibrium is sustained by punishment phases which use, in an unusual way, the pure actions that were played before the start of the punishment.

International audience; The authors study new notions of positive dependence that are associated to multivariate stochastic orders of positive dependence introduced recently by Colangelo et al. [J. Multivar. Anal., to appear]. In particular, they discuss the relationship of these new notions to other existing concepts of positive dependence.

International audience; We provide some counterexamples showing that some concepts of positive dependence are strictly stronger than others. In particular we will settle two questions posed by Pemantle (2000) and Pellerey (2002) concerning respectively association versus weak association, weak association versus supermodular dependence, and supermodular dependence versus positive orthant dependence.

International audience; We settle an open conjecture regarding the newsvendor game. We prove that its core is always non-empty, for all possible joint distributions of the random demands. We give sufficient conditions under which the core is a singleton or it contains non-negative elements.

International audience; We will state a general version of Simpson's paradox, which corresponds to the loss of some dependence properties under marginalization. We will then provide conditions under which the paradox is avoided. Finally we will relate these Simpson-type paradoxes to some well-known paradoxes concerning the loss of ageing properties when the level of information changes.

International audience; We consider the convex ordering for random vectors and some weaker versions of it, like the convex ordering for linear combinations of random variables. First we establish conditions of stochastic equality for random vectors that are ordered by one of the convex orderings. Then we establish necessary and sufficient conditions for the convex ordering to hold in the case of multivariate normal distributions and sufficient conditions for the positive linear convex ordering (without the restriction to multi-normality).

International audience; One of the most useful tools for handling multivariate distributions with givenunivariatemarginals is the copula function. Using it, any multivariate distribution function can be represented in a way that emphasizes the separate roles of the marginals and of the dependence structure. The goal of the present paper is to introduce an analogous tool, called the linkage function, that can be used for the study of multivariate distributions with givenmultivariatemarginals by emphasizing the separate roles of the dependence structurebetweenthe given multivariate marginals, and the dependence structurewithineach of the nonoverlapping marginals. Preservation of some setwise positive dependence properties, from the linkage functionLto the joint distributionFand vice versa, are studied. When two different distribution functions are associated with the same linkage function (that is, have the same setwise dependence structure) we show that strong stochastic dominance order among the corresponding multivariate marginal distributions implies an overall stochastic dominance between the two underlying distribution functions.

We consider a finite sequence of exchangeable binary random variables and assume that the conditional expected value of each variable is an average of the observed frequency of success and a prior guess. We obtain a representation of the law of the finite sequence as a beta-binomial. In this way we prove known results for infinite sequences by a simple passage to the limit. Our approach does not have the generality of the usual representation theorems for (finite or infinite) exchangeable sequences, but is very natural and is completely elementary.

International audience; Several agents, each with his own opinion (probability measure), make decisions in order to maximize their expected utility. A super partes person, ‘the chief', releases information with the goal of maximizing a social expected utility, which is an increasing function of the agents' utilities. Additional bits of information are individually beneficial to each agent, but might be socially detrimental if the social utility is concave and therefore diversification is valuable. In this paper, information is modeled by filtrations on a suitable probability space, and the problem of establishing how much information ought to be released is tackled. Two situations are examined, in which the chief either updates or does not update her opinion.

Stochastic comparisons of Markov processes have mostly been in terms of transition functions or infinitesimal generators. For Itô processes, that is, solutions of stochastic differential equations, it is possible to obtain very intuitive comparisons in terms of three deterministic functions that govern the drift, diffusion, and jumps. Some further results on semimartingale Hunt processes show the detrimental effect of time changes upon such comparisons.

In order to explain the Ellsberg paradox, a non-additive expected utility has recently been proposed. In this paper we determine dominance conditions for non-additive expected utilities. In the univariate case all the well-known stochastic dominance theorems can be extended to the non-additive framework, whereas in the multivariate case the generalization applies only to those results that assume a weak preference ordering or do not require extension to linear combinations of utilities.

International audience; A lower bound for the distribution function of a k-dimensional, n-extensible exchangeable process is provided when the marginals are uniform on the unit segment. The result is obtained by means of standard linear programming techniques. The lower bound for infinitely extendible exchangeable processes is the distribution of independent random variables.

International audience; It is shown that convergence in probability is sufficient for a strong measure of concordance to converge to one, and that convergence to one of a strong measure of concordance, along with convergence in law, is sufficient for convergence in probability; Si mostra che la convergenza in probabilità è condizione sufficiente perché una misura forte della concordanza converga a uno, e che la convergenza a uno di una misura forte della concordanza, insieme con la convergenza in legge, è condizione sufficiente per la convergenza in probabilità.

International audience; A sequence of partial orders (called inverse stochastic dominances) is introduced on the set of distribution functions (of nonnegative random variables). The partial orders previously defined are used to rank income distributions when Lorenz ordering does not hold, i.e., when Lorenz curves intersect. It is known that the Gini index is coherent with second degree stochastic dominance (and with second degree inverse stochastic dominance). It will be shown that it is coherent with third degree inverse stochastic dominance, too. It will finally be shown that a sequence of ethically flexible Gini indices due to D. Donaldson and J. A. Weymark (Ethically flexible Gini indices for income distribution in the continuum, J. Econ. Theory 29 (1983), 353–356) is coherent with the sequence of nth degree inverse stochastic dominances

The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite., Comment: 22 pages, 7 figures

Candogan et al. (2011) provide an orthogonal direct-sum decomposition of finite games into potential, harmonic and nonstrategic components. 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 of payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompositions., 43 pages