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

Stabilization of Capacitated Matching games 1

24th International Conference on Integer Programming and combinatorial Optimization (IPCO)

作者： Gerstbrein, Matthew Sanita, Laura Verberk, Lucy Univ Waterloo Waterloo ON Canada Bocconi Univ Milan Italy Eindhoven Univ Technol Eindhoven Netherlands

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

An edge-weighted, vertex-capacitated graph G 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 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. 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. Finally, in unit-capacity graphs there is an equivalence between the stability of a graph, existence of a stable solution for network bargaining games, and existence of a stable solution for cooperative matching games. We show that this equivalence does not extend to the capacitated case.

关键词： Matching game theory Network bargaining

来源：评论

学校读者我要写书评

暂无评论

Maker-Breaker on Galton-Watson trees

arXiv

引用

arXiv 2024年

作者： Vilkas, Timo Statistiska institutionen Ekonomihögskolan vid Lunds universitet Lund220 07 Sweden

We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree’s root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning probability of Breaker via fixed point equations in three natural information regimes. These results provide new insights into combinatorial game theory and random structures, with potential applications to network theory, algorithmic game design and probability *** Codes 05C57, 91A43, 60G50 © 2024, CC BY.

关键词： game theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Disjunctive sums of quasi-nimbers

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期945卷

作者： Silva, Alexandre dos Santos, Carlos Pereira Neto, Joao Pedro Nowakowski, Richard J. Univ Minho Braga Portugal FCT NOVA Ctr Math & Applicat NovaMath Caparica Portugal Univ Lisbon Comp Sci Dept Fac Sci Lisbon Portugal LASIGE Lisbon Portugal Dalhousie Univ Dept Math & Stat Halifax NS Canada

pAINT CAN is an example of a game whose positions are disjunctive sums, and a move in any component reduces that component to a nimber. Conway, in On Numbers and games, partially analyzed the related game SupERNIm, and called these components "superstars", mentioning "There does not appear to be a complete theory". The book contains one result about these games, and, until now, there has been no advance in finding good strategies. Here, we show that, for a human, the use of canonical forms is not a good approach. We present an algorithmic, recursive approach to the general case, based on a fundamental reduction of these positions, as well as on a Nimber Avoidance Theorem. An analysis of the computational time of the algorithm is presented. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： combinatorial game theory Superstars Quasi-nimbers Supernim Paint can

来源：评论

学校读者我要写书评

暂无评论

A Framework for Computing the Nucleolus via Dynamic Programming

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2023年第1-2期11卷 3-3页

作者： Koenemann, Jochen Toth, Justin Univ Waterloo Waterloo ON Canada

This article defines a general class of cooperative games for which the nucleolus is efficiently computable. This class includes new members for which the complexity of computing their nucleolus was not previously known. We show that when the minimum excess coalition problem of a cooperative game can be formulated as a hypergraph dynamic program, its nucleolus is efficiently computable. This gives a general technique for designing efficient algorithms for computing the nucleolus of a cooperative game. This technique is inspired by a recent result of Pashkovich [27] on weighted voting games. However, our technique significantly extends beyond the capabilities of previous work. We demonstrate this by applying it to give an algorithm for computing the nucleolus of b-matching games in polynomial time on graphs of bounded treewidth.

关键词： combinatorial optimization algorithmic game theory dynamic programming

来源：评论

学校读者我要写书评

暂无评论

The continualization approach to the on-line hypergraph coloring

arXiv

引用

arXiv 2022年

作者： Margarita, Akhmejanova Ilya, Bogdanov Grigory, Chelnokov Thuwal23955-6900 Saudi Arabia Moscow Institute of Physics and Technology Laboratory of Combinatorial and Geometric Structures Dolgoprudny Russia National Research University Higher School of Economics Moscow Russia

The paper deals with an algorithmic problem concerning combinatorial game theory. Here we introduce and analyze a continuous generalization of Chip game from [9]. The general Chip game was introduced by Aslam and Dhag... 详细信息

关键词： game theory

来源：评论

学校读者我要写书评

暂无评论

Generative Models of Huge Objects

arXiv

引用

arXiv 2023年

作者： Hu, Lunjia Livni-Navon, Inbal Reingold, Omer Stanford University United States

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. Copyright © 2023, The Authors. All rights reserved.

关键词： game theory

来源：评论

学校读者我要写书评

暂无评论

Stability based on single-agent deviations in additively separable hedonic games

引用

ARTIFICIAL INTELLIGENCE 2024年 334卷

作者： Brandt, Felix Bullinger, Martin Tappe, Leo Tech Univ Munich Sch Computat Informat & Technol Boltzmannstr 3 D-85748 Munich Germany Univ Oxford Dept Comp Sci 7 Parks Rd Oxford OX1 3QD England

Coalition formation is a central concern in multiagent systems. A common desideratum for coalition structures is stability, defined by the absence of beneficial deviations of single agents. Such deviations require an agent to improve her utility by joining another coalition. On top of that, the feasibility of deviations may also be restricted by demanding consent of agents in the welcoming and/or the abandoned coalition. While most of the literature focuses on deviations constrained by unanimous consent, we also study consent decided by majority vote and introduce two new stability notions that can be seen as local variants of another solution concept called popularity. We investigate stability in additively separable hedonic games by pinpointing boundaries to computational complexity depending on the type of consent and friend-oriented utility restrictions. The latter restrictions shed new light on well-studied classes of games based on the appreciation of friends or the aversion to enemies. Many of our positive results follow from a new combinatorial observation that we call the Deviation Lemma and that we leverage to prove the convergence of simple and natural single -agent dynamics under fairly general conditions. Our negative results, in particular, resolve the complexity of contractual Nash stability in additively separable hedonic games.

关键词： Computational social choice algorithmic game theory Hedonic games Single-agent stability Dynamics Computational complexity

来源：评论

学校读者我要写书评

暂无评论

13th International Symposium on algorithmic game theory, SAGT 2020

13th International Symposium on Algorithmic Game Theory, SAG...

引用

13th International Symposium on algorithmic game theory, SAGT 2020

ISBN: (纸本)9783030579791

The proceedings contain 21 papers. The special focus in this conference is on algorithmic game theory. The topics include: Bribery and Control in Stable Marriage;approximating Stable Matchings with Ties of Bounded Size;envy-Freeness and Relaxed Stability: Hardness and Approximation Algorithms;targeted Intervention in Random Graphs;a New Lower Bound for Deterministic Truthful Scheduling;modified Schelling games;race Scheduling games;line-Up Elections: Parallel Voting with Shared Candidate Pool;recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms;asymptotically Optimal Communication in Simple Mechanisms;a General Framework for Computing the Nucleolus via Dynamic Programming;how Many Freemasons Are There? The Consensus Voting Mechanism in Metric Spaces;finding Fair and Efficient Allocations When Valuations Don’t Add Up;mechanism Design for Perturbation Stable combinatorial Auctions;congestion games with Priority-Based Scheduling;equilibrium Inefficiency in Resource Buying games with Load-Dependent Costs;a Unifying Approximate Potential for Weighted Congestion games;the Impact of Spillback on the Price of Anarchy for Flows over Time;dynamic Equilibria in Time-Varying Networks.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Computing the nucleolus of weighted cooperative matching games in polynomial time

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期183卷 555-581页

作者： Konemann, Jochen Pashkovich, Kanstantsin Toth, Justin Univ Waterloo Waterloo ON N2L 3G1 Canada Univ Ottawa Ottawa ON K1N 6N5 Canada

We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in Faigle (Math Programm, 83: 555-569, 1998).

关键词： combinatorial Optimization algorithmic game theory Matchings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：