The Library
Sequential blocked matching
Tools
Bishop, Nicholas, Chan, Hau, Mandal, Debmalya and Tran-Thanh, Long (2022) Sequential blocked matching. In: Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22), Virtual conference, 22 Feb- 01 Mar 2022. Published in: Proceedings of the AAAI Conference on Artificial Intelligence, 36 (5). pp. 4834-4842. doi:10.1609/aaai.v36i5.20411
|
PDF
WRAP-Sequential-blocked-matching-2022.pdf - Accepted Version - Requires a PDF viewer. Download (477Kb) | Preview |
Official URL: https://doi.org/10.1609/aaai.v36i5.20411
Abstract
We consider a sequential blocked matching (SBM) model where strategic agents repeatedly report ordinal preferences over a set of services to a central planner. The planner's goal is to elicit agents' true preferences and design a policy that matches services to agents in order to maximize the expected social welfare with the added constraint that each matched service can be blocked or unavailable for a number of time periods. Naturally, SBM models the repeated allocation of reusable services to a set of agents where each allocated service becomes unavailable for a fixed duration. We first consider the offline SBM setting, where the strategic agents are aware of their true preferences. We measure the performance of any policy by distortion, the worst-case multiplicative approximation guaranteed by any policy. For the setting with s services, we establish lower bounds of Ω(s) and Ω(√s) on the distortions of any deterministic and randomised mechanisms, respectively. We complement these results by providing approximately truthful, measured by incentive ratio, deterministic and randomised policies based on random serial dictatorship which match our lower bounds. Our results show that there is a significant improvement if one considers the class of randomised policies. Finally, we consider the online SBM setting with bandit feedback where each agent is initially unaware of her true preferences, and the planner must facilitate each agent in the learning of their preferences through the matching of services over time. We design an approximately truthful mechanism based on the explore-then-commit paradigm, which achieves logarithmic dynamic approximate regret.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Artificial intelligence , Neural networks (Computer science), Machine learning | ||||||||
Journal or Publication Title: | Proceedings of the AAAI Conference on Artificial Intelligence | ||||||||
Publisher: | AAAI | ||||||||
Official Date: | 28 June 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 36 | ||||||||
Number: | 5 | ||||||||
Page Range: | pp. 4834-4842 | ||||||||
DOI: | 10.1609/aaai.v36i5.20411 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Copyright Holders: | Copyright © 2022, Association for the Advancement of Artificial Intelligence | ||||||||
Date of first compliant deposit: | 8 February 2022 | ||||||||
Date of first compliant Open Access: | 22 July 2022 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | Virtual conference | ||||||||
Date(s) of Event: | 22 Feb- 01 Mar 2022 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year