Auction Algorithm: Difference between revisions
Jump to navigation
Jump to search
Andrewgracyk (talk | contribs) No edit summary |
Andrewgracyk (talk | contribs) No edit summary |
||
| Line 3: | Line 3: | ||
==The Assignment Problem== | ==The Assignment Problem== | ||
We begin by discussing the assignment problem. Consider the specialized case when weights <math> a_i </math> and <math> b_j </math> are equal. Suppose we have <math> N </math> buyers, denoting the index with <math> i </math>, and <math> N </math> goods to be bought, denoted by <math> j </math>. We look for an assignment <math> j = \sigma(i), \sigma \in S_N </math> which maximizes <math> \sum_{i} u_{i \sigma(i)} </math>. The values <math> u_{ij} </math> are the utilities of buyer <math> i </math> when he/she buys item <math> j </math>. Now, we look at a price system <math> p = (p_j)_j </math>. Given a price system <math> p </math> and as assignment <math> \sigma </math>, we say that it is an equilibrium if for every <math> i </math>, we have <math> u_{i \sigma(i)} - p_{\sigma_i} = max_j u_{ij} - p_j </math>. | We begin by discussing the assignment problem. Consider the specialized case when weights <math> a_i </math> and <math> b_j </math> are equal. Suppose we have <math> N </math> buyers, denoting the index with <math> i </math>, and <math> N </math> goods to be bought, denoted by <math> j </math>. We look for an assignment <math> j = \sigma(i), \sigma \in S_N </math> which maximizes <math> \sum_{i} u_{i \sigma(i)} </math>. The values <math> u_{ij} </math> are the utilities of buyer <math> i </math> when he/she buys item <math> j </math>. Now, we look at a price system <math> p = (p_j)_j </math>. Given a price system <math> p </math> and as assignment <math> \sigma </math>, we say that it is an equilibrium if for every <math> i </math>, we have <math> u_{i \sigma(i)} - p_{\sigma_i} = \max_j u_{ij} - p_j </math>. | ||
Revision as of 03:22, 5 May 2020
The auction algorithm is an algorithm connected to the dual problem, but it is not based on a sequence of improvements of the dual objective function. Instead, it attempts to seek an equilibrium. Because of such, the algorithm has applications in economics.
The Assignment Problem
We begin by discussing the assignment problem. Consider the specialized case when weights and are equal. Suppose we have buyers, denoting the index with , and goods to be bought, denoted by . We look for an assignment which maximizes . The values are the utilities of buyer when he/she buys item . Now, we look at a price system . Given a price system and as assignment , we say that it is an equilibrium if for every , we have .
