Coalition　formation　is　a　key　topic　on　multi-agent　systems.　As　the　number　of　coalition　structures　is　large,　it　is　not　allowed　to　search　the　whole　coalition　structure　tree　exhaustively.　So,　a　partial　search　which　is　guaranteed　to　be　within　a　bound　from　optimum　is　interested.　A　large　number　of　previous　work　has　been　done　to　find　the　optimal　coalition　structure　in　Characteristic　Function　Games　(CFGs),　where　the　value　of　a　coalition　was　independent　from　co-existing　coalitions　in　the　system.　However,　usually　it　is　not　appropriate　to　the　real　situation　because　an　agent＇s　effectiveness　may　change　from　one　coalition　structure　to　another.　Thus,　much　more　general　Partition　Function　Games　(PFGs)　have　to　be　applied.　In　this　context,　we　develop　an　algorithm　based　on　partition　cardinality　structure,　which　consider　the　coalition　value　in　PFGs.　We　use　different　strategies　in　two　classes　of　PFGs,　and　improve　the　bound　with　further　search.　©2010　IEEE.