IEICE TRANSACTIONS on Information
Bounded Approximate Payoff Division for MC-nets Games
Summary :
To the best of our knowledge, there have been very few work on computational algorithms for the core or its variants in MC-nets games. One exception is the work by [Hirayama, et.al., 2014], where a constraint generation algorithm has been proposed to compute a payoff vector belonging to the least core. In this paper, we generalize this algorithm into the one for finding a payoff vector belonging to ϵ-core with pre-specified bound guarantee. The underlying idea behind this algorithm is basically the same as the previous one, but one key contribution is to give a clearer view on the pricing problem leading to the development of our new general algorithm. We showed that this new algorithm was correct and never be trapped in an infinite loop. Furthermore, we empirically demonstrated that this algorithm really presented a trade-off between solution quality and computational costs on some benchmark instances.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.12 pp.2085-2091
- Publication Date
- 2022/12/01
- Publicized
- 2022/09/13
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022EDP7039
- Type of Manuscript
- PAPER
- Category
- Information Network
Authors
Katsutoshi HIRAYAMA
Kobe University
Tenda OKIMOTO
Kobe University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Katsutoshi HIRAYAMA, Tenda OKIMOTO, "Bounded Approximate Payoff Division for MC-nets Games" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 12, pp. 2085-2091, December 2022, doi: 10.1587/transinf.2022EDP7039.
Abstract: To the best of our knowledge, there have been very few work on computational algorithms for the core or its variants in MC-nets games. One exception is the work by [Hirayama, et.al., 2014], where a constraint generation algorithm has been proposed to compute a payoff vector belonging to the least core. In this paper, we generalize this algorithm into the one for finding a payoff vector belonging to ϵ-core with pre-specified bound guarantee. The underlying idea behind this algorithm is basically the same as the previous one, but one key contribution is to give a clearer view on the pricing problem leading to the development of our new general algorithm. We showed that this new algorithm was correct and never be trapped in an infinite loop. Furthermore, we empirically demonstrated that this algorithm really presented a trade-off between solution quality and computational costs on some benchmark instances.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7039/_p
Copy
@ARTICLE{e105-d_12_2085,
author={Katsutoshi HIRAYAMA, Tenda OKIMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Bounded Approximate Payoff Division for MC-nets Games},
year={2022},
volume={E105-D},
number={12},
pages={2085-2091},
abstract={To the best of our knowledge, there have been very few work on computational algorithms for the core or its variants in MC-nets games. One exception is the work by [Hirayama, et.al., 2014], where a constraint generation algorithm has been proposed to compute a payoff vector belonging to the least core. In this paper, we generalize this algorithm into the one for finding a payoff vector belonging to ϵ-core with pre-specified bound guarantee. The underlying idea behind this algorithm is basically the same as the previous one, but one key contribution is to give a clearer view on the pricing problem leading to the development of our new general algorithm. We showed that this new algorithm was correct and never be trapped in an infinite loop. Furthermore, we empirically demonstrated that this algorithm really presented a trade-off between solution quality and computational costs on some benchmark instances.},
keywords={},
doi={10.1587/transinf.2022EDP7039},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Bounded Approximate Payoff Division for MC-nets Games
T2 - IEICE TRANSACTIONS on Information
SP - 2085
EP - 2091
AU - Katsutoshi HIRAYAMA
AU - Tenda OKIMOTO
PY - 2022
DO - 10.1587/transinf.2022EDP7039
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2022
AB - To the best of our knowledge, there have been very few work on computational algorithms for the core or its variants in MC-nets games. One exception is the work by [Hirayama, et.al., 2014], where a constraint generation algorithm has been proposed to compute a payoff vector belonging to the least core. In this paper, we generalize this algorithm into the one for finding a payoff vector belonging to ϵ-core with pre-specified bound guarantee. The underlying idea behind this algorithm is basically the same as the previous one, but one key contribution is to give a clearer view on the pricing problem leading to the development of our new general algorithm. We showed that this new algorithm was correct and never be trapped in an infinite loop. Furthermore, we empirically demonstrated that this algorithm really presented a trade-off between solution quality and computational costs on some benchmark instances.
ER -
English
