The following LP gives a solution that does not satisfy the expected envy-freeness constraints
ユーザーの入力を待っています。def XEF_U_Allocation(N,p):
# Define the linear program
lp=gp.Model("""Envy-Free Utilitarian Allocation""")
# Define the decision variables
decision_vars = []
k = len(N)
n = N[0].shape[0]
# m=N.shape[1]
for l in range(k):
for i in range(n):
for a in range(n):
decision_vars.append(lp.addVar(name=f'x_{l}{i}{a}'))
# for l in range(k):
decision_vars=np.array(decision_vars).reshape(k,n,n)
# Define the objective function - Utilitarian objective
lp.setObjective(sum(N[l][i][a]*decision_vars[l][i][a]*p[l] for l in range (k) for i in range(n) for a in range(n)),GRB.MAXIMIZE)
# *p[l]
# Each agent receives exactly one object
for l in range(k):
for i in range(n):
lp.addConstr(sum(decision_vars[l][i][a] for a in range(n))==1)
# Each object is allocated exactly one agent
for l in range(k):
for a in range(n):
lp.addConstr(sum(decision_vars[l][i][a] for i in range(n))==1)
# Expected envy-freeness constraints
for l in range(k):
for i in range(n):
for j in [t for t in range(n) if t!=i]:
lp.addConstr(sum((p[l] / (sum(p[t] for t in range(k) if np.array_equal(decision_vars[t][i],decision_vars[l][i]))))*decision_vars[t][i]*N[t][i] for t in range(k) if np.array_equal(decision_vars[t][i],decision_vars[l][i])) >= sum((p[l] / (sum(p[t] for t in range(k) if np.array_equal(decision_vars[t][i],decision_vars[l][i]))))*(decision_vars[t][j])*N[t][i] for t in range(k) if np.array_equal(decision_vars[t][i],decision_vars[l][i])))
lp.update()
lp.optimize()
lp.printQuality()
solution=np.zeros((k,n,n))
if lp.SolCount == 0:
return "For the given instance, there is no expected envy-free allocation."
else:
for l in range(k):
for i in range(n):
for a in range(n):
solution[l][i][a]=decision_vars[l][i][a].X
XEF_U_Allocation = solution
obj_exante = lp.getObjective()
print(obj_exante.getValue())
A = [XEF_U_Allocation, obj_exante.getValue()]
return A
-
Hi Agha,
Please note that just posting a lengthy non-reproducible code does not reflect good forum culture.
Please at least try to provide a minimal reproducible example. In particular, why do you think that the solution does not satisfy a particular constraints. How did you verify that it does not satisfy this constraint? Did you write the model to an LP file via the write method and analyzed it in a standard text editor to see whether your model is correct?
Best regards,
Jaromił0
サインインしてコメントを残してください。
コメント
1件のコメント