Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
59
0
0.0
(
0
)
Added by
Lane A. Hemaspaandra
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant--optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm. The problem of determining Dodgson winners is known to be complete for parallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is a ``frequently self-knowingly correct algorithm. We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenscheins junta distributions [PR07].
rate research
Read More
We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. We also study some features of probability weight of correctness with respect to generalizations of Procaccia and Rosenscheins junta distributions [PR07b].
In this short note, we describe an approval-based committee selection rule that admits a polynomial-time algorithm and satisfies the Extended Justified Representation (EJR) axiom. This rule is based on approximately maximizing the PAV score, by means of local search. Our proof strategy is to show that this rule provides almost optimal average satisfaction to all cohesive groups of voters, and that high average satisfaction for cohesive groups implies extended justified representation.
We investigate a class of weighted voting games for which weights are randomly distributed over the standard probability simplex. We provide close-formed formulae for the expectation and density of the distribution of weight of the $k$-th largest player under the uniform distribution. We analyze the average voting power of the $k$-th largest player and its dependence on the quota, obtaining analytical and numerical results for small values of $n$ and a general theorem about the functional form of the relation between the average Penrose--Banzhaf power index and the quota for the uniform measure on the simplex. We also analyze the power of a collectivity to act (Coleman efficiency index) of random weighted voting games, obtaining analytical upper bounds therefor.
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimise the average time per transition and player Max wants to maximise it. A solution of average-time games is presented using a reduction to average-price game on a finite graph. A direct consequence is an elementary proof of determinacy for average-time games. This complements our results for reachability-time games and partially solves a problem posed by Bouyer et al., to design an algorithm for solving average-price games on priced timed automata. The paper also establishes the exact computational complexity of solving average-time games: the problem is EXPTIME-complete for timed automata with at least two clocks.
We consider the classic principal-agent model of contract theory, in which a principal designs an outcome-dependent compensation scheme to incentivize an agent to take a costly and unobservable action. When all of the model parameters---including the full distribution over principal rewards resulting from each agent action---are known to the designer, an optimal contract can in principle be computed by linear programming. In addition to their demanding informational requirements, such optimal contracts are often complex and unintuitive, and do not resemble contracts used in practice. This paper examines contract theory through the theoretical computer science lens, with the goal of developing novel theory to explain and justify the prevalence of relatively simple contracts, such as linear (pure commission) contracts. First, we consider the case where the principal knows only the first moment of each actions reward distribution, and we prove that linear contracts are guaranteed to be worst-case optimal, ranging over all reward distributions consistent with the given moments. Second, we study linear contracts from a worst-case approximation perspective, and prove several tight parameterized approximation bounds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
