Extended Abstract

AAMAS 2022, May 9–13, 2022, Online

Capacitated Network Design Gameson a Generalized Fair Allocation Model
Extended Abstract
Tesshu Hanaka

Toshiyuki Hirose

Hirotaka Ono

Nagoya University
Nagoya, Japan
hanaka@nagoya-u.jp

KDDI CorporationTokyo, Japants-hirose@kddi.com

Nagoya University
Nagoya, Japan
ono@nagoya-u.jp

ABSTRACTcan model many real-world situations for sharing the cost of adesigned network, such as a virtual overlay, multicast tree, or othersub-network of the Internet [7].
In the previous studies, the link cost is fairly shared, whichmeans that the total cost paid for a link does not vary even if any
number of agents use it. However, sharing resources yields more orless extra costs (overheads) in realistic cost-sharing situations; byincreasing the number of users, extra commission fees are charged,
service degradation occurs, and so on. The existing models are not
powerful enough to handle such situations.
In this paper, we model the more realistic scenario of CSCSG bygeneralizing cost-sharing functions. The arguments on the model
do not depend on specific cost-sharing functions, and are applicablefor a wide class of cost-sharing functions satisfying certain naturalproperties. Let pe and c e be the cost and capacity associated withlink (edge) e, respectively. Suppose that x agents use link e, wherex ≤ c e . In our model, a cost-sharing function fe (x) for link e is(1) non-increasing with respect to x, (2) fe (x) ≥ pe /x, and (3)fe (1) = pe . Condition (1) is a natural property in cost-sharing
models, (2) represents the situation that if two or more agents use
a link, overheads may arises, and (3) represents that no overheadarises when only an agent uses the edge. We emphasize that thissignificant generalization does not restrict any nature of fair costsharing. We believe that any natural fair cost-sharing function isin this scheme. Note that the cost-sharing function in the previous
studies [5–7] is fe (x) = pe /x, which clearly satisfies (1), (2) and (3).
We investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of the game. A pure Nash equilibrium (we simply say
Nash equilibrium) is a state where no agent can reduce its costby changing the path that he/she currently chooses. Such a Nashequilibrium does not always exist in a general game, but it does in
CSCSG. Thus, a major interest of analyzing games is to measure
a goodness of Nash equilibrium. As social goodness measures, weconsider two criteria. One is sum-cost criterion, where the social
cost function is defined as the summation of the costs paid by all
the agents, and the other is max-cost criterion, where it is definedas the maximum among the costs paid by all agents. Both PoA andPoS are well used measures for evaluating the efficiency of Nashequilibria of games. The PoA is the ratio between the cost of theworst Nash equilibrium and the social optimum, whereas the PoS
refers to the ratio between the cost of the best Nash equilibrium
and the social optimum.

The cost-sharing connection game is a variant of routing games on
a network. In this model, given a directed graph with edge costs
and capacities, each agent wants to construct a path from a source
to a sink with low cost. The cost of each edge is shared by theusers based on a cost-sharing function. One of simple cost-sharing
functions is defined as the cost divided by the number of users. It
models an ideal setting, where no overhead arises when people
share things, though it might be quite rare in real life. In this paper,
we model more realistic scenarios of cost-sharing connection games
by generalizing the cost-sharing function. The arguments do notdepend on specific cost-sharing functions and are applicable fora class of all natural cost-sharing scenarios, which include equal
divisions with any natural functional overheads. We show thatmany bounds of the Price of Anarchy and the Price of Stability
under sum-cost and max-cost criteria inherit the no-overhead case.

KEYWORDS
Capacitated network design games, Cost-sharing games, Nash equilibrium, Price of anarchy, Price of stability
ACM Reference Format:
Tesshu Hanaka, Toshiyuki Hirose, and Hirotaka Ono. 2022. Capacitated
Network Design Games on a Generalized Fair Allocation Model: ExtendedAbstract. In Proc. of the 21st International Conference on Autonomous Agentsand Multiagent Systems (AAMAS 2022), Online, May 9–13, 2022, IFAAMAS,
2 pages.

1INTRODUCTION

The capacitated symmetric cost-sharing connection game (CSCSG)
is a network design model of multiple agents’ sharing costs toconstruct a network infrastructure for connecting a given sourcesink pair. In the game, a possible network structure is given, but
actual links are not built yet. For example, imagine to build anoverlay network structure on a physical network. Each agent wants
to construct a path from source s to sink t. To construct a path,each agent builds links by paying the costs associated with them.
Two or more agents can commonly use a link if the number ofagents is within the capacity associated with the link, and in sucha case, the cost of the link is fairly shared by the agents that use it.
Thus, the more agents use a common link, the less cost of the linkthey pay. Under this setting, each agent selfishly chooses a path
to construct so that they minimize their costs to pay. The CSCSG

In this extended abstract, we briefly summarize our contribution
and related work. For the detailed proofs, see the full paper at [9].

Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS 2022), P. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.), May 9–13,2022, Online. © 2022 International Foundation for Autonomous Agents and Multiagent
Systems (www.ifaamas.org). All rights reserved.

1616

Extended Abstract

AAMAS 2022, May 9–13, 2022, Online

Table 1: The summary of PoA and PoS of CSCSG under sum-cost and max-cost. Our results are marked with ∗ .
parallel-link
Uncapacitated
Sum-cost

CapacitatedCapacitated+General cost
UncapacitatedMax-cost

CapacitatedCapacitated+General cost2

