User:Erel Segal

Fair cake-cutting

• Proportional cake-cutting
• Proportional cake-cutting with different entitlements
• Envy-free cake-cutting
• Fair pie-cutting
• Exact division (also called: consensus division)
• Problem of the Nile
• Equitable cake-cutting
• Egalitarian cake-cutting
• Equitability
• Efficient cake-cutting
• Utilitarian cake-cutting
• Hill–Beck land division problem
• Super-proportional division
• Super envy-freeness
• Radon–Nikodym set
• Individual pieces set
• Divide and choose
• Last diminisher
• Lone divider
• Austin moving-knife procedure
• Brams–Taylor procedure
• Brams–Taylor–Zwicker moving knives procedure
• Dubins–Spanier theorems
• Weller's theorem
• Even–Paz protocol
• Edmonds–Pruhs protocol
• Robertson–Webb envy-free cake-cutting algorithm
• Selfridge–Conway protocol
• Stromquist moving-knives procedure
• Robertson–Webb rotating-knife procedure
• Levmore–Cook moving-knives procedure
• Simmons–Su protocols
• Fink protocol
• Chore division
• Symmetric fair cake-cutting
• Stromquist–Woodall theorem
• Truthful cake-cutting
• Robertson–Webb query model

Graph theory

• Fractional matching
• Matching polytope
• Matching in hypergraphs
• Many-to-many assignment
• Vertex cover in hypergraphs
• Dulmage-Mendelsohn decomposition
• Bipartite hypergraph
• Balanced hypergraph
• Hall-type theorems for hypergraphs
• Width of a hypergraph
• Perfect matching in high-degree hypergraphs
• Normal hypergraph
• Deficiency (graph theory)
• Rainbow matching
• Rainbow independent set
• Rainbow covering
• Ryser's conjecture
• Truncated projective plane
• Meshulam game
• Graph homology
• Independence complex
• Width of a hypergraph
• D-interval hypergraph
• Priority matching
• Fractional spanning tree
• Minor: Dominating set, Conflict-free coloring

Fair division

• List of unsolved problems in fair division
• Some more /Open questions in fair division
• Proportional division
• Envy-freeness
• Egalitarian equivalence
• Resource monotonicity
• Population monotonicity
• Fair division of a single homogeneous resource
• Group envy-freeness
• Price of fairness
• Fair river sharing
• Fair division experiments
• Envy-free matching
• No-justified-envy matching
• Truthful resource allocation
• Strategic fair division
• Partial allocation mechanism
• Efficient envy-free division
• Leximin order
• Online fair division
• Temporal fair division
• Repeated fair division
• Fair division among groups
• Coherence (fair division)
• Surplus sharing
• Entitlement (fair division)
• Ordinal Pareto efficiency
• Dominant resource fairness
• Approximate Competitive Equilibrium from Equal Incomes
• Equal treatment of equals
• Minor: Proportional representation

Bankruptcy problem

• Proportional rule (bankruptcy)
• Adjusted proportional rule
• Constrained equal awards
• Constrained equal losses
• Contested garment rule
• Strategic bankruptcy problem

Fair item allocation

• Envy-free item allocation
• Fair allocation of items and money
• Envy minimization
• Proportional item allocation
• Maximin-share
• Egalitarian item allocation (Max-min item allocation)
• Rental harmony
• Picking sequence
• Top trading cycle
• Undercut procedure
• AL procedure
• envy-graph procedure
• A-CEEI mechanism
• Decreasing Demand procedure

• Gross substitutes (indivisible items)
• Utility functions on indivisible goods
• Responsive set extension
• Single-minded agent

• House allocation problem
• Fair random assignment
• Random priority item allocation
• Simultaneous eating algorithm
• Birkhoff algorithm
• Random two-sided matching

• Rank-maximal allocation
• Adjusted winner
• Envy-free pricing
• Demand oracle

• Efficient approximately-fair item allocation
• Round-robin item allocation

• Course allocation
• School-choice mechanism
• Agreeable set

• Welfare maximization problem (aka utilitarian item allocation)

Social choice

• Utilitarian rule
• Egalitarian rule
• Proportional-fair rule
• Anonymity (social choice)
• Neutrality (social choice)
• Dictatorship mechanism
• Fractional social choice

Voting

