System Regulations

[hrothgar]

Couple quick comments about one of Adam's posts

 

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.

 

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]

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]

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]

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]

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]

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.... :P

[Echognome]

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.... :P

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.

[Guest Jlall]

*HEAD ASPLODES*

[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]

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]

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. 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]

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]

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.