Some points on balancing games:

One way to make individual games more balanced would be to ensure that everyone
played the same number of games, and if possible, the same games. Regardless,
the overall tournament is balanced if players are treated indistinguishably:
however, balancing games requires fewer lifetimes to analyze.

My simplest recommendation is this: suppose that there are 9 players. Every
three rounds, we generate one game, and break the nine players up into three
groups. Then, each of these groups plays the game. We repeat. While there is
bias in terms of who you play with, at least everyone is playing the same game
every round.

So, you ask, why not just run every triple of players every round, shuffling all
games played? There are two reasons: first, if we do it in the same order every
round, this may give an advantage to people who play earlier (or later? not
sure): regardless, the detailed order on every round becomes a source of
asymmetry (at least within a lifetime) if we are not careful.

An alternative might be to consider some sort of lockstep sorting, such that any
two players have each played the same number of games before any game in which
they play. This becomes complicated, because if you figured out you played X and
Y, and then played Y and Z, you might know you play X and Z on the next round.

If the number of players divides by three, then the above method seems perfect:
if you have 3k+1 or 3k+2 players, then you leave out 1 or 2 players respectively
every k rounds. You have to select this player left out independently every k
rounds or you run into problems. Regardless, this reduces the likelihood of
being left with no rounds on the first k rounds: e.g., if there are 8 players,
then k=2, so you have a 2/8 chance of being left out of  the first 2 rounds. On
the other hand, if I were draw 3 of 8 bots randomly each round, then you would
have a 5/8 * 5/8=39% chance of being left out instead of a 25% chance.
Therefore, this method reduces variance of number of rounds played, increases
the similarity in games played between players, and gives no additional
information regarding the identities of your opponents.

Comments?

I agree that lifetimes should be limited to some, K, number of games and then
the players should be reset.  This ensures that any impact that an agent's
learning has on its performance is averaged over the range of possible
circumstances under which it could have started learning.  Although I like the
idea of rewarding agents who learn faster, I agree with Marty's proposal to have
fairly long lifetimes in order to ensure that learning for each agent either
stagnates or goes into a cycle.  Having shorter lifetimes would reward faster
learning, but I feel that it's more important to ensure that learning has
stopped before resetting the agents, or else it would prompt the question of
whether the results would be different if only the agents had played more games
per lifetime.

I also want to point out that while I expect that learning will generally
benefit agents, that may not always be the case.  I can imagine scenarios where
learning agents adapt their behavior around the unresponsive behavior of a
non-learning agent, resulting in a benefit to the non-learner.  I hope that at
least 1 or 2 non-learners are in the next competition so that we can see how
learners and non-learners interact over time.

Reducing the number of rounds, N, in a game appears to have several advantages. 
As Wunder observes, many games reach a state where agents continue to play in
the same positions, or enter into a repeating cycle.  Continuing the game once
agent behavior has calcified diminishes the relative impact of early rounds and
makes the results of the game potentially more lopsided if two agents enter a
sustained cooperative pattern that hurts the 3rd agent.  Shorter games will also
reward learning agents for learning faster, which I've already mentioned seems
like a quality that should be rewarded.

It is outside the focus of our discussions about the next tournament, but as
Marty pointed out, reducing the number of rounds to 20 also opens the
possibility of involving human agents (who will be less likely to lose interest
during a shorter game).  I'll admit that I've invited friends to play against my
agents as a sort of proof-of-concept test, and that I (purely by coincidence)
lowered the number of rounds to 20 with the aim of keeping the humans from
losing interest.  I imagine some interesting possibilities for shorter games,
such as getting people on Amazon's Mechanical Turk to play against each other
and collecting statistics about their behavior.





--- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@...> wrote:
>
> Everyone is WELCOME to respond. Committee members are OBLIGATED to respond.
>
>
> So, while everything is up for discussion, three key items for discussion are
N, K, game distribution, time to compute, and anonymity.
>
>
> Let me begin by explaining a format, and then explain what I hope to resolve.
>
> First, let me define a round to be when three players submit actions
simultaneously and then observe each other's actions and receive utility. A game
consists of N rounds played between the same players and the same utilities. A
lifetime consists of K games.
>
> The major change is that, during a lifetime, there are no resets to players.
Between lifetimes, all players are reset. This gives players an opportunity to
learn about what different types of behavior exist in the environment. However,
the other players are anonymous. This means that it is difficult to model
another individual player.
>
> The number of lifetimes required to obtain statistically significant results
may be daunting. Thus, I would like to have lifetimes be short: less than an
hour at most. If we get 8 submissions, then you get approximately 7.5 minutes to
learn. On a modern machine, this is a lifetime.
>
>
> What I hope to gain from all this is to make the competition less subject to
preliminary guesses by the players. Lifelong learning rewards teams that have a
broader understanding of what other intelligent agents might play like.
>
>
>
> As Tom has suggested, there are no rounds that "don't count". I am not going
to take up why bots that would play for fun would be really cool, but I can
accept this based on the argument that it makes things more complex. Secondly, I
agree (sadly) that changing the game distribution and the structure
simultaneously may be overkill. I think that making this about lifelong learning
focuses efforts.
>
>
> I also want to address Wunder's suggestion. First of all, I want to be
shuffling opponents as fast as utilities. I don't have a fancy argument for
this, it is just a simpler game design. However, Wunder has pointed out in the
past that games often "end" earlier than 100 rounds. Thus, one suggestion might
be to reduce N from 100 to 20. This will balance out the advantage of being
chosen to play early,  as well as allow for a larger K, which should make
learning easier, and emphasize learning about the other players in general. I
think this also pushes the game closer to a game which would be of interest to
humans.
>

Overall I like Marty's proposal.  It meets my usual criteria for good
competition changes: (1) there is a plan for how the results will have
statistically significant meaning, and (2) change is added incrementally so that
we can understand the affect of the additional complexity.  Focusing on
population-level learning seems like a good choice to me.

I only have one concern with this original proposal which is dropping N from 100
to 20.  Even if it only takes a handful of rounds for teams to settle and things
remain static after that, it doesn't mean we can drop N to 20.  N is what is
reward collusive behavior.  The more rounds you have to benefit from being part
of some collusion the more important it is to be in on it.  Alternatively, why
not require a time-limit on games rather than decisions, that would allow bots
to think hard for a few rounds, but then the remaining "static" rounds could
still be played out quickly.  Tom seems to point out the same thing as a
positive reason to drop N to 20, but I still see it as negative.  It would seem
to be violating my rule (2) above, as the results of the competition would now
be both about short cooperation times *and* lifetimes, not just the addition of
lifetimes.

Marty's follow-up post discusses some variance reduction options.  Mainly
focusing on the fact that the sampling of the utilities are adding in a sort of
variance, and sharing the order of games across each bot's lifetime may result
in substantial variance reduction (and thus need fewer lifetimes for statistical
significance).  But, if I try to think of the main source of variance that comes
from utilities it's that some games might have large sum of utilities (so that
all players benefit).  Why not simply subtract off the total utility on the
island (divided by 3) so that a game's scores are how much over the average the
player achieved.  This is essentially variance reduction through control
variates, and so is unbiased.  And it seems to get most of the advantage that
Marty's suggested complicated scheduling scheme provides, without any of the
complication.

I recommend having a poll on the details of the competition. Below is a response
to Michael B's comments. I will send some preliminary suggestions as to what we
need to poll.


First of all, I think Michael B. and Michael W. points are both valid about the
value of N.


Secondly, I think Michael B. is correct that subtracting off the average utility
of the game is appropriate. Let us call this difference the net utility. I would
additionally average by number of games (so if Alice plays 10 games and gets
900, and Bob plays 8 games and gets 800, then Bob gets 100, Alice gets 90, and
Bob wins). Key is the control variates point Michael makes: the objective is
still to maximize utility per game.

Thirdly, Michael points out correctly that these adjustments can improve
analysis without changing the game. However, my point about balancing the number
of games played was ABOUT changing the game, at least a bit. I feel that it is
fairer to keep the number of games played to be roughly equal. This focuses
players on the lifelong learning: they can assume that other players are roughly
as "old" as they are.

The following is subject to approval by the rest of the committee. I think that
the structure recommended here is appropriate. I have included options which I
believe are reasonable, and I feel that the committee may wish to add or remove
options. I think that these questions impact the competition, but it is unclear
whether for good or ill.

I recommend instant runoff voting between all previously entered teams. From
wikipedia:

http://en.wikipedia.org/w/index.php?title=Instant-runoff_voting&oldid=441951647

"Voters rank candidates in order of preference, and their ballots are counted as
one vote for their first choice candidate. If a candidate secures a majority of
votes cast, that candidate wins. Otherwise, the candidate with the fewest votes
is eliminated. A new round of counting takes place, with each ballot counted as
one vote for the advancing candidate who is ranked highest on that ballot. This
process continues until the winning candidate receives a majority of the vote
against the remaining candidates."

Here, candidates are options: (A,B,...) The options are independent. After the
structure of the game is decided, we will try to estimate the number of repeats
required and get the resources for that.

