We study the problem of designing a distributed voting scheme for electing a candidate that maximizes the preferences of a set of agents. We assume the preference of agent i for candidate j is a real number xi,j, and we do not make any assumptions on the mechanism generating these preferences. We show simple randomized voting schemes guaranteeing the election of a candidate whose expected total preference is nearly the highest among all candidates. The algorithms we consider are designed so that...

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our...

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization....

A vertex i of a graph G = (V,E) is said to be controlled by $M\subseteq V$ if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex $i\in V$ is controlled by M. Given a set $M\subseteq V$ and two graphs G1 = ($V,E_1$) and G2 = ($V,E_2$) where $E_1\subseteq E_2$, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where $E_1\subseteq E\subseteq E_2$) such that M is a monopoly in G = (V,E). If the answer to the mvp is No, we then consider...

A vertex i of a graph G = (V,E) is said to be controlled by $M\subseteq V$ if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex $i\in V$ is controlled by M. Given a set $M\subseteq V$ and two graphs G1 = ($V,E_1$) and G2 = ($V,E_2$) where $E_1\subseteq E_2$, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where $E_1\subseteq E\subseteq E_2$) such that M is a monopoly in G = (V,E). If the answer to the mvp is No, we then consider...

We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also yield polynomial...