论文标题
灵活性会损害动态匹配系统性能
Flexibility can hurt dynamic matching system performance
论文作者
论文摘要
我们研究一般动态匹配模型的性能。该模型由连接的图定义，其中节点代表项目类别和项目之间的兼容性。不同类别的项目根据给定的概率分布一个人到达系统。到达后，根据第一次使用的纪律，将项目与兼容的项目匹配，并立即离开系统，而该项目与同一类的其他项目（如果有）中加入。我们表明，这样的模型可能表现出非直观的行为：通过在匹配图中添加新边缘来提高服务能力可能会导致平均人群较大。这类似于盲文悖论。我们首先考虑一个带有四个节点的准完整图，并提供了到达的概率分布的值，以便当我们添加边缘时，平均项目数量更大。然后，我们考虑一个任意的匹配图，并显示出足够的条件，以表明该悖论的存在或不存在。我们得出的结论是，当特定的独立集在饱和的情况下，即系统接近稳定性条件时，给出了匹配模型中对布拉斯悖论的类似物。
We study the performance of general dynamic matching models. This model is defined by a connected graph, where nodes represent the class of items and the edges the compatibilities between items. Items of different classes arrive one by one to the system according to a given probability distribution. Upon arrival, an item is matched with a compatible item according to the First Come First Served discipline and leave the system immediately, whereas it is enqueued with other items of the same class, if any. We show that such a model may exhibit a non intuitive behavior: increasing the services ability by adding new edges in the matching graph may lead to a larger average population. This is similar to a Braess paradox. We first consider a quasicomplete graph with four nodes and we provide values of the probability distribution of the arrivals such that when we add an edge the mean number of items is larger. Then, we consider an arbitrary matching graph and we show sufficient conditions for the existence or non-existence of this paradox. We conclude that the analog to the Braess paradox in matching models is given when specific independent sets are in saturation, i.e., the system is close to the stability condition.