Amongst those things that I believe that there is little question, but I feel
strongly about:
5. Players are anonymous
6. There is no indication of how many different players exist.

This encourages to learn about the domain.


Here are four questions on the structure.

1. What should N be?
A. 20
B. 100

2. On average, how many rounds should a single player play in a lifetime? I.e.,
what should K x N/(3 x # players) be?
A. 5000 Rounds
B. 10,000 Rounds
C. 20,000 Rounds
D. 50,000 Rounds
E. 100,000 Rounds

With 100,000 rounds per player, that is 1000 games given option B above, or
seeing EVERY other player about 250 times, assuming 9 teams.

3. How much time in minutes should a player have in a lifetime?
A. 3 minutes
B. 4 minutes
C. 5 minutes
D. 6 minutes
E. 7 minutes
F. 8 minutes (assuming 8 players, this is roughly 1 hour per game).

4. Should we use randomly match players independently every game, or use a trick
to reduce the variance in the number of games and type of games played? NOTE:
there is still no self-play.
A. Randomly match independently every round.
B. Block off M=floor(# players/3) games, and draw independently without
replacement within every M games. Also, round # games played to multiple of M.


If I were to vote on the above options, it would be:
1. B,A (prefer 100 rounds to 20 rounds)
2. B,C,D,A,E (I think that 100 games of 100 rounds is ideal: enough to get an
idea, but not enough to try to model every other player exactly.
3. A,B,C,D,E,F (From a designers perspective, 3 minutes should be MORE than
sufficient, but I don't want to pigeonhole design to aggressively.
4. B,A

Let us take alternative questions or different answers by Wednesday. I would
also accept it if people feel that these answers need to be answered over time:
e.g., maybe 1 needs to be answered before 2, and 2 needs to be answered before
3.

Starting Thursday, please post responses.

-Marty

First of all, well done Marty on making these proposals open for a vote, and
thank-you to Michael B., Michael W. and Tom for driving the discussion so far. 
Although I am not convinced that lifelong learning is the best next step for the
tournament (and I'll reserve my opinion on that), I also think that it is far
from the worst.  So, in light of others' interest in this particular direction,
I am happy to see the tournament take this step.

Regarding the specific questions at hand, and before we vote on the proposals:

   i) I think that we need to decide on 1, 2 and 3 sequence; 1 then 2 then 3. 
This is because my personal preference on 3 depends on our decision on 2, and 2
on our decision on 1.

   ii) On 5 Anonymity and 6 Knowledge of the total number of players -- I agree
with Marty, they should remain as they are for the next version of the game.

On the vote itself, can I suggest a small perturbation to the voting rule.  As
someone who has grown up with IRV/STV, I suggest that we use an optional
preferential voting scheme -- where a voter does not need to rank every item on
the ballot.  This provides for a vote to be exhausted when a voter has no
preference over lower ranked outcomes (as many of us may have for some of the
candidates in questions 2 and 3).

Regards,
Archie Chapman


--- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@...> wrote:
>
> Let us take alternative questions or different answers by Wednesday. I would
also accept it if people feel that these answers need to be answered over time:
e.g., maybe 1 needs to be answered before 2, and 2 needs to be answered before
3.
>
> Starting Thursday, please post responses.
>
> -Marty
>

I have no problem with people expressing indifference beyond a certain number of
options. I think that this could improve the outcome.

I think that these are good suggestions. However, they would imply a fairly
rapid sequence of votes: first vote (handling 1 and 4) due Friday August 5th
midnight PDT.

Second vote (question 2) due Tuesday August 9th midnight PDT.
Third vote (question 3) due Friday August 12th midnight PDT.

Does the rest of the committee have an opinion on this?

-Marty

--- In lemonadegame@yahoogroups.com, "Archie" <acchapman@...> wrote:
>
> First of all, well done Marty on making these proposals open for a vote, and
thank-you to Michael B., Michael W. and Tom for driving the discussion so far. 
Although I am not convinced that lifelong learning is the best next step for the
tournament (and I'll reserve my opinion on that), I also think that it is far
from the worst.  So, in light of others' interest in this particular direction,
I am happy to see the tournament take this step.
>
> Regarding the specific questions at hand, and before we vote on the proposals:
>
>   i) I think that we need to decide on 1, 2 and 3 sequence; 1 then 2 then 3. 
This is because my personal preference on 3 depends on our decision on 2, and 2
on our decision on 1.
>
>   ii) On 5 Anonymity and 6 Knowledge of the total number of players -- I agree
with Marty, they should remain as they are for the next version of the game.
>
> On the vote itself, can I suggest a small perturbation to the voting rule.  As
someone who has grown up with IRV/STV, I suggest that we use an optional
preferential voting scheme -- where a voter does not need to rank every item on
the ballot.  This provides for a vote to be exhausted when a voter has no
preference over lower ranked outcomes (as many of us may have for some of the
candidates in questions 2 and 3).
>
> Regards,
> Archie Chapman
>
>
> --- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@> wrote:
> >
> > Let us take alternative questions or different answers by Wednesday. I would
also accept it if people feel that these answers need to be answered over time:
e.g., maybe 1 needs to be answered before 2, and 2 needs to be answered before
3.
> >
> > Starting Thursday, please post responses.
> >
> > -Marty
> >
>

I'm not sure if you're asking for this, but I approve of the voting format.  If
others want the votes to be done in a particular order, that's fine by me as
well.

My votes are:

1) B, A
2) B, C, A, D, E
3) I have no preference... I have preferences on orders of magnitude, but
there's not an order of magnitude between the options.
4) A, B

