Experiments concerning frugal path mechanisms.
Published: 2005
Language: eng
Number of pages: 109
Description: In the path selection problem, we must find the least expensive path between two given points in a graph. This problem is easily solved in classical graph theory but the associated mechanism design problem, in which we strive to design a mechanism that selects a path and induces truthful reporting of costs without paying a high premium, is not as elegantly solved. In fact, all path selection mechanisms can be forced to pay a prohibitively high premium for truthfulness. As the worst-case performance bound is the same for any mechanism, how a given mechanism behaves in practice becomes very important. In this thesis we investigate the performance of three proposed mechanisms in two real-life scenarios, one geographical and one network-based.
Notes: Source: Masters Abstracts International, Volume: 44-02, page: 0935.

Advisor: A. Borodin.

Thesis (M.Sc.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.

GERSTEIN MICROTEXT copy on microfiche (2 microfiches).