Connected Trading Cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909492258537472 |
|---|---|
| author | Song, Xinwei Yang, Tianyi Zhao, Dengji |
| author_facet | Song, Xinwei Yang, Tianyi Zhao, Dengji |
| contents | Incentivizing the existing participants to invite new participants to join an auction, matching or cooperative game have been extensively studied recently. One common challenge to design such incentive in these games is that the invitees and inviters are competitors. To have such an incentive, we normally have to sacrifice some of the traditional properties. Especially, in a housing market (one kind of one-sided matching), we cannot maintain the traditional stability and optimality. The previous studies proposed some new matching mechanisms to have the invitation incentive (part of the incentive compatibility), but did not have any guarantee on stability and optimality.
In this paper, we propose new notions of stability and optimality which are achievable with incentive compatibility. We weaken stability and optimality on a special structure (complete components) on networks. We first prove that the weakened notions are the best we can achieve with incentive compatibility. Then, we propose three mechanisms (Swap With Neighbors, Leave and Share, and Connected Trading Cycles) to satisfy the desirable properties. Connected Trading Cycles is the first mechanism to satisfy the best stability and optimality compatible with incentive compatibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09759 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Connected Trading Cycles Song, Xinwei Yang, Tianyi Zhao, Dengji Computer Science and Game Theory Incentivizing the existing participants to invite new participants to join an auction, matching or cooperative game have been extensively studied recently. One common challenge to design such incentive in these games is that the invitees and inviters are competitors. To have such an incentive, we normally have to sacrifice some of the traditional properties. Especially, in a housing market (one kind of one-sided matching), we cannot maintain the traditional stability and optimality. The previous studies proposed some new matching mechanisms to have the invitation incentive (part of the incentive compatibility), but did not have any guarantee on stability and optimality. In this paper, we propose new notions of stability and optimality which are achievable with incentive compatibility. We weaken stability and optimality on a special structure (complete components) on networks. We first prove that the weakened notions are the best we can achieve with incentive compatibility. Then, we propose three mechanisms (Swap With Neighbors, Leave and Share, and Connected Trading Cycles) to satisfy the desirable properties. Connected Trading Cycles is the first mechanism to satisfy the best stability and optimality compatible with incentive compatibility. |
| title | Connected Trading Cycles |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2303.09759 |