Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Game Theory With Apache Spark, Part 3

DZone 's Guide to

Game Theory With Apache Spark, Part 3

In this article, we dive in to the Java code needed to work the algorithms discussed in Part 1 and Part 2 using Apache Spark.

· Big Data Zone ·
Free Resource

Series So Far

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 < 2size. 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 Vi(P) at price P, i.e. it solves the maximization problem:

max x ∈ X{Ui(x) - P * x}

where Xi is the consumption set of the agent.

Recall that

  • Ui = [ui1 ui2 ... uiK]T 

  • Ui(x) = UiT  * x = ∑ j = 1, 2, ..., K  (uij * xij)

  • Ui(x) - P * x = ∑ j = 1, 2, ..., K  (uij - pj)* xij 

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

  • xij = Lij, if uij - pj > 0

  • xij = 0, if uij - pj ≤ 0

Note that a maximizing x is not necessarily unique because if uij - pj   ≤ 0 then we could have chosen any xij satisfying 0 ≤ xij ≤  Lij.

The input parameter consumptionSet is a vector where the j-th element is equal to Lij (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 uij - pj, j = 1, ..., K. An entry in tmp2 will be 0 if uij - pj < 0 and uij - pj otherwise, j = 1, ..., K. An entry in normalized will be 0 if  uij - pj < 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 ∈ X{Ui(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 Ptmp.

  // 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, Ptmp (= 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 Ptmp  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 Pand OptimalAssignments. The variables P_new and Omega correspond to Pnew 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 Pand 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 Pfor 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 Allocij 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, Zj := Sj (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.

Topics:
big data ,game theory ,apache spark ,algorithms ,tutorial

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}