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

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

algorithmicA 2014年第3期69卷 619-640页

作者： Christodoulou, Giorgos Mehlhorn, Kurt Pyrga, Evangelia Univ Liverpool Ashton BldgAshton St Liverpool L69 3BX Merseyside England Max Planck Inst Informat D-66123 Saarbrucken Germany Tech Univ Munich D-80290 Munich Germany

We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3;this maximum is attained already for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if l(e) (x) is the latency function of an edge e, we replace it by (l) over cap (e)(x) with l(e) (x) <= (l) over cap (e)(x) for all x. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if (C) over cap (N)(r) denotes the cost of the worst Nash flow in the modified network for rate r and (C) over cap (opt)(r) denotes the cost of the optimal flow in the original network for the same rate then ePoA = max(r >= 0) (C) over cap (N)(r)/(C) over cap (opt) (r) We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4=1.25. Then, for the case of two parallel links, we describe an optimal mechanism;its engineered Price of Anarchy lies between 1.191 and 1.192.

关键词： algorithmic game theory Selfish routing Price of Anarchy Coordination mechanisms

来源：评论

学校读者我要写书评

暂无评论

On efficient computation of equilibrium under social coalition structures

引用

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES 2020年第3期28卷 1686-1698页

作者： Caskurlu, Bugra Ekici, Ozgun Kizilkaya, Fatih Erdem TOBB Univ Econ & Technol Fac Engn Dept Comp Engn Ankara Turkey Ozyegin Univ Fac Business Dept Econ Istanbul Turkey

In game-theoretic settings the key notion of analysis is an equilibrium, which is a profile of agent strategies such that no viable coalition of agents can improve upon their coalitional welfare by jointly changing their strategies. A Nash equilibrium, where viable coalitions are only singletons, and a super strong equilibrium, where every coalition is deemed viable, are two extreme scenarios in regard to coalition formation. A recent trend in the literature is to consider equilibrium notions that allow for coalition formation in between these two extremes and which are suitable to model social coalition structures that arise in various real-life settings. The recent literature considered the question on the existence of equilibria under social coalition structures mainly in Resource Selection games (RSGs), due to the simplicity of this game form and its wide range of application domains. We take the question on the existence of equilibria under social coalition structures from the perspective of computational complexity theory. We study the problem of deciding the existence of an equilibrium in RSGs with respect to a given social coalition structure. For an arbitrary coalition structure, we show that it is computationally intractable to decide whether an equilibrium exists even in very restricted settings of RSGs. In certain settings where an equilibrium is guaranteed to exist we give polynomial-time algorithms to find an equilibrium.

关键词： algorithmic game theory laminar equilibrium contiguous equilibrium resource selection games

来源：评论

学校读者我要写书评

暂无评论

Truthful algorithms for scheduling selfish tasks on parallel machines

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期369卷 157-168页

作者： Angel, Eric Bampis, Evripidis Pascual, Fanny Univ Evry Val Essonne LaMI CNRS UMR 8042 F-91000 Evry France

We consider the problem of designing truthful mechanisms for scheduling selfish tasks (or agents)-whose objective is the minimization of their completion times-on parallel identical machines in order to minimize the makespan. A truthful mechanism can be easily obtained in this context (if we, of course, assume that the tasks cannot shrink their lengths) by scheduling the tasks following the increasing order of their lengths. The quality of a mechanism is measured by its approximation factor (price of anarchy, in a distributed system) w.r.t. the social optimum. The previous mechanism, known as SPT, produces a (2 - 1/m)-approximate schedule, where in is the number of machines. The central question in this paper is the following: "Are there other truthful mechanisms with better approximation guarantee (price of anarchy) for the considered scheduling problem?" This question has been raised by Christodoulou. et al. [Coordination mechanisms, in: Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, 345-357.] in the context of coordination mechanisms, but it is also relevant in centrally controlled systems. We present (randomized) truthful mechanisms for both the centralized and the distributed settings that improve the (expected) approximation guarantee (price of anarchy) of the SPT mechanism. Our centralized mechanism holds for any number of machines and arbitrary task lengths, while the coordination mechanism holds only for two machines and task lengths that are powers of a certain constant. (c) 2006 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory truthful algorithm scheduling coordination mechanism mechanism design

来源：评论

学校读者我要写书评

暂无评论

Computing equilibria for integer programming games

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第3期303卷 1057-1070页

