检索结果-内蒙古大学图书馆

The structure and complexity of Nash equilibria for a selfish routing game

THEORETICAL COMPUTER SCIENCE 2009年第36期410卷 3305-3326页

作者： Fotakis, Dimitris Kontogiannis, Spyros Koutsoupias, Elias Mavronicolas, Marios Spirakis, Paul Comp Technol Inst Res Acad Patras 26500 Greece Univ Aegean Dept Informat & Commun Syst Engn Samos 83200 Greece Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece Univ Athens Dept Informat GR-10679 Athens Greece Univ Cyprus Dept Comp Sci CY-1678 Nicosia Cyprus Univ Patras Dept Comp Sci & Informat Patras 26500 Greece

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of it users, each employing a mixed strategy, which is a probability distribution over links, to control the routing Of her own traffic. In a Nosh equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and Computing the Social Cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system. (C) 2008 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Selfish routing Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Multi-agent systems for computational economics and finance

引用

AI COMMUNICATIONS 2022年第4期35卷 369-380页

作者： Kampouridis, Michael Kanellopoulos, Panagiotis Kyropoulou, Maria Melissourgos, Themistoklis Voudouris, Alexandros A. Univ Essex Sch Comp Sci & Elect Engn Colchester Essex England

In this article we survey the main research topics of our group at the University of Essex. Our research interests lie at the intersection of theoretical computer science, artificial intelligence, and economic theory. In particular, we focus on the design and analysis of mechanisms for systems involving multiple strategic agents, both from a theoretical and an applied perspective. We present an overview of our group's activities, as well as its members, and then discuss in detail past, present, and future work in multi-agent systems.

关键词： algorithmic game theory mechanism design computational social choice machine learning

来源：评论

学校读者我要写书评

暂无评论

Graphical Congestion games

引用

algorithmicA 2011年第2期61卷 274-297页

作者： Bilo, Vittorio Fanelli, Angelo Flammini, Michele Moscardelli, Luca Univ G dAnnunzio Dipartimento Sci I-65127 Pescara Italy Univ Salento Dipartimento Matemat I-73100 Lecce Italy Nanyang Technol Univ Div Math Sci Sch Phys & Math Sci Singapore Singapore Univ Aquila Dipartimento Informat I-67100 Laquila Italy

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem. We then investigate the impact of the limited knowledge of the players on the performance of the game. More precisely, given a bound on the maximum degree of G, for the convergent cases we provide tight lower and upper bounds on the price of stability and asymptotically tight bounds on the price of anarchy. Such results are determined for four natural social cost functions: total and maximum presumed latencies, that is the ones the players believe to pay due to the fact that they are only aware of the existence of their neighbors, and total and maximum perceived latencies, i.e. actually experienced due to all (and not only the known) players using the same facilities. All the results are then extended to singleton congestion games.

关键词： algorithmic game theory Nash equilibrium Price of anarchy Price of stability Congestion games Social knowledge

来源：评论

学校读者我要写书评

暂无评论

Enforcing Efficient Equilibria in Network Design games via Subsidies

引用

algorithmicA 2015年第1期72卷 44-82页

作者： Augustine, John Caragiannis, Ioannis Fanelli, Angelo Kalaitzis, Christos Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India Univ Patras Res Acad Comp Technol Inst Rion 26504 Greece Univ Patras Dept Comp Engn & Informat Rion 26504 Greece CNRS Caen France Univ Caen F-14032 Caen France Ecole Polytech Fed Lausanne Sch Comp & Commun Sci Lausanne Switzerland

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users' selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results.

关键词： Network design algorithmic game theory Equilibria Price of stability

来源：评论

学校读者我要写书评

暂无评论

GEOMETRIC NETWORK CREATION gameS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第1期38卷 277-315页

作者： Bilo, Davide Friedrich, Tobias Lenzner, Pascal Melnichenko, Anna Univ Sassari Dept Humanities & Social Sci Sassari Italy Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany

