Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPersuading Voters: Its Easy to Whisper, Its Hard to Speak Loud
91
0
0.0
(
0
)
Added by
Andrea Celli
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We focus on the following natural question: is it possible to influence the outcome of a voting process through the strategic provision of information to voters who update their beliefs rationally? We investigate whether it is computationally tractable to design a signaling scheme maximizing the probability with which the senders preferred candidate is elected. We focus on the model recently introduced by Arieli and Babichenko (2019) (i.e., without inter-agent externalities), and consider, as explanatory examples, $k$-voting rule and plurality voting. There is a sharp contrast between the case in which private signals are allowed and the more restrictive setting in which only public signals are allowed. In the former, we show that an optimal signaling scheme can be computed efficiently both under a $k$-voting rule and plurality voting. In establishing these results, we provide two general (i.e., applicable to settings beyond voting) contributions. Specifically, we extend a well known result by Dughmi and Xu (2017) to more general settings, and prove that, when the senders utility function is anonymous, computing an optimal signaling scheme is fixed parameter tractable w.r.t. the number of receivers actions. In the public signaling case, we show that the senders optimal expected return cannot be approximated to within any factor under a $k$-voting rule. This negative result easily extends to plurality voting and problems where utility functions are anonymous.
rate research
Read More
We focus on the scenario in which an agent can exploit his information advantage to manipulate the outcome of an election. In particular, we study district-based elections with two candidates, in which the winner of the election is the candidate that wins in the majority of the districts. District-based elections are adopted worldwide (e.g., UK and USA) and are a natural extension of widely studied voting mechanisms (e.g., k-voting and plurality voting). We resort to the Bayesian persuasion framework, where the manipulator (sender) strategically discloses information to the voters (receivers) that update their beliefs rationally. We study both private signaling, in which the sender can use a private communication channel per receiver, and public signaling, in which the sender can use a single communication channel for all the receivers. Furthermore, for the first time, we introduce semi-public signaling in which the sender can use a single communication channel per district. We show that there is a sharp distinction between private and (semi-)public signaling. In particular, optimal private signaling schemes can provide an arbitrarily better probability of victory than (semi-)public ones and can be computed efficiently, while optimal (semi-)public signaling schemes cannot be approximated to within any factor in polynomial time unless P=NP. However, we show that reasonable relaxations allow the design of multi-criteria PTASs for optimal (semi-)public signaling schemes. In doing so, we introduce a novel property, namely comparative stability, and we design a bi-criteria PTAS for public signaling in general Bayesian persuasion problems beyond elections when the senders utility function is state-dependent.
As an emerging technique for confidential computing, trusted execution environment (TEE) receives a lot of attention. To better develop, deploy, and run secure applications on a TEE platform such as Intels SGX, both academic and industrial teams have devoted much effort to developing reliable and convenient TEE containers. In this paper, we studied the isolation strategies of 15 existing TEE containers to protect secure applications from potentially malicious operating systems (OS) or untrusted applications, using a semi-automatic approach combining a feedback-guided analyzer with manual code review. Our analysis reveals the isolation protection each of these TEE containers enforces, and their security weaknesses. We observe that none of the existing TEE containers can fulfill the goal they set, due to various pitfalls in their design and implementation. We report the lessons learnt from our study for guiding the development of more secure containers, and further discuss the trend of TEE container designs. We also release our analyzer that helps evaluate the container middleware both from the enclave and from the kernel.
A basic lesson from game theory is that strategic behavior often renders the equilibrium outcome inefficient. The recent literature of information design -- a.k.a. signaling or persuasion -- looks to improve equilibria by providing carefully-tuned information to players in order to influence their actions. Most previous studies have focused on the question of designing optimal signaling schemes. This work departs from previous research by considering a descriptive question and looks to quantitatively characterize the power of signaling (PoS), i.e., how much a signaling designer can improve her objective of the equilibrium outcome. We consider four signaling schemes with increasing power: full information, optimal public signaling, optimal private signaling and optimal ex-ante private signaling. Our main result is a clean and tight characterization of the additional power each signaling scheme has over its immediate predecessor above in the broad classes of cost-minimization and payoff-maximization games where: (1) all players minimize non-negative cost functions or maximize non-negative payoff functions; (2) the signaling designer (naturally) optimizes the sum of players utilities. We prove that the additional power of signaling -- defined as the worst-case ratio between the equilibrium objectives of two consecutive signaling schemes in the above list -- is bounded precisely by the well-studied notion of the price of anarchy of the corresponding games. Moreover, we show that all these bounds are tight.
Large pre-trained language models have been shown to encode large amounts of world and commonsense knowledge in their parameters, leading to substantial interest in methods for extracting that knowledge. In past work, knowledge was extracted by taking manually-authored queries and gathering paraphrases for them using a separate pipeline. In this work, we propose a method for automatically rewriting queries into BERTese, a paraphrase query that is directly optimized towards better knowledge extraction. To encourage meaningful rewrites, we add auxiliary loss functions that encourage the query to correspond to actual language tokens. We empirically show our approach outperforms competing baselines, obviating the need for complex pipelines. Moreover, BERTese provides some insight into the type of language that helps language models perform knowledge extraction.
We study the problem of computing Stackelberg equilibria Stackelberg games whose underlying structure is in congestion games, focusing on the case where each player can choose a single resource (a.k.a. singleton congestion games) and one of them acts as leader. In particular, we address the cases where the players either have the same action spaces (i.e., the set of resources they can choose is the same for all of them) or different ones, and where their costs are either monotonic functions of the resource congestion or not. We show that, in the case where the players have different action spaces, the cost the leader incurs in a Stackelberg equilibrium cannot be approximated in polynomial time up to within any polynomial factor in the size of the game unless P = NP, independently of the cost functions being monotonic or not. We show that a similar result also holds when the players have nonmonotonic cost functions, even if their action spaces are the same. Differently, we prove that the case with identical action spaces and monotonic cost functions is easy, and propose polynomial-time algorithm for it. We also improve an algorithm for the computation of a socially optimal equilibrium in singleton congestion games with the same action spaces without leadership, and extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques, which computational experiments show to scale quite well.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
