Can anyone maximize this expression?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
BSaito
Posts: 25
Joined: Mon Oct 13, 2008 2:41 am UTC

Can anyone maximize this expression?

Postby BSaito » Thu Oct 29, 2009 3:10 pm UTC

I ran into a problem with a little personal project of mine, tried to model it mathematically and got stuck when the math became complicated. I need to find x to maximize the following expression:
Image
where x is less than or equal to n, n is an even number, and
Image

The problem keeps getting more complicated as I think of more factors I forgot to take into account in my model, but for now at least it seems to have settled on this form, so I thought I'd ask you more mathematically inclined xkcdians for help.

User avatar
BSaito
Posts: 25
Joined: Mon Oct 13, 2008 2:41 am UTC

Re: Can anyone maximize this expression?

Postby BSaito » Thu Nov 05, 2009 3:50 pm UTC

Perhaps this will elicit more interest if I give the problem itself.

Imagine a simple game in which n participants are each assigned a role as a sheep or a wolf. There are an equal number of sheep and wolves, and while each player knows which they are, they have no way of proving to other players. Players pair off, and receive a payoff 2p if their partner is a sheep (they get a meal or avoid being eaten), or no payoff if their partner is a wolf (they starve or get eaten). (For a zero sum game, each player pays an ante p before the game).

Imagine a strategy involving forming a team of x players, and splitting payoff equally between all team members. Each player reveals whether they are a sheep or wolf (They should have no reason to lie now, since their success is tied to the success of the team). All sheep players pair off so as to keep those positive payoffs within the team. If their are an odd number of sheep players and at least one wolf player on the team, the remaining sheep player pairs off with one of the wolf players. The remaining team members then form pairs outside the team in an attempt to bring greater payoff to the team by pairing with a sheep. Assume that the other players do not employ a similar strategy and form their own teams, and that team members pairing outside the team cannot do better than selecting a random non-team member.

How do you find the ideal team size to maximize expected payoff per team member?
Anonymous wrote:So... wait... evil exists because Satan was after tenure, and needed publications?

Douglas Adams wrote:You live and learn. At any rate, you live.

Niels Bohr wrote:Prediction is very difficult, especially about the future.

User avatar
Woxor
Posts: 506
Joined: Mon May 07, 2007 11:28 pm UTC

Re: Can anyone maximize this expression?

Postby Woxor » Thu Nov 05, 2009 4:43 pm UTC

That looks interesting, but yeah, it's pretty complicated! One thing that may or may not help is that min(a,b) can be rewritten as (a+b-|a-b|)/2. My instinct is to try to use that and the first derivative test (even though you're dealing with integers, it might give you a clue).

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Can anyone maximize this expression?

Postby HenryS » Thu Nov 05, 2009 5:18 pm UTC

Write some code and generate some data?

Presumably you can get numerical answers up to the biggest size of any real life game very easily.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Can anyone maximize this expression?

Postby Yakk » Thu Nov 05, 2009 6:09 pm UTC

This is mostly blather, with an unsupported conclusion at the end.

There are A sheep and B wolves in the team.

There are N/2-A sheep outside the team.
There are N/2-B wolves outside the team.

Expected value of a wolf on your team is then 2 * (N/2-A)/(N/2-X), excluding odd-sheep-wolves.

Expected value of a sheep on your team is 2, excluding odd-sheep.

Expected value of an odd-sheep is 1.

Adding a sheep grants 2 or 3 points to your team.
Adding a wolf, if you have 0 wolves, can add 2 points to your team if you have an odd-sheep. Otherwise, it adds 2 * (N/2-A)/(N/2-X) points. Note that this is bounded above by 2, and below by 0.

Let's eliminate odd sheep; your team has an even number of sheep and wolves. We can analyze the odd sheep case seperately.

Pairs of sheep generate 4 points; pairs of wolves generate 0 to 4 points. The value of wolves goes up if you have fewer sheep, and down if you have more sheep.

We could even allow for pairs of sheep, and any number of wolves.

The 0 wolf case is special, as in that case the odd sheep acts like a wolf.

Hmm. So ideally, your sheep would pair off perfectly. Your wolf expected value ends up being a counter-weight on the 'more sheep=more points' fact, but your sheep:wolf ratio doesn't change with size. The odd sheep is worth less than the even sheep; the impact (in terms of average points) for odd sheep is lower if your group is larger.

