4
$\begingroup$

Consider a multiset $S$ containing $n$ positive integers $\{s_1, s_2, \ldots, s_n\}$. For the purpose of this question, assume that (some of) the integers are very large with respect to $n$, i.e. much larger than $2^n$ such that the number of bits to describe them is not polynomial in $n$. I am interested in whether we can reduce the size of the numbers in $S$ without changing the total ordering on the sums of subsets of $S$, or more formally:

Given such a multiset $S$, does there exist a function $f : S \rightarrow \mathbb{N}$ such that for all subsets $S', S'' \subseteq S$ it holds that $\sum _{x \in S'} x \leq \sum_{x \in S''} x$ if and only if $\sum _{x \in S'} f(x) \leq \sum_{x \in S''} f(x)$, and such that the number of bits needed to represent the numbers $f(s_i)$ is polynomial in $n$?

If such a function $f$ exists for all multisets $S$, can we compute $f$ in time polynomial in the bitrepresentation of $S$?

It is not hard to verify that if we take $S$ to be the sequence $2^0, 2^1, 2^2, \ldots, 2^n$ then we cannot shrink these numbers any further: the smallest possible number we may assign is 1, so $f(2^0) \geq 1$. Then $f(2^1)$ needs to be strictly greater than $f(2^0)$, so $f(2^1) > f(2^0) \geq 1$ hence $f(2^1) \geq 2$. Now $f(2^3)$ must be strictly greater than $f(2^0) + f(2^1)$ so $f(2^3) > 1 + 2$ so $f(2^3) \geq 4$; and so on, and so on.

Thanks in advance for any insights. Since I am new to this area, it would also be nice to get some pointers to the literature, if related questions have been studied.

$\endgroup$
6
  • $\begingroup$ I'd rephrase it as: given n variables, an assignment of integer values induces a partial order on the subsets. Given a partial order (which comes from an unknown integer assignment) find the best integer assignment which induces it. Does that capture what you want? $\endgroup$ Feb 9, 2011 at 13:02
  • $\begingroup$ @Aaron: It's a quasiorder, not necessarily a partial order. $\endgroup$ Feb 9, 2011 at 16:29
  • $\begingroup$ @Chris True . Best might be to say that it is an equivalence relation with a linear order on the equivalence classes (and satisfies certain latice related properties..). I'm not sure what one would call that, maybe a total quasi-order (which is well behaved with respect to the latice of subsets...). quasi-order=reflexive+transitive include antisymetric to get partial order add to that total to get a linear order. so QO=R+TR LO=R+TR+AS+TO here we have R+TR+TO. Anyway, the question was, must we start from a weight function or do we want to start from the total quasi-order on the power set. $\endgroup$ Feb 9, 2011 at 21:54
  • $\begingroup$ @Aaron: The intention was to start from a weight function, instead of a quasi-order on the powerset. It makes a significant difference when talking about whether the mapping $f$ is polynomial-time computable or not, since a representation of a weight function is much smaller than giving an explicit total quasi-order relationship. $\endgroup$ Feb 10, 2011 at 10:15
  • $\begingroup$ On the other hand, from the weights you can get the quasi order but not vice versa so they carry more information and that extra information is irrelevant for your problem. $\endgroup$ Feb 12, 2011 at 16:14

1 Answer 1

3
$\begingroup$

Here is a much expanded answer. the old answer is below.

There are some very interesting questions here. What I say here is far from answering them completely but does go a certain distance. The sequence A009997 in the OEIS and its references turns out to be very relevant. I suggest looking for books and articles about Threshold Logic (perhaps a hotter topic before 1980 than after). My remarks grow from a paper of mine Maximal Intersecting Families European Journal of Combinatorics Volume 16, Issue 5, September 1995, Pages 491-501.

Indulge me in some terminology first (skip to the next paragraph if you wish) : A voting scheme consists of a set $S$ of $n$ elements (voters) and a way to decide for each partition $S=A \cup B$ into disjoint sets (coalitions) which of $A$ or $B$ wins. (If $A$ wins then each set containing $A$ should also win). To specify this it is enough to know the minimal winning coalitions, those $A$ which beat their complement, but fail to do so if any one voter changes sides (these form an intersecting antichain.) One way to specify a voting scheme is to assign each voter an integer weight with the total weight odd and taking weighted majority rules. Up to 5 voters, every voting scheme is of this type (for $n \ge 6$ only some are). Before I go on let me say that the question here is more structured, I might say that it concerns voting systems where some voters can abstain (just not every last voter) and if the remaining voters form two coalitions one must be the winner (As asked, one could perhaps have ties between sets but I think that small pertubations would only make it harder without changing the existing orders.) With 5 voters and no abstentions there are 5 weight functions: 10000 (dictator) 31111 (near dictator) 21110 32211 22111 and 11111(pure democracy). For 6 voters there are 30 voting schemes (up to isomorphism) of which 21 can be obtained by weights. The most complicated is 543221. There is a sense in which these are the optimal integer weight functions: The $2^n$ subsets can be identified with the corners of the standard cube of side 1 in $\mathbb{R}^n$. The corners corresponding to the winning coalitions in a voting scheme (or any other family of subsets) span a convex polytope of affine dimension $n$ or less. A voting scheme can be given by a weight function exactly if all but one of the supporting hyperplanes of this polytope are also supporting hyperplanes of the hypercube. Then the weight fuction can be given by the components of the appropriately scaled normal vector to that hyperplane.

I will take the problem as this: suppose that we have a linear order on the power-set of a given $n$ element set which respects set containment and that some weight function gives that order, find an efficient weight function achieving this. Here are ad hoc results up to $n=5$ then thoughts on a method.

In case $n=2$ use weights 21. For $n=3$ use either 421 or 432. for $n=4$ there are 3 voting schemes with weight functions 1000 1110 and 2111. This becomes 14 cases with abstentions allowed and the minimal weight functions are 7653, 8421, 8432, 8542, 8641, 8643, 8654, 8742, X432, X632, X742, X762, X843, X863 (here X stands for 10). Doing a massive number of random integer weight assignments for $n=5$ lead me to suspect (and later confirm from the OEIS) that there are 516 orders arising from weights. Finding the minimal weight assignments (just by looking at all cases of $0<e<d<c<b<a<32$ ) lead to these frequencies for the largest weight:

$$[13, 2], [14, 8], [15, 5], [16, 62], [17, 21], [18, 47], [19, 32], [20, 97]$$ $$ [22, 91], [23, 18], [24, 42], [25, 17], [26, 46], [28, 14], [30, 14]$$

The numbers 2,14,516 were enough to go to the OEIS and that lead to Number of comparative probability orderings on all subsets of n elements that can arise by assigning a probability distribution to the individual elements. Maybe the references there will help find out about the weight/probability distributions which leading to these orders.

It seems that one might be able to do the following: First find the minimal winning coalitions as described above and find the integer weight function giving them, it determines a hyperplane. A parallel hyperplane contains maximal losing coalitions. Take the plane parallel to these and running through the center of the cube. Now we want to slightly tilt it but not so much that it strictly crosses any corner of the cube. To do this, look at the subsets of one (or more) of the minimal winning coalitions. We have a linear order on them and a smaller voting scheme, find a weight function which works there and use it to perturb the weights (say multiply all the old weights by some factor and add in the new weights.) There are a hyper-exponential number of (isomorphism types) of voting schemes so we can't list them all, let alone the linear orders. Still it might be easy to process any one (though saying this is less convincing than doing it.) Alternately, set aside the lightest (or heaviest as seems easier) element. Solve the problem for the other $n-1$ elements. Then adjust to give a weight to the missing element.


old answer You have a system of inequalities which you could solve by linear programing getting rational weights. Then you have the problem of efficiently scaling to integers. The information is highly redundant. Maybe something like this could work: Looking at the order on singleton sets you can find the lowest weight. Set it aside. Solve the problem for the other n-1 weights. Now try to assign an appropriate weight to the minimum .

Another idea and an interesting question in itself is this: assume for now that no set is equal in weight to its complement. Then the inclusion minimal sets with this property are pairwise intersecting but none contains any other. These are the minimal winning coalitions in some voting scheme. Find weights which do this.

$\endgroup$
2
  • $\begingroup$ Using an ILP formulation is an interesting idea, but it seems hard to appropriately bound the size of the solution that is found (i.e. the size of the numbers in the solution). From an input multiset with $n$ numbers you get $2^n$ subsets and hence naively you would have to make $(2^n)^2$ inequalities in an ILP formulation. According to lecture notes from Kurt Mehlhorn, if an ILP has a solution that it has one whose integers are bounded by $4^{nL}$ where $L$ is the number of bits needed to describe the coefficient matrix; but then $L$ would be $\Omega((2^n)^2)$ so this is not yet good enough. $\endgroup$ Feb 10, 2011 at 10:33
  • $\begingroup$ Thanks for your extensive answer and insights. The pointer to threshold logic was very valueable: it lead me to the paper "On the Size of Weights for Threshold Gates" by Johan Hastad ( nada.kth.se/~johanh/threshweights.pdf ) where it is shown that in this voting scheme setting (which corresponds to a threshold gate) numbers of O(n log n) bits always suffice. Using an ILP characterization one can show that numbers of poly(n) bits also suffice for the original question. Whether you can find such numbers in polynomial time remains an open question. $\endgroup$ Mar 2, 2011 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.