Assume |S|= m, for some m>0. Then, corresponding set of incorrectly-labelled examples is of size | S|= m(k 1). Let D S, be any distribution over m (k 1). We show that we can construct a distribution D S S over m k, for which the guarantee in the Lemma holds. First, observe that there must exist a m and b1,...,bm (k 1), such that for all i,j, we have D(i,j) = a(i)bi(j).

The central question in the game theory of cake-cutting is how to fairly distribute a finite resource among multiple players. Most research has focused on how to do this for a heterogeneous cake in a situation where the players do not have access to each other's valuation function, but I argue that even sharing homogeneous cake can have interesting mechanism design. Here, I introduce a new game, based on the compositional structure of iterated cake-cutting, that in the case of a homogeneous cake has a Nash equilibrium where each of $n$ players gets $1/n$ of the cake. Furthermore, the equilibrium distribution is the result of just $n-1$ cuts, so each player gets a contiguous piece of cake. Naive composition of the `I cut you choose' rule leads to an exponentially unfair cake distribution with a Gini-coefficient that approaches 1, and suffers from a high Price of Anarchy. This cost is completely eliminated by the proposed \textit{Biggest Player} rule for composition which achieves decentralised and asynchronous fairness at linear Robertson-Webb complexity. After introducing the game, proving the fairness of the equilibrium, and analysing the incentive structure, the game is implemented in Haskell and the Open Game engine to make the compositional structure explicit.

Choices made by individuals have widespread impacts--for instance, people choose between political candidates to vote for, between social media posts to share, and between brands to purchase--moreover, data on these choices are increasingly abundant. Discrete choice models are a key tool for learning individual preferences from such data. Additionally, social factors like conformity and contagion influence individual choice. Traditional methods for incorporating these factors into choice models do not account for the entire social network and require hand-crafted features. To overcome these limitations, we use graph learning to study choice in networked contexts. We identify three ways in which graph learning techniques can be used for discrete choice: learning chooser representations, regularizing choice model parameters, and directly constructing predictions from a network. We design methods in each category and test them on real-world choice datasets, including county-level 2016 US election results and Android app installation and usage data. We show that incorporating social network structure can improve the predictions of the standard econometric choice model, the multinomial logit. We provide evidence that app installations are influenced by social context, but we find no such effect on app usage among the same participants, which instead is habit-driven. In the election data, we highlight the additional insights a discrete choice framework provides over classification or regression, the typical approaches. On synthetic data, we demonstrate the sample complexity benefit of using social information in choice models.

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We define a generalization of cut-and-choose protocols - forced-cut protocols - in which some cuts are made exogenously while others are made by the cutter, and show that there exist non-exploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a non-adaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.