Yotam Gafni

Yotam Gafni

Consider a social-choice function (SCF) is chosen to decide votes in a formal system, including votes to replace the voting method itself. Agents vote according to their ex-ante belief over what decisions are considered, and whether they prefer them to be decided by the incumbent SCF or the suggested replacement. The existing SCF then aggregates the agents' votes and arrives at a decision of whether it should itself be replaced. An SCF is self-maintaining if it can not be replaced in such fashion by any other SCF. Our focus is on the implications of self-maintenance for centralization. For this purpose, unlike [Barbera and Jackson, 2004], we do not generally restrict attention to anonymous SCFs. We also do not restrict attention to neutral SCFs, unlike [Koray, 2000]. We present results considering optimistic, pessimistic and i.i.d. approaches with respect to agent beliefs, different tie-breaking rules, and different SCF domains. To highlight two of the results, (i) for the i.i.d. unbiased case with arbitrary tie-breaking and general Boolean functions, we prove an Arrow-Style Theorem for Dynamics: We show that only a dictatorship is self-maintaining, and any other SCF has a path of changes that arrives at a dictatorship. (ii) With a pessimistic approach, tie-breaking that prefers the status quo, and WMGs, we provide a tight characterization of the self-maintaining rules, which are exactly all games with minimal winning coalitions of size at most 2. We then consider two extensions, (i) forward-looking voters, (ii) Where the voter utility depends on wisdom of the crowd effects. In both cases, less centralized SCFs become self-maintaining. All in all we provide a basic framework and body of results for centralization dynamics and stability, applicable for institution design, especially in formal De-Jure systems, such as Blockchain Decentralized Autonomous Organizations (DAOs).

Yotam Gafni, Aviv Yaish

We study a \emph{financial} version of the online problem of scheduling weighted packets with deadlines. The main novelty is that, while prior works assume packets have \emph{fixed} weights, we consider packets with \emph{time-decaying} values. Such considerations are natural in financial environments, where the present value of future actions may be discounted. We analyze the competitive ratios of scheduling algorithms under a range of discount rates encompassing the traditional undiscounted case where weights are fixed (i.e., a discount rate of 1), the fully discounted myopic case (i.e., a rate of 0), and those in between. We show how existing methods from the literature perform suboptimally in the more general discounted setting. Notably, we devise a novel memoryless deterministic algorithm, and prove that for discount factors up to $\approx 0.77$, it guarantees the best competitive ratio attainable by deterministic algorithms. Moreover, we develop a randomized algorithm and prove that it outperforms the best possible deterministic algorithm for any discount rate.

Yotam Gafni, Ronen Gradwohl, Moshe Tennenholtz

Two firms are engaged in a competitive prediction task. Each firm has two sources of data -- labeled historical data and unlabeled inference-time data -- and uses the former to derive a prediction model, and the latter to make predictions on new instances. We study data-sharing contracts between the firms. The novelty of our study is to introduce and highlight the differences between contracts that share prediction models only, contracts to share inference-time predictions only, and contracts to share both. Our analysis proceeds on three levels. First, we develop a general Bayesian framework that facilitates our study. Second, we narrow our focus to two natural settings within this framework: (i) a setting in which the accuracy of each firm's prediction model is common knowledge, but the correlation between the respective models is unknown; and (ii) a setting in which two hypotheses exist regarding the optimal predictor, and one of the firms has a structural advantage in deducing it. Within these two settings we study optimal contract choice. More specifically, we find the individually rational and Pareto-optimal contracts for some notable cases, and describe specific settings where each of the different sharing contracts emerge as optimal. Finally, in the third level of our analysis we demonstrate the applicability of our concepts in a synthetic simulation using real loan data.

Yotam Gafni, Moshe Tennenholtz

The quality of learning generally improves with the scale and diversity of data. Companies and institutions can therefore benefit from building models over shared data. Many cloud and blockchain platforms, as well as government initiatives, are interested in providing this type of service. These cooperative efforts face a challenge, which we call ``exclusivity attacks''. A firm can share distorted data, so that it learns the best model fit, but is also able to mislead others. We study protocols for long-term interactions and their vulnerability to these attacks, in particular for regression and clustering tasks. We conclude that the choice of protocol, as well as the number of Sybil identities an attacker may control, is material to vulnerability.