# 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!

Join the DZone community and get the full member experience.

Join For Free## 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) := P^{T} * S + ∑_{i ∈ {1,...,N}} V_{i}(P)

Consider Q_{i}(P) defined previously for i = 1, ..., N. Let Q_{i}^{1}(P) be defined as the K-dimensional vector where the j-th entry is 1 if and only if there exists an element in Q_{i}(P) where the j-th entry is greater than 0, j = 1,..., K. In other words, if the j-th entry of Q_{i}^{1}(P) is 0 then for every element in Q_{i}(P) the j-th entry must be 0; if the j-th entry of Q_{i}^{1}(P) is 1 then for at least one element in Q_{i}(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 P^{o} has been reached. Along with P^{o} we also obtain Q_{i}^{1}(P^{o}), i = 1, ..., N, which we call *optimal assignments*. If the j-th entry of Q_{i}^{1}(P^{o}) = 0 then agent i will not be allocated any units of resource type j. On the other hand, if the j-th entry of Q_{i}^{1}(P^{o}) = 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 + ω)

_{ω ∈ Ω}C(P + ω)

Initialize a scalar, minimum := -1.

Initialize a K-dimensional vector, P

_{tmp}:= null.Initialize a set called

__Assignments__, as an empty set.For each element Ω repeat. (Let ω denote the element.)

Define P

_{ω}:= P_{tmp}+ ωCalculate C(P

_{ω})If minimum < 0 or minimum > C(P

_{ω}) thenminimum := C(P

_{ω})__Assignments__:= {Q_{1}^{1}(P_{ω}), Q_{2}^{1}(P_{ω}), ..., Q_{N}^{1}(P_{ω})}P

_{tmp }:= P_{ω}

End If

End For

Return P

_{tmp }(= min_{ω ∈ Ω}C(P + ω)) and__Assignments__

#### Part 1

Now, we can give Part 1 of the algorithm**.**

Initialize price vector P

_{min}:= [0 0 ... 0]^{T}- Initialize a K-dimensional vector, P
_{new}:= null. Initialize a set called

__OptimalAssignments__, as an empty set.Obtain set Ω.

While true repeat

- Calculate P
_{new}:= min_{ω ∈ Ω}C(P_{min}+ ω) If P

_{min}< P_{new }*// price increased*P

_{min }:= P_{new}

End If

Else

*// P*_{min}must be equal to P_{new}and hence price no longer increases- P
^{o }:= P_{min} __OptimalAssignments__:=__Assignments__(from calculation of min_{ω ∈ Ω}C(P_{min}+ ω))break While

- P
End Else

- Calculate P
End While

Hence, once the algorithm reaches a state where the price vector no longer increases, we have obtained P^{o }to be P_{min} and Q_{i}^{1}(P^{o}) to be __OptimalAssignments__, i = 1, ..., N.

**Part 2: Allocations Corresponding to Optimal Price**

Optimal price P^{o }and __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 __OptimalAssignments___{ij}, 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 __OptimalAssignments___{ij} ∈ {0, 1} for each i, j. Also let p^{o}_{j }denote the j-th element of P^{o}, 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, Z

_{j}:= S_{j}For each agent i = 1, ..., N, and each resource type j = 1, ..., K, define Alloc

_{ij}:= 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

__OptimalAssignments___{ij}> 0 and u_{ij}> p^{o}_{j }Allocate to agent amount of units Δ := min(Z

_{j}, L_{ij})Z

_{j}:= Z_{j}- Δ, Alloc_{ij}: = Alloc_{ij}+ Δ

End For

For each agent i = 1, ..., N where

__OptimalAssignments___{ij}> 0Allocate to agent amount of units Δ := min(Z

_{j}, L_{ij }- Alloc_{ij})Z

_{j}:= Z_{j}- Δ, Alloc_{ij}: = Alloc_{ij}+ Δ

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, x^{o}_{ij }= Alloc_{ij}, 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 := [S |
Vector of available supply units for each resource type, S |

u |
Value coefficient indicating for agent i the value of resource type j, i = 1, ..., N, j = 1, ..., K; u |

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

L |
Indicates for agent i at most how many units of resource type j is needed; L |

P := [p |
Price vector where p |

X |
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 X dimension j corresponds to resource type j and is less than or equal to L |

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

V |
max i = 1, ..., N. |

Q |
Subset of X i = 1, ..., N. Equivalently, Q |

Q |
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 Q |

P |
The optimal price. |

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

C(P) |
A particular cost function defined as 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!

Opinions expressed by DZone contributors are their own.

Comments