Great, my votes are:

1. B
4. B

Archie

--- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@...> wrote:
>
> I have no problem with people expressing indifference beyond a certain number
of options. I think that this could improve the outcome.
>
> I think that these are good suggestions. However, they would imply a fairly
rapid sequence of votes: first vote (handling 1 and 4) due Friday August 5th
midnight PDT.
>
> Second vote (question 2) due Tuesday August 9th midnight PDT.
> Third vote (question 3) due Friday August 12th midnight PDT.
>
> Does the rest of the committee have an opinion on this?
>
> -Marty
>
> --- In lemonadegame@yahoogroups.com, "Archie" <acchapman@> wrote:
> >
> > First of all, well done Marty on making these proposals open for a vote, and
thank-you to Michael B., Michael W. and Tom for driving the discussion so far. 
Although I am not convinced that lifelong learning is the best next step for the
tournament (and I'll reserve my opinion on that), I also think that it is far
from the worst.  So, in light of others' interest in this particular direction,
I am happy to see the tournament take this step.
> >
> > Regarding the specific questions at hand, and before we vote on the
proposals:
> >
> >   i) I think that we need to decide on 1, 2 and 3 sequence; 1 then 2 then 3.
This is because my personal preference on 3 depends on our decision on 2, and 2
on our decision on 1.
> >
> >   ii) On 5 Anonymity and 6 Knowledge of the total number of players -- I
agree with Marty, they should remain as they are for the next version of the
game.
> >
> > On the vote itself, can I suggest a small perturbation to the voting rule. 
As someone who has grown up with IRV/STV, I suggest that we use an optional
preferential voting scheme -- where a voter does not need to rank every item on
the ballot.  This provides for a vote to be exhausted when a voter has no
preference over lower ranked outcomes (as many of us may have for some of the
candidates in questions 2 and 3).
> >
> > Regards,
> > Archie Chapman
> >
> >
> > --- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@> wrote:
> > >
> > > Let us take alternative questions or different answers by Wednesday. I
would also accept it if people feel that these answers need to be answered over
time: e.g., maybe 1 needs to be answered before 2, and 2 needs to be answered
before 3.
> > >
> > > Starting Thursday, please post responses.
> > >
> > > -Marty
> > >
> >
>

So far, there were three voters: Michael B., Archie C., and myself.
To help this out a bit, I am extending voting on Question #2 until Friday. Note
that it has been slightly rewritten below, due to a miscalculation on my part.
Michael B., feel free to re-vote.

Also, this means that there is a factor of 30,000 difference between the highest
and lowest lifetimes. Thus, depending on how you feel about learning, it is
important to consider how you feel about this.