series-parallel DAG Generaln [1]1 (trivial)n (UB [7], LB [1])unbounded∗
log n [7]1n∗
unbounded∗
UB∗ : n, LB∗ : n + 1/n − 1

PoA
PoS
PoA
PoS
PoA
PoS
PoA
PoS
PoA
PoS
PoA
PoS

n [1]
1 (trivial)n [7]unbounded∗n (UB [5], LB [7]1 )n∗unbounded∗n∗

OUR CONTRIBUTION

PoS under both sum-cost and max-cost for several graph classes
except the PoS under max-cost for general graphs. Note that theirresults hold only for symmetric CSG. Erlebach and Radoja fill thegap of the exception for CSG under max-cost [5]. Feldman and Ofirinvestigate strong equilibria for the capacitated version of CSG [6].
There are vast applications of CSG. A natural application isthe decision-making in sharing economy [1–3]. Radko and Laclau
mention the relationship between CSG and machine learning [10].
The previous studies for CSCSG do not consider any overhead, butsharing some resource (or tasks) yields some overhead in general.
In fact, controlling overheads to share tasks is a major issue ingrid/parallel computing fields [8].

In this paper, we investigate the PoA and the PoS of CSCSG undera generalized cost-sharing scheme as explained above. We address
two criteria of social cost: sum-cost and max-cost. As for the sumcost case, we first show that PoA is unbounded even on directed
acyclic graphs (DAGs). On the other hand, on series-parallel graphs(SP graphs), we show that PoA under sum-cost is at most n and itis tight, that is, there is an example whose PoA is n. For PoS, weshow that it is at most n and there is an example whose PoS undersum-cost is n + 1/n − 1. This gives the difference from the previous
study, which shows that PoS is at most log n and it is tight withordinary fair cost-sharing functions [7].
Next, we give the results on the max-cost. As with the sum-cost,
we show that PoA under max-cost is unbounded on directed acyclicgraphs. On SP graphs, we prove that PoA is at most n and it is tight.
We also show that PoS is at most n and it is tight. These results
imply that the significant generalization does not affect PoA andPoS under max-cost. Table 1 summarizes these results.
We then discuss the capacitated asymmetric cost-sharing connection game (CACSG), where agents have different source andsink nodes. We show that the lower bounds of PoA and PoS ofCSCSG hold for the asymmetric case, while PoS under sum-costand max-cost are at most n and n 2 , respectively.
Remark that we consider the games on directed graphs, but all
the results except for directed acyclic cases can be easily modified
to undirected cases. In the sense, our results are generic, which
includes the results of [5, 7].

3ACKNOWLEDGMENTS
This work is partially supported by JSPS KAKENHI Grant Numbers
JP17K19960, JP17H01698, JP19K21537, JP20H05967, JP21K17707,
JP21H05852, and JP21K19765.

REFERENCES[1] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler,
and Tim Roughgarden. 2008. The Price of Stability for Network Design with Fair
Cost Allocation. SIAM J. Comput. 38, 4 (2008), 1602–1623.
[2] Chi-Kin Chau and Khaled M. Elbassioni. 2018. Quantifying Inefficiency of Fair
Cost-Sharing Mechanisms for Sharing Economy. IEEE Transactions on Control ofNetwork Systems 5, 4 (2018), 1809–1818.
[3] Sid Chi-Kin Chau, Jiajia Xu, Wilson Bow, and Khaled M. Elbassioni. 2019. Peer-toPeer Energy Sharing: Effective Cost-Sharing Mechanisms and Social Efficiency. InProceedings of the Tenth ACM International Conference on Future Energy Systems.
215–225.
[4] Amir Epstein, Michal Feldman, and Yishay Mansour. 2009. Strong equilibriumin cost sharing connection games. Games and Economic Behavior 67, 1 (2009),
51–68.
[5] Thomas Erlebach and Matthew Radoja. 2015. Further Results on Capacitated
Network Design Games. In Proceedings of the 8th Symposium on Algorithmic
Game Theory (SAGT 2015). 57–68.
[6] Michal Feldman and Geri Ofir. 2016. Do Capacity Constraints Constrain Coalitions? ACM Transactions on Economics and Computation 5, 1 (2016), No.8.
[7] Michal Feldman and Tom Ron. 2015. Capacitated Network Design Games. Theoryof Computing Systems 57 (2015), 576–597.
[8] Alfredo Goldman and Carlos Queiroz. 2004. A model for parallel job scheduling on
dynamical computer Grids. Concurrency and Computation: Practice and Experience16, 5 (2004), 461–468.
[9] Tesshu Hanaka, Toshiyuki Hirose, and Hirotaka Ono. 2021. Capacitated Network
Design Games on a Generalized Fair Allocation Model. arXiv:2107.03040 [cs.GT][10] Ievgen Redko and Charlotte Laclau. 2019. On Fair Cost Sharing Games in Machine
Learning. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence(AAAI 2019). 4790–4797.

RELATED WORKThe cost-sharing connection game (CSG) is firstly introduced byAnshelevich et al. [1]. In the paper, they give the tight bounds ofPoA and PoS under sum-cost, which are n and 1, respectively, foruncapacitated CSG. They also show that the PoS under sum-costof asymmetric CSG, where agents have different source and sinknodes, can be bounded by log n. Epstein, Feldman and Mansour
study the strong equilibria of cost-sharing connection games [4].
Feldman and Ron [7] introduce a capacitated variant of CSGs
on undirected graphs, and they give the tight bounds of PoA and1 In [7], Feldman and Ron gave the lower bounds only for undirected parallel-linkgraphs. They can be easily modified to directed parallel link graphs.

1617