Game Theory With Apache Spark, Part 3

Series So Far

• Game Theory With Apache Spark, Part 1

• Game Theory With Apache Spark, Part 2

Code Review

Now we will review the code that implements the algorithms using Apache Spark Machine Learning Library, Spark version 2.3.1, and Java version 8. The complete code is available on GitHub. 

Helper Methods and Classes

The following method adds a prefix consisting of 0s to the parameter suffix so that length of prefix + suffix equals the input parameter size. If the length of suffix ≥ size, then no prefix is added. It is assumed that size ≥ 1 and the suffix is not null.

private static String pad(int size, String suffix){    
  String zero = "0";    
  StringBuilder bldr = new StringBuilder();    
  for(int i = 0; i < size - suffix.length(); i++){        
    bldr.append(zero);    
  }    
  return bldr.toString() + suffix;
}

The following method returns an array consisting of a base-2 representation strings of all nonnegative integers < 2^size. Each string in the array has a length that equals the input parameter's size padded with 0s if necessary. For example, base2(3) returns the following:

{000,001,010,011,100,101,110,111}

It is assumed that size ≥ 1.

private static String[] base2(int size){    
  int dimension = (int)Math.pow(2,size);    
  String[] retArr = new String[dimension];    
  for(int i = 0; i < dimension; i++){        
    String tmp = Integer.toString(i,2);        
    retArr[i] = pad(size,tmp);    
  }    
  return retArr;
}

The following method returns addition (if isAdd is true) or subtraction (ifisAdd is false) of two vectors. The Vector class belongs to the org.apache.spark.ml.linalg package.

/**
  @param a: Vector of doubles
  @param b: Vector of doubles
  @param isAdd: true to add, false to subtract
*/
private static DenseVector addOrSubtract(Vector a, Vector b, boolean isAdd){    
  double[] tmp1 = a.toArray();    
  double[] tmp2 = b.toArray();    
  double[] tmp3 = new double[tmp1.length];    
  int factor = 1;    
  if(!isAdd){        
    factor = -1;    
  }    

  for(int i = 0; i < tmp1.length; i++){        
    tmp3[i] = tmp1[i] + factor*tmp2[i];    
  }    

  return new DenseVector(tmp3);
}

The two classes below are mainly used in the calculation of C(P).

class AssignmentsAndUtility {
    double[] assignments;
    double utility;
}

class AssignmentsAndPrice{
    ArrayList<double[]> assignmentsL;
    Vector price;
}

For an agent i, the method getMaxUtility() below calculates V_i(P) at price P, i.e. it solves the maximization problem:

max _{x ∈ Xi} {U_i(x) - P * x}

where X_i is the consumption set of the agent.

Recall that

• U_i = [u_i1 u_i2 ... u_iK]^T 

• U_i(x) = U_i^T  * x = ∑ _{j = 1, 2, ..., K}  (u_ij * x_ij)

• U_i(x) - P * x = ∑ _{j = 1, 2, ..., K}  (u_ij - p_j)* x_ij 

Also, for a vector in X_i, dimension j corresponds to a particular resource type and is less than or equal to L_ij. Therefore, the method calculates a maximizer so that:

• x_ij = L_ij, if u_ij - p_j > 0

• x_ij = 0, if u_ij - p_j ≤ 0

Note that a maximizing x is not necessarily unique because if u_ij - p_j   ≤ 0 then we could have chosen any x_ij satisfying 0 ≤ x_ij ≤  L_ij.

The input parameter consumptionSet is a vector where the j-th element is equal to L_ij (i corresponds to the particular agent). The method starts with various variable definitions.

/**
 @param U: K-dimensional vector of value coefficients (K := # resource types).
 @param P: K-dimensional price vector.
 @param consumptionSet: K-dimensional vector, upper bounds on each 
   resource type.
*/
private static AssignmentsAndUtility getMaxUtility(Vector U, Vector P, 
    Vector consumptionSet){
    double[] tmp1 = addOrSubtract(U,P,false).toArray();
    double[] tmp2 = new double[tmp1.length];
    double[] normalized = new double[tmp1.length];
...

The array tmp1 has K elements where each entry stores u_ij - p_j, j = 1, ..., K. An entry in tmp2 will be 0 if u_ij - p_j < 0 and u_ij - p_j otherwise, j = 1, ..., K. An entry in normalized will be 0 if  u_ij - p_j < 0 and 1 otherwise, j = 1, ..., K. 

    int j = 0; // j is an index to resource types
    for(double dbl:tmp1){
        if(dbl < 0d){
            tmp2[j] = 0d;
            normalized[j] = 0d;
            j++;
        }else{
            tmp2[j] = dbl;
            normalized[j] = 1d;
            j++;
        }
    }
...

We then construct the org.apache.spark.ml.linalg.DenseMatrix object uMinusp from tmp2 and utilize it to  calculate max _{x ∈ Xi} {U_i(x) - P * x} (result object). Finally, returnObject is constructed to store return result and the corresponding normalized.

    DenseMatrix uMinusp = new DenseMatrix(1, tmp2.length, tmp2);
    double result = (uMinusp.multiply(consumptionSet).toArray())[0];

    AssignmentsAndUtility returnObject = new AssignmentsAndUtility();
    returnObject.utility = result;
    returnObject.assignments = normalized;
    return returnObject;
}

