How does social status emerge in complex societies? Why are some societies more successful in achieving social equality than others? Answering these questions involves various fields including sociology, economics, and psychology. Status is a fundamental dimension of social stratification, and it has long been a central topic in social science. As Max Weber observed, status hierarchy is sustained by widely shared beliefs that relate characteristics of people to status values. Starting with this observation, status construction theory identified certain conditions and processes of status formation. To be specific, based on hypothetical association between inequality in material resources and a nominal (that is, a cognitively recognized but unordered) distinction between categories of people, the theory specified possible social processes through which this precondition creates and spreads status beliefs that favor the resource-advantaged group. We take status construction theory one step further by investigating processes of status formation without such a precondition. We explore stability of status hierarchy by introducing fair social exchanges within a stratified population. Based on the previous works on social structures, we also investigate effects of network structure in these processes.