Evolutionary dynamics and fast convergence in the assignment game
We study decentralized learning dynamics for the classic assignment game with transferable utility. At random points in time firms and workers match, break up, and re-match in the sesarch for better opportunities. We propose a simple learning process in which players have no knowledge about other...
| Main Author: | |
|---|---|
| Format: | Working paper |
| Published: |
University of Oxford
2014
|
| _version_ | 1826305247853674496 |
|---|---|
| author | Pradelski, B |
| author_facet | Pradelski, B |
| author_sort | Pradelski, B |
| collection | OXFORD |
| description | We study decentralized learning dynamics for the classic assignment game with transferable utility. At random points in time firms and workers match, break up, and re-match in the sesarch for better opportunities. We propose a simple learning process in which players have no knowledge about other players' payoffs or actions and they update their behavior in a myopic fashion. Behavior fluctuates according to a random variable that reflects current market conditions: sometimes the firms exhibit greater price stickiness than the workers, and at other times the reverse holds. We show that this stochastic learning process converges in polynomial time to the core. While convergence to the core is known for some types of decentralized dynamics this paper is the first to prove fast convergence, a crucial feature from a practical standpoint. The proof relies on novel results for random walks on graphs, and more generally suggests a fruitful connection between the theory of random walks and matching theory. |
| first_indexed | 2024-03-07T06:30:01Z |
| format | Working paper |
| id | oxford-uuid:f5acf754-310c-4b9f-8526-5f71e68cd4d1 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:30:01Z |
| publishDate | 2014 |
| publisher | University of Oxford |
| record_format | dspace |
| spelling | oxford-uuid:f5acf754-310c-4b9f-8526-5f71e68cd4d12022-03-27T12:28:59ZEvolutionary dynamics and fast convergence in the assignment gameWorking paperhttp://purl.org/coar/resource_type/c_8042uuid:f5acf754-310c-4b9f-8526-5f71e68cd4d1Bulk import via SwordSymplectic ElementsUniversity of Oxford2014Pradelski, BWe study decentralized learning dynamics for the classic assignment game with transferable utility. At random points in time firms and workers match, break up, and re-match in the sesarch for better opportunities. We propose a simple learning process in which players have no knowledge about other players' payoffs or actions and they update their behavior in a myopic fashion. Behavior fluctuates according to a random variable that reflects current market conditions: sometimes the firms exhibit greater price stickiness than the workers, and at other times the reverse holds. We show that this stochastic learning process converges in polynomial time to the core. While convergence to the core is known for some types of decentralized dynamics this paper is the first to prove fast convergence, a crucial feature from a practical standpoint. The proof relies on novel results for random walks on graphs, and more generally suggests a fruitful connection between the theory of random walks and matching theory. |
| spellingShingle | Pradelski, B Evolutionary dynamics and fast convergence in the assignment game |
| title | Evolutionary dynamics and fast convergence in the assignment game |
| title_full | Evolutionary dynamics and fast convergence in the assignment game |
| title_fullStr | Evolutionary dynamics and fast convergence in the assignment game |
| title_full_unstemmed | Evolutionary dynamics and fast convergence in the assignment game |
| title_short | Evolutionary dynamics and fast convergence in the assignment game |
| title_sort | evolutionary dynamics and fast convergence in the assignment game |
| work_keys_str_mv | AT pradelskib evolutionarydynamicsandfastconvergenceintheassignmentgame |