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

Comment (0)

Save
{{ articles.views | formatCount}} Views

## 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);
}
return retArr;
}``````

The following method returns addition (if `isAdd` is true) or subtraction (if`isAdd` 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;
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());

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());
ArrayList<double[]> tmpArr = new ArrayList<double[]>();
for(int i = 0; i < Ul.size(); i++){
tmpObj = getMaxUtility(Ul.get(i), P_omega,
consumptionSets.get(i));
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){
}

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

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];
}
...``````

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){
}
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

Comment (0)

Save
{{ articles.views | formatCount}} Views

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}