[awm]

A few points on Dr. Todd's "proof":

The method he describes assumes that the goal of bidding is to reach the "best contract for our side." In other words, the assumption is that we bid a bunch and reach some contract, then play it out double-dummy. However, in real bridge the play often depends on the bidding. A method where slightly inferior contracts are often reached but less information is given to the opponents can often outscore a more "scientific" method that reaches better contracts but allows the opponents to lead double-dummy.

Of course, in principle you could combine "all possible sequences of plays" with "all possible definitions of bids" and "all possible sets of hands and sequences of bids" and argue that everything is still finite (albeit ridiculously large) and so an optimum should exist.

However, this still ignores the possibility of randomized strategies. Once we allow people to "sometimes bid one thing, sometimes another" with the same hand in the same auction, the number of possible strategies starts to look infinite.

In addition, there are constraints relating to computability and human memory. For example, it might be possible to show that a particular hand evaluation metric is "best" but if it can't be computed by a human in any reasonable time it's not going to work out in practice. Perhaps computers shouldn't worry about this, but even in that case the possible sets of hands are so large that deciding and disclosing things efficiently could become difficult. It wouldn't surprise me if the total number of deal-auction-play triples exceeded the number of particles in the universe by a large factor (even ignoring randomized strategies).

[Cascade]

DrTodd13, on Jul 11 2007, 08:38 AM, said:

awm, on Jul 10 2007, 11:56 AM, said:

For this to work, you need to make a series of highly unlikely assumptions:

(1) There exists a "best system."

(2) The best system is not, in fact, allowed.

(3) Given that the best system is not allowed, the legal system which is "most similar" to the best system will be the best constrained solution.

All three of these assumptions seem dubious to me.

A more likely explanation is that the effectiveness of a method is highly dependent on the defense which your opponents are using. Good opponents tend to have a good defense to methods which they see frequently. Therefore, it is to a pair's advantage to play methods (subject to some degree of non-ridiculousness) which are unfamiliar to the opponents. The regulatory structures are designed such that "mainstream" methods are close to the "middle" of the constraint set -- this allows people to deviate in small ways (for example playing opening bids a queen lighter than normal, or weak twos with a card less) without running afoul of the regulations. Therefore methods which are close to the boundaries of legality are likely to be "further from mainstream" and therefore less familiar and more advantageous.

...

3) I agree there is no reason to believe this assumption to be true.

But I do not believe it is an assumption that I made.

I simply said and I believe that it is true that the best either lies at some local best completely within the allowed regulations or at the boundary.

Therefore at the very least if we want to find the best we need to explore the boundaries.

And if the boundaries are not well defined or not sensible then there will be problems.

[awm]

The point is that if we postulate an arbitrary constrained function, there is no particular reason that the optimum solution should be at the boundaries. After all, the boundaries have area zero compared to the space as a whole. Obviously the best legal system "could lie anywhere" but the point is that there's no particular reason to care about the boundaries. Making the boundaries slightly fuzzy is also unlikely to make a difference.

Of course, there are some types of optimization where the best solution is very often at the boundaries of a constraint set. These are, for example, convex optimizations. But there's no reason to think that bidding system design is such a problem.

The question I'm trying to ask is: Is there any reason to think that the best legal system is probably close to the boundaries of what's allowed?. If we assume system design to be just an optimization process, I don't see any particular reason to believe this. In fact it's not totally clear that a best system even exists because of the legality of randomized strategies etc.

There is an empirical observation that people who tinker with systems seem to like to push the boundaries. This could be interpreted as "people who like to experiment seem to think that systems close to the boundaries are good" or that "the best system seems to be illegal and people are trying to get as close as possible to that system within the established rules." But I think there are alternate arguments based on familiarity and the advantage of playing something unfamiliar to the opponents which also explain this phenomenon and require fewer controversial assumptions about the nature of system design.

As for "why should the boundaries be clear instead of fuzzy" I don't think this is an optimization issue. I think it's a fair play issue. Whether your methods are legal shouldn't depend on who the director is, or who you are, or who you're playing against.

[pbleighton]

Quote

If we assume system design to be just an optimization process

Why would we assume that?

I design financial information systems for a living, and in that space at least, this is not true at all.

Peter

[helene_t]

