اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTight Bounds for the Price of Anarchy and Stability in Sequential Transportation Games
181
0
0.0
(
0
)
نشر من قبل
Francisco Jhonatas Melo Da Silva
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we analyze a transportation game first introduced by Fotakis, Gourv`es, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, in order to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games.
قيم البحث
اقرأ أيضاً
We consider an atomic congestion game in which each player participates in the game with an exogenous and known probability $p_{i}in[0,1]$, independently of everybody else, or stays out and incurs no cost. We first prove that the resulting game is po
tential. Then, we compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior. It turns out that the price of anarchy as a function of the maximum participation probability $p=max_{i} p_{i}$ is a nondecreasing function. The worst case is attained when players have the same participation probabilities $p_{i}equiv p$. For the case of affine costs, we provide an analytic expression for the parameterized price of anarchy as a function of $p$. This function is continuous on $(0,1]$, is equal to $4/3$ for $0<pleq 1/4$, and increases towards $5/2$ when $pto 1$. Our work can be interpreted as providing a continuous transition between the price of anarchy of nonatomic and atomic games, which are the extremes of the price of anarchy function we characterize. We show that these bounds are tight and are attained on routing games -- as opposed to general congestion games -- with purely linear costs (i.e., with no constant terms).
Pool block withholding attack is performed among mining pools in digital cryptocurrencies, such as Bitcoin. Instead of mining honestly, pools can be incentivized to infiltrate their own miners into other pools. These infiltrators report partial solut
ions but withhold full solutions, share block rewards but make no contribution to block mining. The block withholding attack among mining pools can be modeled as a non-cooperative game called the miners dilemm, which reduces effective mining power in the system and leads to potential systemic instability in the blockchain. However, existing literature on the game-theoretic properties of this attack only gives a preliminary analysis, e.g., an upper bound of 3 for the pure price of anarchy (PPoA) in this game, with two pools involved and no miner betraying. Pure price of anarchy is a measurement of how much mining power is wasted in the miners dilemma game. Further tightening its upper bound will bring us more insight into the structure of this game, so as to design mechanisms to reduce the systemic loss caused by mutual attacks. In this paper, we give a tight bound of (1, 2] for the pure price of anarchy. Moreover, we show the tight bound holds in a more general setting, in which infiltrators may betray.We also prove the existence and uniqueness of pure Nash equilibrium in this setting. Inspired by experiments on the game among three mining pools, we conjecture that similar results hold in the N-player miners dilemma game (N>=2).
The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general conges
tion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.
Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most beneficial state to the society as a whole. Instead, strategies form Nash equilibria which are often socially s
uboptimal. Society, therefore, has to pay a price of anarchy for the lack of coordination among its members. Here we assess this price of anarchy by analyzing the travel times in road networks of several major cities. Our simulation shows that uncoordinated drivers possibly waste a considerable amount of their travel time. Counterintuitively,simply blocking certain streets can partially improve the traffic conditions. We analyze various complex networks and discuss the possibility of similar paradoxes in physics.
Algorithmic-matching sites offer users access to an unprecedented number of potential mates. However, they also pose a principal-agent problem with a potential moral hazard. The agents interest is to maximize usage of the Web site, while the principa
ls interest is to find the best possible romantic partners. This creates a conflict of interest: optimally matching users would lead to stable couples and fewer singles using the site, which is detrimental for the online dating industry. Here, we borrow the notion of Price-of-Anarchy from game theory to quantify the decrease in social efficiency of online dating sites caused by the agents self-interest. We derive theoretical bounds on the price-of-anarchy, showing it can be bounded by a constant that does not depend on the number of users of the dating site. This suggests that as online dating sites grow, their potential benefits scale up without sacrificing social efficiency. Further, we performed experiments involving human subjects in a matching market, and compared the social welfare achieved by an optimal matching service against a self-interest matching algorithm. We show that by introducing competition among dating sites, the selfish behavior of agents aligns with its users, and social efficiency increases.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
