Strategic voting in the context of negotiating teams

Negotiation is a very common interaction between automated agents. A negotiating team is a group of two or more agents who join together as a single negotiating party because they share a common goal related to the negotiation. Since a negotiating team is composed of several stakeholders, represented as a single negotiating party, there is a need for a voting rule for the team to reach decisions. In this talk, we investigate the problem of strategic voting in the context of negotiating teams. To this end, we first study an intuitive protocol for bilateral negotiation with ordinal preferences, named VAOV, where the two parties make offers alternately. We analyze the negotiation protocol under different settings. First, we assume that each party has full information about the other party’s preference order. We provide elegant strategies that specify a sub-game perfect equilibrium for the agents. We further show how the studied negotiation protocol almost completely implements a known bargaining rule. We also analyze the no information setting and study several solution concepts that are distribution-free.
 

We then study the problem of strategic voting in the context of negotiating teams that use the VAOV negotiation protocol. We present a polynomial-time algorithm that finds a manipulation for a single voter when using a positional scoring rule. We show that the problem is still tractable when there is a coalition of manipulators that uses a k-approval rule. The coalitional manipulation problem becomes computationally hard when using Borda, but we provide a polynomial-time algorithm with the following guarantee: given a manipulable instance with k manipulators, the algorithm finds a successful manipulation with at most one additional manipulator. Our results hold for both constructive and destructive manipulations.

The talk is based on joint work with Sefi Erlich, Leora Schmerler and Sarit Kraus.

References:

1) Leora Schmerler and Noam Hazon. Strategic Voting in Negotiation Teams. ADT-21.
2) Sefi Erlich, Noam Hazon and Sarit Kraus. Negotiation Strategies for Agents with Ordinal Preferences. IJCAI-18

To view the seminar recording click here