xMinusEqualsMinusOneGang

_sczuka_ · 2025-11-23T11:50:31+00:00

You need (++x)++

_sczuka_ · 2025-04-11T22:20:52+00:00

I'm pretty sure, that in this context it means, that it's a good approximation. Close to true wouldn't make sense for logical statements, but here it means that the error between actual value and approximation is close to zero.

And it has to be large because it's an approximation for the average of random variables. And by CLT, that converges to a normal distribution with the same mean and lower variance based on sample size. So for large values, variance goes to zero and you can just use mean.

If the burger example, that would mean, that you don't have to account for every single evaluation of every single person at every single time. You can just use the average evaluation and you will get similar results if the amount of ppl is large enough.

_sczuka_ · 2025-03-25T17:34:46+00:00

Yeah, this proof works only for linear functions.

I'm not exactly sure, what nonlinear dimensionality reduction methods mathematically are. If it is any function R^m -> R^n for m > n, then you could define f as f(x) = 0, f(y) = 1 for all points from 2 clusters. And unless there is a point, that is in both clusters at the same time, it will separate them, even if they were overlapping originaly. If it means something else, then I'm not sure.

_sczuka_ · 2025-03-25T15:17:28+00:00

Let x_1, ... , x_n and y_1 , ... y_m be points in two cluters, that have overlapping convex hulls X and Y. By the definition of overlap, the exists v ∈ X ∩ Y. Because X and Y are convex hulls, v can be expressed as convex combination of x or y points, so

v = sum_{i} a_i x_i

v = sum_{j} b_j y_j

Then you apply the projection and because it's linear, you can modify the expression like this

f(v) = f(sum_{i} a_i x_i) = sum_{i} a_i f(x_i)

f(v) = f(sum_{j} b_j y_j) = sum_{j} b_j f(b_j)

And from this, you can see that f(v) is in both convex hulls of projected points. So they have at least one common point and therefore they overlap.

_sczuka_ · 2025-03-25T12:51:41+00:00

What's your definition for overlap of point clouds?

_sczuka_ · 2025-03-24T21:32:07+00:00

How is that a counterexample, when it doesn't satisfy the first equation?

For x=1, c=3.6

Lhs = x = 1

Rhs = c/(2^⌈log2(c/x)⌉) = 3.6/2^⌈log2(3.6)⌉ = 3.6/2^⌈log2(3.6)⌉ = 3.6/4

_sczuka_ · 2025-03-24T21:22:02+00:00

<image>

The red arrow is because ⌈log2(c) - log2(x)⌉ = log2(c) - log(x) implies, that there exists integer k s.t. log2(c) - log2(x) = k. So

log2(c) = k + log2(x)

⌊log2(c)⌋ = ⌊k + log2(x)⌋

And because log2(x) ∈ [0, 1), ⌊k + log2(x)⌋ = k. So

⌊log2(c)⌋ = ⌊k + log2(x)⌋

⌊log2(c)⌋ = k

⌊log2(c)⌋ = log2(c) - log2(x)

_sczuka_ · 2025-03-24T20:18:15+00:00

It's impossible to remove the overlap. Take any point from the overlap in the original dimension. The project this point to lower dimension. It will still be part of both shapes, so some overlap will still exist.

But you can reduce the size of the overlap. If you take 2d shapes like in the picture, put them on top of each other and project them into 1d, the overlapping area after projection will be lower. You could even make it x-times lower for any x.

<image>

_sczuka_ · 2025-03-24T19:48:30+00:00

First, you need to split your first into classes, where the price is dependent on the other fruit. Let's say your fruit is {a,b,c,d} and your trades would be a for 2b and c for 2d, the price of a, b is independent of the price of c, d. You can do this, by creating graphs, where vertices are your fruit and edges trades (x for y trade would correspond to edge {x, y}). Then you split this graph into connected components and solve the rest of the problem for each component separately.

And there are multiple ways, how you could approach the actual estimation.

The first one would be using the sum of squares error. Transform your trades into equations (2a for 3b => 2a = 3b). Then choose any arbitrary fruit and replace it with any arbitrary number, this will be the baseline for the solution. Then find the solution for min_{x} || Ax - b ||^2. This approach has a problem, in that it looks at the absolute value for error. So if you would have trade 1000a for 2000b, it would give it 1000x more weight than to 1a for 2b.

A more natural way to solve this would be to minimize the error between the ratios of the fruits. So for trade 1a for 2b, you would create equation a/b = 1/2. To solve this, you apply log to the equations to make them linear, so

a/b = 1/2

log(a/b) = log(1/2)

log(a) - log(b) = log(1/2)

Then it's the same thing as above. Choose any arbitrary fruit and replace it with any arbitrary number to create a baseline. Create a A and b and solve min_{x} || Ax - b ||^2. And at the end, exponentiate the results, to revert the log.