awm, on Jul 10 2007, 09:56 PM, said:

For this to work, you need to make a series of highly unlikely assumptions:

(1) There exists a "best system."

(2) The best system is not, in fact, allowed.

(3) Given that the best system is not allowed, the legal system which is "most similar" to the best system will be the best constrained solution.

As for 1) and 3), see Todd's post.

As for 2), I think the subset of possible systems that are allowed is so tiny that it is extremely unlikely that the optimal system is allowed. Think of a dynamic system which assigns meanings to each call according to a 5-layer neural network, taking the state of the match, the negative inference from opps' bidding etc. etc. as input. Such a system might be allowed in Australia but not in Europe, let alone North America.

But if "optimal" also includes that it must be possible for a human to memorize all the conventions, I'm less sure. Still I tend to think that it would be possible to construct a system that is highly unusual yet slightly more effective than what we play today.

[hrothgar]

awm, on Jul 11 2007, 12:40 AM, said:

Couple quick comments about one of Adam's posts

Quote

A few points on Dr. Todd's "proof":

The method he describes assumes that the goal of bidding is to reach the "best contract for our side." In other words, the assumption is that we bid a bunch and reach some contract, then play it out double-dummy. However, in real bridge the play often depends on the bidding. A method where slightly inferior contracts are often reached but less information is given to the opponents can often outscore a more "scientific" method that reaches better contracts but allows the opponents to lead double-dummy.

What you're discussing here is how the payoff matrix is constructed. It really isn't a critique of the methodology.

Quote

However, this still ignores the possibility of randomized strategies. Once we allow people to "sometimes bid one thing, sometimes another" with the same hand in the same auction, the number of possible strategies starts to look infinite.

Mixed strategies are a part of life. Very simply games with a very simply 2 x 2 payoff matrix often have solutions that require randomization according to an optimal pdf. Here, once again, the strategy space is infinite, however, the solution is quite simple. (none of this should be construed to suggest that I think that its remotely feasible to "solve" bridge)

As I've mentioned before, intuitively I don't believe that there is any such thing as a "best" system. Rather, I suspect that one needs to define a population of bidding systems that coexist with one another in some form of long term equilibrium.

[helene_t]

hrothgar, on Jul 11 2007, 12:13 PM, said:

As I've mentioned before, intuitively I don't believe that there is any such thing as a "best" system. Rather, I suspect that one needs to define a population of bidding systems that coexist with one another in some form of long term equilibrium.

This depends on how you define a "system". If systems are allowed to adapt to each other without restrictions, e.g. we may play a weak opening system or a strong opening system (or whatever) in 2nd seat depending on the exact meaning of RHO's pass, there must be a single optimum. This is beacuse the optimal defense against a first-seat pass in solved independantly from the optimal 1st-seat opening scheme.

[hrothgar]

helene_t, on Jul 11 2007, 01:20 PM, said:

hrothgar, on Jul 11 2007, 12:13 PM, said:

As I've mentioned before, intuitively I don't believe that there is any such thing as a "best" system.  Rather, I suspect that one needs to define a population of bidding systems that coexist with one another in some form of long term equilibrium.

This depends on how you define a "system". If systems are allowed to adapt to each other without restrictions, e.g. we may play a weak opening system or a strong opening system (or whatever) in 2nd seat depending on the exact meaning of RHO's pass, there must be a single optimum. This is beacuse the optimal defense against a first-seat pass in solved independantly from the optimal 1st-seat opening scheme.

Running off to work: Back in 13 hours.

Couple quick comments

Single player games with no repeat play are very different than multiple player games that get played over long periods of time.

In this specific example, you need to consider the impact of

1. Switching costs to learn a new system
2. Regulatory restrictions that bar players from changing their methods after each board

[joshs]

Echognome, on Jul 10 2007, 04:30 PM, said:

joshs, on Jul 10 2007, 01:21 PM, said:

I was about to comment on convexity and lagranian multipliers but Adam beat me to it.... I strongly doubt that this is a convex problem. Now if this is a continuous function real valued function on a compact set....

Lagrangian is fine and dandy if you have a simple function with an equality constraint. Once you have inequality constraints (such as hcp >7) or mixed constraints, you are talking about Kuhn-Tucker conditions.

