| ชื่อเรื่อง | : | The speed of convergence in congestion games under best-response dynamics. |
| นักวิจัย | : | Fanelli, Angelo. , Flammini, Michele. , Moscardelli, Luca. |
| คำค้น | : | - |
| หน่วยงาน | : | Nanyang Technological University, Singapore |
| ผู้ร่วมงาน | : | - |
| ปีพิมพ์ | : | 2555 |
| อ้างอิง | : | Fanelli, A., Flammini, M., & Moscardelli, L. (2012). The speed of convergence in congestion games under best-response dynamics. ACM Transactions on Algorithms, 8(3). , 1549-6325 , http://hdl.handle.net/10220/12291 , http://dx.doi.org/10.1145/2229163.2229169 |
| ที่มา | : | - |
| ความเชี่ยวชาญ | : | - |
| ความสัมพันธ์ | : | ACM transactions on algorithms |
| ขอบเขตของเนื้อหา | : | - |
| บทคัดย่อ/คำอธิบาย | : | We investigate the speed of convergence of best response dynamics to approximately optimal solutions in congestion games with linear delay functions. In Ackermann et al. [2008] it has been shown that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n. Motivated by such a negative result, we focus on the study of the states (not necessarily being equilibria) reached after a limited number of players' selfish moves, and we show that Θ(n log log n) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that every O(n) steps each player performs a constant (and nonnull) number of best responses. We show that such result is tight also for the simplest case of singleton congestion games. |
| บรรณานุกรม | : |
Fanelli, Angelo. , Flammini, Michele. , Moscardelli, Luca. . (2555). The speed of convergence in congestion games under best-response dynamics..
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Fanelli, Angelo. , Flammini, Michele. , Moscardelli, Luca. . 2555. "The speed of convergence in congestion games under best-response dynamics.".
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Fanelli, Angelo. , Flammini, Michele. , Moscardelli, Luca. . "The speed of convergence in congestion games under best-response dynamics.."
กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2555. Print. Fanelli, Angelo. , Flammini, Michele. , Moscardelli, Luca. . The speed of convergence in congestion games under best-response dynamics.. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2555.
|
ridm@nrct.go.th ระบบคลังข้อมูลงานวิจัยไทย รายการโปรดที่คุณเลือกไว้
