In Hotelling's model of spatial competition, a unit mass of voters is distributed in the interval [0,1] (with their location corresponding to their political persuasion), and each of m candidates selects as a strategy their distinct position in this interval. Each voter votes for the nearest candidate, and candidates choose their strategy to maximize their votes. It is known that if there are more than two candidates, equilibria may not exist in this model. It was unknown, however, how close to an equilibrium one could get. Our work studies approximate equilibria in this model, where a strategy profile is an (additive) ϵ-equilibria if no candidate can increase their votes by ϵ, and provides tight or nearly-tight bounds on the approximation ϵ achievable. We show that for 3 candidates, for any distribution of the voters, ϵ ≥ 1/12. Thus, somewhat surprisingly, for any distribution of the voters and any strategy profile of the candidates, at least 1/12th of the total votes is always left ``on the table.'' Extending this, we show that in the worst case, there exist voter distributions for which ϵ ≥ 1/6, and this is tight: one can always compute a 1/6-approximate equilibria in polynomial time. We then study the general case of m candidates, and show that as m grows large, we get closer to an exact equilibrium: one can always obtain a 1/(m+1)-approximate equilibria in polynomial time. We show this bound is asymptotically tight, by giving voter distributions for which ϵ ≥ 1/(m+3).

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and hence we instead consider a meaningful analog, EQx, that requires equitability up to any item. EQx allocations exist for monotone, additive valuations. However, if (1) the agents' valuations are not additive or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to the current work it was not known whether EQx allocations exist or not. We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we show existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items.