[Cs5500] CS5500 - Rule for Agreement

[Karl Lieberherr]

Hi Yue:

So in summary protocol negation means: switch roles: Alice <-> Bob and
switch: refutation <-> defense.
Is this the way it is implemented?

-- Karl

On Mon, Apr 4, 2011 at 1:40 PM, Yue Liu <liuyue.ly at gmail.com> wrote:
> Hi Professor Lieberherr,
>
> The process of negating an SCG claim/protocol is switching the two roles in
> protocol steps. If the original claim C which proposed by Alice requests
> the claimee Bob to provide an instance first, claimer Alice will provide the
> solution in the second step. So the negated claim !C will ask the claimer to
> provide an instance first, then ask the claimee to provide a solution for
> that instance. In other words, a negated claim means the protocol in that
> claim is negated.
>
> For example:
> Alice made a claim AC: For all instances in the instance set exist a
> solution such that a predicate holds.
> If Bob refuted AC, he needed to provide a instance and Alice will provide a
> solution.
>
> Alice made the negated claim !AC: Exist an instance in the instance set for
> all solutions such that a predicate holds.
> If Bob refuted !AC, Alice should provide an instance and Bob will provide a
> solution.
>
> Best Regards,
> Yue
>
> On Mon, Apr 4, 2011 at 9:58 AM, Karl Lieberherr <lieber at ccs.neu.edu> wrote:
>>
>> Hi Yue:
>>
>> I strengthen your definition by making it more general. You use a
>> protocol based on a mathematical claim.
>> The same agreement rule holds for any claim, also claims involving
>> secrets.
>>
>> In this case we also need the negation of a claim/protocol. Please can
>> you explain again
>> the process of negating an SCG claim/protocol.
>>
>> -- Karl
>>
>> On Mon, Apr 4, 2011 at 1:08 AM, Yue Liu <liuyue.ly at gmail.com> wrote:
>> > Hi Anush, Dan and Rashmi,
>> >
>> > I made the following claim about the rule for agreement. Please
>> > refute/strengthen it. Looking forward to your feedback.
>> >
>> >
>> > Rule for agreement:
>> >
>> > Alice proposes claim AC: For all F in IS exists J: fsat(F, J) >= tAC.
>> >
>> > The negated claim !AC will be: Exist F in IS for all J: fsat(F, J) <
>> > tAC.
>> >
>> > When Bob agrees on claim AC, the following conditions should be true.
>> >
>> > ·       Bob defends claim AC (meaning Bob proposes claim AC and Alice
>> > refutes AC)
>> >
>> > Alice gives F in IS,
>> >
>> > Bob gives J,
>> >
>> > If fsat(F, J) < tAC, Bob loses.
>> >
>> > ·       Otherwise, Bob refutes negated claim !AC (meaning Alice proposes
>> > claim !AC and Bob refutes !AC)
>> >
>> > Alice gives F in IS,
>> >
>> > Bob gives J,
>> >
>> > If fsat(F, J) < tAC, Bob loses.
>> >
>> > ·       Otherwise, Alice defends claim AC.
>> >
>> > Bob gives F in IS,
>> >
>> > Alice gives J,
>> >
>> > If fsat(F, J) < tAC, Alice loses.
>> >
>> > ·       Otherwise, Alice refutes negated claim !AC.
>> >
>> > Bob gives F in IS,
>> >
>> > Alice gives J,
>> >
>> > If fsat(F, J) <  tAC, Alice loses.
>> >
>> >
>> >
>> > Case 1:
>> >
>> > |-------|-------|----------->|
>> >
>> > 0         tAC     topt             1      tAC < topt
>> >
>> > If Bob and Alice are perfect, both Bob and Alice will be able to defend
>> > claim AC and refute negated claim !AC. Then the claim AC will be put
>> > into
>> > social welfare.
>> >
>> > This claim AC may be strengthened or refuted in future tournaments when
>> > scholars have better understanding and solution.
>> >
>> > Case 2:
>> >
>> > |-------|-------|----------->|
>> >
>> > 0         topt     tAC             1      tAC > topt
>> >
>> > If Bob and Alice are perfect, both Bob and Alice will not be able to
>> > defend
>> > claim AC or refute negated claim !AC. Then scholars will know the claim
>> > AC
>> > exceeds the optimal.
>> >
>> > Reputation:
>> >
>> > 1.     As the SCG encourages scholars to refute or strengthen claims,
>> > Bob
>> > will lose reputation as soon as he agreed on claim AC
>> > (-aliceClaimConfidence).
>> >
>> > 2.     Then as Bob proposed the same claim AC with a his confidence, if
>> > Bob
>> > can’t defend claim AC, he will lose reputation again
>> > (-bobClaimConidence).
>> >
>> > 3.     After Bob successfully defends AC, he will refute claim !AC. If
>> > he
>> > cannot  refute it, Bob lose reputation (-alice!ClaimConfidence).
>> >
>> > 4.     After Bob successfully refutes AC, Alice will defend AC. If she
>> > lost,
>> > Alice will lose reputation (-aliceClaimConfidence).
>> >
>> > 5.     At last, if Alice successfully defend AC, she will refute !AC. If
>> > she
>> > cannot refute it, Alice lose reputation (-bob!ClaimConfidence).
>> >
>> >
>> >
>> > Best Regards,
>> >
>> > Yue
>> >
>> >
>
>