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

A game Theoretic Approach for a Minimal Secure Dominating Set

IEEE/CAA Journal of Automatica Sinica 2023年第12期10卷 2258-2268页

作者： Xiuyang Chen Changbing Tang Zhao Zhang the College of Mathematics and System Science Xinjiang UniversityUrumqi 830000China IEEE the College of Physics and Electronic Information Engineering Zhejiang Normal UniversityJinhua 321004China the School of Mathematical Sciences Zhejiang Normal UniversityJinhua 321004China

The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless *** this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent *** design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal *** prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of *** experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.

关键词： algorithmic game theory multi-agent systems po-tential game secure dominating set

来源：评论

学校读者我要写书评

暂无评论

New bounds on the price of anarchy of selfish bin packing with partial punishment

引用

JOURNAL OF combinatorial OPTIMIZATION 2025年第1期49卷 1-17页

作者： Li, Xiaowei Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Coll Math Shanghai 200237 Peoples R China

The selfish bin packing with partial punishment is studied in this paper. In this problem, the utility of an item is defined as the load of the bin it is in. Each item plays the role of a selfish agent and wants to maximize its own utility. If an item with size si moves to another bin, it has to pay the partial punishment of alpha s i , where 0 < alpha < 1. We prove that the price of anarchy (PoA) of this game is at least 1.6424 for any alpha is an element of (0 , 1). In particular, the PoA of this game is at least 5/3 approximate to 1.6667 for any alpha is an element of (2/5, 1). Furthermore, we obtain a new upper bound of h (alpha) <= 31/18 approximate to 1.7222 on the PoA.

关键词： algorithmic game theory Selfish bin packing Price of anarchy Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

WHICH IS THE WORST-CASE NASH EQUILIBRIUM?

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第2期38卷 1701-1732页

作者： Luecking, Thomas Mavronicolas, Marios Monien, Burkhard Spirakis, Paul g. Vrto, Imrich Univ Paderborn Fac Comp Sci Elect Engn & Math D-33102 Paderborn Germany Univ Cyprus Dept Comp Sci CY-1678 Nicosia Cyprus Univ Paderborn Fac Comp Sci Elect Engn & Math D-33102 Paderborn Germany Univ Liverpool Dept Comp Sci Liverpool L69 3BX England Res Acad Comp Technol Inst Patras 26110 Greece Slovak Acad Sci Inst Math Bratislava 4 Slovakia

A Nash equilibrium of a routing game is a stable state where no (randomizing) user could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst -case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev ., 3 (2009), pp. 65--69], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst -case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links.

关键词： algorithmic game theory Nash equilibrium fully mixed Nash equilibrium conjecture

来源：评论

学校读者我要写书评

暂无评论

combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

引用

MATHEMATICS OF OPERATIONS RESEARCH 2023年第2期49卷 653-1302, C2页

作者： Eden, Alon Feldman, Michal Fiat, Amos Goldner, Kira Karlin, Anna R. Hebrew Univ Jerusalem Sch Comp Sci & Engn IL-9190401 Jerusalem Israel Tel Aviv Univ Sch Comp Sci IL-6997801 Tel Aviv Israel Boston Univ Fac Comp & Data Sci Boston MA 02215 USA Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA

