We consider a stochastic matching model with a general compatibility graph with self-loops on every node and a random matching policy. We consider the discrete time Markov chain associated with such a model where arrivals of items are independently and identically distributed. Due to the self-loops in the compatibility graph, the states of this chain are exactly the independent sets of the graph. We prove that this chain is ordinary lumpable if the automorphism group of the compatibility graph is non-trivial. Additionally, we demonstrate how to construct the partition associated with strong aggregation based on certain subgroups of the automorphism group. This approach can efficiently reduce the size of the state space which could be as large as the exponential of the number of nodes in the compatibility graph before the aggregation. Finally, we illustrate this methodology with examples based on simple compatibility graphs, such as rings and the group of rotations.

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

Strong Aggregation in the Stochastic Matching Model with Random Discipline

  • Jean-Michel Fourneau,
  • Moyi Yang

摘要

We consider a stochastic matching model with a general compatibility graph with self-loops on every node and a random matching policy. We consider the discrete time Markov chain associated with such a model where arrivals of items are independently and identically distributed. Due to the self-loops in the compatibility graph, the states of this chain are exactly the independent sets of the graph. We prove that this chain is ordinary lumpable if the automorphism group of the compatibility graph is non-trivial. Additionally, we demonstrate how to construct the partition associated with strong aggregation based on certain subgroups of the automorphism group. This approach can efficiently reduce the size of the state space which could be as large as the exponential of the number of nodes in the compatibility graph before the aggregation. Finally, we illustrate this methodology with examples based on simple compatibility graphs, such as rings and the group of rotations.