TLW comments on shortplav

[TLW]

Here’s a somewhat similar approach:

1. Represent preferences as a directed graph with edge weights. (A.k.a. a network.)

2. An edge from A to B with weight W means ‘the agent would trade A for B in exchange for >=W units of utility’.

   1. (I’m still debating as to if this definition of edge weight is backwards or not. There are arguments either way. That being said, it’s just a sign flip.)

3. An edge does not automatically imply a backedge. (Or alternatively, could have a backedge with a weight of infinity.)

4. A loop (self-edge) is technically allowed, but is ‘interesting’.

Then:

1. An agent is exploitable if there is any negative cycle (cycle with sum weight negative).

2. An agent is open to timewasting if there is any zero cycle.

   1. I don’t know if there is a better term here.

3. There are several approaches to removing the inconsistancies in an inconsistant set of preferences.

   1. One suboptimal but simple approach:

      1. While the graph has a negative cycle of weight -W and length L

         1. Add W/​L to all edges in the cycle.

   2. Another suboptimal but slightly better approach:

      1. While the graph has a negative cycle:

         1. Find the edge with the highest minimum W/​L (that is, for all negative cycles, calculate W/​L for all edges involved in said cycle, then find the edge with the maximum minimum W/​L calculated) and add said W/​L to it.

   3. I strongly suspect that the ‘optimal’ solution is NP-hard^[1]. That being said, roughly:

      1. Minimize the total amount of weight added such that there are no negative cycles.

         1. Tiebreak by minimum maximum weight added to a single edge.

Some examples of a 3-element cycle:

1. A =1> B =1> C =1> A

   1. (That is, the agent would trade B for A only if you provide >=one unit of utility.)

   2. No inconsistencies here.

2. A =1> B =1> C =-2> A

   1. No inconsistencies here either, though the agent is open to timewasting. (‘I’ll trade A B C for A B C. Again. Again. Again. Etc.’)

3. A =1> B =1> C =-5> A

   1. This is inconsistent. Someone could trade A B C for A B C and 3 units of utility.

   2. Consistent result is

      1. A =2> B =2> C =-4> A

4. A =1> B =1> C =-5> A ; A =1> D =1> C

   1. Consistent results from approaches above:

      1. A =2> B =2> C =-3.33> A ; A =1.67> D =1.67> C

      2. A =1> B =1> C =-2> A ; A =1> D =1> C

      3. A =1> B =1> C =-2> A ; A =1> D =1> C

1. ^

   I strongly suspect there’s a reduction to 3SAT, in particular.