Auction Algorithm: Difference between revisions
Andrewgracyk (talk | contribs) No edit summary |
Andrewgracyk (talk | contribs) No edit summary |
||
| Line 4: | Line 4: | ||
== The Assignment Problem == | == The Assignment Problem == | ||
It is necessary to introduce the assignment problem because it applies a context in which we may apply our algorithm to find such an optimal equilibrium. Suppose we have both <math> N </math> buyers as well as <math> N </math> goods. We introduce <math> a_{ij} </math> to quantify the notion of some sort of utility, benefit, or happiness the buyer receives from their corresponding good. The assignment problem therefore seeks a way to maximize <math> \sum_i a_{i \sigma(i)} </math>, i.e., we hope to maximize the total | It is necessary to introduce the assignment problem because it applies a context in which we may apply our algorithm to find such an optimal equilibrium. Suppose we have both <math> N </math> buyers as well as <math> N </math> goods. We introduce <math> a_{ij} </math> to quantify the notion of some sort of utility, benefit, or happiness the buyer receives from their corresponding good. The assignment problem therefore seeks a way to maximize <math> \sum_i a_{i \sigma(i)} </math>, i.e., we hope to maximize the total utility. Note this is different from maximizing the utility of a particular buyer, because we seek to benefit the whole group the most. We use the index <math> i </math> to denote a particular buyer we use the second index <math> j = \sigma(i) </math> to denote the good, where <math> \sigma </math> is some permutation of the goods among all of the buyers. | ||
Revision as of 20:24, 14 May 2020
The auction algorithm[1] is an algorithm in optimal transport in which a set of buyers exchange goods for varied prices until an eventual equilibrium is reached. It is an iterative approach. The algorithm pertains to the discrete formulation of optimal transport, as well as provides a connection to the dual problem. The algorithm is useful in the field of economics because of its ability to find an equilibrium. The algorithm was invented by Bertsekas, but it was eventually updated.
The Assignment Problem
It is necessary to introduce the assignment problem because it applies a context in which we may apply our algorithm to find such an optimal equilibrium. Suppose we have both buyers as well as goods. We introduce to quantify the notion of some sort of utility, benefit, or happiness the buyer receives from their corresponding good. The assignment problem therefore seeks a way to maximize , i.e., we hope to maximize the total utility. Note this is different from maximizing the utility of a particular buyer, because we seek to benefit the whole group the most. We use the index to denote a particular buyer we use the second index to denote the good, where is some permutation of the goods among all of the buyers.
References
Cite error: <ref> tag with name "Santambrogio" defined in <references> is not used in prior text.