welcome:
location: ProblemsDescription / CompanyControls

# 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

ASP Competition 2011: ProblemsDescription/CompanyControls (last edited 2011-01-10 10:36:50 by CarmenSantoro)