{{announcement.body}}
{{announcement.title}}

Game Theory With Apache Spark, Part 2

DZone 's Guide to

Game Theory With Apache Spark, Part 2

We continue our look into Game Theory and Apache Spark by offering a more in-depth exploration of algorithms. Let's get started!

· Big Data Zone ·
Free Resource

Series So Far

Algorithm

Now we will discuss an algorithm that achieves optimal price and allocations. The algorithm consists of two parts. Part 1 involves finding the optimal price vector and part 2 involves finding an optimal allocation corresponding to the optimal price vector found in part 1.

Part 1: Optimal Price and Corresponding Assignments

Definitions

First, define a cost function:

C(P) := PT * S + ∑i ∈ {1,...,N} Vi(P)

Consider Qi(P) defined previously for i = 1, ..., N. Let Qi1(P) be defined as the K-dimensional vector where the j-th entry is 1 if and only if there exists an element in Qi(P) where the j-th entry is greater than 0, j = 1,..., K. In other words, if the j-th entry of Qi1(P) is 0 then for every element in Qi(P) the j-th entry must be 0; if the j-th entry of Qi1(P) is 1 then for at least one element in Qi(P) the j-th entry must be 1.

Part 1 starts with the initial price vector at 0, i.e. P = 0, and then at each iterative step finds a new price vector, built on the previous one, that minimizes C(P). At each step, the newly constructed price vector is guaranteed to be no less than the previous one. When the price vector no longer increases, i.e. the newly constructed and previous price vectors are equal, the optimal price Po has been reached. Along with Po we also obtain Qi1(Po), i = 1, ..., N, which we call optimal assignments. If the j-th entry of Qi1(Po) = 0 then agent i will not be allocated any units of resource type j. On the other hand, if the j-th entry of Qi1(Po) = 1 then agent i may be allocated some units of resource type j in Part 2 of the algorithm, although not necessarily.

Define Ω as the set of all K-dimensional vectors in which an element is either 0 or 1. For example, the following vectors are all members of Ω:

[0 0 ... 0]T, [1 0 ... 0]T, [0 1 ... 0]T, [1 1 ... 0]T, ..., [1 1 ... 1]T

The set Ω should be viewed as all possible 1-unit price increases over a given price vector.

For Part 1, we first need to calculate minω ∈ Ω C(P + ω).

Calculate minω ∈ Ω C(P + ω)

  • Initialize a scalar, minimum := -1.

  • Initialize a K-dimensional vector, Ptmp := null.

  • Initialize a set called Assignments, as an empty set.

  • For each element Ω repeat. (Let ω denote the element.)

    • Define Pω := Ptmp + ω

    • Calculate C(Pω)

    • If minimum < 0 or minimum > C(Pω) then 

      • minimum := C(Pω)

      • Assignments := {Q11(Pω), Q21(Pω), ..., QN1(Pω)}

      • Ptmp := Pω 

    • End If

  • End For

  • Return Ptmp (= minω ∈ Ω C(P + ω)) and Assignments

Part 1

Now, we can give Part 1 of the algorithm.

  • Initialize price vector Pmin := [0 0 ... 0]T

  • Initialize a K-dimensional vector, Pnew := null.
  • Initialize a set called OptimalAssignments, as an empty set.

  • Obtain set Ω. 

  • While true repeat

    • Calculate Pnew := minω ∈ Ω C(Pmin + ω)
    • If Pmin < Pnew // price increased

      • Pmin := Pnew

    • End If

    • Else // Pmin must be equal to Pnew and hence price no longer increases

      • P:= Pmin 
      • OptimalAssignments := Assignments (from calculation of  minω ∈ Ω C(Pmin + ω))
      • break While

    • End Else

  • End While

Hence, once the algorithm reaches a state where the price vector no longer increases, we have obtained Pto be Pmin and Qi1(Po) to be OptimalAssignments, i = 1, ..., N. 

Part 2: Allocations Corresponding to Optimal Price

Optimal price Pand OptimalAssignments from Part 1 are inputs to Part 2, where the goal is to find an optimal allocation.

