Publications associées à Jeu à somme nulle

Improving SAM Requires Rethinking its Optimization Formulation

Volkan Cevher, Kimon Antonakopoulos, Thomas Michaelsen Pethick, Wanyun Xie, Fabian Ricardo Latorre Gomez

This paper rethinks Sharpness-Aware Minimization (SAM), which is originally formulated as a zero-sum game where the weights of a network and a bounded perturbation try to minimize/maximize, respectively, the same differentiable loss. We argue that SAM shou ...

2024

Adversarial Training Should Be Cast As a Non-Zero-Sum Game

Volkan Cevher, Seyed Hamed Hassani, Fabian Ricardo Latorre Gomez

One prominent approach toward resolving the adversarial vulnerability of deep neural networks is the two-player zero-sum paradigm of adversarial training, in which predictors are trained against adversarially-chosen perturbations of data. Despite the promi ...

2023

Improved Cooperation by Exploiting a Common Signal

Boi Faltings, Zeki Doruk Erden, Panayiotis Danassis

Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, rea ...

International Foundation for Autonomous Agents and Multiagent Systems2022

Exploiting environmental signals to enable policy correlation in large-scale decentralized systems

Boi Faltings, Zeki Doruk Erden, Panayiotis Danassis

Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, rea ...

SPRINGER2022

Safety in Numbers: Asymptotic Analysis of a Monitoring Problem

Emre Telatar, Reka Inovan

In this work, we introduce a setup where a monitoring entity attempts to distinguish a cheating player among a group of regular players where all players behave in order to maximize their reward. We assume that the cheating player has an "information advan ...

IEEE2022

Mixed Nash Equilibria in the Adversarial Examples Game

Rafaël Benjamin Pinot

This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually al ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

Balancing management of strategic aggregators using non-cooperative game theory

Sidi-Rachid Cherkaoui, Mokhtar Bozorg, Mohammad Rayati

The aggregators are intermediary players at the distribution system level. They manage the financial transactions of resources such as micro-turbines (MTs), photo-voltaic (PV) production systems, flexible demands (FDs), and must-run demands (MDs) in the en ...

Elsevier2020

Regret Minimization and Separation in Multi-Bidder Multi-Item Auctions

Daniel Kuhn, Napat Rujeerapaiboon, Cagil Kocyigit

We study a robust auction design problem with a minimax regret objective, where a seller seeks a mechanism for selling multiple items to multiple anonymous bidders with additive values. The seller knows that the bidders' values range over a box uncertainty ...

2024

Distributional Robustness in Mechanism Design

Cagil Kocyigit

Mechanism design theory examines the design of allocation mechanisms or incentive systems involving multiple rational but self-interested agents and plays a central role in many societally important problems in economics. In mechanism design problems, agen ...

EPFL2020

Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization

Daniel Kuhn, Viet Anh Nguyen, Soroosh Shafieezadeh Abadeh, Peyman Mohajerin Esfahani

We introduce a distributionally robust minimium mean square error estimation model with a Wasserstein ambiguity set to recover an unknown signal from a noisy observation. The proposed model can be viewed as a zero-sum game between a statistician choosing a ...

2023

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

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

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 t ...

2018

A rational decentralized generalized Nash equilibrium seeking for energy markets

Matteo Salani, Lorenzo Nespoli, Vasco Medici

We propose a method to design a decentralized energy market which guarantees individual rationality (IR) in expectation, in the presence of system-level grid constraints. We formulate the market as a welfare maximization problem subject to IR constraints, ...

IEEE2018

Robust Multidimensional Pricing: Separation without Regret

Daniel Kuhn, Napat Rujeerapaiboon, Cagil Kocyigit

We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pr ...

2022

Finding Mixed Nash Equilibria of Generative Adversarial Networks

Volkan Cevher, Ya-Ping Hsieh, Chen Liu

We reconsider the training objective of Generative Adversarial Networks (GANs) from the mixed Nash Equilibria (NE) perspective. Inspired by the classical prox methods, we develop a novel algorithmic framework for GANs via an infinite-dimensional two-player ...

2018

Essays in Financial Economics

Christopher Trevisan

This thesis is structured in three chapters, each pertaining to a specific problem in financial economics. The first chapter, titled 'High-Frequency Jump Analysis of the Bitcoin Market' and co-authored with Prof. Olivier Scaillet and Adrien Treccani of the ...

EPFL2016

A Continuum of Commitment

Thomas Alois Weber

We examine a generic three-stage game for two players with alternating moves, where the first player can choose the level of adjustment cost to be paid in the last period to modify the action she announced in the first period. In the resulting continuum of ...

2014

Analyzing the Emergence of Semantic Agreement among Rational Agents

Karl Aberer, Zoltán Miklós

Todays complex online applications often require the interaction of multiple services that potentially belong to different business entities. Interoperability is a core element of such an environment, yet not a straightforward one. In this paper, we argue ...

IEEE Computer Society2011

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 ∥Φα̂ − ƒ∥∞ ≤ ∥ ...

IEEE2011

Game Theory in Communications : a Study of Two Scenarios

Vojislav Gajic

Multi-user communication theory typically studies the fundamental limits of communication systems, and considers communication schemes that approach or even achieve these limits. The functioning of many such schemes assumes that users always cooperate, eve ...

EPFL2010

A Two-level Computable Equilibrium Model to Assess the Strategic Allocation of Emission Allowances Within the European Union

Marc Vielle, Alain Haurie, Alain Bernard

This paper deals with the modeling of the strategic allocation of greenhouse gases emission allowances in the EU-wide trading market that results from Kyoto agreement implementation. An M-matrix game is formulated where the players are countries or groups ...

2006