We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation function of every agent depends on the entire signal profile, s = (s1,...,sn). The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations;(ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations;and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d.

关键词： mechanism design interdependent valuations combinatorial auctions algorithmic game theory

来源：评论

学校读者我要写书评

暂无评论

Generative Models of Huge Objects 23

Generative Models of Huge Objects

引用

38th Computational Complexity Conference, CCC 2023

作者： Hu, Lunjia Navon, Inbal Rachel Livni Reingold, Omer Department of Computer Science Stanford University CA United States

ISBN: (纸本)9783959772822

This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that focused on the implementation of huge objects that are indistinguishable from the uniform distribution, satisfying some global properties (which they coined truthfulness). Indistinguishability from a single object is motivated by the study of generative models in learning theory and regularity lemmas in graph theory. Problems that are well understood in the setting of pseudorandomness present significant challenges and at times are impossible when considering generative models of huge objects. We demonstrate the versatility of this study by providing a learning algorithm for huge indistinguishable objects in several natural settings including: dense functions and graphs with a truthfulness requirement on the number of ones in the function or edges in the graphs, and a version of the weak regularity lemma for sparse graphs that satisfy some global properties. These and other results generalize basic pseudorandom objects as well as notions introduced in algorithmic fairness. The results rely on notions and techniques from a variety of areas including learning theory, complexity theory, cryptography, and game theory. © Lunjia Hu, Inbal Rachel Livni Navon, and Omer Reingold;licensed under Creative Commons License CC-BY 4.0.

关键词： game theory

来源：评论

学校读者我要写书评

暂无评论

Geometry of set functions in game theory: combinatorial and computational aspects

arXiv

引用

arXiv 2023年

作者： Mermoud, Dylan Laplace

The main ambition of this thesis is to contribute to the development of cooperative game theory towards combinatorics, algorithmics and discrete geometry. Therefore, the first chapter of this manuscript is devoted to the highlighting of the geometric nature of the coalition functions of transferable utility games, and spotlights the existing connections with the theory of submodular set functions and polyhedral geometry. To deepen the links with polyhedral geometry, we define a new family of polyhedra, called the basic polyhedra, on which we can apply a generalized version of the Bondareva-Shapley Theorem to check their nonemptiness. To allow a practical use of these computational tools, we present an algorithmic procedure generating the minimal balanced collections, based on Peleg’s recursive method. Subsequently, we apply the generalization of the Bondareva-Shapley Theorem to design a collection of algorithmic procedures able to check properties or generate specific sets of coalitions. In the next chapter, the connections with combinatorics are investigated. First, we prove that the balanced collections form a combinatorial species, and we construct the one of k-uniform hypergraphs of size p, as an intermediary step to construct the species of balanced collections. Afterwards, a few results concerning resonance arrangements distorted by games are introduced, which gives new information about the space of preimputations and the facial configuration of the core. Finally, we address the question of core stability using the results from the previous chapters. Firstly, we present an algorithm based on Grabisch and Sudhölter’s nested balancedness characterization of games with a stable core, which extensively uses the generalization of the Bondareva-Shapley Theorem introduced in the second chapter. Secondly, a new necessary condition for core stability is described, based on the application of the aforementioned generalization to a specific cone. Finally, we study the d

关键词： game theory

来源：评论

学校读者我要写书评

暂无评论

Stabilization of capacitated matching games

引用

MATHEMATICAL PROGRAMMING 2024年第1期210卷 313-334页

作者： Gerstbrein, Matthew Sanita, Laura Verberk, Lucy Univ Waterloo Math 200 Univ Ave West Waterloo ON N2L 3G1 Canada Bocconi Univ Comp Sci Via Roentgen 1 I-20136 Milan Lombardy Italy Eindhoven Univ Technol Math & Comp Sci Groene Loper 3 NL-5612 AE Eindhoven Noord brabant Netherlands

An edge-weighted, vertex-capacitated graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stable solutions for popular combinatorial games that involve the structure of matchings in graphs, such as network bargaining games and cooperative matching games. The vertex-stabilizer problem asks to compute a minimum number of players to block (i.e., vertices of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} to remove) in order to ensure stability for such games. The problem has been shown to be solvable in polynomial-time, for unit-capacity graphs. This stays true also if we impose the restriction that the set of players to block must not intersect with a given specified maximum matching of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. In this work, we investigate these algorithmic problems in the more general setting of arbitrary capacities. We show that the vertex-stabilizer problem with the additional restriction of avoiding a given maximum matching remains polynomial-time solvable. Differently, without this restriction, the vertex-stabilizer problem becomes NP-hard and even hard to approximate, in contrast to the unit-capacity case.

关键词： Matching game theory Network bargaining Cooperative matching games

来源：评论

学校读者我要写书评

暂无评论

Best-response dynamics in combinatorial auctions with item

引用

gameS AND ECONOMIC BEHAVIOR 2022年第0期134卷 428-448页

作者： Dutting, Paul Kesselheim, Thomas London Sch Econ Dept Math Houghton St London WC2A 2AE England Univ Bonn Inst Comp Sci Endenicher Allee 19a D-53115 Bonn Germany

In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high social welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria of this game are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective by studying simple best-response dynamics. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents' bid updates are aggressive enough but not too aggressive, the game will reach and remain in states of high welfare after each agent has updated his bid at least once.

关键词： algorithmic game theory combinatorial auctions Item bidding Best-response dynamics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the complexity of nucleolus computation for bipartite b-matching games

引用

THEORETICAL COMPUTER SCIENCE 2024年 998卷

作者： Koenemann, Jochen Toth, Justin Zhou, Felix Univ Waterloo Waterloo ON N2L 1A2 Canada

We explore the complexity of nucleolus computation in b -matching games on bipartite graphs. We show that computing the nucleolus of a simple b -matching game is NP -hard when b equivalent to 3 even on bipartite graphs of maximum degree 7. We complement this with partial positive results in the special case where b values are bounded by 2 . In particular, we describe an efficient algorithm when a constant number of vertices satisfy b = 2 as well as an efficient algorithm for computing the non -simple b -matching nucleolus when b equivalent to 2 .

关键词： algorithmic game theory combinatorial optimization Matching games Cooperative game theory Linear programming Complexity theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：