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 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
- 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 controlled companies 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
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
Authors: Mario Alviano
|