Hoagy
Karma: 71
NewTop
I’ve realised that you’ve gotta be careful with this method because when you find a trichromatic subtriangle of the original, it won’t necessarily have the property of only having points of two colours along the edges, and so may not in fact contain a point that maps to the centre.
This isn’t a problem if we just increase the number n by which we divide the whole triangle instead of recursively dividing subtriangles. Unfortunately now we’re not reducing the range of co-ords where this fixed point must be, only finding a triad of arbitrarily close points that map to a triangle surrounding the centre. You can, for example, take the centre point of the first of these triangles (with some method of numbering to make the function definite) for each value of as a sequence in . This must have a convergent sequence which should converge to a point that maps to the centre but I can’t prove that last stage.
Cleanest solution I can find for #8:
Also, if we have a proof for #6 there’s a pleasant method for #7 that should work in any dimension:
We take our closed convex set that has the bounded function . We take a triangle that covers so that any point in is also in .
Now we define a new function such that where is the function that maps to the nearest point in .
By #6 we know that has a fixed point, since is continuous. We know that the fixed point of cannot lie outside because the range of is . This means has a fixed point within and since for , , has a fixed point.
Yeah agreed, in fact I don’t think you even need to continually bisect, you can just increase n indefinitely. Iterating becomes more dangerous as you move to higher dimensions because an n dimensional simplex with n+1 colours that has been coloured according to analogous rules doesn’t necessarily contain the point that maps to zero.
On the second point, yes I’d been assuming that a bounded function had a bounded gradient, which certainly isn’t true for say sin(x^2), the final step needs more work, I like the way you did it in the proof below.
Here’s a messy way that at least doesn’t need too much exhaustive search:
First let’s separate all of the red nodes into groups so that within each group you can get to any other node in that group only passing through red nodes, but not to red nodes in any other group.
Now, we trace out the paths that surround these groups—they immediately look like the paths from Question 1 so this feels like a good start. More precisely, we draw out the paths such that each vertex forms one side of a triangle that has a blue node at its opposite corner. Note that you can have multiple paths stemming from the same group if the group touches the side of the larger triangle, or if it has internal holes.
Now we have this set of paths we can split them into three kinds. The first is loops, which arise when you have a group which never touches the edge of the larger triangle, or inside ‘holes’ in large groups. These can be seen as a path starting and finishing at the same node. They therefore have an even number of b-g vertices. The second kind is those that begin at the edge of the large triangle and end at the same edge. These paths begin and end on the same colour and therefore also have an even number of b-g vertices. Finally and most importantly there is a kind of path that goes from one edge to the other -in the case of the reds, the left edge to the right edge. This will happen once with the group that includes the top red node, and if any other group spans the larger triangle then it will generate two more of these paths. Sperner’s lemma tells us that these will have an odd number of b-g vertices and we know that there will be an odd number of such paths, so this final type generates an odd number of total b-g vertices.
By the way that we have defined these paths, the total number of r-g-b triangles is equal to the number of g-b vertices on the paths in the set generated above. This number is the sum of an odd number from the spanning paths and a series of even numbers from the other paths, giving an odd overall number of r-g-b vertices, proving number 4 (as long as I haven’t made an error in categorizing the paths).
I hope this makes sense, let me know if it doesn’t or has errors :)
I was able to get at least (I think) close to proving 2 using Sperner’s Lemma as follows:
You can map the continuous function f(x) to a path of the kind found in Question 1 of length n+1
by evaluating f(x) at x=0, x=1 and n-1 equally spaced divisions between these two points and setting a node as blue if f(x) < 0 else as green.By Sperner’s Lemma there is an odd, and therefore non-zero number of b-g vertices. You can then take any b-g pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of x—only one where f(x) is below zero—that are 1/(n^k) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence f(x) of initial nodes x we get a sequence that, by B-W, has a sub-sequence which converges to zero. By continuity we have proved the existence of an x such that f(x)=0.
We can be sure that the sub-sequence does in fact converge to zero, rather than any other value because if it converges to any number |a|>0, the gradient of f(x) would have to be arbitrarily high to dip back below/above 0 for a value of x arbitrarily close by and therefore would not be a continuous function.
Comments to tighten up/poke holes in the above appreciated :)
For long term bets, where the opportunity cost of tying money up in these bets becomes high, I would have thought that the bets should be denominated in US bonds (or other agreed minimal-risk interest rate asset) to minimize this cost.
Even if the bet does not pay out one way or another, the money still accumulates interest.
Other than being incompatible with Augur, are there any theoretical or practical hurdles to using this? It would hopefully reduce the subsidy required to make an attractive market without incurring cost in and of itself.
Thanks for replying :)
If the joining bonus were large enough to give a new member enough DKP to get the choice items, then older members would (quite rightly) complain. If it were smaller, it wouldn’t work.
I guess my central question is, a new player will have infinite EP/GP after they first receive EP. They can therefore wait until their perfect item comes up, and choose that. This to me seems extremely similar to giving an uncertain but potentially very large joining bonus. After losing this infinite ratio status, the situation then seems very similar to a free market one. In particular I don’t understand why having collected lots of points (ie ability to claim future value) would lead to your incentive dropping off, while accumulating a high ratio (which you’d presumably need to ‘save’ for a while for really top items) doesn’t have this problem.
I’m curious but a bit confused about some of the benefits of EP/GP over the straight free-market model, but if EP/GP did indeed take over then I’m sure there’s something I’m missing.
1: Presumably, in both models, in the long run it takes roughly the same average amount of time (modulated by your efficiency of pro-social activity) to get an item of quality >x, but it seems that in EP/GP you get your first almost immediately, while in DKP your timer starts from 0. Was there the issue of individuals jumping around guilds to try and get that first item?
2: Is there any system by which one can defer the receiving of items in EP/GP so that you don’t end up getting something that is of low or nil value to you (especially since they can’t be traded)? The main advantage of the free-market, at least in systems where individuals have similar ability to earn currency, is usually that items go to those who value them most, so you’d expect DWP to have a big efficiency advantage if you can’t choose whether to accept. On the other hand, if this deferral is possible, would this degenerate into something like a free market, except where new entrants have first dibs over everything?
The power of attracting new players is a valuable advantage I’m sure but it’s the only one that I really see from the 3 given above, and I can’t see how this isn’t possible in a similar way by, say, a free market system where a new member gets some kind of joining bonus.
When you talk about ‘black-box’ versions of Hugh, do you envision that H is able to answer questions relating to the cognitive processes that lead to the answer given, or about H’s thinking in general? This seems to contradict the spirit of a black box but self reflection is an important part of Hugh’s cognitive ability.
Perhaps they are both useful possibilities, my intuition is that this kind of self reflection is as far from being possible for AI as any human ability and so we should expect that we might have systems powerful enough to take on wide responsibility without this ability. If it were possible, though, the ability to use loops of self reflection to check whether a cognitive process serves a certain goal would be very helpful.