Network creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real -world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games only considered the creation of networks with unit -weight edges. In practice, e.g., when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depend on the distance between the involved nodes, and such settings can be modeled via edge -weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [Proceedings of PODC'03, ACM, 2003, pp. 347--351] to edge -weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state of the art for the unit -weight version, where the price of anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric case. Moreover, we analyze the existence of equilibria, the computational hardness, and the game dynamics for several natural metrics. The model we propose can be seen as the game -theoretic analogue of the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.

关键词： network design algorithmic game theory network creation games price of anarchy geometry communication networks existence of equilibria game dynamics

来源：评论

学校读者我要写书评

暂无评论

Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction games

引用

algorithmicA 2017年第4期77卷 1143-1158页

作者： Caragiannis, Ioannis Fanelli, Angelo Gravin, Nick Univ Patras Comp Technol Inst Diophantus Rion 26504 Greece Univ Patras Dept Comp Engn & Informat Rion 26504 Greece Univ Caen Basse Normandie CNRS Lab CREM UMR 6211 Caen France Microsoft Res One Mem Dr Cambridge MA 02142 USA

We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al. (EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property which, to the best of our knowledge, was not known before. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler.

关键词： algorithmic game theory Complexity of equilibria Pure Nash equilibrium Potential games Constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types

引用

ARTIFICIAL INTELLIGENCE 2013年 195卷 106-139页

作者： Rabinovich, Zinovi Naroditskiy, Victor Gerding, Enrico H. Jennings, Nicholas R. Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Univ Southampton Southampton SO17 1BJ Hants England King Abdulaziz Univ Dept Comp & Informat Technol Jeddah Saudi Arabia

We extend the well-known fictitious play (FP) algorithm to compute pure-strategy Bayesian-Nash equilibria in private-value games of incomplete information with finite actions and continuous types (G-FACTs). We prove that, if the frequency distribution of actions (fictitious play beliefs) converges, then there exists a pure-strategy equilibrium strategy that is consistent with it. We furthermore develop an algorithm to convert the converged distribution of actions into an equilibrium strategy for a wide class of games where utility functions are linear in type. This algorithm can also be used to compute pure epsilon-Nash equilibria when distributions are not fully converged. We then apply our algorithm to find equilibria in an important and previously unsolved game: simultaneous sealed-bid, second-price auctions where various types of items (e.g., substitutes or complements) are sold. Finally, we provide an analytical characterisation of equilibria in games with linear utilities. Specifically, we show how equilibria can be found by solving a system of polynomial equations. For a special case of simultaneous auctions, we also solve the equations confirming the results obtained numerically. Crown Copyright (C) 2012 Published by Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Bayes-Nash equilibrium Epsilon-Nash equilibrium Fictitious play Simultaneous auctions

来源：评论

学校读者我要写书评

暂无评论

Balanced allocation mechanism: An optimal mechanism for multiple keywords sponsored search auctions

引用

INFORMATION SCIENCES 2014年第0期262卷 190-214页

作者： Razzazi, Mohammadreza Esmaeeli, Ali Amirkabir Univ Technol Comp Engn & IT Dept Software Syst R&D Lab Tehran Iran Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran

This paper presents an optimal mechanism for allocating slots of multiple keywords to bidders who have only one budget limit for all their desired keywords;it is called the balanced allocation mechanism. In a balanced allocation, all the bidders and slots for the keywords are partitioned into consecutive and distinct structures called balanced blocks. The study develops efficient algorithms for this mechanism. For instance, an algorithm is developed to create a "perfect schedule" for each independent, balanced block. Using this scheduling, all the slots and budgets of all bidders will be consumed. The balanced allocation mechanism creates a balanced allocation with perfect scheduling for each balanced block. This research confirms that this is an optimal truthful mechanism that maximizes the revenue of a search engine. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Sponsored search auction Mechanism design Optimal mechanism Truthfulness algorithmic game theory

来源：评论

学校读者我要写书评

暂无评论

Nonlinear bipartite matching

引用

DISCRETE OPTIMIZATION 2008年第1期5卷 53-65页

作者： Berstein, Yael Onn, Shmuel Technion Israel Inst Technol Davidson Fac IE & M IL-32000 Haifa Israel

We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient algorithms for it, including a deterministic algorithm for maximizing convex objectives, approximative algorithms for norm minimization and maximization, and a randomized algorithm for optimizing arbitrary objectives. (C) 2007 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory combinatorial optimization game cooperative game transferable utility game solution concept

来源：评论

学校读者我要写书评

暂无评论

On best response dynamics in weighted congestion games with polynomial delays

引用

DISTRIBUTED COMPUTING 2011年第5期24卷 245-254页

作者： Fanelli, Angelo Moscardelli, Luca Univ G dAnnunzio Dept Sci Pescara Italy Nanyang Technol Univ Div Math Sci Sch Phys & Math Sci Singapore Singapore

We investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. Awerbuch et al. (Fast convergence to nearly optimal solutions in potential games. ACM Conference on Electronic Commerce, 2008) showed that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, we show that I similar to(n log log W) (where W is the sum of all the players' weights) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that every O(n) steps each player performs a constant (and non-null) number of best responses. For congestion games in which computing a best response is a polynomial time solvable problem, such a dynamics naturally implies a polynomial time distributed algorithm for the problem of computing the social optimum in congestion games, approximating the optimal solution by a constant factor.

关键词： Speed of convergence Congestion games algorithmic game theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：