This yields:
1. B 100 rounds
4. B (Archie+myself v. Michael B.) Block off M=floor(# players/3) games, and
draw independently without replacement within every M games. Also, round # games
played to multiple of M.

Now, I am taking this opportunity to fix Question #2. The problem was that I
miscalculated: you do not play K x N/(3 x # players) rounds, you play K x N x
3/(# players), meaning I was off by a factor of 9 on the length of a lifetime.
Thus, I will rewrite Question #2, and adjust the meanings appropriately.

2. On average, how many rounds should a single player play in a lifetime? The
expected number of rounds a single player would expect to play in a lifetime is
K x N x 3/(#players), or:
A. 45,000 Rounds (K = 150 x #players)
B. 90,000 Rounds (K = 300 x #players)
C. 180,000 Rounds (K = 600 x #players)
D. 450,000 Rounds (K = 1500 x #players)
E. 900,000 Rounds (K = 3000 x #players)
F. 3,000 Rounds (K = 10 x #players)
G. 6,000 Rounds (K = 20 x #players)
H. 9,000 Rounds (K = 30 x #players)
I. 27,000 Rounds (K = 90 x #players)

So, here is the story: I think that playing 900 games is more than sufficient to
get a basic idea of the nature of your competitors. I think that 9,000 games is
way too many. My voting is:

2. B,C,D,A,E,I,H,G,F

My vote (preference first) is:
1: A, B
2: C, B, A, D, E
3: A, B, C, D, E, F
4: B, A

I also vote to keep 5 and 6 unchanged from previous games.

-Tom

--- In lemonadegame@yahoogroups.com, "Archie" <acchapman@...> wrote:
>
> Great, my votes are:
>
> 1. B
> 4. B
>
> Archie
>
> --- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@> wrote:
> >
> > I have no problem with people expressing indifference beyond a certain
number of options. I think that this could improve the outcome.
> >
> > I think that these are good suggestions. However, they would imply a fairly
rapid sequence of votes: first vote (handling 1 and 4) due Friday August 5th
midnight PDT.
> >
> > Second vote (question 2) due Tuesday August 9th midnight PDT.
> > Third vote (question 3) due Friday August 12th midnight PDT.
> >
> > Does the rest of the committee have an opinion on this?
> >
> > -Marty
> >
> > --- In lemonadegame@yahoogroups.com, "Archie" <acchapman@> wrote:
> > >
> > > First of all, well done Marty on making these proposals open for a vote,
and thank-you to Michael B., Michael W. and Tom for driving the discussion so
far.  Although I am not convinced that lifelong learning is the best next step
for the tournament (and I'll reserve my opinion on that), I also think that it
is far from the worst.  So, in light of others' interest in this particular
direction, I am happy to see the tournament take this step.
> > >
> > > Regarding the specific questions at hand, and before we vote on the
proposals:
> > >
> > >   i) I think that we need to decide on 1, 2 and 3 sequence; 1 then 2 then
3.  This is because my personal preference on 3 depends on our decision on 2,
and 2 on our decision on 1.
> > >
> > >   ii) On 5 Anonymity and 6 Knowledge of the total number of players -- I
agree with Marty, they should remain as they are for the next version of the
game.
> > >
> > > On the vote itself, can I suggest a small perturbation to the voting rule.
As someone who has grown up with IRV/STV, I suggest that we use an optional
preferential voting scheme -- where a voter does not need to rank every item on
the ballot.  This provides for a vote to be exhausted when a voter has no
preference over lower ranked outcomes (as many of us may have for some of the
candidates in questions 2 and 3).
> > >
> > > Regards,
> > > Archie Chapman
> > >
> > >
> > > --- In lemonadegame@yahoogroups.com, "Marty" <martinzinkevich@> wrote:
> > > >
> > > > Let us take alternative questions or different answers by Wednesday. I
would also accept it if people feel that these answers need to be answered over
time: e.g., maybe 1 needs to be answered before 2, and 2 needs to be answered
before 3.
> > > >
> > > > Starting Thursday, please post responses.
> > > >
> > > > -Marty
> > > >
> > >
> >
>

Doesn't the number of needed rounds depend on the number of players?  Or at
least it could.

When you say 900 rounds is enough.  If there were 10000 entries, then in 900
rounds you may never see the same player twice.  Since it's anonymous you would
never know this, but if one entry gives you no information about the other entry
then you wouldn't actually be able to learn anything about your last match from
the 899 that preceded it (in probability).  Now, since we're all researchers,
and we probably think in similar fashions, knowing what 1798 other researchers
did for their entries would tell you about the next two, so maybe this is fine.

And we're not exactly going to get 10000 entries.  And for anywhere between 6
and 60, you'll see substantial repeats in 900 rounds.

My vote:
2. B, C, A, I, D, H, E, G, F

Polling closes TONIGHT, so get your votes in.

--- In lemonadegame@yahoogroups.com, Michael Bowling <bowling@...> wrote:
>
> Doesn't the number of needed rounds depend on the number of players?  Or at
least it could.

So, my answer to this question informs the rest. I am not assuming that people
will try to learn individual players, but try to understand what people are like
in general.


> When you say 900 rounds is enough.
I think 900 games is enough, not 900 rounds.

> Now, since we're all researchers, and we probably think in similar fashions,
knowing what 1798 other researchers did for their entries would tell you about
the next two, so maybe this is fine.

EXACTLY.


>
> And we're not exactly going to get 10000 entries.  And for anywhere between 6
and 60, you'll see substantial repeats in 900 rounds.

Players are anonymous, but it is possible that after 20 rounds or so you might
identify a specific opponent. Is that too late to do anything about it?
Possibly...

OK, so here is the voting. All early voters have submitted votes for later
questions as well (or expressed indifference).



1. What should N be?
1. B 100 rounds
2. On average, how many rounds should a single player play in a lifetime? The
expected number of rounds a single player would expect to play in a lifetime is
C. 180,000 Rounds (K = 600 x #players)
3. How much time in minutes should a player have in a lifetime?
A. 3 minutes
4. Should we use randomly match players independently every game, or use a trick
to reduce the variance in the number of games and type of games played? NOTE:
there is still no self-play.
B. Block off M=floor(# players/3) games, and draw independently without
replacement within every M games. Also, round # games played to multiple of M.



Martin Zinkevich

1. B,A
2. B,C,D,A,E,I,H,G,F
3. A,B,C,D,E,F
4. B,A

Jay Pujara (August 8th)

1. b,a
2. e,d,c,b,a
3. c,b,a,d,e
4. a,b

Michael Bowling

1) B, A
2. B, C, A, I, D, H, E, G, F
3) I have no preference... I have preferences on orders of magnitude, but
there's not an order of magnitude between the options.
4) A, B


Tom Goff

My vote (preference first) is:
1: A, B
2: C, B, A, D, E
3: A,
B, C, D, E, F
4: B, A
Archie Chapman
1. B, A
2. C, B, A
3. No preference.
4. B, A

Elimination on 2
2. e,d,c,b,a Jay
2. B,C,D,A,E,I,H,G,F Marty
2. B, C, A, I, D, H, E, G, F Michael B.
2: C, B, A, D, E Tom
2: C,B,A Archie Chapman

2. e,c,b Jay
2. B,C,E Marty
2. B, C, E Michael B.
2: C, B, E Tom
2: C,B Archie Chapman

2. c,b Jay
2. B,C Marty
2. B, C Michael B.
2: C, B Tom
2: C,B Archie Chapman

2: C

2. On average, how many rounds should a single player play in a lifetime? The
expected number of rounds a single player would expect to play in a lifetime is
C. 180,000 Rounds (K = 600 x #players)

Elimination on 3:

3. A,B,C,D,E,F Marty
3: A, B, C, D, E, F Tom
3. c,b,a,d,e Jay
3. indifferent Archie
3. indifferent Michael B.

3. A Marty
3: A Tom
3. c Jay
3. indifferent Archie
3. indifferent Michael B.

3. A
3. How much time in minutes should a player have in a lifetime?
A. 3 minutes

Given the outline presented in the voting, I will work over the next month on
creating a beta version of the code, to be released October 1st. By November
1st, I hope that this code will be finalized.

Each player is an object of a class implementing the interface LifelongStrategy:


public interface LifelongStrategy{
   public void newGame(Game g, int iterations);
   public void observeOutcome(int[] actions);
   public int getAction();
}

In addition, a class must provide a constructor with the signature

(GameInformation info, long seed, String options)

Seed is a random seed, options is a string passed on the command line (in
competition, it is an empty string, and GameInformation is something I haven't
figured out. It could conceivably include:

1. The number of rounds in a game (this seems obvious)
2. The number of players
3. The number of games (total or estimated per player)
4. The game generator

Of course, the number of rounds, the estimated rounds per player, and the game
generator reveal nothing, as we have already agreed upon all these things. The
number of players reveals more information, and I don't believe it should be
added.

LifelongStrategies should not have their own threads and should not require too
much memory.

If there is any feedback on this interface, please post to this list.

-Marty

OK, so the alpha version of the code is on the web:

http://martin.zinkevich.org/lemonade/code/LSG2012.tar.gz

I will close the features by October 1st, and accept bug reports by November
1st.

Key changes:

1. I included the number of players in the game information. This was a side
effect of the way I was using GameInformation. Does it matter?

2. I did NOT include the GameGenerator, because there is no way to set the seed
of a Game Generator such that it gives new behavior. Thus, giving a copy of a
game generator would give you access to the ACTUAL SEQUENCE OF GAMES. This would
be bad. I may adjust the game generator interface to have a setSeed() function,
which could be helpful in a variety of ways.

3. I have not incorporated any Observer() pattern for a lifelong game. I will
try to incorporate this soon.

4. The output of the competition is human readable, but not very
machine-readable.


However, the structure of the competition itself is fairly solidified. Please
start your testing!

-Marty

TAC has decided to keep LSG as an affiliated competition. TADA (their associated
conference) is located at AAMAS this year, which is in Valencia, Spain, June
4th-8th.

LSG folks could also congregate at AAAI: this is in Toronto, CA: July 22-26. The
vague idea in my head right now is to have a workshop with poker: unclear how
exactly to phrase it. In order to have a good workshop, though, you need at
least 10 submissions.

I want to understand how many people could make it to Valencia. If we can only
get two people there, it is of little value. On the other hand, creating a
critical mass for AAAI would be difficult.

My big question is:

1. Would you be willing to go to Toronto?
2. Would you be willing to go to Valencia?

I'll start an informal poll. Please let me know quickly so we can figure this
out next week.

-Marty

The following lemonadegame poll is now closed.  Here are the
final results:


POLL QUESTION: Based on previous post (generalizing game versus lifelong
learning), which applies to you?

NOTE: 1 VOTE PER TEAM

Competition Deadline: JULY 1ST, 2011

OK, same interface and guidelines as 2010. EXCEPT, instead of passing the
vanilla Lemonade Stand Game in the constructor, I will pass a modified utility
function, with the following property. Every position on the clock face will
have a different number of people looking for lemonade, between 1 and 3. Each
person will go to each of the closest lemonade stands with equal probability.
The utility of a position is the expected number of people who go there (times 6
to make it an integer).

If you want changes, please post to the group.

-Marty

CHOICES AND RESULTS
- I like the competition draft, I want to compete, 2 votes, 50.00%
- I want to see changes, but I will compete., 1 votes, 25.00%
- I will not compete unless I see changes., 1 votes, 25.00%
- I will not compete., 0 votes, 0.00%



For more information about this group, please visit
http://groups.yahoo.com/group/lemonadegame

For help with Yahoo! Groups, please visit
http://help.yahoo.com/l/us/yahoo/groups/original/members/forms/general.html

Enter your vote today!  A new poll has been created for the
lemonadegame group:

I want to understand who from the community would be able to attend a
workshop in Toronto versus in Spain. Neither of these is a guarantee to exist.


AAMAS: I would be able to attend the TADA workshop at AAMAS in Valencia, Spain,
June 4-8
AAAI: I would be able to attend a AAAI workshop in Toronto, Canada, July 22-26

-Marty

   o AAAI or AAMAS
   o AAAI, not AAMAS
   o AAMAS, not AAAI
   o neither


To vote, please visit the following web page:
http://groups.yahoo.com/group/lemonadegame/surveys?id=3069635

Note: Please do not reply to this message. Poll votes are
not collected via email. To vote, you must go to the Yahoo! Groups
web site listed above.

Thanks!

I released a beta version. Still more changes to come, will wrap up by November
1st. Bug reports are welcome (post here or e-mail me) until December 1st.


-Marty

The final release of the code is tomorrow. There have been no complaints about
the beta version, so the beta will just become the release version unless anyone
has an issue today.

Now is the time to start on your bot! Lifelong learning by the yule log! Eight
days and nights of lifelong learning! Kwanzaa, a celebration of unity of
multi-agent systems! Or you can do something unconventional like spend quality
time with your family. Your call! ;-)

In all seriousness, a great time to strategize is during food comas.

-Marty

I wanted to ping people to see how many could attend a one day workshop in New
York City at Yahoo! this summer to discuss the competition and its future. I
believe that we are reaching a turning point, in that there is no one clear next
step for the competition (although there are many potential steps). Also, I
would like to look back. One thing that seems to have come out of this
competition is the idea of leaders and followers: however, what a "leader" is
seems to have many definitions. Secondly, the idea of what a collaboration was,
while it was clear in the first and second competition, had many different
interpretations in the second competition. Finally, opponent modeling has had
many flavors over the last three years, and it would be interested to discuss
it.

I would like to have a workshop in New York: some invited talks, some open
discussions. What people could attend? What people would need financial help to
get there?

The primary reason for this is that I am getting indications that few would be
able to attend a meeting in Europe, and it would just be me and a bunch of TAC
folks. So, instead I want to have a separate meeting here, and localize it to
maximize the number of attendees.

At this point, I am up for different locations if others work better. The hope
was that because NYC is a day trip for several teams, this would limit costs.

-Marty

Hi all. I am a firm believer in just enough security. Until there was spam, I
didn't moderate this group.

Well, now there is spam. So the group is moderated.

I apologize for this level of security, but it seems crucial.

This is a related workshop.

http://www.cs.utep.edu/kiekintveld/Workshops/TADAAMEC12.html

Executive Summary:
1. A possible aspect to study in 2013 would be when "long-term social reasoning"
is useful, as opposed to more conventional machine learning techniques.
2. A game which would study this would be a two player, nonzero-sum, repeated
bimatrix game where neither player EVER observed their opponents utilities.
3. I am open to other ideas about the focus of the competition in 2013 and its
rules. This message board is a great place to post them.
4. This isn't one of these things the board has to respond to or anything,
because the board is for 2012.


I have been thinking about the 2013 competition. Specifically, what is the
question that we want to ask? Of course, this is a bit ahead of schedule,
because we haven't seen the results of the 2012 competition. Regardless:

The big interest for me is about "long-term social reasoning" (yes, I will have
another name for it next week). Roughly speaking, are players sacrificing
short-term gains for long term utility, when the only state of the game is
internal to the agents? I can't formally describe this type of reasoning (one
reason to study it empirically), and even describing it as a design pattern is
hard. However, lots of people have strategies that exhibit stationarity above
and beyond just staying in a place because it is locally optimal. This
stationarity is a result of an observation that change will "upset the apple
cart", and lead to another, possibly less optimal, equilibrium. There is a
distinction between this and being UNAWARE of the benefits of local changes. For
example, playing an approximate equilibrium in poker because I don't know what
else to do is not necessarily long term social reasoning. In order to
distinguish long-term social reasoning, there has to be an alternative that
would likely improve short-term utility that is not taken.

It turns out, it is easier to describe what long-term social reasoning is NOT,
at least in the games we play.  Alice assumes Bob is independent of Alice if
Alice believes that Bob is not influenced by Alice's past behavior. Thus, if
Alice believes all other agents have this property, there is no benefit to
sacrificing short-term utility.

Secondly, if Alice is minimizing regret, in the conventional sense of the
utility she would have received if she had transformed her actions, under the
worst case, nonstationary assumptions usually made, there is no benefit to
choosing suboptimal actions now:  an optimal adversary cannot be baited to be
nice to you. Thus, regret is not long-term social reasoning.

As an aside, you could imagine both cooperative and adversarial long-term social
reasoning: are you trying to work together or manipulate? I am mostly interested
in cooperative long-term social reasoning, but I think that any formal
distinction is hard to obtain.



Therefore, I can give a competition (poker) where long-term social reasoning is
not used. I can give a competition (the LSG) where it has become clear that
long-term social
reasoning is the only way to go. Here is a question: is there a game where it is
unclear whether long-term social reasoning is useful?

The most difficult part of this is that most games without long-term social
reasoning have one of two properties: they are either zero-sum (making
cooperative LTSR impossible), or they are very complex, making learning about
opponents, let alone exploiting opponent's learning, very difficult. Or, they're
both.

On the other hand, games like LSG or Iterated Prisoner's Dilemma are so simple,
there is nothing BUT long-term social reasoning.

So here is a middle of the road game. Consider a randomly generated, two player,
12 action, nonzero-sum game. If all utilities were observed, then I don't think
that the game would be interesting. Even if some games involved long-term
reasoning, and some did not, players could calculate equilibria and then play
them.

However, what if the utilities of the opponent are NEVER observed. No
assumptions about symmetry here, the utilities of the two players are completely
independent. Then, do you try to influence your opponent's behavior? Do you try
to negotiate in some fashion? Do you just minimize regret? Assuming the
distribution of utilities is known, what do you consider successful play?

The key here is that we are making the game slightly more complex, but small
enough such that the approaches used in the lemonade stand game would do
SOMETHING. Moreover, it is clear that regret would do SOMETHING too.

The tricky part I haven't figured out is the distribution. It is quite possible
that no distribution will work. A simple uniform distribution might work: for a
sufficiently large game, their will rarely be any strictly dominant action. Even
if the game is solvable, the lack of information makes any such solution
difficult to find.

-Marty

Hi everyone, how does July 27th work for everyone? This is the day after AAAI in
Toronto. ACM-EC is a month before.

If you want to go, then please RSVP by e-mailing me your name, any past team
affiliations, and your institution (if any).

Thanks!

-Marty

There is some confusion about the relationship between TAC and LSG. I am talking
with them now to resolve these issues. I need your feedback on the July 27th
date so we can get a plan in motion.

-Marty

Hi everyone. There is a problem with the Yahoo! NY venue, as there might not BE
a Yahoo! NY venue by July. I will look for alternatives. At that time I will be
a Research Scientist with Google, so the two options I am considering are
Rutgers and Google NY.

-Marty