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.
Join the DZone community and get the full member experience.
Join For FreeSeries 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 ∈ 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.
Opinions expressed by DZone contributors are their own.
Comments