On Equilibria for ADM Minimization Games

On Equilibria for ADM Minimization Games

0.00 Avg rating0 Votes
Article ID: iaor2012675
Volume: 63
Issue: 1
Start Page Number: 246
End Page Number: 273
Publication Date: Jun 2012
Journal: Algorithmica
Authors: ,
Keywords: optimization, graphs
Abstract:

In the ADM minimization problem the input is a set of arcs along a directed ring. The input arcs need to be partitioned into non‐overlapping chains and cycles so as to minimize the total number of endpoints, where a k‐arc cycle contributes k endpoints and a k‐arc chain contains k+1 endpoints. We study ADM minimization problem both as non‐cooperative and cooperative games. In these games each arc corresponds to a player, and the players share the cost of the ADM switches. We consider two cost allocation models, a model which was considered by Flammini et al., and a new cost allocation model, which is inspired by congestion games. We compare the price of anarchy and price of stability in the two cost allocation models, as well as the strong price of anarchy and the strong price of stability.

Reviews

Required fields are marked *. Your email address will not be published.