# Ethics and Incompleteness

So, I was talking to my wife 🙂 about ethics and the types of ethics.  She told me that there is this form called consequential ethics and deontological ethics.  And there are I’m sure a bunch more.  But, what I have discovered is that they each have a set of axioms and from these they base all of there conclusions.  However, I believe that we here are encountering a similar problem as Godel’s incompleteness theorem.  Basically, a complete and consistent set of axioms for all ethics is impossible.

http://philosophy.stackexchange.com/questions/31726/can-g%C3%B6dels-incompleteness-theorems-be-applied-to-ethics is a link I just found and he references Tarski’s undefinability theorem.

# N-Puzzle thoughts

Some n-puzzle ideas:

1. Create an n-dimensional n-puzzle.  This is different from a rubiks cube because it is a sliding puzzle not a sequential move puzzle.  It is sort of like the last puzzle here called the Inside out puzzle by Vadász Kocka, it is of course only 3D not nD.
2. Figure out how to reduce nD n-puzzle to 1D n-puzzle (meaning make a new set of rules for how the pieces move and in a way that eliminates symmetric moves)
3. The number of ways to solve an n-puzzle is in #P (find proof)
4. Can any unsolvable n-puzzle be solved with some number of flips and rotations to the board itself?
5. What would it mean to have a fractional dimensional-puzzle like a 1/2d n-puzzle? How could you move?
6. What if the puzzle is represented as a graph.  Then you can represent it as an adjacency matrix and do math (haha).

I found the paper that proves that n-puzzle is NP-hard here.  Also, I found some papers that cite that paper that I thought sounded interesting:

In writing this I found an amazing source of puzzles here.  It is an index of over 34,000 puzzles!

So, I think that the most interesting of the ideas is 4.  The dimensional aspect I think is a direct mapping of the space and therefore not too interesting.  The fact that it is in #P is sort of interesting but kind of obvious and not really useful.  The interesting thing with that one would be if it was somehow either harder or easier than #P.

So, number 4 is interesting because it is a new way of looking at the board.  However, I believe the answer is yes.  According to the 5th link the number of possible board states is (N*P)! and half of them are not solvable.

I’ve been researching decision theory paradoxes because in my Bounty’s task allocation system I am considering the benefits of giving the bondsman the decision to allocate particular tasks through an auction (ie exclusive) or through its normal bounty (non-exclusive) method.  This brings with it a potentially multi-criteria decision which has me interested about the theoretical ramifications of such a decision.

In my search I have encountered quite a few paradoxes in decision theory, utility theory, and social choice (ie voting).  However, other than the wikipedia listing I haven’t found an authoritative reference (a book) on the subject!  I find this quite strange.  I know probably there are very few people that like this sort of thing, but I believe that knowing about them and that they exist might be of use to multiagent systems researchers who use such theories as the basis for their work.  So, if I can’t find a book or a survey paper on the subject I might write a paper on them.  That would be fun.  I would relate them all to problems in MAS and AI or computer science.  So, it would be Paradoxes that are relevant to an AI researcher.

# N-Queens

n-queens problem is a very interesting problem.  Especially when you start imagining more than 2 dimensions and start thinking d-dimensions it becomes an even more interesting and challenging combinatorics problem.  The link also points to some applications including traffic control, which makes sense.

# Entangled FindSet

Would be cool to use quantum entanglement to do instant FindSets (seeing if two elements are contained in the same set) for Kruskal MST algorithm.

Say each vertex is a photon.  Whenever you do a union you entangle the photons.  Then all you have to do to compare if the photons belong to the same set is to see if they are entangled.

This FindSet operation is already really fast O(lg*n).  However, this would be a constant time lookup.

What would the rest of the quantum MST algorithm be?

So, abstractly what is a road.  It is a queue for vehicles.  Intersections allow elements (vehicles) to change queues.  In this thought experiment I will abstract away lanes to just increased bandwidth and a corresponding increased throughput.  Essentially, the idea with dynamically changing road systems is two fold: one, we want the transitions between queues to be as efficient as possible two, we want the throughput of the queues to be maximized.  Main cause of congestion is crossing traffic which holds up the queue.  So, usually we create a separate lane for those that are turning against opposing traffic.  Or we make roads one way and you can’t turn against traffic (seen in DC).

So, the problem turns into a resource allocation problem at intersections, meaning you have some number of queues (resources) and you have to get the elements (cars) as quickly through to there destination.  The idea then would be to determine how to adjust the queues to increase the resources when necessary and at the right locations.

# Voting and Auction based Monitors

Condition variables and monitors go hand in hand.  There are various monitor protocols: Signal-and-Continue (SC), Signal-and-Urgent-Wait (SU), Signal-and-Exit, Urgent-Signal-and-Continue etc.  Basically these protocols define what order threads get to enter, reenter, and exit methods in a monitor.  They are defined by a first-come first-served (FCFS) queuing schemes to ensure their specific protocols are met.

I am proposing two protocols that are based on Voting and Auctions.  The idea here is that threads get to enter in the order in which they were voted or if they won the auction.  The auction would be like the auctions that google uses for placement of ads on a page.

Monitor queues for producer consumer problem.

The threads could base their decisions on data the monitor has about each of the threads, data the thread has collected, or some other way defined by the coder.  This is the interesting part.

I think that there may be a way to use Arrow’s Theorem to provide some guarantees about some things.

Schepperle, H., & Bohm, K. (2008). Auction-Based Traffic Management: Towards Effective Concurrent Utilization of Road Intersections. E-Commerce Technology and the Fifth …, 105–112. doi:10.1109/CEC/EEE.2008.9

The above reference seems to be heading in the direction I was thinking except they were narrower.

And while I was writing this I found http://www.isi.edu/~lerman/projects/task/ has some good papers on mathematical modeling of multiagent systems.

# Ramsey Theory

Ramsey Theory address problems that ask the question “how many elements of some structure must there be to guarantee that a particular property will hold?”  This is the question that I want to know for brokers.  How many brokers must there be for no price wars to occur.

Very interesting ideas.  I liked the one example on wikipedia Schur’s theorem: for any given c there is a number N such that if the numbers 1, 2, …, N are coloured with c different colours, then there must be a pair of integers xy such that xy, and x+y are all the same colour