= Company Controls = <> == Problem Description == Company Controls is a problem in the area of stock market, in which the goal is to determine the pair of companies X,Y such that X controls Y, given information on stock possessions of companies. We are interested in a decision version of this problem. Given a situation of shareholdership and a company C, is it true that C is the main controller? In other words, is the number of companies controlled by C greater than or equals to the number of companies controlled by any other company? Remind that, in order to control a company Y, a company X has to exert control over more than 50% of the stock of Y. Company X can exert control over stock of Y in two different ways: X itself may possess a certain percentage of stock of Y, in this case we say that X directly exerts control over the respective percentage of stock of Y. Alternatively, if X controls a company Z, which exerts control over stock of Y, then we say that X indirectly exerts control over the respective stock of Y. Company X then exerts control over the sum of stock of Y over which it directly and indirectly exerts control. Alternatively, we can define the control relation inductively, by saying that company X controls Y if the sum of the shares in Y possessed by X and by companies controlled by X is more than 50%. The input is comprised of the company C, the set of all companies and the percentages of directly controlled stock. More details in the following papers: * Inderpal Singh Mumick and Hamid Pirahesh and Raghu Ramakrishnan, "The Magic of Duplicates and Aggregates", Proceedings of the 16th International Conference on Very Large Data Bases (VLDB'90), pp. 264-277; * David B. Kemp and Peter J. Stuckey, "Semantics of Logic Programs with Aggregates", Proceedings of the International Symposium on Logic Programming (ISLP'91), pp. 387-401. == Input format == The company C is specified by an instance of "checkForMaxControls", for example: checkForMaxControls(c1). The set of companies is specified by instances of "company", for example: company(c1). company(c2). company(c3). company(c4). The percentages of directly controlled stock is given by instances of "owns", for example: owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). == Output format == If the number of companies which are controlled by C is greater than or equals to the number of controlled companies by any other company, the output should be a witness specified by instances of "controls", where controls(x,y) states that company x exerts control on company y. For example, a valid output for the instance above is the following: controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4). Otherwise, if there is a company exerting control on a number of companies greater than the number of companies controlled by C, the output should be the string "UNSATISFIABLE". == Example == For the input checkForMaxControls(c1). company(c1). company(c2). company(c3). company(c4). owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). the output should be controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4). because * c1 controls 3 companies, that is c2, c3, c4; * c3 controls only 1 company, that is c4; * c2 and c4 do not control any company. Similarly, for checkForMaxControls(c3). company(c1). company(c2). company(c3). company(c4). owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). the output should be UNSATISFIABLE == Author(s) == Author: Mario Alviano <
> Affiliation: University of Calabria, Italy