As the number of agents increases rapidly on the Internet, discovering appropriate service agents with required capabilities for request agents becomes a crucial issue in multiagent systems. Two major discovering approaches have been developed: centralized matchmaking approaches and distributed bidding approaches. However, the former approaches may suffer the problem of middle agent overload and can not reflect the dynamic characteristic of agent capabilities, while the later has the problems of the overhead for maintaining contact lists of service agents in each request agent and sending ineffective CFP messages to non-qualified service agents. To address the above problems, in this paper, we propose a CNP-based bidding mechanism based on Possibilistic Petri Nets that facilitates request agents to find preferred service agents. Moreover, our mechanism provides more flexible match that not only supports exact match but also takes the degree of satisfaction into account.