Language：English  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Association for Computing Machinery (ACM)  

In this study, we propose a polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual rationality, and Pareto optimality, and works with polymatroidal environments. A notable feature of this mechanism for the indivisible setting is that the entire procedure can be conducted in time polynomial of the number of buyers and goods. Moreover, we show additional efficiency guarantees, recently established by Sato for the divisible setting: the liquid welfare (LW) of our mechanism achieves more than half of the optimal LW, and the social welfare is more than the optimal LW.

DOI： 10.1145/3708506

researchmap

Other Link： https://dl.acm.org/doi/pdf/10.1145/3708506

Language：English   Publishing type：Part of collection (book)   Publisher：Springer Nature Switzerland  

DOI： 10.1007/978-3-031-48974-7_21

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Institute for Operations Research and the Management Sciences (INFORMS)  

In this paper, we present a new model and mechanisms for auctions in two-sided markets of buyers and sellers, where budget constraints are imposed on buyers. Our model incorporates polymatroidal environments and is applicable to a variety of models that include multiunit auctions, matching markets, and reservation exchange markets. Our mechanisms are built on the polymatroidal network flow model by Lawler and Martel. Additionally, they feature nice properties such as the incentive compatibility of buyers, individual rationality, Pareto optimality, and strong budget balance. The first mechanism is a two-sided generalization of the polyhedral clinching auction by Goel et al. for one-sided markets. The second mechanism is a reduce-to-recover algorithm that reduces the market to be one-sided, applies the polyhedral clinching auction by Goel et al., and lifts the resulting allocation to the original two-sided market via the polymatroidal network flow. Both mechanisms are implemented by polymatroid algorithms. We demonstrate how our framework is applied to the Internet display advertisement auctions.

DOI： 10.1287/moor.2021.1124

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.spa.2017.07.014

researchmap

Language：Japanese   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap