Consider the following game, known as the Stable Invitation Game. The input is a

Question

Consider the following game, known as the Stable Invitation Game.

The input is a set of agents A= {a1...an} and, for each agent, Fi(friends), Ei (enemies), and a range [li, ui].  

Each individual only wants to be invited to the party if

all their friends are invited

none of their enemies are invited

the number of people invited is in the interval [li, ui].

For each of the following questions, give upper and/or lower bounds on the complexity, with and without the assumption that friendships and enmity are symmetric. (Either both or neither should be symmetric.)   Note that an algorithm gives an upper bound on complexity (e.g., a polynomial-time algorithm proves that the problem is no harder than P), and a completeness proof gives a lower bound.

Given i, is there a stable party (set of invitations) that includes ai?

Is there a stable party that is nonempty?

Is there a stable party of size in the range [l,u]?

Explanation / Answer

Here consider A = {a1,a2,a3,a4,a5};

1. We consider first case as Symmetric Friendship and Enemity. Consider the following table where:

0 = Friend and

1 = Enemy.

Here consider i = 1.

We have [l1 u1] = [3 4].

as we are considering Symmetric case we get a1-a3, a1-a4 as friends from row1, a3-a4 friend from row3. Hence a1,a3 and a4 gets invited for the party.

2. In second case we consider Friendship and Enemity as Asymmetric. Consider the following table where:

Here consider i = 1.

We have [l1 u1] = [3 4].

as we are considering Asymmetric case we get a1-a3, a1-a4 as friends from row1 i.e. a1 is friends with a3 and a4. From the rows corresponding to a3 we get a3-a1,a3-a4 friend from row3 i.e. a3 is friends with a1 and a4. Similarly we can find friends for a4 from row corresponding to a4.

Hence a1,a3 and a4 gets invited for the party.

a1 a2 a3 a4 a5 [li ui] a1 0 1 0 0 1 [3 4] a2 1 0 0 1 1 [1 3] a3 0 0 0 0 0 [4 5] a4 0 1 0 0 0 [1 4] a5 1 1 0 0 0 [2 5]

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.