Air pollution control is an ultimate task for the Chinese government to undertake. The air pollution control requires the joint efforts from various provinces in China, in the process of which the provincial interests will be jeopardized and various conflicts of interests will occur among provinces. A twolevel hierarchical graph model is developed effectively to help provinces solve these conflicts in the pursuit of their own interests. The research shows that the provinces generating air pollution are not motivated in the joined efforts with other provinces while the pollution affected provinces want to take a free ride, expecting other provinces to take actions to control air pollution. The Chinese government should bear the responsibility of taking more stringent measures and establishing a collaborative mechanism among provinces at multilevels to control air pollution more effectively.