Cover Image

Approximating the Shapley Value of Minimum Cost Spanning Tree Games: An FPRAS for Saving Games

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jimbo, Takumi, Matsui, Tomomi
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory 91A68, 68W20, 91A12
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Computing the Shapley Value in Bankruptcy Games -llustrated by Rectified Linear Function Game-
by: Yamazaki, Shunta, et al.
Published: (2025)

Mechanism Design for Locating Facilities with Capacities with Insufficient Resources
by: Auricchio, Gennaro, et al.
Published: (2024)

Distributed Nash Equilibrium Seeking over Time-Varying Directed Communication Networks
by: Nguyen, Duong Thuy Anh, et al.
Published: (2022)

Equilibrium Computation in the Hotelling-Downs Model of Spatial Competition
by: Bhaskar, Umang, et al.
Published: (2024)

The Value of Recall in Extensive-Form Games
by: Berker, Ratip Emin, et al.
Published: (2024)

A Linear Programming Approach to Estimate the Core in Cooperative Games
by: Camacho, J, et al.
Published: (2025)

Facility Location Problem with Aleatory Agents
by: Auricchio, Gennaro, et al.
Published: (2024)

Time-Dependent Blackwell Approachability and Application to Absorbing Games
by: Kwon, Joon, et al.
Published: (2023)

A Characterization of Complexity in Public Goods Games
by: Gilboa, Matan
Published: (2023)

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
by: Tewolde, Emanuel, et al.
Published: (2024)

The Geometry of Cooperative Game Solutions: Stratified Egalitarian Shapley Values
by: Feys, Frank M. V.
Published: (2026)

Computing Game Symmetries and Equilibria That Respect Them
by: Tewolde, Emanuel, et al.
Published: (2025)

Facility Location Problems with Capacity Constraints: Two Facilities and Beyond
by: Auricchio, Gennaro, et al.
Published: (2024)

EF1 Allocations for Identical Trilean and Separable Single-Peaked Valuations
by: Bhaskar, Umang, et al.
Published: (2024)

The Power of Matching for Online Fractional Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

On the Approximate Core and Nucleon of Flow Games with Public Arcs
by: Liu, Pengfei, et al.
Published: (2024)

On marginal feature attributions of tree-based models
by: Filom, Khashayar, et al.
Published: (2023)

Algorithmic Cheap Talk
by: Babichenko, Yakov, et al.
Published: (2023)

A Tractable Class of Cooperative Games Defined by Directed Networks: Unanimity Decomposition and Shapley Value
by: Ryzák, David, et al.
Published: (2026)

Markov $α$-Potential Games
by: Guo, Xin, et al.
Published: (2023)

Multi-Player Resource-Sharing Games with Fair Reward Allocation
by: Wijewardena, Mevan, et al.
Published: (2024)

Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value
by: Lim, Tongseok
Published: (2021)

Cost-sharing in Parking Games
by: Elder, Jennifer, et al.
Published: (2023)

A Coopetition Index for Coalitions in Simple Games
by: Aleandri, Michele, et al.
Published: (2024)

Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
by: Caragiannis, Ioannis, et al.
Published: (2024)

A Partially Defined Game with Costs
by: Masuya, Satoshi
Published: (2024)

Efficient Equilibrium Computation in Symmetric First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2026)

A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights
by: Legacci, Davide, et al.
Published: (2024)

The core of housing markets from an agent's perspective: Is it worth sprucing up your home?
by: Schlotter, Ildikó, et al.
Published: (2021)

Nash Welfare in Additively Separable Hedonic Games
by: Pagano, Marta, et al.
Published: (2026)

A Complete Characterization of Convexity in Flow Games
by: Xiao, Han, et al.
Published: (2026)

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

Stability theory of game-theoretic group feature explanations for machine learning models
by: Miroshnikov, Alexey, et al.
Published: (2021)

Almost and Approximate EFX for Few Types of Agents
by: HV, Vishwa Prakash, et al.
Published: (2025)

Polynomial-Time Algorithms for Computing the Nucleolus: An Assessment
by: Meinhardt, Holger I.
Published: (2025)

Cohesion-Sensitive Power Indices: Representation Results for Banzhaf and Shapley Values
by: Pitz, Thomas, et al.
Published: (2026)

Winning Criteria for Open Games: A Game-Theoretic Approach to Prefix Codes
by: Kraizberg, Dean
Published: (2026)

A Parallelizable Approach for Characterizing NE in Zero-Sum Games After a Linear Number of Iterations of Gradient Descent
by: Kim, Taemin, et al.
Published: (2025)

Extending Games beyond the Finite Horizon
by: Sakahara, Kiri, et al.
Published: (2025)

Carbon Pricing in Traffic Networks
by: Griesbach, Svenja M., et al.
Published: (2025)