4
$\begingroup$

The problem I'm seeing is with Case 2 of Lemma 4.5 in the latest version of the ArXiv preprint:

Unallocated contested piece a has proper trims on it (recall that we are ignoring part that is left of the rightmost non-winner’s trim mark). Since the only proper trim on a piece can be by some agent in W, this means that a admits a proper trim by an agent j ∈ W. But this is a contradiction because j finds a strictly more preferred than his current allocation.

It isn't obvious to me why this is true. As I mentioned in a blog post of mine on this topic:

This last sentence is based on the following observation: any trims by some agent j ∈ W must be such that the right hand side is equal in value to j’s most-valued unallocated piece. However, during the next iteration of the while loop from the Subcore protocol, it is possible that all of the contested pieces that j values as much as any of the unallocated pieces from the previous round have been allocated to other agents in (now expanded) W. Once this happens it is possible for agent j to place trim to the right of the agent who this case 2 from the lemma incorrectly is claiming must continue having the right-most trim.

Can someone explain what either I or the authors are missing here. I want to understand this.

$\endgroup$
  • $\begingroup$ not sure this is on topic here... meta.mathoverflow.net/questions/2328/… $\endgroup$ – Carlo Beenakker Nov 18 '16 at 21:57
  • $\begingroup$ @CarloBeenakker I asked about a specific part of a lemma from the paper. Not asking "is this paper correct", I gave a well-explained possible route to a counterexample. $\endgroup$ – Justin Archer Nov 19 '16 at 3:38
  • $\begingroup$ Your intent seems good, but in defense of Carlo, your wording could be improved. There may be a problem with the protocol, but it is more politic to assume first that you have a problem understanding it, and your title does not reflect that. I suggest rewriting it as "Problems With (my understanding of)...", so that the post appears less of an attack. Gerhard "We've All Got Some Problems" Paseman, 2016.11.22. $\endgroup$ – Gerhard Paseman Nov 22 '16 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.