اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Value of Correlation
40
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Correlated equilibrium (Aumann, 1974) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents surplus (expected sum of payo s) is greater than their surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & Papadimitriou, 1999;Papadimitriou, 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs: 1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.
قيم البحث
اقرأ أيضاً
We consider Young (1985)s characterization of the Shapley value, and give a new proof of this axiomatization. Moreover, as applications of the new proof, we show that Young (1985)s axiomatization of the Shapley value works on various well-known subclasses of TU games.
In some games, additional information hurts a player, e.g., in games with first-mover advantage, the second-mover is hurt by seeing the first-movers move. What properties of a game determine whether it has such negative value of information for a par
ticular player? Can a game have negative value of information for all players? To answer such questions, we generalize the definition of marginal utility of a good to define the marginal utility of a parameter vector specifying a game. So rather than analyze the global structure of the relationship between a games parameter vector and player behavior, as in previous work, we focus on the local structure of that relationship. This allows us to prove that generically, every game can have negative marginal value of information, unless one imposes a priori constraints on allowed changes to the games parameter vector. We demonstrate these and related results numerically, and discuss their implications.
We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cos
t (OPT). The $k^{th}$ moment of Distortion is the expected approximation factor with respect to the $k^{th}$ power of OPT. We consider mechanisms that elicit alternatives by randomly sampling voters for their favorite alternative. We design two families of mechanisms that provide constant (with respect to the number of voters and alternatives) $k^{th}$ moment of Distortion using just $k$ samples if all voters can then participate in a vote among the proposed alternatives, or $2k-1$ samples if only the sampled voters can participate. We also show that these numbers of samples are tight. Such mechanisms deviate from a constant approximation to OPT with probability that drops exponentially in the number of samples, independent of the total number of voters and alternatives. We conclude with simulations on real-world Participatory Budgeting data to qualitatively complement our theoretical insights.
In markets such as digital advertising auctions, bidders want to maximize value rather than payoff. This is different to the utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who
maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as a means to achieve truthfulness, and we study which approximation ratios we can get from truthful approximation mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with $n$ bidders and $m$ items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(sqrt(m)). We provide better ratios for environments with restricted valuations.
Partially defined cooperative games are a generalisation of classical cooperative games in which the worth of some of the coalitions is not known. Therefore, they are one of the possible approaches to uncertainty in cooperative game theory. The main
focus of this paper is the class of 1-convex cooperative games under this framework. For incomplete cooperative games with minimal information, we present a compact description of the set of 1-convex extensions employing its extreme points and its extreme rays. Then we investigate generalisations of three solution concepts for complete games, namely the $tau$-value, the Shapley value and the nucleolus. We consider two variants where we compute the centre of gravity of either extreme games or of a combination of extreme games and extreme rays. We show that all of the generalised values coincide for games with minimal information and we call this solution concept the emph{average value}. Further, we provide three different axiomatisations of the average value and outline a method to generalise several axiomatisations of the $tau$-value and the Shapley value into an axiomatisation of the average value. We also briefly mention a similar derivation for incomplete games with defined upper vector and indicate several open questions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
