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. AI/ML
  4. Game Theory With Apache Spark, Part 4

Game Theory With Apache Spark, Part 4

We wrap up this interesting look into game theory and Apache Spark by finalizing the algorithms and Java code we started last time.

Konur Unyelioglu user avatar by
Konur Unyelioglu
·
Nov. 12, 18 · Tutorial
Like (3)
Save
Tweet
Share
6.09K 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

  • Game Theory With Apache Spark, Part 3

Bringing Pieces Together: Example 1

Now let us revisit Example 1 from the previous article and employ Part 1 and 2 algorithms to obtain the results in Table 3. We start with constructing variables Ul and consumptionSets that correspond to the rows U and L in Table 2 for each agents 1 - 4.

private static void Example1(){
    double cons_set1_vals[] = {0,8,4,2,8,4,2,8,4};
    DenseVector consSet1 = new DenseVector(cons_set1_vals);

    double u1_vals[] = {0,2,3,5,2,3,6,3,6};
    DenseVector u1 = new DenseVector(u1_vals);

    double cons_set2_vals[] = {4,4,0,0,8,6,0,4,2};
    DenseVector consSet2 = new DenseVector(cons_set2_vals);

    double u2_vals[] = {2,3,0,0,2,4,0,3,5};
    DenseVector u2 = new DenseVector(u2_vals);

    double cons_set3_vals[] = {1,2,4,2,4,2,1,8,4};
    DenseVector consSet3 = new DenseVector(cons_set3_vals);

    double u3_vals[] = {1,2,3,3,1,2,3,1,1};
    DenseVector u3 = new DenseVector(u3_vals);

    double cons_set4_vals[] = {2,1,0,0,2,1,0,1,0};
    DenseVector consSet4 = new DenseVector(cons_set4_vals);

    double u4_vals[] = {5,2,0,0,3,2,0,4,0};
    DenseVector u4 = new DenseVector(u4_vals);

    ArrayList<Vector> Ul = new ArrayList<Vector>();
    Ul.add(u1);
    Ul.add(u2);
    Ul.add(u3);
    Ul.add(u4);

    ArrayList<Vector> consumptionSets = new ArrayList<Vector>();
    consumptionSets.add(consSet1);
    consumptionSets.add(consSet2);
    consumptionSets.add(consSet3);
    consumptionSets.add(consSet4);
...

Then, we define S, the available supply units from Table 1.

    double S_vals[] = {4,2,1,1,4,4,1,4,2};
    DenseVector S = new DenseVector(S_vals);
...

Finally, we call getOptimalAssignmentsAndPrice() to obtain the optimal price and corresponding assignments. We then pass those values to  getAllocations() to obtain the allocations corresponding to the optimal price.

AssignmentsAndPrice Optimal = getOptimalAssignmentsAndPrice(Ul, S, 
    consumptionSets);
    getAllocations(Optimal.price, Ul, S, consumptionSets, Optimal.assignmentsL);
}

We placed a breakpoint in the last statement in  getAllocations(), i.e. next to return allocations, to view the variables via the debugger. That gives us the results in Table 3.

Variables in debugger that show optimal price and allocations for Example 1.

Figure 4. Variables in the debugger that show optimal price and allocations for Example 1.

Bringing Pieces Together: Example 2

Let us revisit Example 2 from the previous article and employ Part 1 and 2 algorithms to obtain the results in Table 5. We start with constructing variables  Ul and  consumptionSets that correspond to the rows U and L in Table 4 for each agents 1 - 4.

