Game with Chairs (and possible ties to economic mobility)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Game with Chairs (and possible ties to economic mobility)

Postby Cradarc » Wed Jun 03, 2015 5:38 am UTC

The Game:
There are N players. There are N seats lined up in a row, numbered consecutively.
Each player is assigned a unique integer from the set [1,N]. Each seat is also assigned a unique integer from the set [1,N]. V(j) will denote the value assigned to seat j.

Each seat is equipped with a random integer generator. The generator for seat j draws from the set [0, j+P(j)], where P(j) is the number assigned to the person currently sitting in the seat. The distribution is uniform so each number has an equal chance of being chosen.
At the start of the game, the everyone is seated in some random permutation in the seats. Every round, a chime will sound, directing each person to pick a random number using the generator on their seat.

- If the number drawn is 0, the person occupying the seat must stand up and walk away.
- Anybody who did not draw 0 will then have the option to move into an unoccupied seat directly adjacent to the seat they are sitting in. The person sitting in the highest valued seat gets to moves first, followed by the person sitting in the next highest valued seat, etc.
- Once everyone has finished moving, the people who stood up will fill the remaining seats. They are allowed to choose which seat they take, but someone who had left a higher valued seat gets priority over someone who had left a lower valued seat. (Note that this means the last person doesn’t actually have a choice since there will only be one free seat left.)

At the beginning of every round (before the chime), each player’s score is incremented by the value of the seat they are sitting in. The goal of every player is to accumulate as many score points as possible.

The Question
The game is considered “fair” if the standard deviation of the scores become small as the number of rounds increases.
The game is considered “well-correlated” if, for all j, the player who is assigned the value j has a tendency to stay in the vicinity of the jth seat (which may not be the seat with value j).
Is there a way to define V(j) to maximize fairness and correlation?


The players can be seen as different people in society. The number they are assigned is their relative talents/capabilities.
The seats represent jobs. The number of the seat represent the talent/capabilities that the job is suited for. The value assigned to each seat is the salary or the influence that comes with having the job.
An ideal system will match people with jobs that allow them to use their talents fully. It will also make sure the distribution of wealth and power is as uniform as possible.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Game with Chairs (and possible ties to economic mobility

Postby quintopia » Tue Jun 09, 2015 2:03 pm UTC

The thing that makes it a hard problem is the fact that V(j) does not depend on the number of the person sitting in it, like the value of a job might do in real society. However, since we have perfect information, allowing it in this case would obviously make the problem trivial.

What makes it impossible is the fact that we are optimizing for two measures simultaneously which clearly vary differently for different choices of V. Which is more important? How much should each measure be weighted? Tell us how to combine these two properties into a single number and it may become a problem that is actually able to be solved. It will still be difficult.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Game with Chairs (and possible ties to economic mobility

Postby Cradarc » Thu Jun 11, 2015 7:20 pm UTC

Hope this helps:

Correlation
After every round there is a person in every seat. Sum over all seats the product of the person's value with the number of the seat they occupy.
That is, Sum(j = 1 to N){j*P(j)}. Divide this with the maximum possible correlation ( Sum(j = 1 to N){j2} )to get a value in [0,1]. As the number of rounds increase, the correlation should form a roughly Gaussian distribution. We will use the mean, U, of this distribution for the metric.

Fairness
Every round, a total of T = N(N+1)/2 score points is awarded. Let S(k, r) be the points awarded to player k on round r. Define the normalized score of person k over R rounds as NS(k) = sum(r = 1 to R){S(k,r)/(R*T)}. The distribution of NS(k) over all k should be roughly Gaussian as N becomes large. We will use the standard deviation, Z, of this distribution for the metric.

U and Z are both restricted to [0,1]. We want to minimize Z while maximizing U. So a reasonable combined metric would be M = U/Z.


I've fiddled around with the problem on paper for small N, but haven't gotten around to writing a computer simulation for it.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
measure
Posts: 123
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Game with Chairs (and possible ties to economic mobility

Postby measure » Fri Jun 12, 2015 2:38 pm UTC

Firstly, am I correct in understanding that V(j) produces only integer values in [1,N] and that every value is used exactly once, so that there are N! possible ways of defining V(j)?

Secondly, as far as individual strategy for simulation, it seems that the naive strategy of always moving to the highest-valued available seat at every opportunity is less than optimal for some V(j). Any thoughts on more intelligent strategies?

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Game with Chairs (and possible ties to economic mobility

Postby Cradarc » Sat Jun 13, 2015 6:19 pm UTC

measure wrote:Firstly, am I correct in understanding that V(j) produces only integer values in [1,N] and that every value is used exactly once, so that there are N! possible ways of defining V(j)?

Yes.

measure wrote:Secondly, as far as individual strategy for simulation, it seems that the naive strategy of always moving to the highest-valued available seat at every opportunity is less than optimal for some V(j). Any thoughts on more intelligent strategies?

That's a very good point. I've been assuming the naive strategy, but it's totally possible that people are willing to make "sacrifices" to have a better shot at long-term gain. I guess you would need some metric function to calculate the probability of moving up or down a seat for any given V(j) configuration.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Game with Chairs (and possible ties to economic mobility

Postby quintopia » Wed Jun 24, 2015 5:37 am UTC

It was never obvious for me that the naive strategy is suboptimal. I considered a person with a high-value seat intentionally moving to the lowest value seat when ousted so as to maximize their chances of getting up again soon, but if he did that, he'd get last pick every time, and never advance EXCEPT one chair to the right at a time. So if there's an alternate strategy to the naive one that improves upon it, I'd love to see it. (The reason the naive strategy seems optimal to me is that once one has a high-valued seat, one is unlikely to have to vacate it, and when it does happen, one won't have to move very far back in value.)

EDIT: wait, no, I see it now. One might consistently choose a low-valued seat that is directly adjacent or very near to a high-valued seat, hoping to be able to advance to that seat when its occupant gets unlucky. Since this is the only scenario I can imagine, I suspect that the naive strategy IS optimal when V(j) is monotonic. But I've been assuming monotonicity because it seems the most likely means to achieve well-correlatedness.


Return to “Mathematics”

Who is online

Users browsing this forum: Google [Bot] and 2 guests