So, I'm guessing that the ideal size for the group is ... everybody, in order to reduce the odd-sheep penalty. Nothing else really varies systematically with group size, and is instead dominated by the luck of "did I get more sheep or more wolves".

Before going further and trying to prove this, I'd simulate it, and see if the expected score does go up (slightly) as you increase the size of the group. As this effect will (I expect) be quite small, random sampling isn't sufficient; exhaustively walk the possibilities for some relatively small cases.

I cannot see an elegant way to prove this. I might approach it by looking at the expected change from adding an additional group member to a group of size X with a pool of size N. (break that down into the expected change in average points when you add a sheep or a wolf, then break it down into A sheep and B wolves in your group, and then sum over the possibilities, and see if it simplifies...) But there really isn't any guarantee that it will look pretty.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Can anyone maximize this expression?

Postby Tirian » Thu Nov 05, 2009 6:41 pm UTC

Yakk wrote:So, I'm guessing that the ideal size for the group is ... everybody, in order to reduce the odd-sheep penalty.


I don't buy that. If all the players cooperate, then the corporate payoff is zero (all the sheep except an odd one win, all the wolves except an odd one lose). Imagine a team of two players. If they were both sheep, then they team up and both win. If they were a sheep and a wolf, then they could team up and break even. If they were two wolves, then they "play the field", which would have some positive expectation because there are more sheep than wolves in the field. So it would seem that a team of two dominates a team of everybody.

LLCoolDave
Posts: 165
Joined: Wed Apr 11, 2007 10:17 am UTC

Re: Can anyone maximize this expression?

Postby LLCoolDave » Thu Nov 05, 2009 7:09 pm UTC

Tirian wrote:
Yakk wrote:So, I'm guessing that the ideal size for the group is ... everybody, in order to reduce the odd-sheep penalty.


I don't buy that. If all the players cooperate, then the corporate payoff is zero (all the sheep except an odd one win, all the wolves except an odd one lose). Imagine a team of two players. If they were both sheep, then they team up and both win. If they were a sheep and a wolf, then they could team up and break even. If they were two wolves, then they "play the field", which would have some positive expectation because there are more sheep than wolves in the field. So it would seem that a team of two dominates a team of everybody.


Exactly the same argument I wanted to add. Well let's analyze the 3 person group:

Sheep, Sheep, Sheep has a value of 4 + X, X < 1 because there are more wolves left
3x Sheep, Sheep, Wolf has a value of 4 + X, X < 1 because there are more wolves left
3x Sheep, Wolf, Wolf has a value of a bit over 3 because the Sheep and Wolf can match and the lone Wolf has positive EV because there is one more sheep left
Wolf, Wolf, Wolf has a value of over 3 because each Wolf individually has a slightly positive expectation because there is more sheep than wolves left even if the other teammates grab a sheep.

So again, in all cases the EV of a three participants group is positive. Note that should you try a 3 person group in a field of 4 players only the middle two cases can happen, and the value is 4 in both cases.

In fact, let's calculate the value of a 2 person and a 3 person group with 4 players:
Group of two:
Sheep Sheep => 4
Wolf Wolf => 4
2x Sheep Wolf => 2, no matter if they pair up or not
So on average the group gets 3 points for 3/2 points per teammember

Group of three:
Sheep Sheep Wolf => 4
Sheep Wolf Wolf => 4
So on Average the group gets 4 points for 4/3 < 3/2 per teammember, so the two person group is the optimal choice for 4 Players. Not sure if this tells anything about the general case, I have a suspcious feeling the 2 person group may always be optimal.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Can anyone maximize this expression?

Postby Yakk » Thu Nov 05, 2009 7:58 pm UTC

Sure, adding wolves suck. If you can avoid adding wolves, you should. But I'm assuming the group is randomly selected from the original 50-50 supply.

This isn't a zero-sum game as described.

At low populations, due to the zero-wolf with odd-sheep case, things behave weird. (if you have no wolves in your group, and an odd number of sheep, that odd sheep 'acts like a wolf' in scoring, as it has to play the field and hope for a sheep -- even if there are few sheep remaining!)

Interesting; it might not be a good idea to always pair up the odd sheep even in the general case. Imagine if the 'field' only has sheep left; then 1 sheep and 1 wolf earns 4 points if they play the field, and only 2 if they pair up. Sheep-sheep pairs remain optimal (you cannot earn more than 4 points from 2 animals)

In a group of 20, 2 players:
50% sheep 1, then 45% sheep 2.
50% sheep 1, then 55% wolf 2
50% wolf 1, then 45% wolf 2
50% wolf 1, then 55% sheep 2.

