Exploring new ideas is a fundamental aspect of research and development (R\&D), which often occurs in competitive environments. Most ideas are subsequent, i.e. one idea today leads to more ideas tomorrow. According to one approach, the best way to encourage exploration is by granting protection on discoveries to the first innovator. Correspondingly, only the one who made the first discovery can use the new knowledge and benefit from subsequent discoveries, which in turn should increase the initial motivation to explore. An alternative approach to promote exploration favors the \emph{sharing of knowledge} from discoveries among researchers allowing explorers to use each others' discoveries to develop further knowledge, as in the open-source community. With no protection, all explorers have access to all existing discoveries and new directions are explored faster. We present a game theoretic analysis of an abstract research-and-application game which clarifies the expected advantages and disadvantages of the two approaches under full information. We then compare the theoretical predictions with the observed behavior of actual players in the lab who operate under partial information conditions in both worlds. Our main experimental finding is that the no protection approach leads to \emph{more} investment efforts overall, in contrast to theoretical prediction and common economic wisdom, but in line with a familiar cognitive bias known as `underweighting of rare events'.

Crowdsourcing platforms use various truth discovery algorithms to aggregate annotations from multiple labelers. In an online setting, however, the main challenge is to decide whether to ask for more annotations for each item to efficiently trade off cost (i.e., the number of annotations) for quality of the aggregated annotations. In this paper, we propose a novel approach for general complex annotation (such as bounding boxes and taxonomy paths), that works in an online crowdsourcing setting. We prove that the expected average similarity of a labeler is linear in their accuracy \emph{conditional on the reported label}. This enables us to infer reported label accuracy in a broad range of scenarios. We conduct extensive evaluations on real-world crowdsourcing data from Meta and show the effectiveness of our proposed online algorithms in improving the cost-quality trade-off.

The explosion of conference paper submissions in AI and related fields, has underscored the need to improve many aspects of the peer review process, especially the matching of papers and reviewers. Recent work argues that the key to improve this matching is to modify aspects of the \emph{bidding phase} itself, to ensure that the set of bids over papers is balanced, and in particular to avoid \emph{orphan papers}, i.e., those papers that receive no bids. In an attempt to understand and mitigate this problem, we have developed a flexible bidding platform to test adaptations to the bidding process. Using this platform, we performed a field experiment during the bidding phase of a medium-size international workshop that compared two bidding methods. We further examined via controlled experiments on Amazon Mechanical Turk various factors that affect bidding, in particular the order in which papers are presented \cite{cabanac2013capitalizing,fiez2020super}; and information on paper demand \cite{meir2021market}. Our results suggest that several simple adaptations, that can be added to any existing platform, may significantly reduce the skew in bids, thereby improving the allocation for both reviewers and conference organizers.

In the Approval Participatory Budgeting problem an agent prefers a set of projects $W'$ over $W$ if she approves strictly more projects in $W'$. A set of projects $W$ is in the core, if there is no other set of projects $W'$ and set of agents $K$ that both prefer $W'$ over $W$ and can fund $W'$. It is an open problem whether the core can be empty, even when project costs are uniform. the latter case is known as the multiwinner voting core. We show that in any instance with uniform costs or with at most four projects (and any number of agents), the core is nonempty.

Voting rules may fail to implement the will of the society when only some voters actively participate, and/or in the presence of sybil (fake or duplicate) voters. Here we aim to address social choice in the presence of sybils and voter abstention. To do so we assume the status-quo (Reality) as an ever-present distinguished alternative, and study Reality Enforcing voting rules, which add virtual votes in support of the status-quo. We measure the tradeoff between safety and liveness (the ability of active honest voters to maintain/change the status-quo, respectively) in a variety of domains, and show that the Reality Enforcing voting rule is optimal in this respect.

A population of voters must elect representatives among themselves to decide on a sequence of possibly unforeseen binary issues. Voters care only about the final decision, not the elected representatives. The disutility of a voter is proportional to the fraction of issues, where his preferences disagree with the decision. While an issue-by-issue vote by all voters would maximize social welfare, we are interested in how well the preferences of the population can be approximated by a small committee. We show that a k-sortition (a random committee of k voters with the majority vote within the committee) leads to an outcome within the factor 1+O(1/k) of the optimal social cost for any number of voters n, any number of issues $m$, and any preference profile. For a small number of issues m, the social cost can be made even closer to optimal by delegation procedures that weigh committee members according to their number of followers. However, for large m, we demonstrate that the k-sortition is the worst-case optimal rule within a broad family of committee-based rules that take into account metric information about the preference profile of the whole population.

Truth discovery is a general name for a broad range of statistical methods aimed to extract the correct answers to questions, based on multiple answers coming from noisy sources. For example, workers in a crowdsourcing platform. In this paper, we design simple truth discovery methods inspired by \emph{proxy voting}, that give higher weight to workers whose answers are close to those of other workers. We prove that under standard statistical assumptions, proxy-based truth discovery (\PTD) allows us to estimate the true competence of each worker, whether workers face questions whose answers are real-valued, categorical, or rankings. We then demonstrate through extensive empirical study on synthetic and real data that \PTD is substantially better than unweighted aggregation, and competes well with other truth discovery methods, in all of the above domains.

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core---the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.

The first part of this book asks "are there voting rules that are truthful?" in that all voters have an incentive to report their true preferences. In the second, we ask "what would be the outcome when voters do vote strategically?" rather than preventing such behavior. We overview various game-theoretic models and equilibrium concepts, demonstrate how they apply to voting games, and discuss their implications on social welfare. ISBN 9781681733593, 167 pages.

Understanding the nature of strategic voting is the holy grail of social choice theory, where game-theory, social science and recently computational approaches are all applied in order to model the incentives and behavior of voters. In a recent paper, Meir et al.[EC'14] made another step in this direction, by suggesting a behavioral game-theoretic model for voters under uncertainty. For a specific variation of best-response heuristics, they proved initial existence and convergence results in the Plurality voting system. This paper extends the model in multiple directions, considering voters with different uncertainty levels, simultaneous strategic decisions, and a more permissive notion of best-response. It is proved that a voting equilibrium exists even in the most general case. Further, any society voting in an iterative setting is guaranteed to converge to an equilibrium. An alternative behavior is analyzed, where voters try to minimize their worst-case regret. As it turns out, the two behaviors coincide in the simple setting of Meir et al.[EC'14], but not in the general case.