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, 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.

Omer Ben-Porat, Yotam Gafni, Or Markovetzki

Explore-and-exploit tradeoffs play a key role in recommendation systems (RSs), aiming at serving users better by learning from previous interactions. Despite their commercial success, the societal effects of explore-and-exploit mechanisms are not well understood, especially regarding the utility discrepancy they generate between different users. In this work, we measure such discrepancy using the economic notion of envy. We present a multi-armed bandit-like model in which every round consists of several sessions, and rewards are realized once per round. We call the latter property reward consistency, and show that the RS can leverage this property for better societal outcomes. On the downside, doing so also generates envy, as late-to-arrive users enjoy the information gathered by early-to-arrive users. We examine the generated envy under several arrival order mechanisms and virtually any anonymous algorithm, i.e., any algorithm that treats all similar users similarly without leveraging their identities. We provide tight envy bounds on uniform arrival and upper bound the envy for nudged arrival, in which the RS can affect the order of arrival by nudging its users. Furthermore, we study the efficiency-fairness trade-off by devising an algorithm that allows constant envy and approximates the optimal welfare in restricted settings. Finally, we validate our theoretical results empirically using simulations.

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.