Zero-Sum Polymatrix Games: A Generalization of Minmax by Cai, Yang, Candogan, Ozan, Papadimitriou, Christos, Daskalakis, Konstantinos

“…In contrast, other important properties of two-person zero-sum games are not preserved: Nash equilibrium payoffs need not be unique, and Nash equilibrium strategies need not be exchangeable or max-min.…”
Get full text
Get full text

Bayesian Proportional Resource Allocation Games by Tsitsiklis, John N., Xu, Yunjian

“…We prove the existence of a Bayes-Nash equilibrium. Furthermore, under some mild assumptions, we establish asymptotic efficiency: we show that the per user social welfare achieved at any Bayes-Nash equilibrium is asymptotically equal to the maximum possible.…”
Get full text
Get full text

Implicit posterior variational inference for deep Gaussian processes by Jaillet, Patrick

“…This consequently inspires us to devise a best-response dynamics algorithm to search for a Nash equilibrium (i.e., an unbiased posterior belief). …”
Get full text

Parameterized Supply Function Bidding: Equilibrium and Efficiency by Johari, Ramesh, Tsitsiklis, John N.

“…We show that by restricting the strategy space of the firms to parameterized supply functions, we can provide upper bounds on both the inflation of aggregate cost at the Nash equilibrium relative to the socially optimal level, as well as the markup of the Nash equilibrium price above the competitive level: as long as N > 2 firms are competing, these quantities are both upper bounded by 1 + 1/(N − 2). …”
Get full text
Get full text

On the complexity of Nash equilibria of action-graph games by Daskalakis, Constantinos, Schoenebeck, Grant, Valiant, Gregory, Valiant, Paul

“…In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP- complete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one). …”
Get full text

On minmax theorems for multiplayer games by Cai, Yang, Daskalakis, Constantinos

“…We show that finding a pure Nash equilibrium in coordination-only polymatrix games is PLS-complete; hence, computing a mixed Nash equilibrium is in PLS ∩ PPAD, but it remains open whether the problem is in P. …”
Get full text
Get full text

A Non-Cooperative Game Theory Based Controller Tuning Method for Microgrid DC-DC Converters by Mei, Jie, Kirtley Jr, James L

“…According to the solved Nash Equilibrium, best tuning parameters for the PI controller may be determined.…”
Get full text

Efficiency of scalar-parameterized mechanisms by Johari, Ramesh, Tsitsiklis, John N.

“…We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the maximum possible utility), and show that the proportional allocation mechanism of Kelly (1997) minimizes the efficiency loss when users are price anticipating. …”
Get full text
Get full text

Competitive scheduling in wireless collision channels with correlated channel state by Parrilo, Pablo A., Candogan, Utku Ozan, Menache, Ishai, Ozdaglar, Asuman E.

“…Assuming that all users employ stationary, state-dependent transmission strategies, we investigate the properties of the Nash equilibrium of the resulting game between users. While the equilibrium performance can be arbitrarily bad (in terms of aggregate utility), we bound the efficiency loss at the best equilibrium as a function of a technology-related parameter. …”
Get full text
Get full text
Get full text

Dynamics in congestion games by Shah, Devavrat, Shin, Jinwoo

“…Second, evaluation of (a) time to converge to equilibrium under this behavior model and (b) distance to Nash equilibrium. Finally, determination of tradeoff between the rate of dynamics and quality of performance (distance to equilibrium) which leads to an interesting uncertainty principle. …”
Get full text
Get full text

The equivalence of sampling and searching by Aaronson, Scott

Get full text
Get full text