The method getMaxUtility() will be called repeatedly from getCMin(), to be discussed next.

Main Methods

Calculate  min_{ω ∈ Ω} C(P + ω)

The following method calculates and returns min_{ω ∈ Ω} C(P + ω) along with the corresponding Assignments. 

/**
  @param Ul: A list of value coefficients for agents. List consists of N 
    vectors, one for each agent, where each vector is K-dimensional (N := 
    number of agents, K := number of resource types).
  @param P: K-dimensional price vector.
  @param consumptionSets: List of upper bounds on each resource type. List
    consists of N vectors, one for each agent, where each vector is 
    K-dimensional. 
  @param S: K-dimensional vector where the j-th entry corresponds to available
    supply units. 
  @param Omega: All possible 1-unit price increases over the price vector.
*/
private static AssignmentsAndPrice getCMin(ArrayList<Vector> Ul, 
   Vector P, ArrayList<Vector> consumptionSets, Vector S, String[] Omega){  
...

The method starts with variable initializations. The variable optimal will eventually become Assignments. The variable P_tmp corresponds to P_tmp.

  // Variable initializations.
  ArrayList<double[]> optimal = null;  
  double minimum = -1d;    
  Vector P_tmp = null;    
  String optimalRepresentation = null;    
...

Below, the loop for(String s:Omega) corresponds to the repeat statement for each element in Ω. The tmp[] array is used to construct omega_v, which corresponds to ω ∈ Ω. The variable P_omega  corresponds to P_ω. When the loop ends, P_tmp (= min_{ω ∈ Ω} C(P + ω)) has been calculated and the and variable optimal has become Assignments.

for(String s:Omega){
        AssignmentsAndUtility tmpObj = null;
        double[] tmp = new double[s.length()];
        for(int j = 0; j < tmp.length; j++){
            tmp[j] = Character.getNumericValue(s.charAt(j));
        }
        DenseVector omega_v = new DenseVector(tmp);
        Vector P_omega = addOrSubtract(P,omega_v,true);
        double maximum = ((new DenseMatrix(1, P_omega.size(), 
            P_omega.toArray())).multiply(S).toArray())[0];
        ArrayList<double[]> tmpArr = new ArrayList<double[]>();
        for(int i = 0; i < Ul.size(); i++){
            tmpObj = getMaxUtility(Ul.get(i), P_omega, 
                consumptionSets.get(i));
            tmpArr.add(tmpObj.assignments);
            maximum +=  tmpObj.utility;
        }

        if(minimum < 0 || maximum < minimum){
            minimum = maximum;
            optimal = tmpArr;
            optimalRepresentation = s;
            P_tmp = P_omega;
        }
    }
...

We finally return P_tmp  and Assignments encapsulated by an AssignmentsAndPrice object. 

   AssignmentsAndPrice result = new AssignmentsAndPrice();
   result.price = P_tmp;
   result.assignmentsL = optimal;
   return result;
}

Calculate Part 1: Optimal Price and Corresponding Assignments

The following method performs Part 1, utilizing getCMin() to calculate the optimal price vector.

/**
  @param Ul: A list of value coefficients for agents. List consists of N 
    vectors, one for each agent, where each vector is K-dimensional (N := 
    number of agents, K := number of resource types).
  @param S: K-dimensional vector where the j-th entry corresponds to available
    supply units. 
  @param consumptionSets: List of upper bounds on each resource type. List
    consists of N vectors, one for each agent, where each vector is 
    K-dimensional. 
*/ 
private static AssignmentsAndPrice getOptimalAssignmentsAndPrice(
  ArrayList<Vector> Ul, Vector S, ArrayList<Vector> consumptionSets){
...

The method starts with various initializations. In particular, variable Optimal will encapsulate the optimal price vector P^o and OptimalAssignments. The variables P_new and Omega correspond to P_new and Ω, respectively.

    Vector P = Vectors.zeros(S.size());
    Vector P_new = null;
    AssignmentsAndPrice Optimal = null;
    String[] Omega = base2(P.size());
...

The while loop will run until price no longer increases. Recall from the previous section that getCMin()calculates and returns min_{ω ∈ Ω} C(P + ω) along with the corresponding Assignments.

    while(true){
        AssignmentsAndPrice result = getCMin(Ul,P,consumptionSets,S,Omega);
        P_new = result.price;

        if(P.equals(P_new)){
            Optimal = new AssignmentsAndPrice();
            Optimal.price = P_new;
            Optimal.assignmentsL = result.assignmentsL;
            break;
        }else{
            P = P_new;
        }
    }
...

Finally, the method returns the variable Optimal that encapsulates P^o and OptimalAssignments.

    return Optimal;
}

