This is a correction to: Piotr Faliszewski, Rica Gonen, Martin Koutecý, Nimrod Talmon, Opinion diffusion and campaigning on society graphs, Journal of Logi

Abstract We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting the clusters. Our model can incorporate different campaigning actions, various partitions of the society into clusters and very general diffusion processes. Perhaps surprisingly, we show that computing the cheapest campaign for rigging a given election can usually be done efficiently, even with arbitrarily-many voters. Moreover, we report on computational simulations we have performed to evaluate the quality and efficiency of finding such solutions.

In two-sided markets, Myerson and Satterthwaite's impossibility theorem states that one can not maximize the gain-from-trade while also satisfying truthfulness, individual-rationality and no deficit. Attempts have been made to circumvent Myerson and Satterthwaite's result by attaining approximately-maximum gain-from-trade: the double-sided auctions of McAfee (1992) is truthful and has no deficit, and the one by Segal-Halevi et al. (2016) additionally has no surplus — it is strongly-budget-balanced. They consider two categories of agents — buyers and sellers, where each trade set is composed of a single buyer and a single seller.The practical complexity of applications such as supply chain require one to look beyond two-sided markets. Common requirements are for: buyers trading with multiple sellers of different or identical items, buyers trading with sellers through transporters and mediators, and sellers trading with multiple buyers. We attempt to address these settings.We generalize Segal-Halevi et al. (2016)'s strongly-budget-balanced double-sided auction setting to a multilateral market where each trade set is composed of any number of agent categories. Our generalization refines the notion of competition in multi-sided auctions by introducing the concepts of external competition and trade reduction. We also show an obviously-truthful implementation of our auction using multiple ascending prices.Full version, including omitted proofs and simulation experiments, is available at https://arxiv.org/abs/1911.08094.

We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting those clusters. Our model is very general and can incorporate many campaigning actions, various partitions of the society into voter clusters, and very general diffusion processes. Perhaps surprisingly, we show that computing the cheapest campaign for rigging a given election can usually be done efficiently, even with arbitrarily-many voters.

Viral marketing is a methodology which is based on exploiting a pre-existing social network in order to increase brand awareness or product sales through selfreplicating viral processes. An essential computational task towards setting up an effective viral marketing campaign is to estimate social influence. Such estimates are usually done by analyzing user activity data. The data analysis and sharing that is needed to estimate social influence raises important privacy issues that may jeopardize the legal, ethical and societal acceptability of such practice, and in turn, the concrete applicability of viral marketing in the real world. Tassa and Bonchi (EDBT 2014) devised secure multi-party protocols that allow a group of service providers and a social networking platform to jointly compute social influence in a privacy preserving manner. They assumed that the players are semi-honest, i.e., that they follow the protocol correctly, but at the same time they examine their view of the protocol in order to extract information on inputs provided by their peers. In this paper we discuss the case of selfish rational players, such players participate in the protocol and follow it correctly only if it is in their best interest and maximizes their utility. We enhance the protocol of Tassa and Bonchi by incorporating into it mechanisms that incentivize the players to participate in the protocol truthfully.

This paper presents a truthful sponsored search auction based on an incentive-compatible multi-armed bandit mechanism. The mechanism described combines several desirable traits. The mechanism gives advertisers the incentive to report their true bid, learns the click-through rate for advertisements, allows for slots with different quality, and loses the minimum welfare during the sampling process.

When designing a mechanism there are several desirable properties tomaintain such as incentive compatibility (IC), individual rationality (IR), and budget balance (BB). It is well known [15] that it is impossible for a mechanism to maximize social welfare whilst also being IR, IC, and BB. There have been several attempts to circumvent [15] by trading welfare for BB, e.g.,in domains such as double-sided auctions [13], distributed markets [3] and supply chain problems [2, 4].

We study k-resilient Nash equilibria, joint strategies where no member of a coalition C of size up to k can do better, even if the whole coalition defects. We show that such k-resilient Nash equilibria exist for secret sharing and multiparty computation, provided that players prefer to get the information than not to get it. Our results hold even if there are only 2 players, so we can do multiparty computation with only two rational agents. We extend our results so that they hold even in the presence of up to t players with "unexpected" utilities. Finally, we show that our techniques can be used to simulate games with mediators by games without mediators.

This paper introduces a new class of mechanisms based on negotiation between market participants. This model allows us to circumvent Myerson and Satterthwaite's impossibility result and present a bilateral market mechanism that is efficient, individually rational, incentive compatible, and budget balanced in the single-unit heterogeneous setting. The underlying scheme makes this combination of desirable qualities possible by reporting a price range for each buyer-seller pair that defines a zone of possible agreements, while the final price is left open for negotiation.

This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to single minded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.

Article Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics Share on Authors: Rica Gonen School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, IsraelView Profile , Daniel Lehmann School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, IsraelView Profile Authors Info & Claims EC '00: Proceedings of the 2nd ACM conference on Electronic commerceOctober 2000 Pages 13–20https://doi.org/10.1145/352871.352873Online:17 October 2000Publication History 102citation538DownloadsMetricsTotal Citations102Total Downloads538Last 12 Months18Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access