private static void Example2_Step1(){

    double cons_set1_vals[] = {50,20,30,100,0,0,0,0,0,0,0};
    DenseVector consSet1 = new DenseVector(cons_set1_vals);

    double u1_vals[] = {3,3,0,6,0,0,0,0,0,0,0};
    DenseVector u1 = new DenseVector(u1_vals);


    double cons_set2_vals[] = {40,40,20,50,0,0,0,0,0,0,0};
    DenseVector consSet2 = new DenseVector(cons_set2_vals);

    double u2_vals[] = {5,5,0,8,0,0,0,0,0,0,0};
    DenseVector u2 = new DenseVector(u2_vals);


    double cons_set3_vals[] = {0,0,0,0,20,20,10,50,0,0,0};
    DenseVector consSet3 = new DenseVector(cons_set3_vals);

    double u3_vals[] = {0,0,0,0,5,5,5,5,0,0,0};
    DenseVector u3 = new DenseVector(u3_vals);


    double cons_set4_vals[] = {0,0,50,0,80,30,40,50,100,100,50};
    DenseVector consSet4 = new DenseVector(cons_set4_vals);

    DenseVector u4 = (Vectors.zeros(11)).toDense();

    ArrayList<Vector> Ul = new ArrayList<Vector>();
    Ul.add(u1);
    Ul.add(u2);
    Ul.add(u3);
    Ul.add(u4);

    ArrayList<Vector> consumptionSets = new ArrayList<Vector>();
    consumptionSets.add(consSet1);
    consumptionSets.add(consSet2);
    consumptionSets.add(consSet3);
    consumptionSets.add(consSet4);
...

Then, we define S, the available supply units from Table 4.

    double S_vals[] = {50,50,100, 50, 100, 50, 50, 100, 100, 100, 50};
    DenseVector S = new DenseVector(S_vals);
...

Finally, we call  getOptimalAssignmentsAndPrice() to obtain the optimal price and corresponding assignments. We then pass those values to getAllocations() to obtain the allocations corresponding to the optimal price.

    AssignmentsAndPrice Optimal = getOptimalAssignmentsAndPrice(Ul, S,
       consumptionSets);
    getAllocations(Optimal.price, Ul, S, consumptionSets, Optimal.assignmentsL);
}

We placed a breakpoint in the last statement in getAllocations(), i.e. next to return allocations, to view the variables via debugger. That shows us below giving the results in Table 5. 

Variables in debugger that show optimal price and allocations for Example 2, step 1.

Figure 5. Variables in the debugger that show the optimal price and allocations for Example 2, step 1.

Goods are transported based on the above allocation to achieve the state summarized in the below figure, where the number of goods transported over each link is highlighted in red.

Transportation of goods after step 1 is completed.

Figure 6. Transportation of goods after step 1 is completed. (Copy from Figure 2.)

For step 2, a new formulation is created as shown below. For agent 2, the values for each transportation link is greater than those for agents 1, 3, because the shipping of B type goods has higher priority (5 vs 4).

Resource Type  1 2 3 4 5 6 7 8 9 10 11
Description

Link
1-3

Link
1-4

Link
1-5

Link
1-6

Link
2-3

Link
2-4

Link
2-5

Link
2-6

Link
3-6

Link
4-6

Link
5-6

S 50 50 100 50 100 50 50 100 100 100 50
Agent 1 (A)
U 0 0 4 4 0 0 0 0 4 4 4
L 0 0 100 50 0 0 0 0 10 10 30
Agent 2 (B)
U 0 0 0 0 0 0 0 0 5 5 5
L 0 0 0 0 0 0 0 0 40 40 20
Agent 3 (C)
U 0 0 0 0 0 0 0 0 4 4 4
L 0 0 0 0 0 0 0 0 20 20 10
Agent 4 (auxiliary)
U 0 0 0 0 0 0 0 0 0 0 0
L 50 50 0 0 100 50 50 100 30 30 0

Table 7

In terms of our code, information in Table 7 is utilized similarly to the previous step.

private static void Example2_Step2(){

    double cons_set1_vals[] = {0,0,100, 50,0,0,0,0,10,10,30};
    DenseVector consSet1 = new DenseVector(cons_set1_vals);

    double u1_vals[] = {0,0,4,4,0,0,0,0,4,4,4};
    DenseVector u1 = new DenseVector(u1_vals);


    double cons_set2_vals[] = {0,0,0,0,0,0,0,0,40,40,20};
    DenseVector consSet2 = new DenseVector(cons_set2_vals);

    double u2_vals[] = {0,0,0,0,0,0,0,0,5,5,5};
    DenseVector u2 = new DenseVector(u2_vals);


    double cons_set3_vals[] = {0,0,0,0,0,0,0,0,20,20,10};
    DenseVector consSet3 = new DenseVector(cons_set3_vals);

    double u3_vals[] = {0,0,0,0,0,0,0,0,4,4,4};
    DenseVector u3 = new DenseVector(u3_vals);


    double cons_set4_vals[] = {50,50,0,0,100,50,50,100,30,30,0};
    DenseVector consSet4 = new DenseVector(cons_set4_vals);

    DenseVector u4 = (Vectors.zeros(11)).toDense();

    ArrayList<Vector> Ul = new ArrayList<Vector>();
    Ul.add(u1);
    Ul.add(u2);
    Ul.add(u3);
    Ul.add(u4);

    ArrayList<Vector> consumptionSets = new ArrayList<Vector>();
    consumptionSets.add(consSet1);
    consumptionSets.add(consSet2);
    consumptionSets.add(consSet3);
    consumptionSets.add(consSet4);

    double S_vals[] = {50,50,100,50,100,50,50,100,100,100,50};
    DenseVector S = new DenseVector(S_vals);

    AssignmentsAndPrice Optimal = getOptimalAssignmentsAndPrice(Ul, S, 
    consumptionSets);
    getAllocations(Optimal.price, Ul, S, consumptionSets, Optimal.assignmentsL);

}