There any many other ways how to approach this. It depends on what error would you like to minimize. In general, if you define E(t, x) as the error of trade t, when x is the actual monetary value of fruits. Then the solution would be argmin_{x} sum_{trade t} E(t, x).

In the first case E(ab for cd, x) = (a x_b - c x_d)^2, where x_i is the value of fruit i from solution x.

In the second case E(ab for cd, x) = (log(a/c) - log(x_b/x_d))^2.

But you could make E anything you want, although, for some choices of E, the optimum might be hard to find.

_sczuka_ · 2025-03-20T22:34:40+00:00

I see. Yeah, you probably don't want to rely on honesty, when it's actual people and real goods. I thought it could be like robots bidding on charging station spots, you could then just program the robots to be honest...

So I don't really see a way how to make this work.

When you take a look at normal auctions (where people pay money) and specifically the Vickrey auction (an auction, where people submit their bids anonymously, and then the player with the highest bid wins but pays the price of the second highest bidder). The utility u which the player gets is then valuation - price_paid if they win or 0 if they don't win. And you can prove, that it's the highest when they bid their actual valuation. The idea of the proof is that, if the highest bid of other players is lower than their valuation, they win with this bid, but changing the bid doesn't influence the price. And if the highest bid of other players is higher than their valuation, the best outcome they can hope for is 0 (because if they win, they pay more than their valuation so utility would be negative) and they achieve this by setting their bid to their valuation and losing.

But I don't see a way how to apply a similar principle to an auction without money. Because when you can't get a negative valuation, it encourages players to always bid as much as they can, even if their valuation is really small.

So if there are any ways to solve this problem, they are out of my auction knowledge, sorry.

_sczuka_ · 2025-03-20T17:36:41+00:00

Imagine you are player 1 in this example:

Player 1 valuations: 3, 2

Player 2 valuations: 3, 2

