Ordering a Power Set
Dennis
first, the context later:
Suppose we have a set of n objects, and a binary relation S that is a
linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
there any way to use this relation to induce some soft of ordering on
the power set of our set of objects?
This arises from an examination of equilibrium in the jungle: we have
N agents, and S is strength(1 is stronger than 2, etc.) To see if
this equilibirum is "coalition-proof" we need some way to order
coalitions of agents. Which I don't know how to do.
Arturo Magidin
Dennis <dco...@hotmail.com> wrote:
>This question arises from economics, but I'll give you the question
>first, the context later:
>Suppose we have a set of n objects, and a binary relation S that is a
>linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
>there any way to use this relation to induce some soft of ordering on
>the power set of our set of objects?
There are many ways to do it.
One way would be to use a variant of the lexicographic ordering:
(a) The empty set is the smallest set.
(b) Let A and B be nonempty. Let a be the smallest element of A, and b
the smallest element of B. Then we say that A is smaller than B if and
only if
(i) a<b; or
(ii) a=b and A-{a}<B-{b}.
This sets up a recursion process.
This works because any total ordering on a finite set is a
well-ordering, so it makes sense to talk about "smallest element".
However, this ordering has a number of "unnatural" features. A
slightly more interesting and natural way is to extend the natural
partial ordering that exists in P(S) under inclusion.
Order P(S) as follows:
(1) Two subsets of different size are ordered by their size; that is,
if A and B are subsets, and A has fewer elements than B, then A<B.
(2) Order the singletons by letting {a} < {b} if and only if a<b.
(3) Assuming all subsets of fewer than k elements have been ordered,
k>1, order the subsets of k elements as follows: if A and B both
have k elements, let a be the smallest element of A and b the
smallest element of B. Then A<B if and only if a<b or (a=b and
A-{a}<B-{b}).
But of the many ways to order P(S) "in some way" induced by the
ordering of S, you need to consider your problem.
>This arises from an examination of equilibrium in the jungle: we have
>N agents, and S is strength(1 is stronger than 2, etc.) To see if
>this equilibirum is "coalition-proof" we need some way to order
>coalitions of agents. Which I don't know how to do.
How you order the coalitions will depend on the properties of the
strength. Does a coalition involving strength 2 and 3 beat one
involving 1 and 4? You seem to be putting the horse before the cart:
you want to understand how the strength of a coalition works, so you
can then order the coalitions; you don't first order the coalitions in
some way and then use that order to figure out their relative
strengths.
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
A N Niel
Subsets of an n-element set correspond to strings of length n made up
of the symbols 0 and 1... 1 means "this object is in the set" 0 means
"this object is not in the set". But strings of 0s and 1s of length n
correspond to binary representations of the integers from 0 to 2^n-1.
There is a natural way to order THIS set, right?
Tim Sweeney
> first, the context later:
> Suppose we have a set of n objects, and a binary relation S that is a
> linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
> there any way to use this relation to induce some soft of ordering on
> the power set of our set of objects?
Yes: Associate each (finite) set with a sorted array containing
exactly those elements in that set, and use the lexocographic
(dictionary) order of those arrays. It will also be a linear order
with a minimum element (the empty array) but no maximum element.
Federico
> linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
> there any way to use this relation to induce some soft of ordering on
> the power set of our set of objects?
Yes, there are several ways.
For example a max-min criterion is: Let < be the
linear order. Any subset of A has a smallest element,
i(A) in <. Say that A is smaller than B if i(A) =< i(B).
You can also do min-max.
More generally, you want "responsive" preferences
over subsets. A good reference is Roth and Sotomayor's
book on two-sided matching.
Federico Echenique
Denny
Well, i was hoping there was some way to do it without getting any more
specific on the properties of S. If there was some natural way that S
could in some sense extend to the power set, then that would have been
nice. It seems that I'm going to have to move away from S to some
cardinal representation of it, some function from the set of agents to the
reals, so say exactly how strong each agent is in relation to each other,
and then have some sort of shapely value of strength for agent. This is a
much weaker result, though, since we'll get different allocations
depending onthe function I use for S.
>
> ======================================================================
> "It's not denial. I'm just very selective about
> what I accept as reality."
> --- Calvin ("Calvin and Hobbes")
> ======================================================================
>
> Arturo Magidin
> mag...@math.berkeley.edu
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Denny
wrote:
but not one that in any way uses S. The idea is to extend the idea of
strength of individuals to strength of coalitions.
William Elliot
> >> This question arises from economics, but I'll give you the question
> >> first, the context later:
> >> Suppose we have a set of n objects, and a binary relation S that is a
> >> linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
> >> there any way to use this relation to induce some soft of ordering on
> >> the power set of our set of objects?
> >>
> >> This arises from an examination of equilibrium in the jungle: we have
> >> N agents, and S is strength(1 is stronger than 2, etc.) To see if
> >> this equilibirum is "coalition-proof" we need some way to order
> >> coalitions of agents. Which I don't know how to do.
> >
What do you mean coalition proof? Can't the top dogs always beat up on
the bottom dogs. Even in US democracy, we see how well the rich top have
coaluded to succefully control, own and extort the poorer bottom.
> > Subsets of an n-element set correspond to strings of length n made up
> > of the symbols 0 and 1... 1 means "this object is in the set" 0 means
> > "this object is not in the set". But strings of 0s and 1s of length n
> > correspond to binary representations of the integers from 0 to 2^n-1.
> > There is a natural way to order THIS set, right?
>
> but not one that in any way uses S. The idea is to extend the idea of
> strength of individuals to strength of coalitions.
>
Use weights. Give each a weight or strength. Make the weights linearly
independent so that no sum of weights of one subset equals the sum of
weights of another subset. For example square roots of different primes.
Then order subsets by sum of weights of members. The order of the subsets
will depend upon the weights assigned each individual.
Why insist upon a complete order?
Federico
> specific on the properties of S. If there was some natural way that S
> could in some sense extend to the power set, then that would have been
> nice. It seems that I'm going to have to move away from S to some
> cardinal representation of it, some function from the set of agents to the
> reals, so say exactly how strong each agent is in relation to each other,
> and then have some sort of shapely value of strength for agent. This is a
> much weaker result, though, since we'll get different allocations
> depending onthe function I use for S.
Since there are many "natural" ways, you can work with
an arbitrary order that is somehow consistent with
the order on the individual elements of S: Look at how
people in two-sided matching theory do it (see my
previous post).
Virgil
> This question arises from economics, but I'll give you the question
> first, the context later:
> Suppose we have a set of n objects, and a binary relation S that is a
> linear ordering, ie irreflexive, asymmetric, complete, transitive. Is
> there any way to use this relation to induce some soft of ordering on
> the power set of our set of objects?
>
> This arises from an examination of equilibrium in the jungle: we have
> N agents, and S is strength(1 is stronger than 2, etc.) To see if
> this equilibirum is "coalition-proof" we need some way to order
> coalitions of agents. Which I don't know how to do.
In order to transfer unambiguously the order on the underlying
ordered set to an order on (finite) subsets or coalitions, the
underlying order must do something like allowing comparisons of
intervals, or differences in order, so that, say, given w, x, y and
z in the underlying set, one may compare w-x to y-z ( find whether w
as much greater than x as y is greater than z).
Since this requires more than simple ordering, there cannot be any
unique extention to coalitions based only on simple ordering.
The question is just how much more than simple ordering is required
on the underlying set in order to make such comparisons of
coalitions meaningful or useful.
Denny
> On Tue, 11 Nov 2003, Denny wrote:
>
>> >> This question arises from economics, but I'll give you the question
>> >> first, the context later:
>> >> Suppose we have a set of n objects, and a binary relation S that is a
>> >> linear ordering, ie irreflexive, asymmetric, complete, transitive.
>> Is
>> >> there any way to use this relation to induce some soft of ordering on
>> >> the power set of our set of objects?
>> >>
>> >> This arises from an examination of equilibrium in the jungle: we
>> have
>> >> N agents, and S is strength(1 is stronger than 2, etc.) To see if
>> >> this equilibirum is "coalition-proof" we need some way to order
>> >> coalitions of agents. Which I don't know how to do.
>> >
> What do you mean coalition proof? Can't the top dogs always beat up on
> the bottom dogs. Even in US democracy, we see how well the rich top have
> coaluded to succefully control, own and extort the poorer bottom.
>
Well, it's a well defined concept in general equilibrium theory.
>> > Subsets of an n-element set correspond to strings of length n made up
>> > of the symbols 0 and 1... 1 means "this object is in the set" 0 means
>> > "this object is not in the set". But strings of 0s and 1s of length n
>> > correspond to binary representations of the integers from 0 to 2^n-1.
>> > There is a natural way to order THIS set, right?
>>
>> but not one that in any way uses S. The idea is to extend the idea of
>> strength of individuals to strength of coalitions.
>>
> Use weights. Give each a weight or strength. Make the weights linearly
> independent so that no sum of weights of one subset equals the sum of
> weights of another subset. For example square roots of different primes.
> Then order subsets by sum of weights of members. The order of the
> subsets
> will depend upon the weights assigned each individual.
>
> Why insist upon a complete order?
Because if I don't have one I can say whether or not a particular
coalition would be able to appropriate some allocation from another person.
Denny
relative power, and lets us say how much stronger 1 is than 2, etc. The
properties of the equilibirum will then depend pretty strongly on how we
specify this function, won't it?
--