Refine
Language
- English (6)
Keywords
- mechanism design (4)
- combinatorial optimization (3)
- cooperative game theory (3)
- cost sharing mechanisms (3)
- scheduling problems (3)
- Moulin mechanisms (1)
- acyclic mechanisms (1)
- cost sharing (1)
- game theory (1)
- network design problems (1)
Project
- B16 (5)
Application Area
- B (5)
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
Roughgarden and Sundararajan recently introduced an alternative measure
of efficiency for cost sharing mechanisms.
We study cost sharing methods for combinatorial optimization problems
using this novel efficiency measure, with a particular focus on
scheduling problems. While we prove a lower bound of $\Omega(\log n)$ for a very general class of problems, we give a best possible cost sharing method for minimum makespan scheduling. Finally, we show that no budget balanced cost sharing methods for completion or flow time objectives exist.
Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every rho-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and rho-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost.
About 15 years ago, Goemans and Williamson formally introduced the primal-dual framework for approximation algorithms and applied it to a class of network design optimization problems. Since then literally hundreds of results appeared that extended, modified and applied the technique to a wide range of optimization problems.
In this paper we define a class of cost-sharing games arising from Goemans and Williamson's original network design problems. We then show how to derive a group-strategyproof (i.e., collusion resistant) mechanism for such a game, using an existing primal-dual algorithm for the underlying optimization problem as a black box. The budget-balance factor of this mechanism is proportional to the performance ratio of the primal-dual algorithm if the optimization problem satisfies an additional technical condition.
Most existing collusion-resistant cost-sharing mechanisms are obtained through skillful adaptation of existing primal-dual algorithms for the associated optimization problems. This paper shows that, at least for a large class of games arising from network design problems, no such adaptation is necessary.
We propose an online model for general demand cost sharing games and identify critical properties for group-strategyproofness and weak group-strategyproofness of cost sharing mechanisms for these games. We define incremental online cost sharing mechanisms which can be derived from competitive algorithms.
Based on our general results, we develop online cost sharing mechanisms for several binary demand and general demand cost sharing games derived from network design and scheduling problems. Our results complement the work on incremental mechanisms by Moulin.
For many fundamental cooperative cost sharing games, especially when costs are supermodular, it is known that Moulin mechanisms inevitably suffer from poor budget balance factors. Mehta, Roughgarden, and Sundararajan recently introduced acyclic mechanisms, which achieve a slightly weaker notion of group-strategyproofness, but leave more flexibility to improve upon the approximation guarantees with respect to budget balance and social cost.
In this paper, we provide a very simple but powerful method for turning any rho-approximation algorithm for a combinatorial optimization problem into a rho-budget balanced acyclic mechanism. Hence, we show that there is no gap between the best possible approximation guarantees of full-knowledge approximation algorithms and weakly group-strategyproof cost sharing mechanisms.
The applicability of our method is demonstrated by deriving mechanisms for scheduling and network design problems which beat the best possible budget balance factors of Moulin mechanisms. By elaborating our framework, we provide means to construct weakly group-strategyproof mechanisms with approximate social cost. The mechanisms we develop for completion time scheduling problems perform surprisingly well by achieving the first constant budget balance and social cost factors.