Again, I don't see what convexity has to do with the problem. You can still hit boundaries with concave functions.

You of course can use Bolzano-Weierstrauss to show a maximum exists if it's continuous. We don't have continuity of course, but I don't think it's too big a step to approximate with continuity. We have a pretty good range once we start adding texture into the hands, such as comparing a suit of AK432 with AK984 or with AKT98.

The Lagranian multiplier tells you how "strongly" the constraint influenced your answer (and will equal 0 if the optimal answer was not on the boundary at all). That is, if you take a normal to your surface at the point of the maximum, the lagrangian multiplier tells how much the objecive function improves as you cross the boundary. If it is high, its likely (although not certain) that the true optimum was a decent ways away from the constraint surface. Basically this is a first derivative.

Theorem A: For a linear program (maximize a linear function on a space with linear constraints), the Maximum always occurs on the boundary, and in fact will always occur on the corners.

Note: A non-zero linear function never has a zero derivative anywhere so has no local maxima or minima.

Theorem B: if we replace your linear functions with convex functions, the same is true.

Proof: Suppose there was a local extrema of the function. That is the gradient of the function was 0 there. This is in fact a local minima and not a local maxima. Why, because convexity implies that the hessian (the matrix of second derivatives) was positive definite everywhere, and that plus a 0 gradient is the criteria for a local min.

Theorem C: If you don't want the maximum but instead want a minimum you can replace the word convex with concave.

Proof: See above proof. For a concave function the hessian is negative definite everywhere, hence every local extrema is a local max.

For a convex problem, its minimum might well be in the interior, and for a concave problem its maximum might also occur in the interior.


The issue isn't about existance of maximums (continuity and compactness answer that question) its about if the maximum has to be on the boundary. I hope that helps.

[Echognome]

joshs, on Jul 11 2007, 04:30 PM, said:

The issue isn't about existance of maximums (continuity and compactness answer that question) its about if the maximum has to be on the boundary.

Right. So explain how your discussion of linear, concave, and convex meshes with the example I gave of a concave function who's solution is on the boundary, namely:

f(x) = 1-x^2, x>=1/2

P.S. I have done a lot of work with constrained optimization, not to mention for multivariate functions (where your notions of concavity and convexity are going to be too strict).

P.S.S. Wayne's original point was that one should not only check the interior, but also the boundary. I still do not see why that would be untrue, unless you are going to put further restrictions on your function. One can simply imagine the "interior" solution lying outside of the feasible set.

[joshs]

Echognome, on Jul 11 2007, 08:01 PM, said:

joshs, on Jul 11 2007, 04:30 PM, said:

The issue isn't about existance of maximums (continuity and compactness answer that question) its about if the maximum has to be on the boundary.

Right. So explain how your discussion of linear, concave, and convex meshes with the example I gave of a concave function who's solution is on the boundary, namely:

f(x) = 1-x^2, x>=1/2

P.S. I have done a lot of work with constrained optimization, not to mention for multivariate functions (where your notions of concavity and convexity are going to be too strict).

P.S.S. Wayne's original point was that one should not only check the interior, but also the boundary. I still do not see why that would be untrue, unless you are going to put further restrictions on your function. One can simply imagine the "interior" solution lying outside of the feasible set.

I am still missing something:

Convex Function: Maximum is On Boundary, No comment on where the minimum is. it might be on the boundary or in the interior.

Concave Function: minimum is on the boundary, No comment on where the maximum is, it might be on the boundary or the interior.

In fact, your problem which was maximize 1-x^2 with x>=1/2 isn't even really in the set up for the problem (not a bounded, or more generally compact constraint space) but yes its maximum is at its boundary. The theorems cited Said absolute nothing about the maximum of a concave function or a minimum of a convex function. Change your constraints to x>=-1 and x<=173 and now the maximum is in the interior. On the other hand, pick ANY convex function with those contraints and the maximum will be at -1 or at 173.

Wayne wasn't remembering the math theorems very well. The interior plus the boundary is everywhere....

[Echognome]

joshs, on Jul 11 2007, 05:23 PM, said:

