The following LP gives a solution that does not satisfy the expected envy-freeness constraints

Awaiting user input

Agha Mammadov

March 30, 2023 01:37

• 
• 

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
    

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 13, 2026 01:45

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  March 30, 2023 07:57

  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

Post is closed for comments.