Date: Thu, 9 May 2024 | Total: 6
Partially observable Markov decision processes (POMDPs) rely on the key assumption that probability distributions are precisely known. Robust POMDPs (RPOMDPs) alleviate this concern by defining imprecise probabilities, referred to as uncertainty sets. While robust MDPs have been studied extensively, work on RPOMDPs is limited and primarily focuses on algorithmic solution methods. We expand the theoretical understanding of RPOMDPs by showing that 1) different assumptions on the uncertainty sets affect optimal policies and values; 2) RPOMDPs have a partially observable stochastic game (POSG) semantic; and 3) the same RPOMDP with different assumptions leads to semantically different POSGs and, thus, different policies and values. These novel semantics for RPOMDPS give access to results for the widely studied POSG model; concretely, we show the existence of a Nash equilibrium. Finally, we classify the existing RPOMDP literature using our semantics, clarifying under which uncertainty assumptions these existing works operate.
We present version 2.0 of the Partial Exploration Tool (PET), a tool for verification of probabilistic systems. We extend the previous version by adding support for stochastic games, based on a recent unified framework for sound value iteration algorithms. Thereby, PET2 is the first tool implementing a sound and efficient approach for solving stochastic games with objectives of the type reachability/safety and mean payoff. We complement this approach by developing and implementing a partial-exploration based variant for all three objectives. Our experimental evaluation shows that PET2 offers the most efficient partial-exploration based algorithm and is the most viable tool on SGs, even outperforming unsound tools.
An election is defined as a pair of a set of candidates C=\{c_1,\cdots,c_m\} and a multiset of votes V=\{v_1,\cdots,v_n\}, where each vote is a linear order of the candidates. The Borda election rule is characterized by a vector \langle m-1,m-2,\cdots,0\rangle, which means that the candidate ranked at the i-th position of a vote v receives a score m-i from v, and the candidate receiving the most score from all votes wins the election. Here, we consider the control problems of a Borda election, where the chair of the election attempts to influence the election outcome by adding or deleting either votes or candidates with the intention to make a special candidate win (constructive control) or lose (destructive control) the election. Control problems have been extensively studied for Borda elections from both classical and parameterized complexity viewpoints. We complete the parameterized complexity picture for Borda control problems by showing W[2]-hardness with the number of additions/deletions as parameter for constructive control by deleting votes, adding candidates, or deleting candidates. The hardness result for deleting votes settles an open problem posed by Liu and Zhu. Following the suggestion by Menon and Larson, we also investigate the impact of introducing top-truncated votes, where each voter ranks only t out of the given m candidates, on the classical and parameterized complexity of Borda control problems. Constructive Borda control problems remain NP-hard even with t being a small constant. Moreover, we prove that in the top-truncated case, constructive control by adding/deleting votes problems are FPT with the number \ell of additions/deletions and t as parameters, while for every constant t\geq 2, constructive control by adding/deleting candidates problems are W[2]-hard with respect to \ell.
In many real-world applications of committee elections, the candidates are associated with certain attributes and the chosen committee is required to satisfy some constraints posed on the candidate attributes. For instance, when dress collocation, it is generally acknowledged that when wearing a tie, you'd better wear a shirt, and wearing a suit, you'd better wear leather shoes. Here, dresses are categorized by upper garment, lower garment, shoes et.al, and upper garment is with the attribute tie and shirt, lower garment is with the attribute suit, and shoes is with the attribute leather. And two constraints "tie infers shirt" and "suit infers leather shoes" are proposed. We study this variant of committee elections from the computational complexity viewpoint. Given a set of candidates, each with some attributes and a profit, and a set of constraints, given as propositional logical expressions of the attributes, the task is to compute a set of k candidates, whose attributes satisfy all constraints and whose total profit achieves a given bound. We achieve a dichotomy concerning classical complexity with no length limit on constraints: the problem is polynomial-time solvable, if the following two conditions are fulfilled: 1) each candidate has only one attribute and 2) each attribute occurs at most once in the constraints. It becomes NP-hard if one of the two conditions is violated. Moreover, we examine its parameterized complexity. The parameterization with the number of constraints, the size of the committee, or the total profit bound as parameter leads to para-NP-hardness or W[1]-hardness, while with the number of attributes or the number of candidates as parameter, the problem turns out to be fixed-parameter tractable.
In Hotelling's model of spatial competition, a unit mass of voters is distributed in the interval $[0,1]$ (with their location corresponding to their political persuasion), and each of $m$ candidates selects as a strategy his distinct position in this interval. Each voter votes for the nearest candidate, and candidates choose their strategy to maximize their votes. It is known that if there are more than two candidates, equilibria may not exist in this model. It was unknown, however, how close to an equilibrium one could get. Our work studies approximate equilibria in this model, where a strategy profile is an (additive) $\epsilon$-equilibria if no candidate can increase their votes by $\epsilon$, and provides tight or nearly-tight bounds on the approximation $\epsilon$ achievable. We show that for 3 candidates, for any distribution of the voters, $\epsilon \ge 1/12$. Thus, somewhat surprisingly, for any distribution of the voters and any strategy profile of the candidates, at least $1/12$th of the total votes is always left ``on the table.'' Extending this, we show that in the worst case, there exist voter distributions for which $\epsilon \ge 1/6$, and this is tight: one can always compute a $1/6$-approximate equilibria. We then study the general case of $m$ candidates, and show that as $m$ grows large, we get closer to an exact equilibrium: one can always obtain an $1/(m+1)$-approximate equilibria in polynomial time. We show this bound is asymptotically tight, by giving voter distributions for which $\epsilon \ge 1/(m+3)$.
We consider a truthful two-facility location problem in which there is set of agents with private locations on the line of real numbers, and the goal is to place two facilities at different locations chosen from the set of those reported by the agents. Given a feasible solution, each agent suffers an individual cost which is either its total distance to both facilities (sum-variant) or its distance to the farthest facility (max-variant). For both variants, we show tight bounds on the approximation ratio of deterministic and randomized mechanisms in terms of the social cost, the total individual cost of the agents.