Polynomially Computable Bounds for the Probability of the Union of Events

We consider the problem of finding upper and lower bounds for the probability of the union of events when the probabilities of the single events and the probabilities of the intersections of up to m events are given. It is known that the best possible bounds can be obtained by solving linear programming problems with a number of variables that is exponential in the number of events. Because of their size and structure, these large linear programs are known to be very hard to solve. In the literature simpler, polynomially sized aggregations are considered and numerous closed form or polynomially computable bounds are derived from those. We present here a new approach that introduces additional constraints to the dual linear programming problems in such a way that those become polynomially solvable. By using different sets of additional constraints, we introduce three new classes of polynomially computable upper and lower bounds. We show that they dominate almost all efficiently computable bounds known in the literature. Furthermore, by characterizing the vertices of two new classes of polyhedra, we can show that in two cases our bounds coincide with classical bounds, proving new extremal properties for those well-known bounds. Finally, we provide extensive numerical results comparing the average tightness of the various bounds on a large number of instances.