Search

We study political parties that strategically place their candidates in districts so to maximise the number of their nominees that get elected. In each district, voters rank the nominated candidates and elect the plurality winners. After studying equilibrium existence in restricted instances, we show that deciding the existence of pure Nash equilibria for these games is NP-complete if party size is bounded by a constant and Σ P 2 -complete for the general case. For the hardness part of the latter result we reduce from ∃∃!-3sat.

In single-elimination knockout tournaments, participants face each other based on a starting seeding and progress to the next rounds by beating their direct opponents. In this paper we initiate the study of coalitional knockout tournaments, which generalise single-elimination knockout tournaments by allowing groups of players, or coalitions, to strategically select one of their members to take part in the tournament, following the starting seeding. We investigate the algorithmic properties of pure strategies Nash equilibria in these games under various setups, i.e., whether or not choices can be made at each round and whether or not tournament progression is important to the group. Despite the more complex tournament structure when compared to single-elimination, we provide (quasi-) polynomial-time algorithms for all cases. Our results can be applied to those tournaments where pre-play selection plays an important role, such as sport events or elections with run-off.

We study several fairness notions in allocating indivisible chores (i.e., items with non-positive values): envy-freeness and its relaxations. For allocations under each fairness criterion, we establish their approximation guarantees for other fairness criteria. Under the setting of additive cost functions, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. Furthermore, we investigate the efficiency loss under these fairness constraints and establish their prices of fairness.

We study voting games on binary issues, where voters hold an objective over the outcome of the collective decision and are allowed, before the vote takes place, to negotiate their ballots with the other participants. We analyse the voters’ rational behaviour in the resulting two-phase game when ballots are aggregated via non-manipulable rules and, more specifically, quota rules. We show under what conditions undesirable equilibria can be removed and desirable ones sustained as a consequence of the pre-vote phase.

International audience; We study voting games on binary issues, where voters hold an objective over the outcome of the collective decision and are allowed, before the vote takes place, to negotiate their ballots with the other participants. We analyse the voters' rational behaviour in the resulting two-phase game when ballots are aggregated via non-manipulable rules and, more specifically, quota rules. We show under what conditions undesirable equilibria can be removed and desirable ones sustained as a consequence of the pre-vote phase.

Artificial agents are typically oriented to the realization of an externally assigned task and try to optimize over secondary aspects of plan execution such time lapse or power consumption, technically displaying a quasi-dichotomous preference relation. Boolean games have been developed as a paradigm for modelling societies of agents with this type of preference. In boolean games agents exercise control over propositional variables and strive to achieve a goal formula whose realization might require the opponents' cooperation. Recently, a theory of incentive engineering for such games has been devised, where an external authority steers the outcome of the game towards certain desirable properties consistent with players' goals, by imposing a taxation mechanism on the players that makes the outcomes that do not comply with those properties less appealing to them. The present contribution stems from a complementary perspective and studies, instead, how games with quasi-dichotomous preferences can be transformed from inside, rather than from outside, by endowing players with the possibility of sacrificing a part of their payoff received at a certain outcome in order to convince other players to play a certain strategy. Concretely we explore the properties of endogenous games with goals, obtained coupling strategic games with goals, a generalization of boolean games, with the machinery of endogenous games coming from game theory. We analyze equilibria in those structures, showing the preconditions needed for desirable outcomes to be achieved without external intervention. What our results show is that endogenous games with goals display specific irreducible features - with respect to what already known for endogenous games - which makes them worth studying in their own sake., (under submission)