• Median voting rule = Median mechanism
• Average voting rule
• Implicit utilitarian voting
• Combinatorial participatory budgeting (also called: participatory budgeting rule)
• Participatory budgeting experiments
• Participatory budgeting ballot types
• Budget-proposal aggregation
• Moving-phantoms mechanism
• Donor coordination
• Jury theorem
• Justified representation
• Fully proportional representation - also Monroe voting rule, Chamberlin-Courant voting rule.
• Multiwinner voting
• Multiwinner approval voting
• Fractional approval voting
• Phragmen's voting rules
• Thiele's voting rules
• Expanding Approvals Rule
• Multi-issue voting (also: perpetual voting, combinatorial voting)
• Compilation complexity
• Minor: Approval ballot

Apportionment

• Mathematics of apportionment
• Optimal apportionment
• Balance (apportionment)
• State-population monotonicity
• House monotonicity
• Vote-ratio monotonicity
• Rank-index apportionment method
• Seat bias
• Minor: Apportionment by country

Preferences

• Ordinal utility
• Multi-attribute utility
• Additive utility
• Random utility model
• Unit demand
• Gross substitutes (indivisible items)
• Utility functions on indivisible goods
• Utility functions on divisible goods
• Single-parameter utility
• Dichotomous preferences
• Fractionally subadditive
• Budget-additive valuation
• Piecewise-constant valuation
• Utility assessment (aka: utility measurement)
• Star-shaped preferences
• Minor: Single peaked preferences

Land

• Land reform in ancient Egypt
• Land reform in Athens
• Land reform in Sparta
• Land reform in the Roman republic
• Land reform in India
• Land reform in Prussia
• Land reform in Savoy
• Land reform in the Habsburg monarchy
• Land reform in the Austrian empire
• Land reform in Scotland
• Land reforms by country
• Pocket contract

Economics

• Competitive equilibrium
• Gross substitutes
• Linear utility
• Leontief utilities
• Marshallian demand function
• Abstract economy
• Utility representation theorem
• Debreu's representation theorems
• Throw away paradox
• Fisher market
• Arrow-Debreu exchange market
• Market equilibrium computation
• Proportional response dynamics
• Pigou–Dalton principle
• Cardinal welfarism
• Free disposal
• Fractional Pareto efficiency
• Nash equilibrium computation
• Minor: Emissions trading, Pareto efficiency, Pareto front, Optimal labor income taxation, Consumer sovereignty, /Equilibrium

Game theory

• Folk theorem (game theory)
• Bimatrix game
• Overtaking criterion
• Facility location (cooperative game)
• Facility location (competitive game)
• Perfect Bayesian equilibrium
• Matching pennies
• Alternating offers protocol
• Sequential bargaining
• Kalai–Smorodinsky bargaining solution
• Congestion games
• Price of anarchy: in congestion games, in auctions.
• Nucleolus (game theory)
• Minimum-cost spanning tree game
• Compositional game theory
• Non-atomic game
• Concave game
• Aggregative game
• Minor: Cooperative bargaining, Signaling game, Backward induction, Shapley value, Potential game

Auction theory

• First-price sealed-bid auction
• Double auction
• Digital goods auction
• Deferred-acceptance auction
• Knapsack auction
• Sequential auction
• Japanese auction
• Jump bidding
• Price of anarchy in auctions
• Supply-chain auction

Mechanism design

• Strategyproofness
• Incentive compatibility
• Regret-free mechanism
• Vickrey–Clarke–Groves mechanism
• Revelation principle
• Gibbard–Satterthwaite theorem‎
• Myerson–Satterthwaite theorem
• Truthful job scheduling
• Monotonicity (mechanism design)
• Maskin monotonicity
• Implementability
• Bayesian-optimal mechanism
• Bayesian-optimal pricing
• Algorithmic pricing
• Prior-independent mechanism
• Prior-free mechanism
• Random-sampling mechanism
• Consensus estimate
• Profit extraction mechanism
• Virtual valuation
• Rural hospitals theorem
• Cost-sharing mechanism
• Budget-balanced mechanism
• Budget-feasible mechanism

Topology and analysis