In fact your problem which was maximize 1-x^2 with x>=1/2 isn't even really in the set up for the problem (not a bounded, or more generally compact constraint space) but yes its maximum is at its boundary. The theorems cited Said absolute nothing about the maximum of a concave function or a minimum of a convex function. Change your constraints to x>=-1 and x<=173 and now the maximum is in the interior. On the other hand, pick ANY convex function with those contraints and the maximum will be at -1 or at 173.

Wayne wasn't remembering the math theorems very well. The interior plus the boundary is everywhere....

jajaja

My point of contention here is on the statement "isn't even really in the set up for the problem." That is so picky. First off, a continuous function on a compact set is compact. That's the theorem to which you are referring. This only guarantees the existence of a max. Of course a maximum may still exist if the set is not compact. So the setup you refer to is one in your mind. Second, if you are so concerned about the compactness, we can always make x >=1/2 and x<=1.

And to your point about boundary + interior is everywhere, of course we mean that there are only going to be a few critical points to check.

Anyway, I'm sure you'll agree with me that there's not much point in worry about convexity or concavity as there's no reason to believe that that's what our function will look like.

[helene_t]

What are you guys talking about? You can ask if a function is concave if it from a set with a certain structure to another set with a certain structure, I think the set of systems would have to be a vector space or some such. The object function is convex if it must necesarily be true that, for example,
0.7*ACOL + 0.3*MOSCITO
is better than both Acol and MOSCITO. This seems absurd but what would it mean to play "0.7*ACOL plus 0.3*MOSCITO"? Some mixed strategy? A variable system? The openings from pass through 2♠ being 7 Acol openings and 3 Moscito openings? Or 1♥ promising at least 2.8 hearts and at least 1.2 spades?

And then for the constraints. Richard factors in the costs of changing from one system to another. That's already so difficult to model that all this mathematical reasoning pretty much collapses. When it comes to legal restrictions, it gets worse. Legal restrictions are some foggy blend of hard rules and soft "gentleman" ethics. Besides, the constraints could be anything. If, for example, the only restriction is that the "optimal" system is explicitly banned, the conclusion is clear. If the only restriction is that some obviously silly system is banned, the conclusion is also clear.

[joshs]

helene_t, on Jul 12 2007, 02:48 AM, said:

What are you guys talking about? You can ask if a function is concave if it from a set with a certain structure to another set with a certain structure, I think the set of systems would have to be a vector space or some such. The object function is convex if it must necesarily be true that, for example,
0.7*ACOL + 0.3*MOSCITO
is better than both Acol and MOSCITO. This seems absurd but what would it mean to play "0.7*ACOL plus 0.3*MOSCITO"? Some mixed strategy? A variable system? The openings from pass through 2♠ being 7 Acol openings and 3 Moscito openings? Or 1♥ promising at least 2.8 hearts and at least 1.2 spades?

And then for the constraints. Richard factors in the costs of changing from one system to another. That's already so difficult to model that all this mathematical reasoning pretty much collapses. When it comes to legal restrictions, it gets worse. Legal restrictions are some foggy blend of hard rules and soft "gentleman" ethics. Besides, the constraints could be anything. If, for example, the only restriction is that the "optimal" system is explicitly banned, the conclusion is clear. If the only restriction is that some obviously silly system is banned, the conclusion is also clear.

Maybe I am not sure who your question is directed at.

Convexity means if you take 0.7Acol + 0.3Moscito then its better than either one, and that in fact for any two systems aSystem1+(1-a)system2 is always better than either one.

Concavity means that these combos are always worse.

By always I mean always. Without this being true, the math conclusions (theorems)about the locations of maxima (for convex) or minima (for concave) do not hold. That doesn't mean that they might not be true anyway in a particular case, but its not a logical/mathematical necessity based on the information given.

[joshs]

Echognome, on Jul 11 2007, 08:47 PM, said:

joshs, on Jul 11 2007, 05:23 PM, said:

In fact your problem which was maximize 1-x^2 with x>=1/2 isn't even really in the set up for the problem (not a bounded, or more generally compact constraint space) but yes its maximum is at its boundary. The theorems cited Said absolute nothing about the maximum of a concave function or a minimum of a convex function. Change your constraints to x>=-1  and x<=173 and now the maximum is in the interior. On the other hand, pick ANY convex function with those contraints and the maximum will be at -1 or at 173.

Wayne wasn't remembering the math theorems very well. The interior plus the boundary is everywhere....