作者： Carvalho, Margarida Lodi, Andrea Pedroso, Joao P. Univ Montreal Dept Informat & Rech Operat Montreal PQ H3T 1J4 Canada Univ Montreal CIRRELT Montreal PQ H3T 1J4 Canada Polytech Montreal CERC Montreal PQ H3C 3A7 Canada Cornell Tech & Technion IIT Jacobs Technion Cornell Inst New York NY 10044 USA Univ Porto Fac Ciencias INESC TEC P-4169007 Porto Portugal

The recently-defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be cast in this way, hence anticipating IPG outcomes is of crucial value for policy makers. Nash equilibria have been widely accepted as the solution concept of a game. Thus, their computation provides a reasonable prediction of games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop a general algorithmic approach that is guaranteed to return a Nash equilibrium when the game is finite and to approximate an equilibrium when payoff functions are Lipschitz continuous. We also showcase how our methodology can be changed to determine other types of equilibria. The performance of our methods is analyzed through computational experiments on knapsack, kidney exchange and a competitive lot-sizing games. To the best of our knowledge, this is the first time that equilibria computation methods for general IPGs have been designed and computationally tested. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Nash equilibria Correlated equilibria algorithmic game theory Integer programming games

来源：评论

学校读者我要写书评

暂无评论

Selfish bin packing with cardinality constraints

引用

THEORETICAL COMPUTER SCIENCE 2013年 495卷 66-80页

作者： Adar, Ron Epstein, Leah Univ Haifa Dept Comp Sci IL-3190501 Haifa Israel Univ Haifa Dept Math IL-3190501 Haifa Israel

Bin packing with cardinality constraints is a variant of bin packing. In this problem, items with sizes of at most 1 are to be partitioned (or packed) into subsets called bins, such that the total size of items packed into a bin would not exceed 1, and each bin would contain at most k items, for a given integer parameter k > 1. We consider a class of games resulting from this problem by seeing the items as selfish players, trying to be packed into a (valid) bin where the total size of items is maximized. Such games always admit pure Nash equilibria. We analyze the Price of Anarchy (PoA) of such games, defined as the asymptotic worst case ratio between the maximum number of bins in a pure Nash equilibrium (NE), and the minimum number of bins in any valid solution, that is, the number of bins in a socially optimal solution. We provide a complete analysis of the PoA as a function of k;we prove that for k = 2, any NE is an optimal solution, for k >= 4, the PoA is exactly 2 - 1/k, and for k = 3, the PoA is exactly 11/7.. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Variants of bin packing Price of anarchy

来源：评论

学校读者我要写书评

暂无评论

Bounded budget betweenness centrality game for strategic network formations

引用

THEORETICAL COMPUTER SCIENCE 2011年第52期412卷 7147-7168页

作者： Bei, Xiaohui Chen, Wei Teng, Shang-Hua Zhang, Jialin Zhu, Jiajie Tsinghua Univ Inst Theoret Comp Sci Beijing Peoples R China Univ So Calif Los Angeles CA 90089 USA Univ Calif Los Angeles Los Angeles CA 90024 USA

In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest path exchanges. In this paper, we introduce a strategic network formation game in which nodes build connections subject to a budget constraint in order to maximize their betweenness in the network. To reflect real world scenarios where short paths are more important in information exchange in the network, we generalize the betweenness definition to only count shortest paths with a length limit l in betweenness calculation. We refer to this game as the bounded budget betweenness centrality game and denote it as l-(BC)-C-3 game, where l is the path length constraint parameter. We present both complexity and constructive existence results about Nash equilibria of the game. For the nonuniform version of the game where node budgets, link costs, and pairwise communication weights may vary, we show that Nash equilibria may not exist and it is NP-hard to decide whether Nash equilibria exist in a game instance. For the uniform version of the game where link costs and pairwise communication weights are one and each node can build k links, we construct two families of Nash equilibria based on shift graphs, and study the properties of Nash equilibria. Moreover, we study the complexity of computing best responses and show that the task is polynomial for uniform 2-(BC)-C-3 games and NP-hard for other games (i.e. uniform l-(BC)-C-3 games with l >= 3 and nonuniform l-(BC)-C-3 games with l >= 2). (C) 2011 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Network formation game Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Price-Based Resource Allocation for Edge Computing: A Market Equilibrium Approach

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2021年第1期9卷 302-317页