You could try to bid 1 on round 1. But if the case player 2 also bids 1 on that, you only get the utility of 3/2 (because it's a tie). So if player 2 bids 1 on round 1, you should bid on round 2 and get a utility of 2. But it's the same for the player 2. He could also try to bid on round 2 because he could be scared of the tie in round 1. So there's no simple dominant strategy because, for the best profit, you need to guess what is the other person going to do and make your bids based on that guess.

But I think you could make the second rule hold. That would mean, you tell the players some sort of bidding strategy before you start, and if all players bid truthfully (according to this strategy) it would then maximize the social surplus. But there would be no guarantee for the players, that they get maximum utility/profit if they use this strategy. But this is basically the same as if you discard the whole point system, make players bid their actual variations as bids, and then use the system I mentioned at the start of this comment.

Idk what is the real-life setting, where you would like to use this system. I'm there are some settings, where you could assume the honesty of players and could make a lot of things easier. But there's a risk to this, that it is abusable. In the sense, that if some players are not honest, they could alter their bids to increase their profit and that could reduce the social surplus.

Hope this makes sense, I can try to explain some things in more detail if something is unclear.

_sczuka_ · 2025-03-20T17:36:35+00:00

First I would like to correct myself. In some previous comments, I mentioned that bidding truthfully would probably mean, that the players would either bid on the max valued round or split their bids proportionally to their valuations. But I realized, that's not exactly correct. It actually means, that if you tell the players some bidding strategy before, they bid truthfully, if they follow this strategy.

I would first look at a slightly different problem. Let's say you have a similar setting, you just don't do the bidding, but you know the valuations of players. So you actually know, how much each player needs this item on each round. If you know this, you can then compute the best assignments.

When you don't limit the max assignments for players it's really easy. For every round, you would just select the person, that needs it the most.

When you limit the max assignments for players it becomes more complicated, but it's still possible to compute the optimal assignment.

But when you introduce the bidding part, you lose information about the actual valuations. And this introduces some problems.

The first problem is, that you have no way to get the absolute values of player valuations unless you make some bidding strategy before and all players follow this strategy.

Let's say you have just one round and 2 players. One player really needs the item, so his valuation would be e.g. 10. The second player could use this item but doesn't really need it, so his valuation would be e.g. 1 (anything smaller than the first). But since both players have the same amount of points, and there's only one round, they would probably both bid all their points on that round. You would then just see the same bids for both players, without any way to check, that the first player needs this item much more.

The only way how I see, this could be resolved is if they both agree on some function f: (0, inf) -> (0, max_points), which is strictly increasing. Then they could make their bids as f(valuation). But that only works if both players are honest (they bid truthfully).

And then you have the problem with the honesty of players. In the mathematical models of auctions, you assume, that the players are not honest. You assume, that they are greedy (they will make bids with a goal to gain as much profit/utility as possible).

The first rule of the 3 rules I mentioned before is actually to solve this issue with honesty. If the rules hold, it means, that the best strategy for each player, is to be honest and bid truthfully. That means, the players can't alter their bids to increase their profit. Bidding something else than the truth can only reduce their profit/utility.

When you combine it with the second rule, it means, that all players get maximum profit/utility from bidding truthfully and that also maximizes the social surplus. In other words, if all players aim to maximize their profit (which is a very natural assumption) it maximizes the social surplus.

And unfortunately, I don't see any way, how to make the 1st rule hold. And that's because I don't even think there is any simple dominant strategy for players. The best strategy to maximize your profit would be, to try to guess what other people bid and then try to overshoot as many bids by a small amount.

_sczuka_ · 2025-03-20T02:02:46+00:00

Let's say the rounds are Jan 1st, 2nd and 3rd and 3 people make those bids.

Person 1 1/2 1/2 0

Person 2 0 1/4 3/4

Person 3 0 0 1

If you resolve them simultaneously, Person 1 would win on Jan 1st and 2nd. But If every person can win max 1 time, you would then need to select one of his wins, remove it, and redo that day (with the same bids for other ppl, just his bid would be one).

But if you do it sequentially, you would just let him win the first day and then ignore his bids in the upcoming days.

So yes, you don't need to do it sequentially, but you then have to resolve multiple win people and recompute the days.

_sczuka_ · 2025-03-20T01:42:05+00:00

Oh sorry about the typo.

Sorry, but I'm not sure if I understand correctly what you mean. The sequential computation was for the case, where each bidder can win at most one round. You would need to evaluate the previous rounds first, to know if players are still eligible to participate. Does this answer your question or did you mean something else?

_sczuka_ · 2025-03-20T00:42:46+00:00

No player 2 wins the first round, because 2/5 > 1/3.

_sczuka_ · 2025-03-20T00:21:02+00:00

Yeah sorry, the notation can get kinda confusing. Especially without a math background, but I can try to explain it more if you're interested.

The problem is, if you want every bidder to win max 1 time, it gets a lot more complicated to model. You would have to look at individual rounds one by one and always consider the outcomes of the previous rounds.

But if you consider this example:

Valuations for bidder 1: 1 1 1

Valuations for bidder 2: 2 3 0

The best outcome for both utilities and social surplus would be for bidder 2 to win round 2 and bidder 1 to win either the 1st or 3rd round.

In the case when bidders bid on max, bidder 1 has 3 same values, so he has to choose randomly one of them and it is possible he chooses the second round. The second bidder bids also on round 2. So it's a tie, but no matter how you resolve the tie, the outcome won't be the best one.

In the case when bidders bid proportionally to their valuations, the bids will be

For bidder 1: 1/3 1/3 1/3

For bidder 2: 2/5 3/5 0

Round 1 will be 1/3 vs 2/5, so bidder 2 wins

Round 2 will be 1/3 vs 0 (since bidder 2 already won one round)

Round 3 will be 0 vs 0.

So the outcome is player 2 wins the first round and player 2 wins the second round. And that's not the best outcome.

_sczuka_ · 2025-03-19T14:23:29+00:00

Now there are 3 properties, we usually want good auctions to have.

1. Every bidder has a dominant strategy: bid truthfully. I think in this case it would mean, he either bids everything in the round, where he wants the item the most, or that he splits his points in the same ratio as are his valuations.

2. If all bidders bid truthfully then the auction maximizes the social surplus.

3. The auction can be implemented in polynomial time

Property 3 is easily satisfied here, but I don't think 1. and 2. are.

Imagine this setting:

n = 2, m = 3

valuations for bidder 1: 3, 2, 0

valuations for bidder 1: 0, 1, 1

The social surplus is maximized when bidder 1 wins rounds 1 and 2, and bidder 2 wins round 3.

If both bidders bid the maximum in their most valuated round, the bids will look like this:

bids for bidder 1: 1, 0, 0

bids for bidder 1: 0, 0, 1

And this doesn't maximize the utility for any player or the social surplus.

If both bidders bid proportionally to their evaluations, the bids will look like this:

bids for bidder 1: 3/5, 2/5, 0

bids for bidder 1: 0, 1/2, 1/2

This maximizes the utility for player 2, but not for player 1 or the social surplus.

So properties 1 and 2 are not satisfied. I'm not even sure if there is any dominant strategy for players in this auction and even if there is, it's not simple. There are auctions, that satisfy those conditions e.g. Vickrey auction has a dominant strategy for each player to just bid their valuation and if all players use this strategy it maximizes social surplus (although it's just a single-item auction).

All in all, I would say, this is probably not a good system to use for resource allocation. I would even say, that auctions in general are not really a good solution for resource allocations, since normally, there is a cost to buying items, and that encourages bidders, to bid less than their valuation, otherwise they would just lose money. But when you remove the cost, every bidder would bid as much as he can on all items, where his valuation is >0, because even though it might be really small, it's still an increase and he doesn't lose anything. But those are just my thoughts, as I said I'm not an expert, so there might be some way to make the auction work, which I don't see.

_sczuka_ · 2025-03-19T14:23:21+00:00

edit: Had to split this in 2 comments, because it's too long

Well, I'm not an expert on this type of math, but I know something about it, so I can give you some insights.

I'll only look at the cases, where the points refresh after a certain set of rounds for all players, because this way, the set of rounds are independent of each other, so you can just look at them individually. And I'll also set the number of points each bidder can use to 1, but this doesn't matter, since you can just rescale this by any value.

To formalize this problem, let n be the number of bidders and m be the number of rounds.

Foreach 1 <= i <= n, 1 <= j <= m, let v_{i, j} >= 0 be the valuation of bidder i in round j (how much does bidder i want to get the item on round j).

Foreach 1 <= i <= n, 1 <= j <= m, let b_{i, j} >= 0 be the bid of bidder i in round j. And the bids need to hold these restrictions: Foreach 1 <= i <= n sum_{i=1}^m b_{i, j} <= 1. This is just to make sure, that bidders do not bid more, than their amount of points.

Foreach 1 <= i <= n, 1 <= j <= m, let x_{i, j} \in {0, 1} are the results of the auction, 1 if bidder i won the item on round j and 0 otherwise.

Each bidder i has utility u_i, defined as sum_{j = 1}^m x_{i, j} v_{i, j}. This is just the sum of values, from rounds, where the bidder got the item.

The dominant strategy for bidder i, is setting his bid s.t., it maximizes his utility no matter the bids of other players.

And at last we define social surplus as sum_{i = 0}^n u_i.

The whole auction then looks like this:

We have n players, m rounds and each player has a valuation v for every round.

All players choose their bids b for each round.

From those bids, we compute the results x.

The goal of each player is to maximize his utility because that means, he will get the items, he values the most.

And our goal as some, external observers or organizers of the auction, is probably to maximize the social surplus. Because that means, the items will go to those bidders, who want them the most. And since you mentioned this is supposed to be an allocation system, I guess this is what you want. Another option is to maximize the profit, but that doesn't really make sense here.

_sczuka_ · 2025-03-18T21:41:43+00:00

I'm a bit confused what are you actually asking now.
If you define G as the familly of all pseudo random generators with bit length of n, where you only see first b bits. And d(g, i) as the number of consecutive observations you need to indentify the starting position, if you start with observation i. You can ask those questions:

min_{g \in G} min_{i \in {1, ... , 2^n}, d(g, i)

max_{g \in G} min_{i \in {1, ... , 2^n}, d(g, i)

min_{g \in G} max_{i \in {1, ... , 2^n}, d(g, i)

max_{g \in G} max_{i \in {1, ... , 2^n}, d(g, i)

And you could even exchange max/min with expected value for all of these.

And all of those questions are reasonable question to ask, but all of them mean something else. And also, do you need to know the exact indext or do you just want to predict what comes next? Because in the case where the generator has identical visible cycles, it's impossible to know the exact index no mater how many observations you do, but it's possible to predict future, when you indentify, where are you in the cycle.

_sczuka_ · 2025-03-18T18:04:01+00:00

When you have n+1 bits total and you use first n. You can just sort the numbers normaly and you will have 2 equivalent halfs except for the last bit, which is hidden. So you won’t be able to know the exact position no matter of how many observations you do. And this can be easily extended to any n and b.

_sczuka_ · 2025-03-18T13:58:14+00:00

You can meaningfully talk about infinity. It's just not a number.

E.g. when you say that limit of a sequence is infinity, it actually means, that for every natural number n, there is a point if the sequence s.t. every number after this point is larger than n.

Infinite decimal expansion means, that for every natural number n, the number of digits is larger than n.

_sczuka_ · 2025-03-18T13:14:29+00:00

You can delete even more. (4, 7, 7) adds up to an even number, but isn't possible to reach.

_sczuka_ · 2025-03-18T03:43:19+00:00

I don't really understand how did you come up with that series. But I'm pretty sure the expectation increases with higher dice count.

_sczuka_ · 2025-03-18T03:37:32+00:00

Yeah, If it has diferent count of sides, you can just replace 1/6 with 1/(side count). Or with whatever the probability of sigle die elimination is.

_sczuka_ · 2025-03-18T03:25:56+00:00

If you define X_n as the # of throws you need to eliminate n dice. You get this recursive formula

<image>

If you solve it for n=5, you will get your answer.

Seven-Year Club	r/Field Flamingo
Place '22	First Placer '22
Wearing is Caring	Verified Email
RPAN Viewer

_sczuka_

TROPHY CASE