jajaja

My point of contention here is on the statement "isn't even really in the set up for the problem." That is so picky. First off, a continuous function on a compact set is compact. That's the theorem to which you are referring. This only guarantees the existence of a max. Of course a maximum may still exist if the set is not compact. So the setup you refer to is one in your mind. Second, if you are so concerned about the compactness, we can always make x >=1/2 and x<=1.

And to your point about boundary + interior is everywhere, of course we mean that there are only going to be a few critical points to check.

Anyway, I'm sure you'll agree with me that there's not much point in worry about convexity or concavity as there's no reason to believe that that's what our function will look like.

Come on Matt. I took your example seriously, and changed it ever so slightly (by putting another boundary condition on in addition) to make it conform to the spirit of the problem we were talking about. The content of your example had nothing so every with the fact that the set was unbounded at one end, so I didn't nitpick about that at all.

Without the compactness we are not guaranteed a max or a min at all. If we want to prove something definitive about the locations of max's or mins, you need to know if there has to be maxs or mins in the first place. Yes there might be a max or min for a particular function, but a theorem is a statement that given some conditions some conclusions are ALWAYS not just sometimes true.

Here is your argument in a nutshell:
Wayne made (or tried to make) a statement that If susch an such a condition is true, then such and such is true for the maximum of the function.

And you said, but wait, take this example where that condition does not hold, then the same fact was still true for an example.

I orginally thought that your confusion was merely about statements about maxima vs statements about extrema. But now its looking like you seem to think that:
A implies B has some logical bearing on if
1. Not A implies B or
2. Not A implies not B
Of course there no such logical relationship.

Of course we all agree, that for the problem we were interested in (the existance and location of the optimal system) that even if there existed a function from the space of systems to the real line such that a higher number means a better system (where better means will beat the other system over the long hawl). that we all doubt that that function is convex or concave. I was just trying to correct the statements of the theorems, lest someone here finds another example in there life where they truely have a convex or concave function....

Note: Most of modern economics is built on the assumptions that
there exists a utility function from the set of baskets of goods to the real line that satisfies
a. If someone prefers A to B, U[A] > U[B]
b. Transitivity holds (People are rational, which is doubtful)
c. The Utility function is convex, that is people always prefer a mix of goods than one or the other (on a technical note this only applies to goods that have positive utility, so you would not choose to purchase something that makes you unhappy or has no value whatsoever).

So the set up in the theorems discussed here are pretty common.

[Cascade]

joshs, on Jul 12 2007, 01:23 PM, said:

Wayne wasn't remembering the math theorems very well. The interior plus the boundary is everywhere....

I'm not so sure about that.

All I said was that the optimum will occur somewhere in the interior but it must be at a local optimum or somewhere on the boundary but not necessarily at a local optimum since the local or global optimum might occur beyond the boundary.

In mathematics there are often ways to check for local optima so we would normally find those points and then check the boundary.

In terms of a bidding system it might be relatively hard to determine the local optima especially if we wanted a great deal of precision (excuse the pun).

However my main contention was simply that if we consider that the global optimum might be outside the contraints then it will be natural and wise to check the boundaries. This will be made much harder if the boundaries are fuzzy or not well defined in some other way.

[joshs]

Cascade, on Jul 12 2007, 03:54 PM, said:

joshs, on Jul 12 2007, 01:23 PM, said:

Wayne wasn't remembering the math theorems very well. The interior plus the boundary is everywhere....

I'm not so sure about that.

All I said was that the optimum will occur somewhere in the interior but it must be at a local optimum or somewhere on the boundary but not necessarily at a local optimum since the local or global optimum might occur beyond the boundary.

In mathematics there are often ways to check for local optima so we would normally find those points and then check the boundary.

In terms of a bidding system it might be relatively hard to determine the local optima especially if we wanted a great deal of precision (excuse the pun).

However my main contention was simply that if we consider that the global optimum might be outside the contraints then it will be natural and wise to check the boundaries. This will be made much harder if the boundaries are fuzzy or not well defined in some other way.

Sorry Wayne I was using your name in vain. I just reread your original post. It wasn't you who made the claim about convexity at all (somehow it snuck into the discussion). Of course what you said was 100% correct.