作者： Duong Tung Nguyen Long Bao Le Bhargava, Vijay Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Univ Quebec INRS EMT Montreal PQ H5A 1K6 Canada

The emerging edge computing paradigm promises to deliver superior user experience and enable a wide range of Internet of Things (loT) applications. In this paper, we propose a new market-based framework for efficiently allocating resources of heterogeneous capacity-limited edge nodes (EN) to multiple competing services at the network edge. By properly pricing the geographically distributed ENs, the proposed framework generates a market equilibrium (ME) solution that not only maximizes the edge computing resource utilization but also allocates optimal resource bundles to the services given their budget constraints. When the utility of a service is defined as the maximum revenue that the service can achieve from its resource allotment, the equilibrium can be computed centrally by solving the Eisenberg-Gale (EG) convex program. We further show that the equilibrium allocation is Pareto-optimal and satisfies desired fairness properties including sharing incentive, proportionality, and envy-freeness. Also, two distributed algorithms, which efficiently converge to an ME, are introduced. When each service aims to maximize its net profit (i.e., revenue minus cost) instead of the revenue, we derive a novel convex optimization problem and rigorously prove that its solution is exactly an ME. Extensive numerical results are presented to validate the effectiveness of the proposed techniques.

关键词： Market equilibrium Fisher market fairness algorithmic game theory edge computing fog computing

来源：评论

学校读者我要写书评

暂无评论

A new allocation rule for the housing market problem with ties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期43卷 98-115页

作者： Xiong, Xinsheng Wang, Xianjia He, Kun Wuhan Univ Sch Econ & Management Wuhan 430072 Peoples R China Huaihua Coll Dept Math & Computat Sci Huaihua 418000 Peoples R China Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

We address a general housing market problem with a set of agents and a set of houses. Each agent has a weak ordinal preference list that allows ties on houses as well as an initial endowment;moreover, each agent wishes to reallocate to a better house on the housing market. In this work, we reduces the complexity of the family of top trading cycles algorithms by selecting a specific house from the preferred set during the trading phase. The rule of construction digraphs is used to select an appropriate house. Based on these digraphs, we propose an extended top trading cycles algorithm with complexity O(n(2)r), where n is the number of agents and r is the maximum length of ties in the preference lists. The algorithm complexity is lower than that of the state-of-the-art algorithms. We show that the proposed algorithm is individually rational, Pareto efficient, and strategy-proof. It thus overcomes the limitations of a classic top trading cycles algorithm, and features Pareto efficiency and strategy-proofness on the weak preference domain.

关键词： algorithmic game theory Resource allocation Pareto efficiency Strategy-proofness Top trading cycles algorithm

来源：评论

学校读者我要写书评

暂无评论

Computational Aspects of Uncertainty Profiles and Angel-Daemon games

引用

theory OF COMPUTING SYSTEMS 2014年第1期54卷 83-110页

作者： Gabarro, Joaquim Garcia, Alina Serna, Maria Univ Politecn Cataluna ALBCOM Res Grp ES-08034 Barcelona Spain

We analyze the complexity of equilibria problems for a class of strategic zero-sum games, called angel-daemon games. Those games were introduced to asses the performance of the execution of a web orchestration on a moderate faulty or under stress environment. Angel-daemon games are a natural example of zero-sum games whose representation is naturally succinct. We show that the problems of deciding the existence of a pure Nash equilibrium or of a dominant strategy for a given player are -complete. Furthermore, computing the value of an angel-daemon game is EXP-complete. Thus, our results match the already known classification of the corresponding problems for the generic families of succinctly represented games with exponential number of actions.

关键词： Nash equilibrium Zero-sum games Succinct games Angel-daemon games algorithmic game theory Orchestrations Fault tolerance Computational complexity

来源：评论

学校读者我要写书评

暂无评论

The Exact Computational Complexity of Evolutionarily Stable Strategies

引用

MATHEMATICS OF OPERATIONS RESEARCH 2019年第3期44卷 783-792页

作者： Conitzer, Vincent Duke Univ Dept Comp Sci Durham NC 27708 USA

While the computational complexity of many game-theoretic solution concepts, notably Nash equilibrium, has now been settled, the question of determining the exact complexity of computing an evolutionarily stable strategy has resisted solution since attention was drawn to it in 2004. In this paper, I settle this question by proving that deciding the existence of an evolutionarily stable strategy is Sigma(p)(2) complete.

关键词： algorithmic game theory equilibrium computation evolutionarily stable strategies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：