Convexity of b-matching Games
Authors: Soh Kumabe, Takanori Maehara
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this study, we give a necessary and sufficient condition of the convexity of a b-matching game (Lemma 3.6). Based on this characterization, we propose a polynomial-time algorithm to check the convexity of a given b-matching game. Formally, the following is our main theorem. Theorem 1.1. There is an O(n log n + mα(n)) time algorithm to check whether a given b-matching game is convex, where α is the inverse Ackermann function1. As an application of our characterization, we derive a polynomial-time algorithm to compute the Shapley value of a convex b-matching game. |
| Researcher Affiliation | Academia | Soh Kumabe1,2 and Takanori Maehara2 1The University of Tokyo 2RIKEN AIP |
| Pseudocode | Yes | Algorithm 1 Checking the supermodularity of ν |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | This paper is theoretical and does not use or analyze any datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and focuses on mathematical proofs and algorithm complexity; therefore, it does not describe any specific hardware used for experiments. |
| Software Dependencies | No | This paper is theoretical and does not mention any specific software dependencies with version numbers required for implementation or reproduction. |
| Experiment Setup | No | This paper is theoretical and does not include details on experimental setup, hyperparameters, or training configurations. |