The debug point shows us the final results as follows.

Variables in debugger that show optimal price and allocations for Example 2, step 2.

Figure 7. Variables in the debugger that show the optimal price and allocations for Example 2, step 2.

Hence, the algorithm yields the following optimal price and allocations.

Resource Type        1 2 3 4 5 6 7 8 9 10 11
Description

Link
1-3

Link
1-4

Link
1-5

Link
1-6

Link
2-3

Link
2-4

Link
2-5

Link
2-6

Link
3-6

Link
4-6

Link
5-6

Price 0 0 0 0 0 0 0 0 0 0 4

Agent 1 (A)

0 0 100 50 0 0 0 0 10 10 30

Agent 2 (B)

0 0 0 0 0 0 0 0 40 40 20

Agent 3 (C)

0 0 0 0 0 0 0 0 20 20 0

Agent 4 (auxiliary)

50 50 0 0 100 50 50 100 30 30 0

Table 8

Goods are transported based on the above allocation to achieve the state summarized in the below figure, where the number of goods transported over each link is highlighted in red.

Figure 6. Transportation of goods after step 2 is completed.

Figure 8. Transportation of goods after step 2 is completed.

At this point, all type B goods have been transported. The process is repeated three more times to complete transportation of type A and C goods. Those steps (3 - 5) are shown below (for simplicity we omitted the coding details as those are similar to the code above). 


Transportation of goods after steps 3 - 5 are completed.

Figure 9. Transportation of goods after steps 3 - 5 are completed.

Conclusion

In this article, we discussed an algorithm based on game theory for optimal resource allocation. The algorithm provides a fairness-based equilibrium where every agent (bidder) maximizes its utility and the resource manager (auctioneer) maximizes the price of the resources it is allocating. In addition, all the available units are allocated across all resource types and no agent is forced to take more than it is willing to. The algorithm is based on economist Ausubel's Efficient Dynamic Auction Method.

We showed via two examples that the algorithm can be applied to different types of resource allocation problems. In one example, we applied the algorithm to allocate cloud computing resources, e.g. CPU, memory, bandwidth, to computing clients. Secondly, we applied the algorithm to a logistics example where various types of goods are transported over shared transportation resources. 

We provided an implementation of the algorithm using Apache Spark Machine Learning Library and reviewed the corresponding Java code. Apache Spark Machine Learning Library is particularly useful to implement the algorithm because the corresponding Java API has built-in vector operations, which are essential to execute the algorithm.

In various respects, the dynamic auction method in Ausubel's original paper is more extensive than the version we considered in this article. Firstly, in this article we restricted the value function Ui(x) to be a linear function over x. However, the original algorithm does not have that restriction. Instead, a broader class of concave functions are allowed. Our restriction is for simplicity but also we believe that a linear value function is still very potent in many practical applications (interested users can refer to this article for a review of various concave functions that can be used as a value function in the original paper). Secondly, the original algorithm to find the optimal price does not necessarily start from an initial price vector at 0. However, to deal with an initial price vector different from 0, the algorithm has a descending section as well as an ascending one and hence it is more complex. By restricting the initial price vector to be 0 our implementation became simpler. Thirdly, for the purposes of coherence, we divided the algorithm into parts 1 and 2. Although those concepts are inherent the original algorithm does not have an explicit breakup in that manner.Konur Unyelioglu

Apache Spark Links Algorithm Database Machine learning

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Top 5 Node.js REST API Frameworks
  • Why You Should Automate Code Reviews
  • Data Mesh vs. Data Fabric: A Tale of Two New Data Paradigms
  • Spring Cloud: How To Deal With Microservice Configuration (Part 1)

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: