2011/03/13 by Uriel Feige, Feige, Uriel, Moshe Tennenholtz +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1103.2520
openalex publication_date 2011/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a task of scheduling with a common deadline on a single machine.\nEvery player reports to a scheduler the length of his job and the scheduler\nneeds to finish as many jobs as possible by the deadline. For this simple\nproblem, there is a truthful mechanism that achieves maximum welfare in\ndominant strategies. The new aspect of our work is that in our setting players\nare uncertain about their own job lengths, and hence are incapable of providing\ntruthful reports (in the strict sense of the word). For a probabilistic model\nfor uncertainty our main results are as follows.\n 1) Even with relatively little uncertainty, no mechanism can guarantee a\nconstant fraction of the maximum welfare.\n 2) To remedy this situation, we introduce a new measure of economic\nefficiency, based on a notion of a em fair share of a player, and design\nmechanisms that are \Ω(1)-fair. In addition to its intrinsic appeal, our\nnotion of fairness implies good approximation of maximum welfare in several\ncases of interest.\n 3) In our mechanisms the machine is sometimes left idle even though there are\njobs that want to use it. We show that this unfavorable aspect is unavoidable,\nunless one gives up other favorable aspects (e.g., give up\n\Ω(1)-fairness).\n We also consider a qualitative approach to uncertainty as an alternative to\nthe probabilistic quantitative model. In the qualitative approach we break away\nfrom solution concepts such as dominant strategies (they are no longer well\ndefined), and instead suggest an axiomatic approach, which amounts to listing\ndesirable properties for mechanisms. We provide a mechanism that satisfies\nthese properties.\n