A Matching model describes the waiting times suffered by items before they match with other items and disappear immediately without service. The matching relation is described by a compatibility graph. It is an easy representation of multiple types synchronizations between items. When we add an edge in the compatibility graph, one expects that the expected total number of items decreases. Unexpectedly this is not always true and there is a performance paradox. Extending previous results, we show new matching models with performance paradoxes which seems to be more frequent than one can expect.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Performance Paradoxes in Matching Systems are not that Rare

  • A. Busic,
  • J. M. Fourneau,
  • A. Lunven,
  • S. Li

摘要

A Matching model describes the waiting times suffered by items before they match with other items and disappear immediately without service. The matching relation is described by a compatibility graph. It is an easy representation of multiple types synchronizations between items. When we add an edge in the compatibility graph, one expects that the expected total number of items decreases. Unexpectedly this is not always true and there is a performance paradox. Extending previous results, we show new matching models with performance paradoxes which seems to be more frequent than one can expect.