Recall that OptimalAssignments is an ordered set consisting of N elements corresponding to agents 1, 2, ..., N. Each such element is a vector of dimension K where entry j is 0, if at the particular price no allocation of resource type j should be made to the agent, or 1, if at the particular price some allocation of resource type j could be, but not necessarily, made to the agent.

Let OptimalAssignmentsij, i = 1, ..., N, j = 1, ..., K, denote the j-th entry in the i-th element of OptimalAssignments, i.e. the entry for j-th resource type corresponding to i-th agent. Note that OptimalAssignmentsij ∈ {0, 1} for each i, j. Also let podenote the j-th element of Po, j = 1, ..., K, i.e. the optimal price for the j-th resource type.

Part 2 is executed for resource types, one by one. 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.

  • For each resource type j = 1, ..., K, define the amount of initial supply, Zj := Sj

  • For each agent i = 1, ..., N, and each resource type j = 1, ..., K, define Allocij := 0 as the initial allocation for agent i of resource type j.

  • For each resource type j = 1, ..., K repeat

    • For each agent i = 1, ..., N where OptimalAssignmentsij > 0 and uij > po

      • Allocate to agent amount of units Δ := min(Zj, Lij)

      • Zj := Zj - Δ, Allocij  : = Allocij  + Δ

    • End For

    • For each agent i = 1, ..., N where OptimalAssignmentsij > 0

      • Allocate to agent amount of units Δ := min(Zj, Lij - Allocij)

      • Zj := Zj - Δ, Allocij  : = Allocij  + Δ

    • End For

  • End For

Notice that there are two separate loops iterating through agents. The first loop processes the agent(s) (if any) that have bid a value greater than the set price for the corresponding resource type. Thus, those agents get their share of the goods before others. The second loop processes agents without any priority on value. At the end, xoij = Allocij, i = 1, ..., N, j = 1, ..., K.

Definitions Recap

For the reader's convenience, this section gives a listing of all the definitions in the algorithm. 

Symbol Description
K Number of resource types, > 0.
N

Number of agents, > 0.

S := [S1  S2  ... SK]T

Vector of available supply units for each resource type, S> 0, j = 1, ..., K.

uij 

Value coefficient indicating for agent i the value of resource type j, i = 1, ..., N, j = 1, ..., K; uij ≥ 0.

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

Vector of value coefficients for agent i, i = 1, ..., N.

Lij 

Indicates for agent i at most how many units of resource type j is needed; Lij ≥ 0, i = 1, ..., N, j = 1, ..., K.

P := [p1 p2 ... pK]T

Price vector where pj ≥ 0 corresponds to resource type j = 1, ..., K.

Xi

Set of all K-dimensional nonnegative integer vectors agent i could accept as part of an allocation,

also known as consumption set, i = 1, ..., N; for a vector in Xi, represented by x := [xi1 xi2 ... xiK]T,

dimension j corresponds to resource type j and is less than or equal to Lij, j = 1, ..., K.

Ui(x) - P*x

Utility of agent i at the price P, i = 1, ..., N.

Vi(P)

max x ∈ X{Ui(x) - P * x}, also known as the maximum utility agent i gets at the price P,

i = 1, ..., N.

Qi(P)

Subset of Xi where each element of Qi(P) achieves the maximum utility at price P, 

i = 1, ..., N. Equivalently, Qi(P) = arg max x ∈ X{Ui(x) - P * x} 

Qi1(P)

For i = 1, ..., N, this is the K-dimensional vector where the j-th entry is 1 if and only if there exists

an element in Qi(P) where the j-th entry is greater than 0, j = 1,..., K.

Po 

The optimal price.

xoij

An optimal allocation corresponding to optimal price, i = 1, ..., N, j = 1, ..., K. It holds that 

[xoi1 xoi2 ... xoiK] ∈ Xi, i = 1, ..., N.

C(P)

A particular cost function defined as PT * S + ∑i ∈ {1,...,N} Vi(P)

Ω

The set of all K-dimensional vectors in which an element is either 0 or 1.

Table 6

That's all for Part 2! Tune back in tomorrow when we dive into some code!

Topics:
big data ,apache kafka ,algorithm ,tutorial ,data science

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}