@DirkLiebhold thanks for your prompt reply! It is inspiring that such reduction is not hard. But embarrassingly, I am new to combinatorial optimization. I don't know how to reduce a deterministic problem to a random one. It is highly appreciated if you could recommend something I can read and learn about this technique.

@zen It is interesting to know a new problem that my problem could potentially be reduced to. Thanks! But in my existing work I reduce my problem to a hypergraph strong coloring problem. Please kindly refer to my updated problem - clarified and concrete.

@DirkLiebhold I totally agree with you. But my reviewers were not happy. They explicitly ask what is the hardness if there are nonzero losses.

@RobinHouston thanks a lot for your attention and kindness to a newbie. Please kindly refer to my clarified and concrete problem.