DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. Data
  4. Game Theory With Apache Spark, Part 3

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.

Konur Unyelioglu user avatar by
Konur Unyelioglu
·
Nov. 11, 18 · Tutorial
Like (3)
Save
Tweet
Share
7.89K Views

Join the DZone community and get the full member experience.

Join For Free

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 < 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 ∈ Xi {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 ∈ Xi {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 Po and 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 Po 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 Po 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 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.

Apache Spark Data structure

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Kotlin Is More Fun Than Java And This Is a Big Deal
  • Why You Should Automate Code Reviews
  • Event Driven 2.0
  • Java Development Trends 2023

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: