Loading...
Please wait, while we are loading the content...
Similar Documents
Price of Anarchy of Non-Truthful Mechanisms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kesselheim, Thomas |
| Copyright Year | 2017 |
| Abstract | Since we started our discussion of mechanisms we were focused on designing truthful mechanisms. While for single-parameter settings the resulting monotonicity requirement turned out to be rather nice, this was not the case for multi-parameter mechanisms. In fact, very simple algorithms give the best approximation in polynomial time but they cannot be turned into truthful mechanisms. In this lecture we will explore a different direction, which consists of relaxing the incentive constraint. Instead of asking for truthful mechanisms, we will ask for mechanisms whose equilibria are all close to optimal. To this end we will translate the smoothness concept that we have seen a few lectures ago from games to mechanisms and use it to design simple, near-optimal mechanisms. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ls2-www.cs.tu-dortmund.de/grav/grav_files/people/kesselheim/AlgSpiel/skript12.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
