There are 25 candidates on Neo blockchain that receive votes. Every voter except me has voted. The candidates ranked 1st to 7th each will give 200 dollars, proportionally to people who vote for them. And the 8th to 21st will each distribute 100 dollars. For example, I cast 100 votes to the currently 8th candidate, pushing him/her to 7th position, and other people voted 900 votes for him, so I get 200*100/(900+100)=20 dollars from the candidate.
I know the voting result yielded by all the other voters, and I can additionally cast N votes to n candidates at maximum, because I have only n agents as my delegates. That is, my voting vector should have no more than n nonzero values, and the sum of my voting vector should equal to N.
How should I vote for highest profit?
("Dollar" is written as "GAS" in the following codes. And the number of votes I can cast is written as "NEO" in the codes)
These codes makes an error: Endogenous $ operation not allowed
(I have not figured out how to deal with the change of position because of my vote. This may be very difficult. )
(LINDO solver gives the best results for now)
Set i "candidate index" /
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
/;
Parameters
V(i) "other people's votes" /
0 11409980
1 3024833
2 2200734
3 2040928
4 2032100
5 2017067
6 2010927
7 2007339
8 2001625
9 1008817
10 1000025
11 1000000
12 641913
13 396926
14 392171
15 390364
16 383919
17 383722
18 382447
19 382310
20 381850
21 923
22 272
23 180
24 0
/
NEO "our NEOs" /1162/
num_agents "our num of agents" /2/
reward_factor(i) "how much gas is given by the candidate at each rank" /
0 200
1 200
2 200
3 200
4 200
5 200
6 200
7 100
8 100
9 100
10 100
11 100
12 100
13 100
14 100
15 100
16 100
17 100
18 100
19 100
20 100
21 0
22 0
23 0
24 0
/;
Integer Variable vote(i) "voting vector that needs to be optimized";
vote.up(i) = NEO;
Free Variable GAS_reward "total GAS reward";
Binary Variable is_nonzero(i) "whether an element in the voting vector is zero";
Integer Variable count_nonzero "count of nonzero values in vote(i)";
Equations
GAS_reward_eqn "the reward according to our voting vector v"
sum_v_eqn "sum of voting vector equals num of our NEOs"
is_nonzero_eqn(i) "whether the element vote(i) is not zero"
num_agents_eqn "sum of nonzero element in voting vector does not exceed num of our agents";
GAS_reward_eqn.. GAS_reward =e= sum(i, reward_factor(i)*vote(i)/(V(i)+vote(i)+0.000001));
sum_v_eqn.. NEO =e= sum(i, vote(i));
is_nonzero_eqn(i).. is_nonzero(i) =e= 1 $ (vote(i));
num_agents_eqn.. sum(i, is_nonzero(i)) =l= num_agents;
Model NEOBurger /all/;
Option MINLP=lindo;
Solve NEOBurger using MINLP maximizing GAS_reward;
(where the code is_nonzero_eqn(i).. is_nonzero(i) =e= 1 $ (vote(i)); is nonlinear!)
If you need extra test cases and references, here are the Python (3.7 or 3.8) codes for the problem
strategy_multi_agents.py
# Good profit
# Can somehow deal with sorting problem
# Cannot restrict num of agents
# Cannot restrict to integer
from typing import Union, List
import numpy as np
np.set_printoptions(suppress=True)
from scipy.optimize import minimize
class BurgerNEOMultiAgentStrategy:
"""
To find the best distribution of our GAS assuming that we do not affect the ranking
"""
consensus_rank, consensus_gain = 7, 200
council_rank, council_gain = 21, 100
def __init__(self, candidate_votes: List[int], our_NEOs: int, num_of_agents: int = 2):
"""
:param candidate_votes: should be sorted in descending order. All the results are based on the descending order.
"""
self.len_candidate_votes = len(candidate_votes)
if self.len_candidate_votes >= self.council_rank:
self.candidate_votes = sorted(candidate_votes, reverse=True)
if self.candidate_votes != candidate_votes:
raise ValueError('You did not input a descending list of candidate_votes.')
self.candidate_votes = np.array(self.candidate_votes, dtype=np.int_) # descending order
else:
raise ValueError(f'len(candidate_votes) should be >= {self.council_rank}. Got {self.len_candidate_votes}.')
self.our_NEOs = np.int_(our_NEOs)
reward_factor = np.zeros(self.len_candidate_votes, dtype=np.int_)
reward_factor[0:self.consensus_rank] = self.consensus_gain
reward_factor[self.consensus_rank:self.council_rank] = self.council_gain
self.reward_factor = reward_factor
self.num_of_agents = num_of_agents
def calc_GAS_gain(self, voting_vector: np.ndarray) -> Union[np.float_, np.int_]:
new_voting_result = voting_vector + self.candidate_votes
argsort = np.flip(new_voting_result.argsort())
voting_vector = voting_vector[argsort]
new_voting_result = new_voting_result[argsort]
return np.sum(self.reward_factor * voting_vector / (new_voting_result + 1e-5))
def calc_voting_vector(self):
def sum_is_our_NEO(voting_vector: np.ndarray):
return np.sum(voting_vector) - self.our_NEOs
starting_point = self.our_NEOs / self.len_candidate_votes * np.ones(self.len_candidate_votes)
constraints = [
{'type': 'ineq', 'fun': lambda voting_vector: voting_vector}, # all greater than or equals 0
{'type': 'eq','fun': sum_is_our_NEO}, # sum is our_NEO
# {'type': 'ineq', 'fun': lambda x: -np.abs(x - np.round(x))}, # all integers
# {'type': 'ineq', 'fun':
# lambda x: - np.count_nonzero(np.invert(np.isclose(x, np.zeros(self.len_candidate_votes), atol=1e-3/self.len_candidate_votes))) + self.num_of_agents}, # num of agents
]
result = minimize(lambda voting_vector: (-self.calc_GAS_gain(voting_vector)),
starting_point, constraints=constraints, tol=1e-15, options={'maxiter': 1e9})
# return np.round(result.x).astype(np.int_), -result.fun, np.sum(np.round(result.x).astype(np.int_))
return result.x, -result.fun, np.sum(result.x)
if __name__ == '__main__':
print(
BurgerNEOMultiAgentStrategy(
[11409980, 3024833, 2200734, 2040928, 2032100, 2017067, 2010927, 2007339, 2001625, 1008817, 1000025, 1000000, 641913, 396926, 392171, 390364, 383919, 383722, 382447, 382310, 381850, 923, 272, 180, 0],
1162, 2).calc_voting_vector()
)
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 0,0,0,0, 0,0], 50, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 0,0], 25, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,1], 25, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,1], 25, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,0], 25, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,0], 1000, 2).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 0,0], 26, 2).calc_voting_vector())
print()
# Restricted to integer
# Restricted num of agents
# Not robust (sometimes constraints are broken)
# Not good profit
# Cannot deal with sorting
from typing import List
import random
from gekko import GEKKO
from strategy_multi_agents import BurgerNEOMultiAgentStrategy as ScipyStrategy
class BurgerNEOMultiAgentStrategy:
"""
To find the best distribution of our GAS assuming that we do not affect the ranking
"""
consensus_rank, consensus_gain = 7, 200
council_rank, council_gain = 21, 100
def __init__(self, candidate_votes: List[int], our_NEOs: int, num_of_agents: int = 2):
"""
:param candidate_votes: should be sorted in descending order. All the results are based on the descending order.
"""
self.model = GEKKO(remote=False, name='neoburger-strategy')
self.model.options.IMODE = 3
self.model.options.MAX_ITER = 10000
self.model.options.COLDSTART = 1
self.model.options.AUTO_COLD = 1
self.len_candidate_votes = len(candidate_votes)
if self.len_candidate_votes >= self.council_rank:
self.candidate_votes = sorted(candidate_votes, reverse=True)
if self.candidate_votes != candidate_votes:
raise ValueError('You did not input a descending list of candidate_votes.')
self.candidate_votes = [self.model.Param(can) for can in self.candidate_votes] # descending order
else:
raise ValueError(f'len(candidate_votes) should be >= {self.council_rank}. Got {self.len_candidate_votes}.')
self.our_NEOs = self.model.Param(our_NEOs, name='our_NEOs')
reward_factor = [self.consensus_gain] * self.consensus_rank \
+ [self.council_gain] * (self.council_rank - self.consensus_rank) \
+ [0] * (self.len_candidate_votes - self.council_rank)
self.reward_factor = [self.model.Param(r) for r in reward_factor]
self.num_of_agents = self.model.Param(num_of_agents, name='num_of_agents')
# voting_vector = [self.our_NEOs / self.len_candidate_votes] * self.len_candidate_votes
voting_vector = ScipyStrategy(candidate_votes, our_NEOs, num_of_agents).calc_voting_vector()[0]
voting_vector = [max(0, round(v)) for v in voting_vector]
self.voting_vector = [self.model.Var(v, lb=0, ub=our_NEOs, integer=True) for v in voting_vector]
def calc_GAS_gain(self):
# new_vote_result = [v+V for v, V in zip(self.voting_vector, self.candidate_votes)]
# sorted_vote_result = [(v, V) for v, V in zip(self.voting_vector, new_vote_result)] # sorted(, key=lambda x: x[1].value)
#
# sorted_voting_vector = [v for v, V in sorted_vote_result]
# sorted_vote_result = [V for v, V in sorted_vote_result]
# return sum([v*r/(V+v+0.0001) for v, V, r in zip(sorted_voting_vector, sorted_vote_result, self.reward_factor)])
return sum([v*r/(V+v+1) for v, V, r in zip(self.voting_vector, self.candidate_votes, self.reward_factor)])
def calc_voting_vector(self):
# constraints
# sum(voting_vector) == our_NEOs
self.model.Equation(sum(self.voting_vector) == self.our_NEOs)
# agent number
nonzero_vote = sum([self.model.if3(v - 0.1, 0, 1) for v in self.voting_vector])
# self.model.Equation(nonzero_vote >= 0)
self.model.Equation(nonzero_vote <= self.num_of_agents)
# objective
self.model.Maximize(self.calc_GAS_gain())
# self.model.options.RTOL = 1e-14
self.model.options.OTOL = 1e-14
self.model.options.REQCTRLMODE = 1
self.model.solve(disp=False, debug=False, GUI=False)
return self.voting_vector, -self.model.options.OBJFCNVAL
if __name__ == '__main__':
print(
BurgerNEOMultiAgentStrategy(
[11409980, 3024833, 2200734, 2040928, 2032100, 2017067, 2010927, 2007339, 2001625, 1008817, 1000025, 1000000, 641913, 396926, 392171, 390364, 383919, 383722, 382447, 382310, 381850, 923, 272, 180, 0],
1162, 6).calc_voting_vector()
)
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 0,0,0,0, 0,0], 50, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 0,0], 25, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,99, 75,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,1], 25, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,1], 25, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,0], 25, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 1,0], 1000, 6).calc_voting_vector())
print(BurgerNEOMultiAgentStrategy([100,100,100,100,100, 100,5, 5,5,5, 5,5,5,5,5, 5,5,5,5,5, 5, 1,1,1,1, 0,0], 26, 6).calc_voting_vector())
print()
And I also have codes (not shown here) which makes everything correct for only 1 or 2 agents. This is achieved not by optimization, but by manual mathematical derivation.
I would write this as:
* This is not using proper GAMS syntax:
*is_nonzero_eqn(i).. is_nonzero(i) =e= 1 $ (vote(i));
* a linear version is:
is_nonzero_eqn(i).. vote(i) =l= is_nonzero(i)*vote.up(i);
This is a standard MIP formulation for this. Using:
Model NEOBurger /all/;
Option MINLP=baron, optcr = 0;
Solve NEOBurger using MINLP maximizing GAS_reward;
we see:
GAMS/BARON 36.1.0 r2c0a44a Released Aug 02, 2021 WEI x86 64bit/MS Window
===========================================================================
BARON version 21.1.13. Built: WIN-64 Wed Jan 13 16:04:12 EST 2021
BARON is a product of The Optimization Firm.
For information on BARON, see https://minlp.com/about-baron
If you use this software, please cite publications from
https://minlp.com/baron-publications, such as:
Kilinc, M. and N. V. Sahinidis, Exploiting integrality in the global
optimization of mixed-integer nonlinear programming problems in BARON,
Optimization Methods and Software, 33, 540-562, 2018.
===========================================================================
This BARON run may utilize the following subsolver(s)
For LP/MIP/QP: ILOG CPLEX
For NLP: MINOS, SNOPT, GAMS external NLP, IPOPT, FILTERSD, FILTERSQP
===========================================================================
Doing local search
Solving bounding LP
Preprocessing found feasible solution with value 0.203660597686E-001
Starting multi-start local search
Done with local search
===========================================================================
Iteration Open nodes Time (s) Lower bound Upper bound
* 1 1 0.50 0.303390 3.71066
1 1 0.56 0.303390 0.303737
* 2 2 0.62 0.303405 0.303737
* 2 2 0.69 0.303428 0.303737
* 4 2 0.83 0.303473 0.303737
* 4 1 0.88 0.303639 0.303737
* 5 1 0.92 0.303681 0.303737
5 0 0.92 0.303681 0.303681
Calculating duals
*** Normal completion ***
Wall clock time: 4.05
Total CPU time used: 0.94
Total no. of BaR iterations: 5
Best solution found at node: 5
Max. no. of nodes in memory: 2
All done
===========================================================================
Solution = 0.30368112407161 found at node 5
Best possible = 0.303681125072
Absolute gap = 1.00039027062238E-9 optca = 1E-9
Relative gap = 3.29421287011233E-9 optcr = 1E-9
(Note that BARON uses a different formula to compute the relative gap as
was used for the above reported value.)
If we display the pertinent variables we see:
---- 90 VARIABLE vote.L voting vector that needs to be optimized
19 466.000, 20 696.000
---- 90 VARIABLE is_nonzero.L whether an element in the voting vector is zero
19 1.000, 20 1.000
This is correct behavior.
Note that MINLP = NLP + MIP so we can (and should) use all the tools and tricks we know about MIP modeling when writing MINLP models.