Abstract
We consider the assignment problem, where n agents have
to be matched to n items. Each agent has a preference order over the
items. In the serial dictatorship (SD) mechanism the agents act in a
particular order and pick their most preferred available item when it is
their turn to act. Applying SD using a uniformly random permutation
as agent ordering results in the well-known random serial dictatorship
(RSD) mechanism. Accurate estimates of the (expected) efficiency of its
outcome can be used to assess whether RSD is attractive compared to
other mechanisms. In this paper, we explore whether such estimates are
possible by sampling a (hopefully) small number of agent orderings and
applying SD using them. We consider a value setting in which agents
have values for the items as well as a metric cost setting where agents
and items are assumed to be points in a metric space, and the cost
of an agent for an item is equal to the distance of the corresponding
points. We show that a (relatively) small number of samples is enough
to approximate the expected social welfare of RSD in the value setting
and its expected social cost in the metric cost setting despite the #P-hardness
of the corresponding exact computation problems.
to be matched to n items. Each agent has a preference order over the
items. In the serial dictatorship (SD) mechanism the agents act in a
particular order and pick their most preferred available item when it is
their turn to act. Applying SD using a uniformly random permutation
as agent ordering results in the well-known random serial dictatorship
(RSD) mechanism. Accurate estimates of the (expected) efficiency of its
outcome can be used to assess whether RSD is attractive compared to
other mechanisms. In this paper, we explore whether such estimates are
possible by sampling a (hopefully) small number of agent orderings and
applying SD using them. We consider a value setting in which agents
have values for the items as well as a metric cost setting where agents
and items are assumed to be points in a metric space, and the cost
of an agent for an item is equal to the distance of the corresponding
points. We show that a (relatively) small number of samples is enough
to approximate the expected social welfare of RSD in the value setting
and its expected social cost in the metric cost setting despite the #P-hardness
of the corresponding exact computation problems.
| Originalsprog | Engelsk |
|---|---|
| Titel | Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings |
| Redaktører | Guido Schäfer, Carmine Ventre |
| Antal sider | 18 |
| Udgivelsessted | Cham |
| Forlag | Springer |
| Publikationsdato | sep. 2024 |
| Sider | 184–201 |
| ISBN (Trykt) | 9783031710322 |
| DOI | |
| Status | Udgivet - sep. 2024 |
| Navn | Lecture Notes in Computer Science |
|---|---|
| Vol/bind | 15156 |
| ISSN | 0302-9743 |