Jeu à somme nulle

Résumé

Un jeu de somme nulle est un jeu où la somme des gains et des pertes de tous les joueurs est égale à 0. Cela signifie donc que le gain de l'un constitue obligatoirement une perte pour l'autre. Par exemple si l'on définit le gain d'une partie d'échecs comme 1 si on gagne, 0 si la partie est nulle et -1 si on perd, le jeu d'échecs est un jeu à somme nulle. En économie, cette notion simplificatrice est importante : les jeux à somme nulle correspondent à l'absence de production ou de destruction de produits. En 1944, John von Neumann et Oskar Morgenstern ont démontré que tout jeu à somme nulle pour n'est en fait qu'une forme généralisée de jeux à somme nulle pour deux personnes, et que tout jeu à somme non nulle pour peut se ramener à un jeu à somme nulle pour , la n+1-ième personne représentant le gain ou la perte globale. Pour une critique pertinente de ce point de vue lire : Jeux de stratégie à somme nulle et non nulle. De ce fait, les jeux à somme nulle pour deux personnes ou de

Source officielle

https://fr.wikipedia.org/wiki/Jeu_%C3%A0_somme_nulle

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (7)

Concepts associés

Chargement

Cours associés (26)

Cours associés

Chargement

Séances de cours associées (40)

Séances de cours associées

Chargement

Let’s be honest: An optimal no-regret framework for zero-sum games

Ehsan Asadi Kangarshahi, Volkan Cevher, Ya-Ping Hsieh, Mehmet Fatih Sahin

We revisit the problem of solving two-player zero- sum games in the decentralized setting. We pro- pose a simple algorithmic framework that simulta- neously achieves the best rates for honest regret as well as adversarial regret, and in addition resolves the open problem of removing the logarithmic terms in convergence to the value of the game. We achieve this goal in three steps. First, we provide a novel analysis of the optimistic mirror descent (OMD), showing that it can be modified to guarantee fast convergence for both honest re- gret and value of the game, when the players are playing collaboratively. Second, we propose a new algorithm, dubbed as robust optimistic mir- ror descent (ROMD), which attains optimal ad- versarial regret without knowing the time horizon beforehand. Finally, we propose a simple signal- ing scheme, which enables us to bridge OMD and ROMD to achieve the best of both worlds. Numerical examples are presented to support our theoretical claims and show that our non-adaptive ROMD algorithm can be competitive to OMD with adaptive step-size selection.

2018

Chargement

Compressive sensing meets game theory

Volkan Cevher, Sina Jafarpour

We introduce the Multiplicative Update Selector and Estimator (MUSE) algorithm for sparse approximation in under-determined linear regression problems. Given ƒ = Φα* + μ, the MUSE provably and efficiently finds a k-sparse vector α̂ such that ∥Φα̂ − ƒ∥∞ ≤ ∥μ∥∞ + O ( 1 over √k), for any k-sparse vector α*, any measurement matrix Φ, and any noise vector μ. We cast the sparse approximation problem as a zero-sum game over a properly chosen new space; this reformulation provides salient computational advantages in recovery. When the measurement matrix Φ provides stable embedding to sparse vectors (the so-called restricted isometry property in compressive sensing), the MUSE also features guarantees on ∥α* − α̂∥2. Simulation results demonstrate the scalability and performance of the MUSE in solving sparse approximation problems based on the Dantzig Selector.

IEEE2011

Chargement

We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula). (C) 2010 Elsevier Inc. All rights reserved.

2010

Chargement