Approximation algorithms for distributed and selfish agents
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/33093 |
| _version_ | 1811089446887489536 |
|---|---|
| author | Mirrokni, Vahab S |
| author2 | Michel X. Goemans. |
| author_facet | Michel X. Goemans. Mirrokni, Vahab S |
| author_sort | Mirrokni, Vahab S |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. |
| first_indexed | 2024-09-23T14:19:19Z |
| format | Thesis |
| id | mit-1721.1/33093 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:19:19Z |
| publishDate | 2006 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/330932019-04-12T09:18:58Z Approximation algorithms for distributed and selfish agents Mirrokni, Vahab S Michel X. Goemans. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. Includes bibliographical references (p. 157-165). Many real-world systems involve distributed and selfish agents who optimize their own objective function. In these systems, we need to design efficient mechanisms so that system-wide objective is optimized despite agents acting in their own self interest. In this thesis, we develop approximation algorithms and decentralized mechanisms for various combinatorial optimization problems in such systems. First, we investigate the distributed caching and a general set of assignment problems. We develop an almost tight LP-based ... approximation algorithm and a local search ... approximation algorithm for these problems. We also design efficient decentralized mechanisms for these problems and study the convergence of the corresponding games. In the following chapters, we study the speed of convergence to high quality solutions on (random) best-response paths of players. First, we study the average social value on best response paths in basic-utility, market sharing, and cut games. Then, we introduce the sink equilibrium as a new equilibrium concept. We argue that, unlike Nash equilibria, the selfish behavior of players converges to sink equilibria and all strategic games have a sink equilibrium. To illustrate the use of this new concept, we study the social value of sink equilibria in weighted selfish routing (or weighted congestion) games and valid-utility (or submodular-utility) games. In these games, we bound the average social value on random best-response paths for sink equilibria.. Finally, we study cross-monotonic cost sharings and group-strategyproof mechanisms. (cont.) We study the limitations imposed by the cross-monotonicity property on cost-sharing schemes for several combinatorial optimization games including set cover and metric facility location. We develop a novel technique based on the probabilistic method for proving upper bounds on the budget-balance factor of cross-monotonic cost sharing schemes, deriving tight or nearly-tight bounds for these games. At the end, we extend some of these results to group-strategyproof mechanisms. by Vahab S. Mirrokni. Ph.D. 2006-06-19T17:39:49Z 2006-06-19T17:39:49Z 2005 2005 Thesis http://hdl.handle.net/1721.1/33093 62174049 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 165 p. 9483194 bytes 9492590 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Mirrokni, Vahab S Approximation algorithms for distributed and selfish agents |
| title | Approximation algorithms for distributed and selfish agents |
| title_full | Approximation algorithms for distributed and selfish agents |
| title_fullStr | Approximation algorithms for distributed and selfish agents |
| title_full_unstemmed | Approximation algorithms for distributed and selfish agents |
| title_short | Approximation algorithms for distributed and selfish agents |
| title_sort | approximation algorithms for distributed and selfish agents |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/33093 |
| work_keys_str_mv | AT mirroknivahabs approximationalgorithmsfordistributedandselfishagents |