Project 4: Community

You live in a community that works together to achieve tasks, without overwhelming any of its members with work. Each member of the community has a particular combination of abilities that enables them to perform certain tasks well, while being less able at other tasks. The goal is to reach a steady state in which the community as a whole achieves as many tasks as possible.

The number of abilities n is a parameter, anywhere between 3 and 8. To motivate the problem, we'll give names to these abilities. The abilities are a prefix from the following list:

1. Food
2. Water
3. Clothing
4. Building
5. Plants
6. Animals
7. Transport
8. Medicine

Any individual in the community has a score between 0 and 10 for each of the abilities $a_1,\ldots,a_n$. A larger score implies higher skill for that particular ability.

At any moment in time, the community will have a set of pending tasks. A task has an n-dimensional vector of difficulty levels $(d_1,\ldots,d_n)$, each also between 0 and 10.

Each individual has an energy level that starts at 10, and will vary during the course of the simulation. Energy levels can drop below zero, but there are consequences for doing so, which will be explained below.

An individual can elect to perform a task alone. If they do that, they expend an amount of energy equal to the sum of (d_i-a_i) where i varies over all dimensions for which d_i>a_i. In other words, if an individual has skill below the required level for a certain ability, then it costs energy to achieve that task. For example, suppose n=4 and that an individual has skill levels (8,6,4,2), and that the task has difficulty vector (5,5,5,5). Then the individual would use up 1+3=4 units of energy to perform the task.

Two individuals can collaborate to perform a task. In that case, the energy penalty is calculated using the maximum skill level for each of the two individuals. So suppose that another individual with skill levels (2,3,6,4) chooses to collaborate with the previous player on the same task. Then the total energy needed would now be 5-max(2,4)=1, which would be halved and subtracted from the energy totals of each of the partners.

A person may also choose to rest on a given turn. A resting player whose energy is non-negative will regain one unit of energy by resting for one turn. A resting player with negative energy is exhausted, and only gains 0.5 units of energy per turn. The energy never exceeds 10 units.

A player whose energy drops too low becomes incapacitated and can no longer perform any tasks. If the simulator detects that a player drops to an energy level of -10 or less, that player will stop participating in the simulation.

There are p players in the simulation, where p is a parameter. Each player is running a different code instance. At the beginning of each turn all players attend the town hall, where there will be a listing of up to 2p tasks that need to be completed. On the very first turn, there will be exactly 2p tasks. On later turns, uncompleted tasks will remain on the listing, while completed tasks will be removed. Only when all of the initially listed tasks are complete will a new set of 2p tasks be posted to the task list.

In a first phase, players may volunteer to work as a partner on one or more tasks, including a list of other individuals with whom they would be prepared to work for each task. Each player knows the abilities and current energy levels of all players in the simulation, so they can make an informed decision about who might be a good partner. After this initial phase, the simulator will find tasks with compatible partners and assign the task to that partnership. In the event that multiple pairings are possible, the simulator will choose pairs at random. Once a player is part of a partnership, they cannot be a partner for another task on the same turn.

In a second phase, remaining players may volunteer to work alone for one or more tasks. The simulator will then assign tasks to volunteers, choosing at random if there are multiple volunteers for a task.

When assigning players to tasks in each phase, the simulator will order tasks according to the metric $\sum_i d_i$, in decreasing order. That way, harder tasks are assigned to players before easier tasks.

Any remaining players will rest for the given turn. By not volunteering for anything, you will be guaranteed to rest.

The distribution of abilities and the distribution of task difficulty will be a parameter of the game. One player ability distribution might be a simple independent uniform distribution between 0 and 10 for each ability. Note that some players may have more ``total skill'' than others under such a distribution. A task difficulty distribution might be that each task has exactly three nonzero difficulty levels that are uniformly distributed between 4 and 10.

The game ends after a fixed number of turns. Importantly, players do not know the value of this turn limit. Not knowing the limit means that end-of-game optimizations (such as going all out on tasks despite negative energy balances) are not possible. The community as a whole receives a score equal to the number of tasks completed during the simulation. There are no individual scores for players. Nevertheless, we'll be able to compare players by running tournaments with and without certain players, or by running tournaments where all community members are running one group's code.

Some things to think about:

• How might the overall abilities of community members affect how you view which tasks are the most challenging ones?
• What tasks are good candidates for partnerships?