• Poincaré–Miranda theorem
• Borsuk–Ulam theorem
• L-infinity
• Concavification
• Bauer maximum principle
• Closed graph
• Selection theorem
• Direction-preserving function
• Integrally-convex set
• Power cone
• Discrete fixed-point theorem
• Fixed-point computation
• FIXP (complexity)
• Homotopy method
• Hole (topology)
• Homotopical connectivity
• Homological connectivity
• Nerve complex (minor)
• Simplicial complex recognition problem
• Subdivision (simplicial complex)
• Chessboard complex
• Deleted join
• Metric projection, Chebyshev set
• /Matveev on Algebraic Topology
• Minor: Brouwer fixed-point theorem, Knaster–Tarski theorem, Kakutani fixed point theorem, Stone–Tukey theorem, Connected space, Riemann mapping theorem, Covering number, Colorful Helly theorem, CW complex, Gordan's lemma, Sigma-additive set function, Link (simplicial complex), join (topology), Betweenness

Probability Statistics and Learning

• Lexicographic dominance
• Correlation gap
• Concentration inequalities
• Growth function
• Rademacher complexity
• Belief aggregation
• Belief merging
• Judgement aggregation
• Bayesian persuasion
• Minor: VC dimension, Chernoff bound, Uniform convergence to probability, Covering number, /Probability and Computing 2006

Combinatorics

• Tucker's lemma
• Ky Fan lemma
• Sperner's lemma (minor)
• Steinhaus chessboard theorem
• Knaster–Kuratowski–Mazurkiewicz lemma (KKM lemma)
• Ramsey partitions
• Positional game
• Strong positional game
• Maker-breaker game
• Avoider-Enforcer game
• Discrepancy game
• Biased positional game
• Clique game
• Box-making game
• Pairing strategy
• Discrete fixed-point theorem
• Base-orderable matroid
• Basis of a matroid
• Laminar set family
• Geometric discrepancy theory
• Discrepancy of permutations
• Minor: Law of Excluded Middle, Matroid rank, Matroid intersection
• Template:Analogous fixed-point theorems

Computational Geometry

• Fat object
• Geometric separator
• Maximum disjoint set
• Polygon covering
• Polygon partition
• Rectilinear polygon
• Map segmentation
• Rectangle packing
• Guillotine cutting
• Guillotine partition
• Guillotine separation
• Minor: Aspect ratio, Space partitioning, Treemapping

Algorithms

• 3SUM
• Balls into bins
• Maximal independent set#Algorithms
• Non-constructive algorithm existence proofs
• Set balancing
• Zero-weight cycle problem
• Hall's marriage theorem#Constructive proof of the hard direction
• Hall violator
• Assignment problem
• Rank-maximal matching
• Maximally-matchable edge
• Partition problem
• Multiway number partitioning
• 3-partition
• Balanced number partitioning
• Matroid-constrained number partitioning
• Greedy number partitioning
• Pseudopolynomial time number partitioning
• Largest differencing method
• Multifit algorithm
• Bin covering problem
• High-multiplicity bin packing
• Karmarkar-Karp bin packing algorithms
• Multiple subset sum
• ADCOP
• Configuration linear program
• Strongly-polynomial time
• Optimal job scheduling: Interval, single machine, Identical machines, Uniform machines, Unrelated machines, Template.
• Online job scheduling
• [Minor] Bin packing problem: Next-fit, First-fit, Best-fit, Harmonic, FFD, NFD.
• List scheduling
• Longest-processing-time-first scheduling
• Lexicographic optimization
• Lexicographic max-min optimization
• Fully polynomial-time approximation scheme (FPTAS)
• Optimal kidney exchange
• Algorithmic problems on convex sets
• Minimum mean weight cycle
• /Optimal algorithms with unknown runtime complexity
• Minor: Set packing, Subset sum, Sample complexity, Makespan, Multiprocessor scheduling, Gallai–Edmonds decomposition, Hungarian algorithm, Maximum weight matching, Distributed constraint optimization, Quadratic programming, Minimum cut

Convex optimization

• Center-of-gravity method
• Square-root sum problem
• Minor: Self-concordant barrier, Interior-point method, Semidefinite programming

Linear programming

• Basic feasible solution
• Dual linear program
• Minimum relevant variables in linear system
• Minimum weight solution to linear equations
• Separation oracle
• Assignment problem#Solution by linear programming
• n-dimensional polyhedron
• Minor: Farkas' lemma

Data structures

• Dialog manager
• Distance oracle
• Set intersection oracle
• Interleave lower bound
• Dynamic connectivity
• Minor: Tango tree, Splay tree