50% * (.55 + .55) wolf+sheep
50% * 45% sheep sheep
50% * 45% wolf wolf
55% wolf*sheep
27.5% wolf^2
27.5% sheep^2

For wolf*sheep, we can earn 2 points by pairing, or an average of 1 point each by playing the field, for 1.0 average.
For wolf*wolf, 10/18 remaining are sheep, so they'll get 20/18 sheep, for 40/18 points, or 20/18 average.
Sheep*Sheep is 4/2.

2*.275 + 20/18*.275 + 1*.55 = 1.007355556 average points.

20 case:
20 points, 1.0 average.

19 case:
10/9 W/S is 16 points. 1 wolf kills the last sheep for 2. remaining sheep earns 2. 20/19 points is 1.0526 (beating the 2 case).
9/10 W/S is 20 points.

So group of 19 beats group of 20, because they have enough wolves to eat all of the free sheep guaranteed. Didn't account for that!

At 14, if you have 9 sheep and 5 wolves, you cannot eat every sheep guaranteed.
At 15, if you have 9 sheep, you have enough wolves to eat the last sheep in your group, and send the other 5 off to eat the remaining 5 critters. Any case with more sheep is 100% eat success, and any case with fewer sheep you have more wolves (and thus can guarantee you eat every sheep). Thus 15 has a score of 40/15, or 2 and 2/3.

It is possible that 14, even thought it cannot guarantee to be able to eat all of the free sheep, might beat 15.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Can anyone maximize this expression?

Postby Tirian » Thu Nov 05, 2009 8:16 pm UTC

Yakk wrote:This isn't a zero-sum game as described.


It is. There are equal numbers of sheep and wolves. Everyone takes a partner. If your partner is a sheep, you win p. If your partner is a wolf, you lose p.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Can anyone maximize this expression?

Postby Yakk » Thu Nov 05, 2009 8:42 pm UTC

Error in my earlier post: You get a total of 20 points, not 40, when you eat every sheep in a 20 population case.

Which hits 1 1/3 for the 15 sized group in a population of 20.

Tirian wrote:
Yakk wrote:This isn't a zero-sum game as described.


It is. There are equal numbers of sheep and wolves. Everyone takes a partner. If your partner is a sheep, you win p. If your partner is a wolf, you lose p.

From the second post:
or no payoff if their partner is a wolf (they starve or get eaten).

(For a zero sum game, each player pays an ante p before the game).

I took it being in brackets meaning that this is a variation (if you want it to be zero sum)? (bold mine)

However, given that you are averaging, maximisation of group and zero-sum will be quite similar. The interactions between individual players are not, however, zero-sum.

I think one way to approach this might be the calculus approach -- we presume that the individual sheep and wolves are infinitesimal compared to the total population. In that case, the group we select is guaranteed 50-50 (I think?).

Sheep become worth 2*|.| for a given length of sheep.
Wolves are worth 1*|.| so long as there are enough prey (as the

So a group of size 2/3 of the entire population gets (2/3 + 1/3) / (2/3) = 3/2 = 1.5 average score.

Smaller populations get the same score. Larger populations get less average score.

Can we show that no strategy on discreet sheep and wolves can manage better than this 1.5 average?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Can anyone maximize this expression?

Postby lordatog » Thu Nov 05, 2009 9:33 pm UTC

Are we to assume that our wolves can always find a partner outside the team if possible? That is, if our team has 10 wolves and there are a total of 10 people outside our team, do we disregard the possibility that some of them might match up with each other, leaving some of our wolves unable to earn points?

User avatar
BSaito
Posts: 25
Joined: Mon Oct 13, 2008 2:41 am UTC

Re: Can anyone maximize this expression?

Postby BSaito » Tue Nov 10, 2009 3:37 pm UTC

lordatog wrote:Are we to assume that our wolves can always find a partner outside the team if possible? That is, if our team has 10 wolves and there are a total of 10 people outside our team, do we disregard the possibility that some of them might match up with each other, leaving some of our wolves unable to earn points?


Good point. Let's put in the same category as "other players may be employing the same strategy" and ignore it for now.
Anonymous wrote:So... wait... evil exists because Satan was after tenure, and needed publications?

Douglas Adams wrote:You live and learn. At any rate, you live.

Niels Bohr wrote:Prediction is very difficult, especially about the future.


Return to “Mathematics”

Who is online

Users browsing this forum: Exabot [Bot] and 7 guests