Publication Type

Conference Proceeding Article



Publication Date



The relations between unobserved events and observed outcomes in partiallyidentified models can be characterized by a bipartite graph. We estimate the probabilitymeasure on the events given observations of the outcomes based on the graph. The feasibleset of the probability measure on the events is defined by a set of linear inequality constraints.The number of inequalities is often much larger than the number of observations. Theset of irredundant inequalities is known as the Core Determining Class. We propose analgorithm that explores the structure of the graph to construct the exact Core DeterminingClass when data noise is not taken into consideration. We prove that if the graph and themeasure on the observed outcomes are non-degenerate, the Core Determining Class doesnot depend on the probability measure of the outcomes but only on the structure of thegraph. For more general problem of selecting linear inequalities under noise, we investigatethe sparse assumptions on the full set of inequalities, i.e., only a few inequalities are trulybinding. We show that the sparse assumptions are equivalent to certain sparse conditionson the dual problems. We propose a procedure similar to the Dantzig Selector to select thetruly informative constraints. We analyze the properties of the procedure and show thatthe feasible set defined by the selected constraints is a nearly sharp estimator of the truefeasible set. Under our sparse assumptions, we prove that such a procedure can significantlyreduce the number of inequalities without throwing away too much information. We applythe procedure to the Core Determining Class problem and obtain a stronger theorem takingadvantage of the structure of the bipartite graph. We design Monte-Carlo experiments todemonstrate the good performance of our selection procedure, while the traditional CHTinference is difficult to apply.


Core Determining Class, Sparse Model, Linear Programming, Inequality Selection


Theory and Algorithms

Research Areas

Intelligent Systems and Decision Analytics


American Economic Review: Papers & Proceedings: American Economic Association Annual Meeting 2017, January 6-8, Chicago, IL





First Page


Last Page





American Economic Association

City or Country

Nashville, TN

Copyright Owner and License


Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL