EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
986. A generalized voting game for categorical network choices
Invited abstract in session TA-28: Fairness and responsible AI, stream Advancements of OR-analytics in statistics, machine learning and data science.
Tuesday, 8:30-10:00Room: 065 (building: 208)
Authors (first author is the speaker)
| 1. | Yueh LIN
|
| quantitative methods, IESEG school of management | |
| 2. | Stefano Nasini
|
| IESEG School of Management | |
| 3. | Martine Labbé
|
| computer Science, Université Libre de Bruxelles |
Abstract
This paper presents a game theoretical framework for data classification, based on the interplay of pairwise influences in multivariate choices. This consists of a voting game wherein individuals, connected through a weighted network, select features from a finite list. A voting rule captures the positive or negative influence of an individual's neighbours, categorized as attractive (friend-like relationships) or repulsive (enemy-like relationships). Payoffs are assigned based on the total number of matching choices from an individual's neighbours. We show that our approach constitutes a natural generalization of the K-nearest neighbours’ method, establishing the proposed game as a theoretical framework for data classification. Computationally, we construct a mixed-integer linear programming formulation to approach the Nash equilibria of the game, facilitating their applicability to real-world data. Our results provide conditions for the existence of Nash equilibria and for the NP-completeness of its characterization. On the empirical side, we use the proposed approach to impute missing data and highlight its competitive advantage over the K-nearest neighbour’s approach.
Keywords
- Machine Learning
- Game Theory
- Combinatorial Optimization
Status: accepted
Back to the list of papers