Calculate Part 2: Allocations Corresponding to Optimal Price

The following method performs Part 2, i.e. for each resource type, the available supply is allocated to the agents prioritizing the agent (if any) that has bid a higher value for the resource type than the set price for that resource type. When calling getAllocations(), we will pass P^o for parameter P and OptimalAssignments for parameter assignmentsL.

/**
  @param P: K-dimensional price vector.
  @param Ul: A list of value coefficients for agents. List consists of N 
    vectors, one for each agent, where each vector is K-dimensional (N := 
    number of agents, K := number of resource types).
  @param S: K-dimensional vector where the j-th entry corresponds to available
    supply units. 
  @param consumptionSets: List of upper bounds on each resource type. List
    consists of N vectors, one for each agent, where each vector is 
    K-dimensional. 
  @param assignmentsL: List of N assignments, each has size K, where an entry 
    equals 0 or 1
*/ 
private static ArrayList<DenseVector> getAllocations(Vector P, 
ArrayList<Vector> Ul, Vector S, ArrayList<Vector> consumptionSets, 
    ArrayList<double[]> assignmentsL){
  ...

We start with initializing various temporary variables. In particular, the variable Alloc corresponds to Alloc_ij i.e. the allocation of resource type j to agent i .

    int K = S.size(); // size of supply vector
    int N = assignmentsL.size(); // size of bidders

    double P_vals[] = P.toArray();

    ArrayList<double[]> Ul_vals = new ArrayList<double[]>();
    for(Vector v:Ul){
        Ul_vals.add(v.toArray().clone());
    }

    ArrayList<double[]> consumptionSet_vals = new ArrayList<double[]>();
    for(Vector v:consumptionSets){
        consumptionSet_vals.add(v.toArray().clone());
    }

    double S_vals[] = S.toArray();
    ArrayList<double[]> Alloc = new ArrayList<double[]>();

    // Initialize allocations
    for(int i = 0; i < N; i++){
        double[] vals = new double[K];
        Alloc.add(vals);
    }
...

We then perform allocations of each resource type one-by-one, starting with defining the initial supply, Z_j := S_j (see double Z_j = S_vals[j]). As mentioned in the algorithm, the allocation is completed in two distinct loops; the forst one prioritizes the agents with a value greater than the set price for the corresponding resource type and the second one does not take into account any priority.

    for(int j = 0; j < K; j++){
        double Z_j = S_vals[j];
        while(Z_j > 0) {
            int bidderIndex = 0;

            // if for that i there is any bidder with nonzero allocation and 
            // ui > price allocate to it
            for (double[] bidder : Alloc) {
                if (assignmentsL.get(bidderIndex)[j] > 0 && 
                    consumptionSet_vals.get(bidderIndex)[j] > 0) {
                    if(Z_j <= 0){
                        break;
                    }
                    if(Ul_vals.get(bidderIndex)[j] - P_vals[j] > 0){
                        double Delta = Math.min(Z_j,consumptionSet_vals.get(
                          bidderIndex)[j]);
                        consumptionSet_vals.get(bidderIndex)[j] = 
                          consumptionSet_vals.get(bidderIndex)[j] - Delta;
                        Z_j = Z_j - Delta;
                        bidder[j] = bidder[j] + Delta;
                    }
                }
                bidderIndex++;
            }

            bidderIndex = 0;

            for (double[] bidder : Alloc) {
                if (assignmentsL.get(bidderIndex)[j] > 0 && 
                    consumptionSet_vals.get(bidderIndex)[j] > 0) {
                    if(Z_j <= 0){
                        break;
                    }
                    double Delta = Math.min(Z_j,consumptionSet_vals.get(
                      bidderIndex)[j]);
                    consumptionSet_vals.get(bidderIndex)[j] = 
                      consumptionSet_vals.get(bidderIndex)[j] - Delta;
                    Z_j = Z_j - Delta;
                    bidder[j] = bidder[j] + Delta;
                }
                bidderIndex++;
            }
        }
    }
...

At the end, the method constructs the final allocations variable and returns it.

    ArrayList<DenseVector> allocations = new ArrayList<DenseVector>();
    for(double[] allocation:Alloc){
        allocations.add(new DenseVector(allocation));
    }
    return allocations;
}

That's it for Part 3! Tune in tomorrow when we'll wrap up this series by bringing all these pieces together in our code.