Optimistic and pessimistic approaches for cooperative games

2024-03-03 · Ata Atay, Christian Trudeau

Cooperative game theory studies how to allocate the joint value generated by a set of players. These games are typically analyzed using the characteristic function form with transferable utility, which represents the value attainable by each coalition. In the presence of externalities, coalition values can be defined through various approaches, notably by trying to determine the best and worst-case scenarios. Typically, the optimistic and pessimistic perspectives offer valuable insights into strategic interactions. In many applications, these approaches correspond to the coalition either choosing first or choosing after the complement coalition. In a general framework in which the actions of a group affects the set of feasible actions for others, we explore this relationship and show that it always holds in the presence of negative externalities, but only partly with positive externalities. We then show that if choosing first/last corresponds to these extreme values, we also obtain a useful inclusion result: allocations that do not allocate more than the optimistic upper bounds also do not allocate less than the pessimistic lower bounds. Moreover, we show that when externalities are negative, it is always possible to guarantee the non-emptiness of these sets of allocations. Finally, we explore applications to illustrate how our findings provide new results and offer a means to derive results from the existing literature.

📄 PDF Abstract BibTeX arXiv:2403.01442

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Computing the Strategy to Commit to in Polymatrix Games (Extended Version)

2018-07-31 · Giuseppe De Nittis, Alberto Marchesi, Nicola Gatti

Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically, breaking ties in favour of the leader. Unfortunately, for r…

Optimistic Exploration even with a Pessimistic Initialisation

2020-02-26 · ICLR 2020 1 · Tabish Rashid, Bei Peng, Wendelin Böhmer, Shimon Whiteson

Optimistic initialisation is an effective strategy for efficient exploration in reinforcement learning (RL). In the tabular case, all provably efficient model-free algorithms rely on it. However, model-free deep RL algor…

Efficient Exploration Q-Learning Reinforcement Learning Reinforcement Learning (RL)

Optimistic variants of single-objective bilevel optimization for evolutionary algorithms

2020-08-22 · Anuraganand Sharma

Single-objective bilevel optimization is a specialized form of constraint optimization problems where one of the constraints is an optimization problem itself. These problems are typically non-convex and strongly NP-Hard…

Bilevel Optimization Decision Making Evolutionary Algorithms Heuristic Search

Reducing Optimism Bias in Incomplete Cooperative Games

2024-02-02 · Filip Úradník, David Sychrovský, Jakub Černý, Martin Černý

Cooperative game theory has diverse applications in contemporary artificial intelligence, including domains like interpretable machine learning, resource allocation, and collaborative decision-making. However, specifying…

Decision Making Interpretable Machine Learning

Hyperparameter Tuning Through Pessimistic Bilevel Optimization

2024-12-04 · Meltem Apaydin Ustun, Liang Xu, Bo Zeng, Xiaoning Qian

Automated hyperparameter search in machine learning, especially for deep learning models, is typically formulated as a bilevel optimization problem, with hyperparameter values determined by the upper level and the model …

Bilevel Optimization Hyperparameter Optimization