Academic Journal
Identifying optimal strategies in kidney exchange games is Σ2p-complete.
| العنوان: | Identifying optimal strategies in kidney exchange games is Σ2p-complete. |
|---|---|
| المؤلفون: | Smeulders, B.1 (AUTHOR) b.smeulders@tue.nl, Blom, D. A. M. P.1 (AUTHOR), Spieksma, F. C. R.1 (AUTHOR) |
| المصدر: | Mathematical Programming. Jan2024, Vol. 203 Issue 1/2, p347-368. 22p. |
| مصطلحات موضوعية: | KIDNEY exchange, PUBLIC hospitals, BLOOD group incompatibility, GAMES, POLYNOMIAL time algorithms |
| مستخلص: | In Kidney Exchange Games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of recipients under its control. Then, the question becomes: which recipient-donor pairs to submit to the collaborative effort? We model this situation by introducing the Stackelberg Kidney Exchange Game, a game where an agent, having perfect information, needs to identify a strategy, i.e., to decide which recipient-donor pairs to submit. We show that even in this simplified setting, identifying an optimal strategy is Σ 2 p -complete, whenever we allow exchanges involving at most a fixed number K ≥ 3 pairs. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| قاعدة البيانات: | Business Source Index |
| ResultId |
1 |
|---|---|
| Header |
bsx Business Source Index 175361013 1360 6 Academic Journal academicJournal 1360.19689941406 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=bsx&AN=175361013&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
|
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Identifying optimal strategies in kidney exchange games is Σ2p-complete.
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Smeulders%2C+B%2E%22">Smeulders, B.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> b.smeulders@tue.nl</i><br /><searchLink fieldCode="AR" term="%22Blom%2C+D%2E+A%2E+M%2E+P%2E%22">Blom, D. A. M. P.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Spieksma%2C+F%2E+C%2E+R%2E%22">Spieksma, F. C. R.</searchLink><relatesTo>1</relatesTo> (AUTHOR) ) Array ( [Name] => TitleSource [Label] => Source [Group] => Src [Data] => <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. Jan2024, Vol. 203 Issue 1/2, p347-368. 22p. ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22KIDNEY+exchange%22">KIDNEY exchange</searchLink><br /><searchLink fieldCode="DE" term="%22PUBLIC+hospitals%22">PUBLIC hospitals</searchLink><br /><searchLink fieldCode="DE" term="%22BLOOD+group+incompatibility%22">BLOOD group incompatibility</searchLink><br /><searchLink fieldCode="DE" term="%22GAMES%22">GAMES</searchLink><br /><searchLink fieldCode="DE" term="%22POLYNOMIAL+time+algorithms%22">POLYNOMIAL time algorithms</searchLink> ) Array ( [Name] => Abstract [Label] => Abstract [Group] => Ab [Data] => In Kidney Exchange Games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of recipients under its control. Then, the question becomes: which recipient-donor pairs to submit to the collaborative effort? We model this situation by introducing the Stackelberg Kidney Exchange Game, a game where an agent, having perfect information, needs to identify a strategy, i.e., to decide which recipient-donor pairs to submit. We show that even in this simplified setting, identifying an optimal strategy is Σ 2 p -complete, whenever we allow exchanges involving at most a fixed number K ≥ 3 pairs. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time. [ABSTRACT FROM AUTHOR] ) Array ( [Name] => AbstractSuppliedCopyright [Label] => [Group] => Ab [Data] => <i>Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Identifiers] => Array
(
[0] => Array
(
[Type] => doi
[Value] => 10.1007/s10107-021-01748-6
)
)
[Languages] => Array
(
[0] => Array
(
[Code] => eng
[Text] => English
)
)
[PhysicalDescription] => Array
(
[Pagination] => Array
(
[PageCount] => 22
[StartPage] => 347
)
)
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => KIDNEY exchange
[Type] => general
)
[1] => Array
(
[SubjectFull] => PUBLIC hospitals
[Type] => general
)
[2] => Array
(
[SubjectFull] => BLOOD group incompatibility
[Type] => general
)
[3] => Array
(
[SubjectFull] => GAMES
[Type] => general
)
[4] => Array
(
[SubjectFull] => POLYNOMIAL time algorithms
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Identifying optimal strategies in kidney exchange games is Σ2p-complete.
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Smeulders, B.
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Blom, D. A. M. P.
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Spieksma, F. C. R.
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 01
[M] => 01
[Text] => Jan2024
[Type] => published
[Y] => 2024
)
)
[Identifiers] => Array
(
[0] => Array
(
[Type] => issn-print
[Value] => 00255610
)
)
[Numbering] => Array
(
[0] => Array
(
[Type] => volume
[Value] => 203
)
[1] => Array
(
[Type] => issue
[Value] => 1/2
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Mathematical Programming
[Type] => main
)
)
)
)
)
)
)
|
| IllustrationInfo |