User john horton - MathOverflow

Conjecture that two nested convex curves have a point with the same slope

2012-08-13T06:05:53Z

I'm trying to prove a conjecture and need some help. Consider a continuous, twice differentiable function $p(a)$ such that $p(0) = 0$ and $\forall a$, $p'(a) > 0$ and $p''(a) < 0$ and $p$ is bounded above by 1. I believe it's the case that for $\gamma > 1$, $\exists a' | p'(a) = \gamma p'(\gamma a)$. Another way of stating that is that if you have two functions, $p(a)$ and $p(\gamma a)$, there is some point $a'$ where the slopes of the two curves are the same.

I'm trying to prove this conjecture but I'm not making much progress. I feel like I'm making this harder than it is, but in in terms of a proof sketch / intuition, I think one approach would be to:

Show that $\gamma p'(0) - p'(0) > 0$
Show that $p(a)$ and $p(\gamma a)$ both have to converge some the same value, say $B$.
Argue that for the $p(a)$ curve to "catch up" to $p(\gamma a)$---because they converge to $B$ and the $p(a)$ curve is everywhere below the $p(\gamma a)$ curve---there has to be some point $\hat{a}$ where $p'(\hat{a}) > \gamma p(\gamma \hat{a})$ and hence $\gamma p'(\gamma \hat{a}) - p'(\hat{a}) < 0$ and so by the IVT, there has to be some $a'$ such that $\gamma p'(\gamma a') - p'(a') = 0$, which is what I'm looking for.

While I think this (might) work, the "catch up" notion is really informal and I suspect there's some much simpler, more rigorous way of showing that it's true. Thanks.

Proving that a constructed curve solves an optimization problem

2012-05-20T23:31:06Z

Caveat up-front: I'm not a mathematician, so please excuse any stupidity/ignorance that follows. First, let me explain what I'm trying to do: I want to choose a function that maximizes the following definite integral:

$\max_{b(q)} \int_0^1 1 - e^{-q b(q)} dq$

subject to

$b(q) \ge 0, \forall q$

$\int_0^1 b(q) = B$

My intuition is that an optimal solution for $b(q)$ will be an allocation so that the derivative of $1-e^{-q b(q)}$ with respect to $b$ will be the same (say $\lambda$) everywhere that b(q) > 0. This condition gives $b(q) = - \frac{1}{q} \log \frac{\lambda}{q}$. The second constraint gives the expression lets us solve for $\lambda$. Below is a plot showing $b(q)$ for various values of $\lambda$. My (guess?) is that I could find this curve explicitly using the calculus of variations.

Now, for the complicated part and my real question. As you can see from some values of $\lambda$, it is not the case that $b'(q) \ge 0$. In fact, the curve as a peak at $e \lambda$. I want to maximize the same definite integral as before, but with the added constraint that $b'(q) \ge 0, \forall q$.

My intuition is that this optimal curve now has three parts: (1) a region where b(q) = 0, as in the unconstrained case (2) a region where the curve has the same shape as the previous, unconstrained portion [the upward sloping region] and (3) a flat, slope = 0 portion that is tangent to the maximum. These restrictions fully define a curve for a given value of B---see below for examples:

I have some sketched ideas for a "proof," but my ideas do not seem that convincing to me. My question is what would be an approach for proving my constructed curve is in fact optimal? Is there some "textbook" way of approaching this kind of problem that I should read up on? Thanks for any advice or pointers.

Equitable Allocation of Individuals to Positions

2012-01-04T03:40:53Z

I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction.

The problem is trying to find a convex combination of different ways of ranking n items that satisfy certain constraints. Let me be more concrete: Suppose we have $n$ individuals with endowments $b_1 > b_2 > b_3 \ldots b_n$. There are positions $1 \dots n$, each of which gives a value of $v_1 > v_2 > v_3 \ldots v_n \ge 0$ that the individuals can be assigned to.

I want to create a non-deterministic algorithm for assigning individuals to positions that is in some sense "equitable." so that for each individual, their expected proportional value from their positions is equal to their proportional endowment. E.g., suppose we have some method that assigns individual $i$ to position with 1 with probability $p_{i1}$, to position 2 with probability $p_{i2}$ and so on, I want it so that the algorithm generates an allocation such that:

$\forall i, \frac{\sum_{j=1}^n p_{ij} v_j}{\sum_{j=1}^n v_j} = \frac{b_i}{\sum_{j=1}^n b_j} $

Some observations / thoughts:

For this to work even in the n=2 case, we need to constrain $b_1$ to that it isn't proportionally larger than $v_1$ (otherwise even always placing individual 1 at position 1 wouldn't be enough).

I originally thought this could be framed as a linear programming problem, where the goal is to find weights for each of the $n!$ possible orderings. Maybe this would work, but it would be computationally infeasible.

A particularly nice approach might be one that sequentially assigns positions by having each remaining individual "buy" probability shares with their budget and then draw a winner. Unfortunately, this doesn't have the equitable property above, but I was thinking that perhaps if we thought of the allocation as happening repeatedly, we could give the "losers" (payoff from position too small) a bigger endowment, taken from the "winners" in such a way that expected payoff converges to the equitable outcome.

Anyway, thanks for reading this far and I appreciate any comments, suggestions, answers etc.

Existence of a sink in directed graphs with a certain structure

2011-03-06T15:04:26Z

I'm not a mathematician (I'm an economist) but I hope that this problem is sufficiently non-trivial that someone here will find it interesting.

Motivation:

I'm trying to model how workers decide what "skills" to acquire when (a) they have different innate abilities for different skills but (b) they face competitive pressure from others that also choose to acquire those skills.

Problem:

Suppose we have $N$ workers that can choose to belong in any of $M$ different groups. Multiple workers can belong to the same group; a worker can be in one and only one group at a time. They can jump from any group to any other group.

A worker $i$ in group $j$ gets value $v_{ij}f(n_m)$ where $n_m$ is the number of workers in that group, and $f'(n_m) < 0$ and $f(1) = 1$ and as $n_m$ approaches infinity, $f$ approaches 0. $v$ is uniformly distributed. Workers jump between groups to try to maximize the value they receive.

Graph theory formulation:

I'm interested in the movement of workers between groups. I've modeled it as a directed graph, where each node is one possible configuration of workers among groups. Two nodes are connected if one worker changing states can convert one node to the other; edges point towards the greatest utility gain for the "jumping" worker.

In simulations, I've found that the system always reaches an equilibrium where no worker wants to jump and I haven't been able to construct a counter-example.

Conjecture:

My conjecture is that this is a general property of graphs with this structure, i.e., for any directed graph with the $(m,n)$ structure described above, there exists at least one "sink" with no outgoing edges and that this sink is reachable from all other nodes.

Ignoring values, it is possible to draw graphs without "sinks" but it leads to contradictions when I try to assign actual values to the worker-group pairings. None of the approaches I've tried so far seem promising enough to mention here.

Comment by John Horton

2012-08-13T14:46:07Z

Of course - thank you! If you migrate this to an answer, I can approve it.

Comment by John Horton

2012-01-04T04:26:18Z

Thanks Will (very helpful reference) - but wouldn't these methods just give me a single, deterministic mapping? I think I need a non-deterministic procedure that generates a distribution of assignments, since any any particular assignment will be "wrong" in the sense that the pay-offs will just reflect the associated $v$'s of the single assignment, which doesn't satisfy the equity criterion.

Comment by John Horton

2011-03-06T21:05:41Z

Thanks Noah! That's exactly the right citation.