Implement a Nash Social Welfare optimization for boss item distribution - the process is described below.
Description of the process
Each player starts with a base total valuation of 1000
Whenever a boss dies:
First, we obtain each players valuation for each of the items.
We do so by asking them whether they Need, Greed or Pass each item.
For an item a player Passes, their valuation is 0
For an item a player Greeds, their valuation is the item's sale price
For an item a player Needs, their valuation is the item's purchase price
Distribute the sale prices of the items a player passed as increments to their valuation of the items they Needed
Drop any items all players passed on the base.
Then, for each possible distribution of the remaining items, add up each player's total valuations of the items they'll get, and add it to their current valuation. This is that player's fitness for that distribution.
The distribution's fitness is equal to the product of all player's fitnesses for it
Pick one of the distributions with the highest total fitness, and distribute the items accordingly
Update each player's current total valuation to their fitness for the chosen distribution
Display a dice roll showing that the player won the item
Example
Boss A just died, and it dropped two items: Item A, with sale value 500 (purchase value 1000), and Item B, with sale value 100 (purchase value 200).
For Item A
Player 1 passes; base valuation for item A is 0.
Player 2 needs; base valuation for item A is 1000.
Player 3 greeds; base valuation for item A is 500.
Player 4 greeds; base valuation for item A is 500.
Player 5 passes; base valuation for item A is 0.
For Item B
Player 1 (current value 1000) passes; base valuation for item B is 0.
Player 2 (current value 1500) passes; base valuation for item B is 0.
Player 3 (current value 1700) passes; base valuation for item B is 0.
Player 4 (current value 1000) passes; base valuation for item B is 0.
Player 5 (current value 2000) passes. base valuation for item B is 0.
Item B is dropped at the team's base.
Since Player 1 passed items, their total sale value (600) is distributed among the items Player 1 needed.
Player 1 didn't need any items.
Since Player 2 passed items, their total sale value (100) is distributed among the items Player 2 needed.
Player 2's valuation for item A is increased to 1100.
Since Player 3 passed items, their total sale value (100) is distributed among the items Player 3 needed.
Player 3 didn't need any items.
Since Player 4 passed items, their total sale value (100) is distributed among the items Player 4 needed.
Player 4 didn't need any items.
Since Player 5 passed items, their total sale value (600) is distributed among the items Player 5 needed.
Player 5 didn't need any items.
Now we look at item distributions. There is one item to distribute.
We will need the players' current values.
Player 1 has current value 1000
Player 2 has current value 1500
Player 3 has current value 1700
Player 4 has current value 1000
Player 5 has current value 2000
Option 1: give item A to Player 1
Player 1 has fitness 1000
Player 2 has fitness 1500
Player 3 has fitness 1700
Player 4 has fitness 1000
Player 5 has fitness 2000
Net fitness is 5.1x10^15
Option 2: give item A to Player 2
Player 1 has fitness 1000
Player 2 has fitness 2600
Player 3 has fitness 1700
Player 4 has fitness 1000
Player 5 has fitness 2000
Net fitness is 8.84x10^15
Option 3: give item A to Player 3
Player 1 has fitness 1000
Player 2 has fitness 1500
Player 3 has fitness 2200
Player 4 has fitness 1000
Player 5 has fitness 2000
Net fitness is 6.6x10^15
Option 4: give item A to Player 4
Player 1 has fitness 1000
Player 2 has fitness 1500
Player 3 has fitness 1700
Player 4 has fitness 1500
Player 5 has fitness 2000
Net fitness is 7.14x10^15
Option 5: give item A to Player 5
Player 1 has fitness 1000
Player 2 has fitness 1500
Player 3 has fitness 1700
Player 4 has fitness 1000
Player 5 has fitness 2000
Net fitness is 5.1x10^15
The algorithm chooses Option 2, and awards the item to Player 2. It then displays a dice roll to justify the decision.
It updates Player 2's current value to 2600.
Note that, had Player 4 Needed the item, they would have been awarded the item, as Option 4's net fitness would have been 10.71x10^15
Pseudocode Suggestion
//Determines how much each player in given player vector values each item in given item vector##
Item_Evaluation(items, players)
for each (player)
set player.passpool = 0
set player.total_needed_items = 0
for each (item, player)
set item.ngp = get_ngp_choice()
for each (item, player)
if item.ngp = greed
set value(item, player) = item.sellprice
if item.ngp = pass
set player.passpool = player.passpool + item.sellprice
set value (item, player) = 0
if item.ngp = need
set value(item, player) = item.buyprice
increase player.total_needed_items
for each (item, player)
if item.ngp = need
set value (item, player) = value (item, player) + player.passpool/player.total_needed_items
//Given item and player vectors, determines best item allocation to maximize Nash Social Welfare##
Value_Calculation(items, players)
selection = 0
selection_fitness = 0
Item_Evaluation(items, players)
for each item_distribution
for each player
fitness(player) = player.current_value + value(items given to player, player)
fitness(item_distribution) = fitness(player1)*fitness(player2)*...*fitness(player5)
if fitness(item_distribution) > selection_fitness
selection = item_distribution
selection_fitness = fitness(item_distribution)
return selection
//Whenever a boss dies, distribute items according to best allocation##
Main()
On_Game_Start
for each (player)
player.current_value = 1000
Whenever (Boss_dies)
item_distribution = Value_Calculation(drops, team)
for each (player)
give items allocated
player.current_value = player.current_value + value (items given to player, player)
display(roll_die)
![dependabot[bot] avatar](https://avatars.githubusercontent.com/in/29110?v=4 "dependabot[bot]")
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent